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 $\mathcal \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 $\mathcal = \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 $\mathcal$ with $(A_1, A_2, \ldots, A_d)$ is defined as the action on $\mathcal$ of the tensor product of these linear maps, namely

$\begin 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$

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 $\mathcal \in V_1 \otimes V_2 \otimes \cdots \otimes V_d$, the multilinear multiplication is

\begin
& \mathcal := (A_1 \otimes A_2 \otimes \cdots \otimes A_d)(\mathcal) \\ pt= & (A_1 \otimes A_2 \otimes \cdots \otimes A_d)\left(\sum_^r \mathbf_i^1 \otimes \mathbf_i^2 \otimes \cdots \otimes \mathbf_i^d\right) \\ pt= & \sum_^r A_1(\mathbf_i^1) \otimes A_2(\mathbf_i^2) \otimes \cdots \otimes A_d( \mathbf_i^d )
\end

where $\mathcal = \sum_^r \mathbf_i^1 \otimes \mathbf_i^2 \otimes \cdots \otimes \mathbf_i^d$ with $\mathbf_i^k \in V_k$ is one of $\mathcal$'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 $\mathcal$ 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, \ldots, A_d) \cdot \mathcal := (A_1 \otimes A_2 \otimes \cdots \otimes A_d)(\mathcal)$and$A_k \cdot_k \mathcal := (\operatorname_, \ldots, \operatorname_, A_k, \operatorname_, \ldots, \operatorname_) \cdot \mathcal,$where $\operatorname_ : 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 $\$ be a basis for $V_k$, let $\$ be the dual basis, and let $\$ be a basis for $W_k$. The linear map $M_k = \sum_^ \sum_^ m_^ f_i^k \otimes (e_j^k)^*$ is then represented by the matrix \widehat_k = _^\in F^. Likewise, with respect to the standard tensor product basis $\_$, the abstract tensor$\mathcal = \sum_^ \sum_^ \cdots \sum_^ a_ e_^1 \otimes e_^2 \otimes \cdots \otimes e_^d$is represented by the multidimensional array \widehat = _\in F^
. Observe that $\widehat = \sum_^ \sum_^ \cdots \sum_^ a_ \mathbf_^1 \otimes \mathbf_^2 \otimes \cdots \otimes \mathbf_^d,$

where $\mathbf_j^k \in F^$ is the ''j''th standard basis vector of $F^$ and the tensor product of vectors is the affine Segre map \otimes : (\mathbf^, \mathbf^, \ldots, \mathbf^) \mapsto _^ v_^ \cdots v_^ . It follows from the above choices of bases that the multilinear multiplication $\mathcal = (M_1, M_2, \ldots, M_d) \cdot \mathcal$ becomes

$\begin \widehat &= (\widehat_1, \widehat_2, \ldots, \widehat_d) \cdot \sum_^ \sum_^ \cdots \sum_^ a_ \mathbf_^1 \otimes \mathbf_^2 \otimes \cdots \otimes \mathbf_^d \\ &= \sum_^ \sum_^ \cdots \sum_^ a_ (\widehat_1, \widehat_2, \ldots, \widehat_d) \cdot (\mathbf_^1 \otimes \mathbf_^2 \otimes \cdots \otimes \mathbf_^d) \\ &= \sum_^ \sum_^ \cdots \sum_^ a_ (\widehat_1 \mathbf_^1) \otimes (\widehat_2 \mathbf_^2) \otimes \cdots \otimes (\widehat_d \mathbf_^d). \end$

The resulting tensor $\widehat$ lives in $F^$.

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_^ \sum_^ \cdots \sum_^ b_ \mathbf_^1 \otimes \mathbf_^2 \otimes \cdots \otimes \mathbf_^d,$where $b_ \in F$ are the coefficients. Then it follows from the above formulae that

$\begin & \left( (\mathbf_^1)^T, (\mathbf_^2)^T, \ldots, (\mathbf_^d)^T \right) \cdot \widehat \\ = & \sum_^ \sum_^ \cdots \sum_^ b_ \left( (\mathbf_^1)^T \mathbf_^1 \right) \otimes \left((\mathbf_^2)^T \mathbf_^2\right) \otimes \cdots \otimes \left( (\mathbf_^d)^T \mathbf_^d \right) \\ = & \sum_^ \sum_^ \cdots \sum_^ b_ \delta_ \cdot \delta_ \cdots \delta_ \\ = & b_, \end$

