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 $\mathbb{ℝ}$ or $\mathbb{ℂ}$. 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 ${\mathbf{𝐯}}_k\in V_k$ such that ${𝒜}={\mathbf{𝐯}}_1\otimes {\mathbf{𝐯}}_2\otimes \cdots \otimes {\mathbf{𝐯}}_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}{rl}{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,\\ {\mathbf{𝐯}}_1\otimes {\mathbf{𝐯}}_2\otimes \cdots \otimes {\mathbf{𝐯}}_d& \mapsto A_1({\mathbf{𝐯}}_1)\otimes A_2({\mathbf{𝐯}}_2)\otimes \cdots \otimes A_d({\mathbf{𝐯}}_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}{rl}& {ℬ}:=(A_1\otimes A_2\otimes \cdots \otimes A_d)({𝒜})\\ =& (A_1\otimes A_2\otimes \cdots \otimes A_d)(\sum _{i=1}^r{\mathbf{𝐚}}_i^1\otimes {\mathbf{𝐚}}_i^2\otimes \cdots \otimes {\mathbf{𝐚}}_i^d)\\ =& \sum _{i=1}^r{A}_1({\mathbf{𝐚}}_i^1)\otimes A_2({\mathbf{𝐚}}_i^2)\otimes \cdots \otimes A_d({\mathbf{𝐚}}_i^d)\end{array}$$

where ${𝒜}={\sum }_{i=1}^r{\mathbf{𝐚}}_i^1\otimes {\mathbf{𝐚}}_i^2\otimes \cdots \otimes {\mathbf{𝐚}}_i^d$ with ${\mathbf{𝐚}}_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^{*}$ 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{)}^{*},\dots ,(e_{n_k}^k{)}^{*}\}$ 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{)}^{*}$ 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}{\mathbf{𝐞}}_{j_1}^1\otimes {\mathbf{𝐞}}_{j_2}^2\otimes \cdots \otimes {\mathbf{𝐞}}_{j_d}^d,$$

where ${\mathbf{𝐞}}_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 :({\mathbf{𝐯}}^{(1)},{\mathbf{𝐯}}^{(2)},\dots ,{\mathbf{𝐯}}^{(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}{rl}\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}{\mathbf{𝐞}}_{j_1}^1\otimes {\mathbf{𝐞}}_{j_2}^2\otimes \cdots \otimes {\mathbf{𝐞}}_{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 ({\mathbf{𝐞}}_{j_1}^1\otimes {\mathbf{𝐞}}_{j_2}^2\otimes \cdots \otimes {\mathbf{𝐞}}_{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{\mathbf{𝐞}}_{j_1}^1)\otimes ({\hat{M}}_2{\mathbf{𝐞}}_{j_2}^2)\otimes \cdots \otimes ({\hat{M}}_d{\mathbf{𝐞}}_{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}{\mathbf{𝐞}}_{j_1}^1\otimes {\mathbf{𝐞}}_{j_2}^2\otimes \cdots \otimes {\mathbf{𝐞}}_{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}{rl}& (({\mathbf{𝐞}}_{i_1}^1{)}^T,({\mathbf{𝐞}}_{i_2}^2{)}^T,\dots ,({\mathbf{𝐞}}_{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}(({\mathbf{𝐞}}_{i_1}^1{)}^T{\mathbf{𝐞}}_{j_1}^1)\otimes (({\mathbf{𝐞}}_{i_2}^2{)}^T{\mathbf{𝐞}}_{j_2}^2)\otimes \cdots \otimes (({\mathbf{𝐞}}_{i_d}^d{)}^T{\mathbf{𝐞}}_{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}{rl}& b_{i_1,i_2,\dots ,i_d}=(({\mathbf{𝐞}}_{i_1}^1{)}^T,({\mathbf{𝐞}}_{i_2}^2{)}^T,\dots ,({\mathbf{𝐞}}_{i_d}^d{)}^T)\cdot \widehat{{ℬ}}\\ =& (({\mathbf{𝐞}}_{i_1}^1{)}^T,({\mathbf{𝐞}}_{i_2}^2{)}^T,\dots ,({\mathbf{𝐞}}_{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}{\mathbf{𝐞}}_{j_1}^1\otimes {\mathbf{𝐞}}_{j_2}^2\otimes \cdots \otimes {\mathbf{𝐞}}_{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}(({\mathbf{𝐞}}_{i_1}^1{)}^T{\hat{M}}_1{\mathbf{𝐞}}_{j_1}^1)\otimes (({\mathbf{𝐞}}_{i_2}^2{)}^T{\hat{M}}_2{\mathbf{𝐞}}_{j_2}^2)\otimes \cdots \otimes (({\mathbf{𝐞}}_{i_d}^d{)}^T{\hat{M}}_d{\mathbf{𝐞}}_{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}{rl}{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}{\mathbf{𝐞}}_{j_1}^1\otimes {\mathbf{𝐞}}_{j_2}^2\otimes \cdots \otimes {\mathbf{𝐞}}_{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}{\mathbf{𝐞}}_{j_1}^1\otimes \cdots \otimes {\mathbf{𝐞}}_{j_{k-1}}^{k-1}\otimes M_k\left(\sum _{j_k=1}^{n_k}{a}_{j_1,j_2,\dots ,j_d}{\mathbf{𝐞}}_{j_k}^k\right)\otimes {\mathbf{𝐞}}_{j_{k+1}}^{k+1}\otimes \cdots \otimes {\mathbf{𝐞}}_{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}{\mathbf{𝐞}}_{j_k}^k\right)\otimes {\mathbf{𝐞}}_{{\mu }_k(j_1,\dots ,j_{k-1},j_{k+1},\dots ,j_d)}:=M_k{{𝒜}}_{(k)},$$

where ${\mathbf{𝐞}}_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}$.