Multilinear multiplication

In multilinear algebra, applying a map that is the tensor product of linear maps to a tensor is called a multilinear multiplication.

Abstract definition

Let $F$ be a field of characteristic zero, such as $ℝ$ or $ℂ$. Let $V_k$ be a finite-dimensional vector space over $F$, and let $𝒜\in V_1\otimes V_2\otimes \cdots \otimes V_d$ be an order-d simple tensor, i.e., there exist some vectors ${𝐯}_k\in V_k$ such that $𝒜={𝐯}_1\otimes {𝐯}_2\otimes \cdots \otimes {𝐯}_d$. If we are given a collection of linear maps $A_k:V_k\to W_k$, then the multilinear multiplication of $𝒜$ with $(A_1,A_2,\dots ,A_d)$ is defined as the action on $𝒜$ of the tensor product of these linear maps, namely

$$\begin{array}{cc}{A}_1\otimes A_2\otimes \cdots \otimes A_d:V_1\otimes V_2\otimes \cdots \otimes V_d& \to W_1\otimes W_2\otimes \cdots \otimes W_d,\\ {𝐯}_1\otimes {𝐯}_2\otimes \cdots \otimes {𝐯}_d& \mapsto A_1({𝐯}_1)\otimes A_2({𝐯}_2)\otimes \cdots \otimes A_d({𝐯}_d)\end{array}$$

Since the tensor product of linear maps is itself a linear map, and because every tensor admits a tensor rank decomposition, the above expression extends linearly to all tensors. That is, for a general tensor $𝒜\in V_1\otimes V_2\otimes \cdots \otimes V_d$, the multilinear multiplication is

$$\begin{array}{cc}& ℬ:=(A_1\otimes A_2\otimes \cdots \otimes A_d)(𝒜)\\ =& (A_1\otimes A_2\otimes \cdots \otimes A_d)(\sum _{i=1}^r{𝐚}_i^1\otimes {𝐚}_i^2\otimes \cdots \otimes {𝐚}_i^d)\\ =& \sum _{i=1}^r{A}_1({𝐚}_i^1)\otimes A_2({𝐚}_i^2)\otimes \cdots \otimes A_d({𝐚}_i^d)\end{array}$$

where $𝒜={\sum }_{i=1}^r{𝐚}_i^1\otimes {𝐚}_i^2\otimes \cdots \otimes {𝐚}_i^d$ with ${𝐚}_i^k\in V_k$ is one of $𝒜$'s tensor rank decompositions. The validity of the above expression is not limited to a tensor rank decomposition; in fact, it is valid for any expression of $𝒜$ as a linear combination of pure tensors, which follows from the universal property of the tensor product.

It is standard to use the following shorthand notations in the literature for multilinear multiplications:$$(A_1,A_2,\dots ,A_d)\cdot 𝒜:=(A_1\otimes A_2\otimes \cdots \otimes A_d)(𝒜)$$and$$A_k{\cdot }_k𝒜:=({\mathrm{Id}}_{V_1},\dots ,{\mathrm{Id}}_{V_{k-1}},A_k,{\mathrm{Id}}_{V_{k+1}},\dots ,{\mathrm{Id}}_{V_d})\cdot 𝒜,$$where ${\mathrm{Id}}_{V_k}:V_k\to V_k$ is the identity operator.

Definition in coordinates

In computational multilinear algebra it is conventional to work in coordinates. Assume that an inner product is fixed on $V_k$ and let $V_k^{\ast }$ denote the dual vector space of $V_k$. Let $\{e_1^k,\dots ,e_{n_k}^k\}$ be a basis for $V_k$, let $\{(e_1^k{)}^{\ast },\dots ,(e_{n_k}^k{)}^{\ast }\}$ be the dual basis, and let $\{f_1^k,\dots ,f_{m_k}^k\}$ be a basis for $W_k$. The linear map $M_k={\sum }_{i=1}^{m_k}{\sum }_{j=1}^{n_k}{m}_{i,j}^{(k)}{f}_i^k\otimes (e_j^k{)}^{\ast }$ is then represented by the matrix ${\hat{M}}_k=[m_{i,j}^{(k)}]\in F^{m_k\times n_k}$. Likewise, with respect to the standard tensor product basis $\{e_{j_1}^1\otimes e_{j_2}^2\otimes \cdots \otimes e_{j_d}^d{\}}_{j_1,j_2,\dots ,j_d}$, the abstract tensor$$𝒜=\sum _{j_1=1}^{n_1}\sum _{j_2=1}^{n_2}\cdots \sum _{j_d=1}^{n_d}{a}_{j_1,j_2,\dots ,j_d}{e}_{j_1}^1\otimes e_{j_2}^2\otimes \cdots \otimes e_{j_d}^d$$is represented by the multidimensional array $\widehat{𝒜}=[a_{j_1,j_2,\dots ,j_d}]\in F^{n_1\times n_2\times \cdots \times n_d}$ . Observe that $$\widehat{𝒜}=\sum _{j_1=1}^{n_1}\sum _{j_2=1}^{n_2}\cdots \sum _{j_d=1}^{n_d}{a}_{j_1,j_2,\dots ,j_d}{𝐞}_{j_1}^1\otimes {𝐞}_{j_2}^2\otimes \cdots \otimes {𝐞}_{j_d}^d,$$

