Tensor reshaping

In multilinear algebra, a reshaping of tensors is any bijection between the set of indices of an order-${\displaystyle M}$ tensor and the set of indices of an order-${\displaystyle L}$ tensor, where ${\displaystyle L<M}$. 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-${\displaystyle M}$ tensors and the vector space of order-${\displaystyle L}$ tensors.

Definition

Given a positive integer ${\displaystyle M}$, the notation ${\displaystyle [M]}$ refers to the set ${\displaystyle \{1,\dots ,M\}}$ of the first M positive integers.

For each integer ${\displaystyle m}$ where ${\displaystyle 1\leq m\leq M}$ for a positive integer ${\displaystyle M}$, let ${\displaystyle V_{m}}$ denote an ${\displaystyle I_{m}}$-dimensional vector space over a field ${\displaystyle F}$. Then there are vector space isomorphisms (linear maps)

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

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

Coordinate representation

The first vector space isomorphism on the list above, ${\displaystyle V_{1}\otimes \cdots \otimes V_{M}\simeq F^{I_{1}}\otimes \cdots \otimes F^{I_{M}}}$, gives the coordinate representation of an abstract tensor. Assume that each of the ${\displaystyle M}$ vector spaces ${\displaystyle V_{m}}$ has a basis ${\displaystyle \{v_{1}^{m},v_{2}^{m},\ldots ,v_{I_{m}}^{m}\}}$. The expression of a tensor with respect to this basis has the form

$${\displaystyle {\mathcal {A}}=\sum _{i_{1}=1}^{I_{1}}\ldots \sum _{i_{M}=1}^{I_{M}}a_{i_{1},i_{2},\ldots ,i_{M}}v_{i_{1}}^{1}\otimes v_{i_{2}}^{2}\otimes \cdots \otimes v_{i_{M}}^{M},}$$

where the coefficients ${\displaystyle a_{i_{1},i_{2},\ldots ,i_{M}}}$ are elements of ${\displaystyle F}$. The coordinate representation of ${\displaystyle {\mathcal {A}}}$ is

$${\displaystyle \sum _{i_{1}=1}^{I_{1}}\ldots \sum _{i_{M}=1}^{I_{M}}a_{i_{1},i_{2},\ldots ,i_{M}}\mathbf {e} _{i_{1}}^{1}\otimes \mathbf {e} _{i_{2}}^{2}\otimes \cdots \otimes \mathbf {e} _{i_{M}}^{M},}$$

where ${\displaystyle \mathbf {e} _{i}^{m}}$ is the ${\displaystyle i^{\text{th}}}$ standard basis vector of ${\displaystyle F^{I_{m}}}$. This can be regarded as a M-way array whose elements are the coefficients ${\displaystyle a_{i_{1},i_{2},\ldots ,i_{M}}}$.

General flattenings

For any permutation ${\displaystyle \pi \in {\mathfrak {S}}_{M}}$ there is a canonical isomorphism between the two tensor products of vector spaces ${\displaystyle V_{1}\otimes V_{2}\otimes \cdots \otimes V_{M}}$ and ${\displaystyle V_{\pi (1)}\otimes V_{\pi (2)}\otimes \cdots \otimes V_{\pi (M)}}$. Parentheses are usually omitted from such products due to the natural isomorphism between ${\displaystyle V_{i}\otimes (V_{j}\otimes V_{k})}$ and ${\displaystyle (V_{i}\otimes V_{j})\otimes V_{k}}$, but may, of course, be reintroduced to emphasize a particular grouping of factors. In the grouping,

$${\displaystyle (V_{\pi (1)}\otimes \cdots \otimes V_{\pi (r_{1})})\otimes (V_{\pi (r_{1}+1)}\otimes \cdots \otimes V_{\pi (r_{2})})\otimes \cdots \otimes (V_{\pi (r_{L-1}+1)}\otimes \cdots \otimes V_{\pi (r_{L})}),}$$

there are ${\displaystyle L}$ groups with ${\displaystyle r_{l}-r_{l-1}}$ factors in the ${\displaystyle l^{\text{th}}}$ group (where ${\displaystyle r_{0}=0}$ and ${\displaystyle r_{L}=M}$).