where $\delta_$ is the Kronecker delta. Hence, if $\mathcal = (M_1, M_2, \ldots, M_d) \cdot \mathcal$, then

$\begin & b_ = \left( (\mathbf_^1)^T, (\mathbf_^2)^T, \ldots, (\mathbf_^d)^T \right) \cdot \widehat \\ = & \left( (\mathbf_^1)^T, (\mathbf_^2)^T, \ldots, (\mathbf_^d)^T \right) \cdot (\widehat_1, \widehat_2, \ldots, \widehat_d) \cdot \sum_^ \sum_^ \cdots \sum_^ a_ \mathbf_^1 \otimes \mathbf_^2 \otimes \cdots \otimes \mathbf_^d \\ = & \sum_^ \sum_^ \cdots \sum_^ a_ ((\mathbf_^1)^T \widehat_1 \mathbf_^1) \otimes ((\mathbf_^2)^T \widehat_2 \mathbf_^2) \otimes \cdots \otimes ((\mathbf_^d)^T \widehat_d \mathbf_^d) \\ = & \sum_^ \sum_^ \cdots \sum_^ a_ m_^ \cdot m_^ \cdots m_^, \end$

where the $m_^$ are the elements of $\widehat_k$ as defined above.

Properties

Let $\mathcal \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_ \otimes (\alpha A_k + \beta B) \otimes A_ \otimes \cdots \otimes A_d = \alpha A_1 \otimes \cdots \otimes A_d + \beta A_1 \otimes \cdots \otimes A_ \otimes B \otimes A_ \otimes \cdots \otimes A_d$

Multilinear multiplication is a linear map: $(M_1, M_2, \ldots, M_d) \cdot (\alpha \mathcal + \beta \mathcal) = \alpha \; (M_1, M_2, \ldots, M_d) \cdot \mathcal + \beta \; (M_1, M_2, \ldots, M_d) \cdot \mathcal$

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

$(M_1, M_2, \ldots, M_d) \cdot \left( (K_1, K_2, \ldots, K_d) \cdot \mathcal \right) = (M_1 \circ K_1, M_2 \circ K_2, \ldots, M_d \circ K_d) \cdot \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 \cdot_k \left( M_\ell \cdot_\ell \mathcal \right) = M_\ell \cdot_\ell \left( M_k \cdot_k \mathcal \right) = M_k \cdot_k M_\ell \cdot_\ell \mathcal,$

if $k \ne \ell.$

Computation

The factor-k multilinear multiplication $M_k \cdot_k\mathcal$ can be computed in coordinates as follows. Observe first that

$\begin M_k \cdot_k \mathcal &= M_k \cdot_k \sum_^ \sum_^ \cdots \sum_^ a_ \mathbf_^1 \otimes \mathbf_^2 \otimes \cdots \otimes \mathbf_^d \\ &= \sum_^ \cdots \sum_^ \sum_^ \cdots \sum_^ \mathbf_^1 \otimes \cdots \otimes \mathbf_^ \otimes M_k \left ( \sum_^ a_ \mathbf_^k \right) \otimes \mathbf_^ \otimes \cdots \otimes \mathbf_^d. \end$

Next, since

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

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

$\left( M_k \cdot_k \mathcal \right)_ := \sum_^ \cdots \sum_^ \sum_^ \cdots \sum_^ M_k \left ( \sum_^ a_ \mathbf_^ \right) \otimes \mathbf_ := M_k \mathcal_,$

where $\mathbf_j$is the ''j''th standard basis vector of $F^$, $N_k = n_1 \cdots n_ n_ \cdots n_d$, and $\mathcal_ \in F^ \otimes F^ \simeq F^$ is the factor-''k'' flattening matrix of $\mathcal$ whose columns are the factor-''k'' vectors _^ in some order, determined by the particular choice of the bijective map

\mu_k : ,n_1\times \cdots \times ,n_\times ,n_\times \cdots \times ,n_d\to ,N_k

In other words, the multilinear multiplication $(M_1, M_2, \ldots, M_d) \cdot \mathcal$ 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 $\mathcal \in F^$ as the multilinear multiplication $\mathcal = (U_1, U_2, \ldots, U_d) \cdot \mathcal$, where $U_k \in F^$ are orthogonal matrices and $\mathcal \in F^{n_1 \times n_2 \times \cdots \times n_d}$.

Further reading

Tensors
Multilinear algebra