where ${𝐞}_j^k\in F^{n_k}$ is the jth standard basis vector of $F^{n_k}$ and the tensor product of vectors is the affine Segre map $\otimes :({𝐯}^{(1)},{𝐯}^{(2)},\dots ,{𝐯}^{(d)})\mapsto [v_{i_1}^{(1)}{v}_{i_2}^{(2)}\cdots v_{i_d}^{(d)}{]}_{i_1,i_2,\dots ,i_d}$. It follows from the above choices of bases that the multilinear multiplication $ℬ=(M_1,M_2,\dots ,M_d)\cdot 𝒜$ becomes

$$\begin{array}{cc}\widehat{ℬ}& =({\hat{M}}_1,{\hat{M}}_2,\dots ,{\hat{M}}_d)\cdot \sum _{j_1=1}^{n_1}\sum _{j_2=1}^{n_2}\cdots \sum _{j_d=1}^{n_d}{a}_{j_1,j_2,\dots ,j_d}{𝐞}_{j_1}^1\otimes {𝐞}_{j_2}^2\otimes \cdots \otimes {𝐞}_{j_d}^d\\ & =\sum _{j_1=1}^{n_1}\sum _{j_2=1}^{n_2}\cdots \sum _{j_d=1}^{n_d}{a}_{j_1,j_2,\dots ,j_d}({\hat{M}}_1,{\hat{M}}_2,\dots ,{\hat{M}}_d)\cdot ({𝐞}_{j_1}^1\otimes {𝐞}_{j_2}^2\otimes \cdots \otimes {𝐞}_{j_d}^d)\\ & =\sum _{j_1=1}^{n_1}\sum _{j_2=1}^{n_2}\cdots \sum _{j_d=1}^{n_d}{a}_{j_1,j_2,\dots ,j_d}({\hat{M}}_1{𝐞}_{j_1}^1)\otimes ({\hat{M}}_2{𝐞}_{j_2}^2)\otimes \cdots \otimes ({\hat{M}}_d{𝐞}_{j_d}^d).\end{array}$$

The resulting tensor $\widehat{ℬ}$ lives in $F^{m_1\times m_2\times \cdots \times m_d}$.

Element-wise definition

From the above expression, an element-wise definition of the multilinear multiplication is obtained. Indeed, since $\widehat{ℬ}$ is a multidimensional array, it may be expressed as $$\widehat{ℬ}=\sum _{j_1=1}^{n_1}\sum _{j_2=1}^{n_2}\cdots \sum _{j_d=1}^{n_d}{b}_{j_1,j_2,\dots ,j_d}{𝐞}_{j_1}^1\otimes {𝐞}_{j_2}^2\otimes \cdots \otimes {𝐞}_{j_d}^d,$$where $b_{j_1,j_2,\dots ,j_d}\in F$ are the coefficients. Then it follows from the above formulae that

