Tensor decomposition
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 formula_1 is assumed to be given in coordinates with respect to some basis as a M-way array, also denoted by formula_2, where "M" is the number of modes and the order of the tensor. formula_3 is the complex numbers and it includes both the real numbers formula_4 and the pure imaginary numbers.
Let formula_5 denote the standard mode-"m" flattening of formula_1, so that the left index of formula_7 corresponds to the formula_8'th index formula_1 and the right index of formula_7 corresponds to all other indices of formula_1 combined. Let formula_12be a unitary matrix containing a basis of the left singular vectors of the formula_7 such that the "j"th column formula_14 of formula_15 corresponds to the "j"th largest singular value of formula_7. Observe that the mode/factor matrix formula_15 does not depend on the particular on the specific definition of the mode "m" flattening. By the properties of the multilinear multiplication, we haveformula_18where formula_19 denotes the conjugate transpose. The second equality is because the formula_15's are unitary matrices. Define now the core tensorformula_21Then, the HOSVD of formula_1 is the decompositionformula_23 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, where the rows and columns corresponding to vanishing singular values are dropped, it is also possible to consider a compact HOSVD, which is very useful in applications.
Assume that formula_24 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 formula_7 of formula_1. Let the columns of formula_15 be sorted such that the formula_28 th column formula_29 of formula_15 corresponds to the "formula_28"th largest nonzero singular value of formula_7. Since the columns of formula_15 form a basis for the image of formula_7, we haveformula_35where 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 formula_36, we find as before thatformula_37where the core tensor formula_38 is now of size formula_39.
Multilinear rank.
The multilinear rank of formula_1 is denoted with rank-formula_41. The multilinear rank is a tuple in formula_42 where formula_43. Not all tuples in formula_42 are multilinear ranks. The multilinear ranks are bounded by formula_45 and it satisfy the constraint formula_46 must hold.
The compact HOSVD is a rank-revealing decomposition 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 formula_47 be the multilinear rank of the tensor formula_1. Since formula_49 is a multidimensional array, we can expand it as followsformula_50where formula_51 is the formula_28th standard basis vector of formula_53. By definition of the multilinear multiplication, it holds thatformula_54where the formula_55 are the columns of formula_56. It is easy to verify that formula_57 is an orthonormal set of tensors. This means that the HOSVD can be interpreted as a way to express the tensor formula_1 with respect to a specifically chosen orthonormal basis formula_59 with the coefficients given as the multidimensional array formula_38.
Computation.
Let formula_61 be a tensor with a rank-formula_47, where formula_63 contains the reals formula_4 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.
Sources:
Interlacing computation.
A strategy that is significantly faster when some or all formula_71 consists of interlacing the computation of the core tensor and the factor matrices, as follows:
In-place computation.
The HOSVD can be computed "in-place" via the Fused In-place Sequentially Truncated Higher Order Singular Value Decomposition (FIST-HOSVD) algorithm by overwriting the original tensor by the HOSVD core tensor, significantly reducing the memory consumption of computing HOSVD.
Approximation.
In applications, such as those mentioned below, a common problem consists of approximating a given tensor formula_79 by one with a reduced multilinear rank. Formally, if the multilinear rank of formula_80 is denoted by formula_81, then computing the optimal formula_82 that approximates formula_80 for a given reduced formula_84 is a nonlinear non-convex formula_85-optimization problem
formula_86where formula_87 is the reduced multilinear rank with formula_88, and the norm formula_89 is the Frobenius norm.
A simple idea for trying to solve this optimization problem is to truncate the (compact) SVD in step 2 of either the classic or the interlaced computation. A classically truncated HOSVD is obtained by replacing step 2 in the classic computation by
while a sequentially truncated HOSVD (or successively truncated HOSVD) is obtained by replacing step 2 in the interlaced computation by
Applications.
The HOSVD is most commonly applied to the extraction of relevant information from multi-way arrays.
Starting in the early 2000s, Vasilescu addressed causal questions by reframing the data analysis, recognition and synthesis problems as multilinear tensor problems. The power of the tensor framework was showcased by decomposing and representing an image in terms of its causal factors of data formation, in the context of Human Motion Signatures for gait recognition, face recognition—TensorFaces and computer graphics—TensorTextures.
The HOSVD has been successfully applied to signal processing and big data, e.g., in genomic signal processing. These applications also inspired a higher-order GSVD (HO GSVD) and a tensor GSVD.
A combination of HOSVD and SVD also has been applied for real-time event detection from complex data streams (multivariate data with space and time dimensions) in disease surveillance.
It is also used in tensor product model transformation-based controller design.
The concept of HOSVD was carried over to functions by Baranyi and Yam via the TP model transformation. This extension led to the definition of the HOSVD-based canonical form of tensor product functions and Linear Parameter Varying system models and to convex hull manipulation based control optimization theory, see TP model transformation in control theories.
HOSVD was proposed to be applied to multi-view data analysis and was successfully applied to in silico drug discovery from gene expression.
Robust L1-norm variant.
L1-Tucker is the L1-norm-based, robust variant of Tucker decomposition. L1-HOSVD is the analogous of HOSVD for the solution to L1-Tucker.