Multilinear multiplication explained

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 R or C .Let V _{k} be a finite-dimensional vector space over F , and let l{A} \in V _{1} ⊗ V _{2} ⊗ … ⊗ V _{d} be an order-d simple tensor, i.e., there exist some vectors v _{k} \in V _{k} such that l{A} = v _{1} ⊗ v _{2} ⊗ … ⊗ v _{d} . If we are given a collection of linear maps A _{k} : V _{k} \to W _{k} , then the multilinear multiplication of l{A} with (A _{1,} A _{2,} \ldots, A _{d)} is defined^[1] as the action on l{A} of the tensor product of these linear maps,^[2] namely

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

l{A} \in V _{1} ⊗ V _{2} ⊗ … ⊗ V _{d} , the multilinear multiplication is

where $\backslash mathcal\; =\; \backslash sum\_^r\; \backslash mathbf\_i^1\; \backslash otimes\; \backslash mathbf\_i^2\; \backslash otimes\; \backslash cdots\; \backslash otimes\; \backslash mathbf\_i^d$ with

a ^{k} _{i} \in V _{k} is one of l{A} '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 l{A} 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,\; \backslash ldots,\; A\_d)\; \backslash cdot\; \backslash mathcal\; :=\; (A\_1\; \backslash otimes\; A\_2\; \backslash otimes\; \backslash cdots\; \backslash otimes\; A\_d)(\backslash mathcal)$$and$$A\_k\; \backslash cdot\_k\; \backslash mathcal\; :=\; (\backslash operatorname\_,\; \backslash ldots,\; \backslash operatorname\_,\; A\_k,\; \backslash operatorname\_,\; \backslash ldots,\; \backslash operatorname\_)\; \backslash cdot\; \backslash mathcal,$$where

\operatorname{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 ^{k,} _{1} \ldots, e ^{k} _{n _{k}} \} be a basis for V _{k} , let \{ (e ^{k)} _{1} ^{*,} \ldots, (e ^{k)} _{n _{k}} ^{*} \} be the dual basis, and let \{f ^{k,} _{1} \ldots, f ^{k} _{m _{k}} \} be a basis for W _{k} . The linear map $M\_k\; =\; \backslash sum\_^\; \backslash sum\_^\; m\_^\; f\_i^k\; \backslash otimes\; (e\_j^k)^*$ is then represented by the matrix \widehat{M} _{k} = [m ^{(k)} _{i,j} ] \in F ^{m _{k} x n _{k}} . Likewise, with respect to the standard tensor product basis \{ e ^{1} _{j _{1}} ⊗ e ^{2} _{j _{2}} ⊗ … ⊗ e ^{d} _{j _{d}} \} _{j _{1,j} _{2,\ldots,j} _{d}} , the abstract tensor$$\backslash mathcal\; =\; \backslash sum\_^\; \backslash sum\_^\; \backslash cdots\; \backslash sum\_^\; a\_\; e\_^1\; \backslash otimes\; e\_^2\; \backslash otimes\; \backslash cdots\; \backslash otimes\; e\_^d$$is represented by the multidimensional array \widehat{ l{A}} = [a _{j _{1,j} _{2,\ldots,j} _{d}} ] \in F ^{n _{1} x n _{2} x … x n _{d}} . Observe that $$\backslash widehat\; =\; \backslash sum\_^\; \backslash sum\_^\; \backslash cdots\; \backslash sum\_^\; a\_\; \backslash mathbf\_^1\; \backslash otimes\; \backslash mathbf\_^2\; \backslash otimes\; \backslash cdots\; \backslash otimes\; \backslash mathbf\_^d,$$

where

e ^{k} _{j} \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 ⊗ : ( v ^{(1)} , v ^{(2)} , \ldots, v ^{(d)} ) \mapsto [v ^{( 1 )} _{i _{1}} v ^{( 2 )} _{i _{2}} … v ^{(d)} _{i _{d}} ] _{i _{1,i} _{2,\ldots,i} _{d}} . It follows from the above choices of bases that the multilinear multiplication l{B} = (M _{1,} M _{2,} \ldots, M _{d)} ⋅ l{A} becomes

The resulting tensor

\widehat{ l{B}} lives in F ^{m _{1} x m _{2} x … x m _{d}} .

Element-wise definition

From the above expression, an element-wise definition of the multilinear multiplication is obtained. Indeed, since

\widehat{ l{B}} is a multidimensional array, it may be expressed as $$\backslash widehat\; =\; \backslash sum\_^\; \backslash sum\_^\; \backslash cdots\; \backslash sum\_^\; b\_\; \backslash mathbf\_^1\; \backslash otimes\; \backslash mathbf\_^2\; \backslash otimes\; \backslash cdots\; \backslash otimes\; \backslash mathbf\_^d,$$where b _{j _{1,j} _{2,\ldots,j} _{d}} \in F are the coefficients. Then it follows from the above formulae that

where

\delta _{i,j} is the Kronecker delta. Hence, if l{B} = (M _{1,} M _{2,} \ldots, M _{d)} ⋅ l{A} , then

where the

m ^{(k)} _{i,j} are the elements of \widehat{M} _{k} as defined above.

Properties

Let

