Tensor reshaping

In multilinear algebra, a reshaping of tensors is any bijection between the set of indices of an order-$d$ tensor and the set of indices of an order-$\ell$ tensor, where $\ell <d$. The use of indices presupposes tensors in coordinate representation with respect to a basis. The coordinate representation of a tensor can be regarded as a multi-dimensional array, and a bijection from one set of indices to another therefore amounts to a rearrangement of the array elements into an array of a different shape. Such a rearrangement constitutes a particular kind of linear map between the vector space of order-$d$ tensors and the vector space of order-$\ell$ tensors.

Definition

Given a positive integer $d$, the notation $[d]$ refers to the set $\{1,\dots ,d\}$ of the first d positive integers. Given a set $S$, the notation $|S|$ refers to the cardinality of $S$, i.e. the number of its elements.

For each integer $k$ where $1\leq k\leq d$ for a positive integer $d$, let V_k denote an n_k-dimensional vector space over a field $F$. Then there are vector space isomorphisms (linear maps)

$${\begin{aligned}V_{1}\otimes \cdots \otimes V_{d}&\simeq F^{n_{1}}\otimes \cdots \otimes F^{n_{d}}\\&\simeq F^{n_{\pi _{1}}}\otimes \cdots \otimes F^{n_{\pi _{d}}}\\&\simeq F^{n_{\pi _{1}}n_{\pi _{2}}}\otimes F^{n_{\pi _{3}}}\otimes \cdots \otimes F^{n_{\pi _{d}}}\\&\simeq F^{n_{\pi _{1}}n_{\pi _{3}}}\otimes F^{n_{\pi _{2}}}\otimes F^{n_{\pi _{4}}}\otimes \cdots \otimes F^{n_{\pi _{d}}}\\&\,\,\,\vdots \\&\simeq F^{n_{1}n_{2}\ldots n_{d}},\end{aligned}}$$

where $\pi \in {\mathfrak {S}}_{d}$ is any permutation and ${\mathfrak {S}}_{d}$ is the symmetric group on $d$ elements. Via these (and other) vector space isomorphisms, a tensor can be interpreted in several ways as an order-$\ell$ tensor where $\ell \leq d$.

Coordinate representation

The first vector space isomorphism on the list above, $V_{1}\otimes \cdots \otimes V_{d}\simeq F^{n_{1}}\otimes \cdots \otimes F^{n_{d}}$, gives the coordinate representation of an abstract tensor. Assume that each of the $d$ vector spaces $V_{k}$ has a basis $\{v_{1}^{k},v_{2}^{k},\ldots ,v_{n_{k}}^{k}\}$. The expression of a tensor with respect to this basis has the form $${\mathcal {A}}=\sum _{j_{1}=1}^{n_{1}}\ldots \sum _{j_{d}=1}^{n_{d}}a_{j_{1},j_{2},\ldots ,j_{d}}v_{j_{1}}^{1}\otimes v_{j_{2}}^{2}\otimes \cdots \otimes v_{j_{d}}^{d},$$ where the coefficients $a_{j_{1},j_{2},\ldots ,j_{d}}$ are elements of $F$. The coordinate representation of ${\mathcal {A}}$ is $$\sum _{j_{1}=1}^{n_{1}}\ldots \sum _{j_{d}=1}^{n_{d}}a_{j_{1},j_{2},\ldots ,j_{d}}\mathbf {e} _{j_{1}}^{1}\otimes \mathbf {e} _{j_{2}}^{2}\otimes \cdots \otimes \mathbf {e} _{j_{d}}^{d},$$where $\mathbf {e} _{j}^{k}$ is the $j^{\text{th}}$ standard basis vector of $F^{n_{k}}$. This can be regarded as a d-dimensional array whose elements are the coefficients $a_{j_{1},j_{2},\ldots ,j_{d}}$.

Vectorization

By means of a bijective map $\mu :[n_{1}]\times \cdots \times [n_{d}]\to [n_{1}\cdots n_{d}]$, a vector space isomorphism between $F^{n_{1}}\otimes \cdots \otimes F^{n_{d}}$ and $F^{n_{1}\cdots n_{d}}$ is constructed via the mapping $\mathbf {e} _{j_{1}}^{1}\otimes \cdots \otimes \mathbf {e} _{j_{d}}^{d}\mapsto \mathbf {e} _{\mu (j_{1},j_{2},\ldots ,j_{d})},$ where for every natural number $j$ such that $1\leq j\leq n_{1}\cdots n_{d}$, the vector $\mathbf {e} _{j}$ denotes the jth standard basis vector of $F^{n_{1}\cdots n_{d}}$. In such a reshaping, the tensor is simply interpreted as a vector in $F^{n_{1}\cdots n_{d}}$. This is known as vectorization, and is analogous to vectorization of matrices. A standard choice of bijection $\mu$ is such that

$\operatorname {vec} ({\mathcal {A}}):={\begin{bmatrix}a_{1,1,\ldots ,1}&a_{2,1,\ldots ,1}&\cdots &a_{n_{1},1,\ldots ,1}&a_{1,2,1,\ldots ,1}&\cdots &a_{n_{1},n_{2},\ldots ,n_{d}}\end{bmatrix}}^{T},$

which is consistent with the way in which the colon operator in Matlab and GNU Octave reshapes a higher-order tensor into a vector. In general, the vectorization of ${\mathcal {A}}$ is the vector $[a_{\mu ^{-1}(j)}]_{j=1}^{n_{1}\cdots n_{d}}$.

General flattenings

For each subset $S$ of $[d]:=\{1,\dots ,d\}$, let

