In multilinear algebra, the higher-order singular value decomposition (HOSVD) of a tensor is a specific orthogonal Tucker decomposition. It may be regarded as one type of generalization of the matrix singular value decomposition. It has applications in computer vision, computer graphics, machine learning, scientific computing, and signal processing. Some aspects can be traced as far back as F. L. Hitchcock in 1928, but it was L. R. Tucker who developed for third-order tensors the general Tucker decomposition in the 1960s, further advocated by L. De Lathauwer et al. in their Multilinear SVD work that employs the power method, or advocated by Vasilescu and Terzopoulos that developed M-mode SVD a parallel algorithm that employs the matrix SVD.
The term higher order singular value decomposition (HOSVD) was coined be DeLathauwer, but the algorithm referred to commonly in the literature as the HOSVD and attributed to either Tucker or DeLathauwer was developed by Vasilescu and Terzopoulos. Robust and L1-norm-based variants of HOSVD have also been proposed.
Definition
For the purpose of this article, the abstract tensor is assumed to be given in coordinates with respect to some basis as a M-way array, also denoted by , where M is the number of modes and the order of the tensor. is the complex numbers and it includes both the real numbers and the pure imaginary numbers.
Let be a unitary matrix containing a basis of the left singular vectors of the standard mode-m flattening of such that the jth column of corresponds to the jth largest singular value of . Observe that the mode/factor matrix does not depend on the particular on the specific definition of the mode m flattening. By the properties of the multilinear multiplication, we havewhere denotes the conjugate transpose. The second equality is because the 's are unitary matrices. Define now the core tensorThen, the HOSVD of is the decomposition The above construction shows that every tensor has a HOSVD.
Compact HOSVD
As in the case of the compact singular value decomposition of a matrix, it is also possible to consider a compact HOSVD, which is very useful in applications.
Assume that is a matrix with unitary columns containing a basis of the left singular vectors corresponding to the nonzero singular values of the standard factor-m flattening of . Let the columns of be sorted such that the th column of corresponds to the th largest nonzero singular value of . Since the columns of form a basis for the image of , we havewhere the first equality is due to the properties of orthogonal projections (in the Hermitian inner product) and the last equality is due to the properties of multilinear multiplication. As flattenings are bijective maps and the above formula is valid for all , we find as before thatwhere the core tensor is now of size .
Multilinear rank
The multilinear rank of is denoted with rank-. The multilinear rank is a tuple in where . Not all tuples in are multilinear ranks. The multilinear ranks are bounded by and it satisfy the constraint must hold.
The compact HOSVD is a rank-revealing deomposition in the sense that the dimensions of its core tensor correspond with the components of the multilinear rank of the tensor.
Interpretation
The following geometric interpretation is valid for both the full and compact HOSVD. Let be the multilinear rank of the tensor . Since is a multidimensional array, we can expand it as followswhere is the th standard basis vector of . By definition of the multilinear multiplication, it holds thatwhere the are the columns of . It is easy to verify that is an orthonormal set of tensors. This means that the HOSVD can be interpreted as a way to express the tensor with respect to a specifically chosen orthonormal basis with the coefficients given as the multidimensional array .
Computation
Let be a tensor with a rank-, where contains the reals as a subset.
Classic computation
The strategy for computing the Multilinear SVD and the M-mode SVD was introduced in the 1960s by L. R. Tucker, further advocated by L. De Lathauwer et al., and by Vasilescu and Terzopulous. The term HOSVD was coined by Lieven De Lathauwer, but the algorithm typically referred to in the literature as HOSVD was introduced by Vasilescu and Terzopoulos with the name M-mode SVD. It is a parallel computation that employs the matrix SVD to compute the orthonormal mode matrices.
M-mode SVD: For , do the following: Construct the mode-m flattening ; Compute the (compact) singular value decomposition , and store the left singular vectors ;