l{A} \in V _{1} ⊗ V _{2} ⊗ … ⊗ 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\; \backslash otimes\; \backslash cdots\; \backslash otimes\; A\_\; \backslash otimes\; (\backslash alpha\; A\_k\; +\; \backslash beta\; B)\; \backslash otimes\; A\_\; \backslash otimes\; \backslash cdots\; \backslash otimes\; A\_d\; =\; \backslash alpha\; A\_1\; \backslash otimes\; \backslash cdots\; \backslash otimes\; A\_d\; +\; \backslash beta\; A\_1\; \backslash otimes\; \backslash cdots\; \backslash otimes\; A\_\; \backslash otimes\; B\; \backslash otimes\; A\_\; \backslash otimes\; \backslash cdots\; \backslash otimes\; A\_d$$

Multilinear multiplication is a linear map: $$(M\_1,\; M\_2,\; \backslash ldots,\; M\_d)\; \backslash cdot\; (\backslash alpha\; \backslash mathcal\; +\; \backslash beta\; \backslash mathcal)\; =\; \backslash alpha\; \backslash ;\; (M\_1,\; M\_2,\; \backslash ldots,\; M\_d)\; \backslash cdot\; \backslash mathcal\; +\backslash beta\; \backslash ;\; (M\_1,\; M\_2,\; \backslash ldots,\; M\_d)\; \backslash cdot\; \backslash mathcal$$

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

$$(M\_1,\; M\_2,\; \backslash ldots,\; M\_d)\; \backslash cdot\; \backslash left((K\_1,\; K\_2,\; \backslash ldots,\; K\_d)\; \backslash cdot\; \backslash mathcal\; \backslash right)=\; (M\_1\; \backslash circ\; K\_1,\; M\_2\; \backslash circ\; K\_2,\; \backslash ldots,\; M\_d\; \backslash circ\; K\_d)\; \backslash cdot\; \backslash mathcal,$$

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\; \backslash cdot\_k\; \backslash left(M\_\backslash ell\; \backslash cdot\_\backslash ell\; \backslash mathcal\; \backslash right)\; =\; M\_\backslash ell\; \backslash cdot\_\backslash ell\; \backslash left(M\_k\; \backslash cdot\_k\; \backslash mathcal\; \backslash right)\; =\; M\_k\; \backslash cdot\_k\; M\_\backslash ell\; \backslash cdot\_\backslash ell\; \backslash mathcal,$$

if

k \ne \ell.

Computation

The factor-k multilinear multiplication

M _{k} ⋅ _{kl{A}} can be computed in coordinates as follows. Observe first that

Next, since

$$F^\; \backslash otimes\; F^\; \backslash otimes\; \backslash cdots\; \backslash otimes\; F^\; \backslash simeq\; F^\; \backslash otimes\; (F^\; \backslash otimes\; \backslash cdots\; \backslash otimes\; F^\; \backslash otimes\; F^\; \backslash otimes\; \backslash cdots\; \backslash otimes\; F^)\; \backslash simeq\; F^\; \backslash otimes\; F^,$$

there is a bijective map, called the factor-k standard flattening, denoted by

( ⋅ ) _{(k)} , that identifies M _{k} ⋅ _{k} l{A} with an element from the latter space, namely

$$\backslash left(M\_k\; \backslash cdot\_k\; \backslash mathcal\; \backslash right)\_\; :=\backslash sum\_^\; \backslash cdots\; \backslash sum\_^\; \backslash sum\_^\; \backslash cdots\; \backslash sum\_^\; M\_k\; \backslash left\; (\backslash sum\_^\; a\_\; \backslash mathbf\_^\; \backslash right)\; \backslash otimes\; \backslash mathbf\_\; :=\; M\_k\; \backslash mathcal\_,$$

where

e _{j} is the jth standard basis vector of F ^{N _{k}} , N _{k} = n _{1} … n _{k-1} n _{k+1} … n _{d} , and l{A} _{(k)} \in F ^{n _{k}} ⊗ F ^{N _{k}} \simeq F ^{n _{k} x N _{k}} is the factor-k flattening matrix of l{A} whose columns are the factor-k vectors [a _{j _{1,\ldots,j} _{k-1} ,i,j _{k+1} ,\ldots,j _{d}} ] ^{n _{k}} _{i =1} in some order, determined by the particular choice of the bijective map

$$\backslash mu\_k\; :\; [1,n\_1]\; \backslash times\; \backslash cdots\; \backslash times\; [1,n\_\{k-1\}]\; \backslash times\; [1,n\_\{k+1\}]\; \backslash times\; \backslash cdots\; \backslash times\; [1,n\_d]\; \backslash to\; [1,N\_k].$$

In other words, the multilinear multiplication

(M _{1,} M _{2,} \ldots, M _{d)} ⋅ l{A} 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

l{A} \in F ^{n _{1} x n _{2} x … x n _{d}} as the multilinear multiplication l{A} = (U _{1,} U _{2,} \ldots, U _{d)} ⋅ l{S} , where U _{k} \in F ^{n _{k} x n _{k}} are orthogonal matrices and l{S} \in F ^{n _{1} x n _{2} x … x n _{d}} .

Further reading

1. Book: M., Landsberg, J.. Tensors : geometry and applications. 2012. American Mathematical Society. 9780821869079. Providence, R.I.. 733546583.
2. Book: Multilinear Algebra Werner Greub Springer. Universitext. 1978. Springer. 9780387902845. en.