In multilinear algebra, applying a map that is the tensor product of linear maps to a tensor is called a multilinear multiplication.
Abstract definition[edit]
Let
be a field of characteristic zero, such as
or
.
Let
be a finite-dimensional vector space over
, and let
be an order-d simple tensor, i.e., there exist some vectors
such that
. If we are given a collection of linear maps
, then the multilinear multiplication of
with
is defined[1] as the action on
of the tensor product of these linear maps,[2] namely
![{\displaystyle {\begin{aligned}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 {v} _{1}\otimes \mathbf {v} _{2}\otimes \cdots \otimes \mathbf {v} _{d}&\mapsto A_{1}(\mathbf {v} _{1})\otimes A_{2}(\mathbf {v} _{2})\otimes \cdots \otimes A_{d}(\mathbf {v} _{d})\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cd38c68db294ead0771aee0e9a6cdc9b387a008e)
Since the tensor product of linear maps is itself a linear map,[2] and because every tensor admits a tensor rank decomposition,[1] the above expression extends linearly to all tensors. That is, for a general tensor
, the multilinear multiplication is
![{\displaystyle {\begin{aligned}&{\mathcal {B}}:=(A_{1}\otimes A_{2}\otimes \cdots \otimes A_{d})({\mathcal {A}})\\[4pt]={}&(A_{1}\otimes A_{2}\otimes \cdots \otimes A_{d})\left(\sum _{i=1}^{r}\mathbf {a} _{i}^{1}\otimes \mathbf {a} _{i}^{2}\otimes \cdots \otimes \mathbf {a} _{i}^{d}\right)\\[5pt]={}&\sum _{i=1}^{r}A_{1}(\mathbf {a} _{i}^{1})\otimes A_{2}(\mathbf {a} _{i}^{2})\otimes \cdots \otimes A_{d}(\mathbf {a} _{i}^{d})\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/578131c96c802126b32a930136da435d8de2f7a3)
where
with
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:
![{\displaystyle (A_{1},A_{2},\ldots ,A_{d})\cdot {\mathcal {A}}:=(A_{1}\otimes A_{2}\otimes \cdots \otimes A_{d})({\mathcal {A}})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/27c03ade99250a475eb63d16f8f1f2ff1e243202)
and
![{\displaystyle A_{k}\cdot _{k}{\mathcal {A}}:=(\operatorname {Id} _{V_{1}},\ldots ,\operatorname {Id} _{V_{k-1}},A_{k},\operatorname {Id} _{V_{k+1}},\ldots ,\operatorname {Id} _{V_{d}})\cdot {\mathcal {A}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/49619a648f44baab839d9fd7aeff68b956b0efb0)
where
![{\displaystyle \operatorname {Id} _{V_{k}}:V_{k}\to V_{k}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9e50224d79479940bfd337e750d256c0247676b2)
is the
identity operator.
Definition in coordinates[edit]
In computational multilinear algebra it is conventional to work in coordinates. Assume that an inner product is fixed on
and let
denote the dual vector space of
. Let
be a basis for
, let
be the dual basis, and let
be a basis for
. The linear map
is then represented by the matrix
. Likewise, with respect to the standard tensor product basis
, the abstract tensor
![{\displaystyle {\mathcal {A}}=\sum _{j_{1}=1}^{n_{1}}\sum _{j_{2}=1}^{n_{2}}\cdots \sum _{j_{d}=1}^{n_{d}}a_{j_{1},j_{2},\ldots ,j_{d}}e_{j_{1}}^{1}\otimes e_{j_{2}}^{2}\otimes \cdots \otimes e_{j_{d}}^{d}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a2896c1b3a54dfeb884a7357e37081ea1b6cbc46)
is represented by the multidimensional array
![{\displaystyle {\widehat {\mathcal {A}}}=[a_{j_{1},j_{2},\ldots ,j_{d}}]\in F^{n_{1}\times n_{2}\times \cdots \times n_{d}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7a39d34160d0f6db294f09c923100419af8a14df)
. Observe that
![{\displaystyle {\widehat {\mathcal {A}}}=\sum _{j_{1}=1}^{n_{1}}\sum _{j_{2}=1}^{n_{2}}\cdots \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},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d2c14611107ad18b977502ff0b1096a6a37df903)
where
is the jth standard basis vector of
and the tensor product of vectors is the affine Segre map
. It follows from the above choices of bases that the multilinear multiplication
becomes
![{\displaystyle {\begin{aligned}{\widehat {\mathcal {B}}}&=({\widehat {M}}_{1},{\widehat {M}}_{2},\ldots ,{\widehat {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},\ldots ,j_{d}}\mathbf {e} _{j_{1}}^{1}\otimes \mathbf {e} _{j_{2}}^{2}\otimes \cdots \otimes \mathbf {e} _{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},\ldots ,j_{d}}({\widehat {M}}_{1},{\widehat {M}}_{2},\ldots ,{\widehat {M}}_{d})\cdot (\mathbf {e} _{j_{1}}^{1}\otimes \mathbf {e} _{j_{2}}^{2}\otimes \cdots \otimes \mathbf {e} _{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},\ldots ,j_{d}}({\widehat {M}}_{1}\mathbf {e} _{j_{1}}^{1})\otimes ({\widehat {M}}_{2}\mathbf {e} _{j_{2}}^{2})\otimes \cdots \otimes ({\widehat {M}}_{d}\mathbf {e} _{j_{d}}^{d}).\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/aca0d8a54ca55871b9afbc629b4a4d1389871e7e)
The resulting tensor
lives in
.
Element-wise definition[edit]
From the above expression, an element-wise definition of the multilinear multiplication is obtained. Indeed, since
is a multidimensional array, it may be expressed as
![{\displaystyle {\widehat {\mathcal {B}}}=\sum _{j_{1}=1}^{n_{1}}\sum _{j_{2}=1}^{n_{2}}\cdots \sum _{j_{d}=1}^{n_{d}}b_{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},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/269f8b7e79bf329799fb0b90d7f9c714aa600ada)
where
![{\displaystyle b_{j_{1},j_{2},\ldots ,j_{d}}\in F}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d08a0d018581a45854b711258911c7978c42f324)
are the coefficients. Then it follows from the above formulae that
![{\displaystyle {\begin{aligned}&\left((\mathbf {e} _{i_{1}}^{1})^{T},(\mathbf {e} _{i_{2}}^{2})^{T},\ldots ,(\mathbf {e} _{i_{d}}^{d})^{T}\right)\cdot {\widehat {\mathcal {B}}}\\={}&\sum _{j_{1}=1}^{n_{1}}\sum _{j_{2}=1}^{n_{2}}\cdots \sum _{j_{d}=1}^{n_{d}}b_{j_{1},j_{2},\ldots ,j_{d}}\left((\mathbf {e} _{i_{1}}^{1})^{T}\mathbf {e} _{j_{1}}^{1}\right)\otimes \left((\mathbf {e} _{i_{2}}^{2})^{T}\mathbf {e} _{j_{2}}^{2}\right)\otimes \cdots \otimes \left((\mathbf {e} _{i_{d}}^{d})^{T}\mathbf {e} _{j_{d}}^{d}\right)\\={}&\sum _{j_{1}=1}^{n_{1}}\sum _{j_{2}=1}^{n_{2}}\cdots \sum _{j_{d}=1}^{n_{d}}b_{j_{1},j_{2},\ldots ,j_{d}}\delta _{i_{1},j_{1}}\cdot \delta _{i_{2},j_{2}}\cdots \delta _{i_{d},j_{d}}\\={}&b_{i_{1},i_{2},\ldots ,i_{d}},\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/15f40f9720d03d44bf0a15150759b81c3d8199e5)
where
is the Kronecker delta. Hence, if
, then
![{\displaystyle {\begin{aligned}&b_{i_{1},i_{2},\ldots ,i_{d}}=\left((\mathbf {e} _{i_{1}}^{1})^{T},(\mathbf {e} _{i_{2}}^{2})^{T},\ldots ,(\mathbf {e} _{i_{d}}^{d})^{T}\right)\cdot {\widehat {\mathcal {B}}}\\={}&\left((\mathbf {e} _{i_{1}}^{1})^{T},(\mathbf {e} _{i_{2}}^{2})^{T},\ldots ,(\mathbf {e} _{i_{d}}^{d})^{T}\right)\cdot ({\widehat {M}}_{1},{\widehat {M}}_{2},\ldots ,{\widehat {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},\ldots ,j_{d}}\mathbf {e} _{j_{1}}^{1}\otimes \mathbf {e} _{j_{2}}^{2}\otimes \cdots \otimes \mathbf {e} _{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},\ldots ,j_{d}}((\mathbf {e} _{i_{1}}^{1})^{T}{\widehat {M}}_{1}\mathbf {e} _{j_{1}}^{1})\otimes ((\mathbf {e} _{i_{2}}^{2})^{T}{\widehat {M}}_{2}\mathbf {e} _{j_{2}}^{2})\otimes \cdots \otimes ((\mathbf {e} _{i_{d}}^{d})^{T}{\widehat {M}}_{d}\mathbf {e} _{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},\ldots ,j_{d}}m_{i_{1},j_{1}}^{(1)}\cdot m_{i_{2},j_{2}}^{(2)}\cdots m_{i_{d},j_{d}}^{(d)},\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1ccdfca0897ff6932ac9433b9643137277df19a7)
where the
are the elements of
as defined above.
Properties[edit]
Let
be an order-d tensor over the tensor product of
-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):[1][2]
![{\displaystyle 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 \beta B_{k}\otimes A_{k+1}\otimes \cdots \otimes A_{d}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/39e12b01b519179d4b07fbf02d65a668260e9d84)
Multilinear multiplication is a linear map:[1][2]
![{\displaystyle (M_{1},M_{2},\ldots ,M_{d})\cdot (\alpha {\mathcal {A}}+\beta {\mathcal {B}})=\alpha \;(M_{1},M_{2},\ldots ,M_{d})\cdot {\mathcal {A}}+\beta \;(M_{1},M_{2},\ldots ,M_{d})\cdot {\mathcal {B}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/04ec5026fcdf96cf7b8818d949811b4847606742)
It follows from the definition that the composition of two multilinear multiplications is also a multilinear multiplication:[1][2]
![{\displaystyle (M_{1},M_{2},\ldots ,M_{d})\cdot \left((K_{1},K_{2},\ldots ,K_{d})\cdot {\mathcal {A}}\right)=(M_{1}\circ K_{1},M_{2}\circ K_{2},\ldots ,M_{d}\circ K_{d})\cdot {\mathcal {A}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/96b148be12bec59ce5a67dcd642153056415c4d6)
where
and
are linear maps.
Observe specifically that multilinear multiplications in different factors commute,
![{\displaystyle M_{k}\cdot _{k}\left(M_{\ell }\cdot _{\ell }{\mathcal {A}}\right)=M_{\ell }\cdot _{\ell }\left(M_{k}\cdot _{k}{\mathcal {A}}\right)=M_{k}\cdot _{k}M_{\ell }\cdot _{\ell }{\mathcal {A}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5f8961540fee92b791a9915d69c1cc63cef5450e)
if
Computation[edit]
The factor-k multilinear multiplication
can be computed in coordinates as follows. Observe first that
![{\displaystyle {\begin{aligned}M_{k}\cdot _{k}{\mathcal {A}}&=M_{k}\cdot _{k}\sum _{j_{1}=1}^{n_{1}}\sum _{j_{2}=2}^{n_{2}}\cdots \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}\\&=\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 {e} _{j_{1}}^{1}\otimes \cdots \otimes \mathbf {e} _{j_{k-1}}^{k-1}\otimes M_{k}\left(\sum _{j_{k}=1}^{n_{k}}a_{j_{1},j_{2},\ldots ,j_{d}}\mathbf {e} _{j_{k}}^{k}\right)\otimes \mathbf {e} _{j_{k+1}}^{k+1}\otimes \cdots \otimes \mathbf {e} _{j_{d}}^{d}.\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d54392d3bc6cae5f38444d3ce04306c63ea7de96)
Next, since
![{\displaystyle 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}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f3474cfbeed756997438858860151fcbe2439f22)
there is a bijective map, called the factor-k standard flattening,[1] denoted by
, that identifies
with an element from the latter space, namely
![{\displaystyle \left(M_{k}\cdot _{k}{\mathcal {A}}\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},\ldots ,j_{d}}\mathbf {e} _{j_{k}}^{k}\right)\otimes \mathbf {e} _{\mu _{k}(j_{1},\ldots ,j_{k-1},j_{k+1},\ldots ,j_{d})}:=M_{k}{\mathcal {A}}_{(k)},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/247560eb7181516b76c48b4f28c8c21d44300fea)
where
is the jth standard basis vector of
,
, and
is the factor-k flattening matrix of
whose columns are the factor-k vectors
in some order, determined by the particular choice of the bijective map
![{\displaystyle \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}].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a3e1d65c6facfa5698a4fcd5230bfa093c2ff272)
In other words, the multilinear multiplication
can be computed as a sequence of d factor-k multilinear multiplications, which themselves can be implemented efficiently as classic matrix multiplications.
Applications[edit]
The higher-order singular value decomposition (HOSVD) factorizes a tensor given in coordinates
as the multilinear multiplication
, where
are orthogonal matrices and
.
Further reading[edit]