$${\begin{aligned}\Pi _{S}:V_{1}\otimes V_{2}\otimes \cdots \otimes \cdots \otimes V_{d}&\to V_{s_{1}}\otimes V_{s_{2}}\otimes \cdots \otimes V_{s_{|S|}}\\v_{1}\otimes v_{2}\otimes \cdots \otimes v_{d}&\mapsto v_{s_{1}}\otimes v_{s_{2}}\otimes \cdots \otimes v_{s_{|S|}}\end{aligned}}$$

denote the projection with $S=\{s_{1},s_{2},\ldots ,s_{|S|}\}\subset [d]$, i.e. $s_{1},s_{2},\ldots ,s_{|S|}$ denote the elements of the subset $S$.

Let $S_{1}\sqcup S_{2}\sqcup \cdots \sqcup S_{\ell }=[d]$ be a partition. Then, the $(S_{1},S_{2},\ldots ,S_{\ell })$-flattening of a simple tensor ${\mathcal {A}}=v_{1}\otimes v_{2}\otimes \cdots \otimes v_{d}$ is defined as

$${\begin{aligned}{\mathcal {A}}_{(S_{1},S_{2},\ldots ,S_{\ell })}:={}&(\Pi _{S_{1}}{\mathcal {A}})\otimes (\Pi _{S_{2}}{\mathcal {A}})\otimes \cdots \otimes (\Pi _{S_{\ell }}{\mathcal {A}})\\[4pt]&\in \left(\bigotimes _{s\in S_{1}}V_{s}\right)\otimes \cdots \otimes \left(\bigotimes _{s\in S_{\ell }}V_{s}\right),\end{aligned}}$$

which may be interpreted as a tensor of order $\ell <d$ by ignoring for each positive integer $k$ with $1\leq k\leq \ell$ the tensor product structure on $\otimes _{s\in S_{k}}V_{s}$.

The standard way to ignore the tensor product structure consists of looking at ${\mathcal {A}}_{(S_{1},\ldots ,S_{\ell })}$ through vector space isomorphisms, which for each positive integer $1\leq k\leq \ell$ allow identifying$\otimes _{s\in S_{k}}V_{s}$ and $\simeq F^{\prod _{s\in S_{k}}n_{s}}$. Using these identifications, ${\mathcal {A}}_{(S_{1},\ldots ,S_{\ell })}$ is viewed as an element of $F^{N_{S_{1}}}\otimes \cdots \otimes F^{N_{S_{\ell }}}$, where for each positive integer $1\leq k\leq \ell$ we define $N_{S_{k}}:=\prod _{s\in S_{k}}n_{s}$, the product of the integers $n_{1},\dots ,n_{s},\dots ,n_{|S_{k}|}$.

For general tensors ${\mathcal {A}}\in V_{1}\otimes V_{2}\otimes \cdots \otimes V_{d}$ the above definition is extended linearly as follows. Since every tensor admits a tensor rank decomposition, we can define the $(S_{1},S_{2},\ldots ,S_{\ell })$-flattening of an arbitrary tensor ${\textstyle {\mathcal {A}}=\sum _{i=1}^{r}\mathbf {a} _{i}^{1}\otimes \mathbf {a} _{i}^{2}\otimes \cdots \otimes \mathbf {a} _{i}^{d}}$ as follows:

$${\mathcal {A}}_{(S_{1},S_{2},\ldots ,S_{\ell })}:=\sum _{i=1}^{r}\left(\mathbf {a} _{i}^{1}\otimes \mathbf {a} _{i}^{2}\otimes \cdots \otimes \mathbf {a} _{i}^{d}\right)_{(S_{1},S_{2},\ldots ,S_{\ell })}.$$

The vectorization of ${\mathcal {A}}$ is an $(S_{1})$-reshaping wherein $S_{1}=[d]$.

Matricization

Let ${\mathcal {A}}\in F^{n_{1}}\otimes F^{n_{2}}\otimes \cdots \otimes F^{n_{d}}$ be the coordinate representation of an abstract tensor with respect to a basis. A standard factor-k flattening of ${\mathcal {A}}$ is an $(S_{1},S_{2})$-reshaping in which $S_{1}=\{k\}$ and $S_{2}=[d]\smallsetminus S_{1}$. Usually, a standard flattening is denoted by

${\mathcal {A}}_{(k)}:={\mathcal {A}}_{(S_{1},S_{2})}$

These reshapings are sometimes called matricizations or unfoldings in the literature. A standard choice for the bijection $\mu$ is the one that is consistent with the reshape function in Matlab and GNU Octave, namely

${\mathcal {A}}_{(k)}:={\begin{bmatrix}a_{1,1,\ldots ,1,1,1,\ldots ,1}&a_{2,1,\ldots ,1,1,1,\ldots ,1}&\cdots &a_{n_{1},n_{2},\ldots ,n_{k-1},1,n_{k+1},\ldots ,n_{d}}\\a_{1,1,\ldots ,1,2,1,\ldots ,1}&a_{2,1,\ldots ,1,2,1,\ldots ,1}&\cdots &a_{n_{1},n_{2},\ldots ,n_{k-1},2,n_{k+1},\ldots ,n_{d}}\\\vdots &\vdots &&\vdots \\a_{1,1,\ldots ,1,n_{k},1,\ldots ,1}&a_{2,1,\ldots ,1,n_{k},1,\ldots ,1}&\cdots &a_{n_{1},n_{2},\ldots ,n_{k-1},n_{k},n_{k+1},\ldots ,n_{d}}\end{bmatrix}}$