Higher-order singular value decomposition

In multilinear algebra, there does not exist a general decomposition method for multi-way arrays or "data-tensors" with all the properties of a matrix singular value decomposition (SVD). A matrix SVD simultaneously computes the orthonormal row/column matrices and a rank-R decomposition. These two properties can be captured by two different decompositions for multi-way arrays: one represents a tensor as the sum of rank-1 tensors (Candecomp–Parafac), while the other computes the othonormal spaces associated with the different axes (or modes) of a tensor. The latter decomposition has been known as a Tucker3, N-mode SVD and N-mode principal component analysis (PCA). It is also used in multilinear subspace learning as multilinear principal component analysis. This terminology was coined by P. Kroonenberg in the 1980s, but it was renamed by L. De Lathauwer to multilinear SVD and HOSVD (higher-order SVD).

History

In 1966, L. Tucker proposed a decomposition method for 3-way arrays (inappropriately referred to as a 3-mode "tensors") as a multidimensional extension of factor analysis. This decomposition was further developed in the 1980s by P. Kroonenberg, who coined the terms Tucker3, Tucker3ALS (an alternating least squares dimensionality reduction algorithm), 3-Mode SVD, and 3-Mode PCA. In the intervening years, several authors developed the decomposition for N-way arrays. Most recently, this work was treated in an elegant fashion and introduced to the SIAM community by L. De Lathauwer et al. who referred to the decomposition as an N-way SVD, multilinear SVD and HOSVD.

Definitions

Let the SVD of a real matrix be $A=USV^{T}$, then it can be written in an elementwise form as

$a_{i_{1},i_{2}}=\sum _{j_{1}}\sum _{j_{2}}s_{j_{1},j_{2}}u_{i_{1},j_{1}}v_{i_{2},j_{2}}.$

$U$ and $V$ give, in a certain sense optimal, orthonormal basis for the column and row space, $S$ is diagonal with decreasing elements. N-mode SVD can be defined by the multidimensional generalization of this concept:

$a_{i_{1},i_{2},\dots ,i_{N}}=\sum _{j_{1}}\sum _{j_{2}}\cdots \sum _{j_{N}}s_{j_{1},j_{2},\dots ,j_{N}}u_{i_{1},j_{1}}^{(1)}u_{i_{2},j_{2}}^{(2)}\dots u_{i_{N},j_{N}}^{(N)},$

where the $U^{(n)}=[u_{i,j}^{(n)}]_{I_{n}\times I_{n}}$ matrices and the ${\mathcal {S}}=[s_{j_{1},\dots ,j_{N}}]_{I_{1}\times I_{2}\times \cdots \times I_{N}}$ core tensor should satisfy certain requirements (similar ones to the matrix SVD), namely

• Each $U^{(n)}$ is an orthogonal matrix (called n-mode singular matrix).
• Two subtensors of the core tensor ${\mathcal {S}}$ are orthogonal i.e., $\langle {\mathcal {S}}_{i_{n}=p},{\mathcal {S}}_{i_{n}=q}\rangle =0$ if $p\neq q$.
• The subtensors in the core tensor ${\mathcal {S}}$ are ordered according to their Frobenius norm, i.e. $\|{\mathcal {S}}_{i_{n}=1}\|\geq \|{\mathcal {S}}_{i_{n}=2}\|\geq \dots \geq \|{\mathcal {S}}_{i_{n}=I_{n}}\|$ for n = 1, ..., N.

Notation:

${\mathcal {A}}={\mathcal {S}}\times _{n=1}^{N}U^{(n)}$

Algorithm

Tensor SVD can be built on SVD as follows:

Given a tensor, T of shape $d_{1}\times d_{2}\times \cdots \times d_{n}$, the i^th singular tensor is given by making a matrix,

$T_{(i)}$, the $d_{i}\times (\prod _{j\neq i}d_{j})$ matrix corresponding to $T$.

taking its left singular vectors, $U_{(i)}$.

The core tensor is then the tensor product of those $U_{(i)}$s.

Applications

Main applications are extracting relevant information from multi-way arrays. Used in factor analysis, face recognition (TensorFaces), human motion analysis and synthesis, and many other signal processing endeavours, such as Genomic Signal Processing.

It is also used in tensor product model transformation-based controller design. In multilinear subspace learning, it is modified to multilinear principal component analysis for gait recognition.