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 isomorphisms of vector spaces

$${\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 <d$.

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 })}.$$

Example

For example, assume that, for each natural number $k$ such that $1\leq k\leq d$, a basis of $V_{k}$ is $\{v_{1}^{k},v_{2}^{k},\ldots ,v_{n_{k}}^{k}\}$, and assume that the tensor is expressed with respect to this basis as $${\mathcal {A}}=\sum _{j_{1},j_{2},\ldots ,j_{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 for each positive integer $k$ such that $1\leq k\leq d$, the notation $j_{k}$ is meant to denote another positive integer $1\leq j_{k}\leq n_{k}$, where $n_{k}$ denotes the dimension of the vector space $V_{k}$, or equivalently the number of elements in the basis $\{v_{1}^{k},v_{2}^{k},\ldots ,v_{n_{k}}^{k}\}$ for $V_{k}$.

Via the first vector space isomorphism, namely $V_{1}\otimes \cdots \otimes V_{d}\simeq F^{n_{1}}\otimes \cdots \otimes F^{n_{d}}$, we can represent ${\mathcal {A}}$ as $${\mathcal {A}}=\sum _{j_{1},j_{2},\ldots ,j_{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, for each positive integer $k$ such that $1\leq k\leq d$, $\mathbf {e} _{j}^{k}$ is the jth standard basis vector of $F^{n_{k}}$.

Taking $S_{1}=[d]$ and a bijective map $\mu :[n_{1}]\times \cdots \times [n_{d}]\to [n_{1}\cdots n_{d}]$, we can construct a vector space isomorphism between $F^{n_{1}}\otimes \cdots \otimes F^{n_{d}}$ and $F^{n_{1}\cdots n_{d}}$ by 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}}$. Via this identification, we have ${\mathcal {A}}_{(S_{1})}=[a_{\mu ^{-1}(j)}]_{j=1}^{n_{1}\cdots n_{d}}$.

Vectorization

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 vectorization of ${\mathcal {A}}$ is an $(S_{1})$-reshaping wherein $S_{1}=[d]$, so that the tensor is simply interpreted as a vector in $F^{n_{1}\cdots n_{d}}$. A standard choice of bijection $\mu$ is such that

$\operatorname {vec} ({\mathcal {A}}):={\mathcal {A}}_{(S_{1})}={\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.

Flattenings

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}}$