$$\begin{array}{cc}& (({𝐞}_{i_1}^1{)}^T,({𝐞}_{i_2}^2{)}^T,\dots ,({𝐞}_{i_d}^d{)}^T)\cdot \widehat{ℬ}\\ =& \sum _{j_1=1}^{n_1}\sum _{j_2=1}^{n_2}\cdots \sum _{j_d=1}^{n_d}{b}_{j_1,j_2,\dots ,j_d}(({𝐞}_{i_1}^1{)}^T{𝐞}_{j_1}^1)\otimes (({𝐞}_{i_2}^2{)}^T{𝐞}_{j_2}^2)\otimes \cdots \otimes (({𝐞}_{i_d}^d{)}^T{𝐞}_{j_d}^d)\\ =& \sum _{j_1=1}^{n_1}\sum _{j_2=1}^{n_2}\cdots \sum _{j_d=1}^{n_d}{b}_{j_1,j_2,\dots ,j_d}{\delta }_{i_1,j_1}\cdot {\delta }_{i_2,j_2}\cdots {\delta }_{i_d,j_d}\\ =& b_{i_1,i_2,\dots ,i_d},\end{array}$$

where ${\delta }_{i,j}$ is the Kronecker delta. Hence, if $ℬ=(M_1,M_2,\dots ,M_d)\cdot 𝒜$, then

$$\begin{array}{cc}& b_{i_1,i_2,\dots ,i_d}=(({𝐞}_{i_1}^1{)}^T,({𝐞}_{i_2}^2{)}^T,\dots ,({𝐞}_{i_d}^d{)}^T)\cdot \widehat{ℬ}\\ =& (({𝐞}_{i_1}^1{)}^T,({𝐞}_{i_2}^2{)}^T,\dots ,({𝐞}_{i_d}^d{)}^T)\cdot ({\hat{M}}_1,{\hat{M}}_2,\dots ,{\hat{M}}_d)\cdot \sum _{j_1=1}^{n_1}\sum _{j_2=1}^{n_2}\cdots \sum _{j_d=1}^{n_d}{a}_{j_1,j_2,\dots ,j_d}{𝐞}_{j_1}^1\otimes {𝐞}_{j_2}^2\otimes \cdots \otimes {𝐞}_{j_d}^d\\ =& \sum _{j_1=1}^{n_1}\sum _{j_2=1}^{n_2}\cdots \sum _{j_d=1}^{n_d}{a}_{j_1,j_2,\dots ,j_d}(({𝐞}_{i_1}^1{)}^T{\hat{M}}_1{𝐞}_{j_1}^1)\otimes (({𝐞}_{i_2}^2{)}^T{\hat{M}}_2{𝐞}_{j_2}^2)\otimes \cdots \otimes (({𝐞}_{i_d}^d{)}^T{\hat{M}}_d{𝐞}_{j_d}^d)\\ =& \sum _{j_1=1}^{n_1}\sum _{j_2=1}^{n_2}\cdots \sum _{j_d=1}^{n_d}{a}_{j_1,j_2,\dots ,j_d}{m}_{i_1,j_1}^{(1)}\cdot m_{i_2,j_2}^{(2)}\cdots m_{i_d,j_d}^{(d)},\end{array}$$

where the $m_{i,j}^{(k)}$ are the elements of ${\hat{M}}_k$ as defined above.

Properties

Let $𝒜\in V_1\otimes V_2\otimes \cdots \otimes V_d$ be an order-d tensor over the tensor product of $F$-vector spaces.

Since a multilinear multiplication is the tensor product of linear maps, we have the following multilinearity property (in the construction of the map):

$$A_1\otimes \cdots \otimes A_{k-1}\otimes (\alpha A_k+\beta B)\otimes A_{k+1}\otimes \cdots \otimes A_d=\alpha A_1\otimes \cdots \otimes A_d+\beta A_1\otimes \cdots \otimes A_{k-1}\otimes B\otimes A_{k+1}\otimes \cdots \otimes A_d$$

Multilinear multiplication is a linear map: $$(M_1,M_2,\dots ,M_d)\cdot (\alpha 𝒜+\beta ℬ)=\alpha (M_1,M_2,\dots ,M_d)\cdot 𝒜+\beta (M_1,M_2,\dots ,M_d)\cdot ℬ$$

It follows from the definition that the composition of two multilinear multiplications is also a multilinear multiplication:

$$(M_1,M_2,\dots ,M_d)\cdot ((K_1,K_2,\dots ,K_d)\cdot 𝒜)=(M_1\circ K_1,M_2\circ K_2,\dots ,M_d\circ K_d)\cdot 𝒜,$$

where $M_k:U_k\to W_k$ and $K_k:V_k\to U_k$ are linear maps.

Observe specifically that multilinear multiplications in different factors commute,