Letting ${\displaystyle S_{l}=(\pi (r_{l-1}+1),\pi (r_{l-1}+2),\ldots ,\pi (r_{l}))}$ for each ${\displaystyle l}$ satisfying ${\displaystyle 1\leq l\leq L}$, an ${\displaystyle (S_{1},S_{2},\ldots ,S_{L})}$-flattening of a tensor ${\displaystyle {\mathcal {A}}}$, denoted ${\displaystyle {\mathcal {A}}_{(S_{1},S_{2},\ldots ,S_{L})}}$, is obtained by applying the two processes above within each of the ${\displaystyle L}$ groups of factors. That is, the coordinate representation of the ${\displaystyle l^{\text{th}}}$ group of factors is obtained using the isomorphism ${\displaystyle (V_{\pi (r_{l-1}+1)}\otimes V_{\pi (r_{l-1}+2)}\otimes \cdots \otimes V_{\pi (r_{l})})\simeq (F^{I_{\pi (r_{l-1}+1)}}\otimes F^{I_{\pi (r_{l-1}+2)}}\otimes \cdots \otimes F^{I_{\pi (r_{l})}})}$, which requires specifying bases for all of the vector spaces ${\displaystyle V_{k}}$. The result is then vectorized using a bijection ${\displaystyle \mu _{l}:[I_{\pi (r_{l-1}+1)}]\times [I_{\pi (r_{l-1}+2)}]\times \cdots \times [I_{\pi (r_{l})}]\to [I_{S_{l}}]}$ to obtain an element of ${\displaystyle F^{I_{S_{l}}}}$, where ${\textstyle I_{S_{l}}:=\prod _{i=r_{l-1}+1}^{r_{l}}I_{\pi (i)}}$, the product of the dimensions of the vector spaces in the ${\displaystyle l^{\text{th}}}$ group of factors. The result of applying these isomorphisms within each group of factors is an element of ${\displaystyle F^{I_{S_{1}}}\otimes \cdots \otimes F^{I_{S_{L}}}}$, which is a tensor of order ${\displaystyle L}$.

Vectorization

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

$${\displaystyle \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_{I_{1},I_{2},\ldots ,I_{M}}\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 ${\displaystyle {\mathcal {A}}}$ is the vector ${\displaystyle [a_{\mu ^{-1}(i)}]_{i=1}^{I_{1}\cdots I_{M}}}$.

The vectorization of ${\displaystyle {\mathcal {A}}}$ denoted with ${\displaystyle vec({\mathcal {A}})}$ or ${\displaystyle {\mathcal {A}}_{[:]}}$ is an ${\displaystyle [S_{1},S_{2}]}$-reshaping where ${\displaystyle S_{1}=(1,2,\ldots ,M)}$ and ${\displaystyle S_{2}=\emptyset }$.

Mode-m Flattening / Mode-m Matrixization

Let ${\displaystyle {\mathcal {A}}\in F^{I_{1}}\otimes F^{I_{2}}\otimes \cdots \otimes F^{I_{M}}}$ be the coordinate representation of an abstract tensor with respect to a basis. Mode-m matrixizing (a.k.a. flattening) of ${\displaystyle {\mathcal {A}}}$ is an ${\displaystyle [S_{1},S_{2}]}$-reshaping in which ${\displaystyle S_{1}=(m)}$ and ${\displaystyle S_{2}=(1,2,\ldots ,m-1,m+1,\ldots ,M)}$. Usually, a standard matrixizing is denoted by

$${\displaystyle {\mathbf {A} }_{[m]}={\mathcal {A}}_{[S_{1},S_{2}]}}$$

This reshaping is sometimes called matrixizing, matricizing, flattening or unfolding in the literature. A standard choice for the bijections ${\displaystyle \mu _{1},\ \mu _{2}}$ is the one that is consistent with the reshape function in Matlab and GNU Octave, namely

$${\displaystyle {\mathbf {A} }_{[m]}:={\begin{bmatrix}a_{1,1,\ldots ,1,1,1,\ldots ,1}&a_{2,1,\ldots ,1,1,1,\ldots ,1}&\cdots &a_{I_{1},I_{2},\ldots ,I_{m-1},1,I_{m+1},\ldots ,I_{M}}\\a_{1,1,\ldots ,1,2,1,\ldots ,1}&a_{2,1,\ldots ,1,2,1,\ldots ,1}&\cdots &a_{I_{1},I_{2},\ldots ,I_{m-1},2,I_{m+1},\ldots ,I_{M}}\\\vdots &\vdots &&\vdots \\a_{1,1,\ldots ,1,I_{m},1,\ldots ,1}&a_{2,1,\ldots ,1,I_{m},1,\ldots ,1}&\cdots &a_{I_{1},I_{2},\ldots ,I_{m-1},I_{m},I_{m+1},\ldots ,I_{M}}\end{bmatrix}}}$$

Definition Mode-m Matrixizing: ^[1]

$${\displaystyle [{\mathbf {A} }_{[m]}]_{jk}=a_{i_{1}\dots i_{m}\dots i_{M}},\;\;{\text{ where }}j=i_{m}{\text{ and }}k=1+\sum _{n=0 \atop n\neq m}^{M}(i_{n}-1)\prod _{l=0 \atop l\neq m}^{n-1}I_{l}.}$$

The mode-m matrixizing of a tensor ${\displaystyle {\mathcal {A}}\in F^{I_{1}\times ...I_{M}},}$ is defined as the matrix ${\displaystyle {\mathbf {A} }_{[m]}\in F^{I_{m}\times (I_{1}\dots I_{m-1}I_{m+1}\dots I_{M})}}$. As the parenthetical ordering indicates, the mode-m column vectors are arranged by sweeping all the other mode indices through their ranges, with smaller mode indexes varying more rapidly than larger ones; thus

References

1. Vasilescu, M. Alex O. (2009), "Multilinear (Tensor) Algebraic Framework for Computer Graphics, Computer Vision and Machine Learning" (PDF), University of Toronto, p. 21