Higher-order singular value decomposition

In multilinear algebra, the higher-order singular value decomposition (HOSVD) is a misnomer. There does not exist a single tensor decomposition that retains all the defining properties of the matrix SVD. The matrix SVD simultaneously yields a

These properties are not realized within a single algorithm for higher-order tensors, but are instead realized by two distinct algorithmic developments and represent two distinct research directions. Harshman, as well as, the team of Carol and Chang proposed Canonical polyadic decomposition (CPD), which is a variant of the tensor rank decomposition, in which a tensor is approximated as a sum of K rank-1 tensors for a user-specified K. L. R. Tucker proposed a strategy for computing orthonormal subspaces for third order tensors. Aspects of these algorithms can be traced as far back as F. L. Hitchcock in 1928.

De Lathauwer et al. introduced clarity to the Tucker concepts, while Vasilescu and Terzopoulos introduced algorithmic clarity. Vasilescu and Terzopoulos introduced the M-mode SVD, which is the classic algorithm that is currently referred in the literature as the Tucker or the HOSVD. The Tucker approach and De Lathauwer's implementation are both sequential and rely on iterative procedures such as gradient descent or the power method. By contrast, the M-mode SVD provides a closed-form solution that can be executed sequentially and is well-suited for parallel computation.

The term M-mode SVD accurately reflects the algorithm employed. It captures the actual computation, a set of SVDs on mode-flattenings without making assumptions about the structure of the core tensor or implying a rank decomposition.

Robust and L1-norm-based variants of this decomposition framework have since been proposed.

For the purpose of this article, the abstract tensor ${\displaystyle {\mathcal {A}}}$ is assumed to be given in coordinates with respect to some basis as a M-way array, also denoted by ${\displaystyle {\mathcal {A}}\in \mathbb {C} ^{I_{1}\times I_{2}\cdots \times \cdots I_{m}\cdots \times I_{M}}}$, where M is the number of modes and the order of the tensor. ${\displaystyle \mathbb {C} }$ is the complex numbers and it includes both the real numbers ${\displaystyle \mathbb {R} }$ and the pure imaginary numbers.

Let ${\displaystyle {\mathcal {A}}_{[m]}\in \mathbb {C} ^{I_{m}\times (I_{1}I_{2}\cdots I_{m-1}I_{m+1}\cdots I_{M})}}$ denote the mode-m flattening of ${\displaystyle {\mathcal {A}}}$, so that the left index of ${\displaystyle {\mathcal {A}}_{[m]}}$ corresponds to the ${\displaystyle m}$'th index ${\displaystyle {\mathcal {A}}}$ and the right index of ${\displaystyle {\mathcal {A}}_{[m]}}$ corresponds to all other indices of ${\displaystyle {\mathcal {A}}}$ combined. Let ${\displaystyle {\bf {U}}_{m}\in \mathbb {C} ^{I_{m}\times I_{m}}}$be a unitary matrix containing a basis of the left singular vectors of the ${\displaystyle {\mathcal {A}}_{[m]}}$ such that the jth column ${\displaystyle \mathbf {u} _{j}}$ of ${\displaystyle {\bf {U}}_{m}}$ corresponds to the jth largest singular value of ${\displaystyle {\mathcal {A}}_{[m]}}$. Observe that the mode/factor matrix ${\displaystyle {\bf {U}}_{m}}$ does not depend on the particular on the specific definition of the mode m flattening. By the properties of the multilinear multiplication, we have$${\displaystyle {\begin{array}{rcl}{\mathcal {A}}&=&{\mathcal {A}}\times ({\bf {I}},{\bf {I}},\ldots ,{\bf {I}})\\&=&{\mathcal {A}}\times ({\bf {U}}_{1}{\bf {U}}_{1}^{H},{\bf {U}}_{2}{\bf {U}}_{2}^{H},\ldots ,{\bf {U}}_{M}{\bf {U}}_{M}^{H})\\&=&\left({\mathcal {A}}\times ({\bf {U}}_{1}^{H},{\bf {U}}_{2}^{H},\ldots ,{\bf {U}}_{M}^{H})\right)\times ({\bf {U}}_{1},{\bf {U}}_{2},\ldots ,{\bf {U}}_{M}),\end{array}}}$$where ${\displaystyle \cdot ^{H}}$ denotes the conjugate transpose. The second equality is because the ${\displaystyle {\bf {U}}_{m}}$'s are unitary matrices. Define now the core tensor$${\displaystyle {\mathcal {S}}:={\mathcal {A}}\times ({\bf {U}}_{1}^{H},{\bf {U}}_{2}^{H},\ldots ,{\bf {U}}_{M}^{H}).}$$Then, the M-mode SVD(HOSVD) of ${\displaystyle {\mathcal {A}}}$ is the decomposition$${\displaystyle {\mathcal {A}}={\mathcal {S}}\times ({\bf {U}}_{1},{\bf {U}}_{2},\ldots ,{\bf {U}}_{M}).}$$ The above construction shows that every tensor has a M-mode SVD(HOSVD).

As in the case of the compact singular value decomposition of a matrix, where the rows and columns corresponding to vanishing singular values are dropped, it is also possible to consider a compact M-mode SVD(HOSVD), which is very useful in applications.