$$M_k{\cdot }_k\left(M_{\ell }{\cdot }_{\ell }𝒜\right)=M_{\ell }{\cdot }_{\ell }\left(M_k{\cdot }_k𝒜\right)=M_k{\cdot }_k{M}_{\ell }{\cdot }_{\ell }𝒜,$$

if $k\ne \ell .$

Computation

The factor-k multilinear multiplication $M_k{\cdot }_k𝒜$ can be computed in coordinates as follows. Observe first that

$$\begin{array}{cc}{M}_k{\cdot }_k𝒜& =M_k{\cdot }_k\sum _{j_1=1}^{n_1}\sum _{j_2=1}^{n_2}\cdots \sum _{j_d=1}^{n_d}{a}_{j_1,j_2,\dots ,j_d}{𝐞}_{j_1}^1\otimes {𝐞}_{j_2}^2\otimes \cdots \otimes {𝐞}_{j_d}^d\\ & =\sum _{j_1=1}^{n_1}\cdots \sum _{j_{k-1}=1}^{n_{k-1}}\sum _{j_{k+1}=1}^{n_{k+1}}\cdots \sum _{j_d=1}^{n_d}{𝐞}_{j_1}^1\otimes \cdots \otimes {𝐞}_{j_{k-1}}^{k-1}\otimes M_k\left(\sum _{j_k=1}^{n_k}{a}_{j_1,j_2,\dots ,j_d}{𝐞}_{j_k}^k\right)\otimes {𝐞}_{j_{k+1}}^{k+1}\otimes \cdots \otimes {𝐞}_{j_d}^d.\end{array}$$

Next, since

$$F^{n_1}\otimes F^{n_2}\otimes \cdots \otimes F^{n_d}\simeq F^{n_k}\otimes (F^{n_1}\otimes \cdots \otimes F^{n_{k-1}}\otimes F^{n_{k+1}}\otimes \cdots \otimes F^{n_d})\simeq F^{n_k}\otimes F^{n_1\cdots n_{k-1}{n}_{k+1}\cdots n_d},$$

there is a bijective map, called the factor-k standard flattening, denoted by $(\cdot {)}_{(k)}$, that identifies $M_k{\cdot }_k𝒜$ with an element from the latter space, namely

$${\left(M_k{\cdot }_k𝒜\right)}_{(k)}:=\sum _{j_1=1}^{n_1}\cdots \sum _{j_{k-1}=1}^{n_{k-1}}\sum _{j_{k+1}=1}^{n_{k+1}}\cdots \sum _{j_d=1}^{n_d}{M}_k\left(\sum _{j_k=1}^{n_k}{a}_{j_1,j_2,\dots ,j_d}{𝐞}_{j_k}^k\right)\otimes {𝐞}_{{\mu }_k(j_1,\dots ,j_{k-1},j_{k+1},\dots ,j_d)}:=M_k{𝒜}_{(k)},$$

where ${𝐞}_j$is the jth standard basis vector of $F^{N_k}$, $N_k=n_1\cdots n_{k-1}{n}_{k+1}\cdots n_d$, and ${𝒜}_{(k)}\in F^{n_k}\otimes F^{N_k}\simeq F^{n_k\times N_k}$ is the factor-k flattening matrix of $𝒜$ whose columns are the factor-k vectors $[a_{j_1,\dots ,j_{k-1},i,j_{k+1},\dots ,j_d}{]}_{i=1}^{n_k}$ in some order, determined by the particular choice of the bijective map

$${\mu }_k:[1,n_1]\times \cdots \times [1,n_{k-1}]\times [1,n_{k+1}]\times \cdots \times [1,n_d]\to [1,N_k].$$

In other words, the multilinear multiplication $(M_1,M_2,\dots ,M_d)\cdot 𝒜$ can be computed as a sequence of d factor-k multilinear multiplications, which themselves can be implemented efficiently as classic matrix multiplications.

Applications

The higher-order singular value decomposition (HOSVD) factorizes a tensor given in coordinates $𝒜\in F^{n_1\times n_2\times \cdots \times n_d}$ as the multilinear multiplication $𝒜=(U_1,U_2,\dots ,U_d)\cdot 𝒮$, where $U_k\in F^{n_k\times n_k}$ are orthogonal matrices and $𝒮\in F^{n_1\times n_2\times \cdots \times n_d}$.