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.

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

$(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_{\ell -1}+1)}\otimes \cdots \otimes V_{\pi (r_{\ell })}),$

there are $\ell$ groups with $r_{j}-r_{j-1}$ factors in the $j^{\text{th}}$ group (where $r_{0}=0$ and $r_{\ell }=d$).

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

The vectorization of ${\mathcal {A}}$ is an $(S_{1})$-reshaping, ${\mathcal {A}}_{(S_{1})}$ wherein $S_{1}=(1,2,\ldots ,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}=(1,2,\ldots ,k-1,k+1,\ldots ,d)$. 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 bijections $\mu _{1},\ \mu _{2}$ 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}}$