Higher-order singular value 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 generalization of the matrix singular value decomposition. The HOSVD has applications in computer graphics, machine learning, scientific computing, and signal processing. Some key ingredients of the HOSVD 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, including the HOSVD. The HOSVD as decomposition in its own right was further advocated by L. De Lathauwer "et al." in 2000. Robust and L1-norm-based variants of HOSVD have also been proposed.
As the HOSVD was studied in many scientific fields, it is sometimes historically referred to as "multilinear singular value decomposition", "m-mode SVD", or "cube SVD," and sometimes it is incorrectly identified with a Tucker decomposition.
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 multidimensional array, also denoted by formula_1, in formula_3, where "d" is the order of the tensor and formula_4 is either formula_5 or formula_6.
Let formula_7be a unitary matrix containing a basis of the left singular vectors of the standard factor-"k" flattening formula_8 of formula_1 such that the "j"th column formula_10 of formula_11 corresponds to the "j"th largest singular value of formula_8. Observe that the factor matrix formula_11 does not depend on the particular freedom of choice in the definition of the standard factor-"k" flattening. By the properties of the multilinear multiplication, we haveformula_14where formula_15 denotes the conjugate transpose. The second equality is because the formula_11's are unitary matrices. Define now the core tensorformula_17Then, the HOSVD of formula_1 is the decompositionformula_19The 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 formula_20 is a matrix with unitary columns containing a basis of the left singular vectors corresponding to the nonzero singular values of the standard factor-"k" flattening formula_8 of formula_1. Let the columns of formula_11 be sorted such that the "j"th column formula_10 of formula_11 corresponds to the "j"th largest nonzero singular value of formula_8. Since the columns of formula_11 form a basis for the image of formula_8, we haveformula_29where 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_30, we find as before thatformula_31where the core tensor formula_32 is now of size formula_33.
Multilinear rank.
The tuple formula_34 where formula_35 is called the multilinear rank of formula_1. By definition, every tensor has a unique multilinear rank, and its components are bounded by formula_37. Not all tuples in formula_38 are multilinear ranks. In particular, it is known that formula_39 must hold.
The compact HOSVD is a rank-revealing factorization 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_40 be the multilinear rank of the tensor formula_1. Since formula_42 is a multidimensional array, we can expand it as followsformula_43where formula_44 is the "j"th standard basis vector of formula_45. By definition of the multilinear multiplication, it holds thatformula_46where the formula_10 are the columns of formula_20. It is easy to verify that formula_49 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_51 with the coefficients given as the multidimensional array formula_32.
Computation.
Let formula_53, where formula_4 is either formula_5 or formula_6, be a tensor of multilinear rank formula_40.
Classic computation.
The classic strategy for computing a compact HOSVD was introduced in 1966 by L. R. Tucker and further advocated by L. De Lathauwer "et al."; it is based on the definition of the decomposition. The next three steps are to be performed:
Interlaced computation.
A strategy that is significantly faster when some or all formula_64 consists of interlacing the computation of the core tensor and the factor matrices, as follows:
Approximation.
In applications, such as those mentioned below, a common problem consists of approximating a given tensor formula_72 by one of low multilinear rank. Formally, if formula_73 denotes the multilinear rank of formula_74, then the nonlinear non-convex formula_75-optimization problem isformula_76where formula_77 with formula_78, is a target multilinear rank that is assumed to be given, and where the norm is the Frobenius norm.
Based on the foregoing algorithms for computing a compact HOSVD, a natural 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
Unfortunately, neither of these strategies results in an optimal solution of the best low multilinear rank optimization problem, contrary to the matrix case where the Eckart-Young theorem holds. However, both the classically and sequentially truncated HOSVD result in a quasi-optimal solution: if formula_87 denotes the classically or sequentially truncated HOSVD and formula_88 denotes the optimal solution to the best low multilinear rank approximation problem, thenformula_89in practice this means that if there exists an optimal solution with a small error, then a truncated HOSVD will for many intended purposes also yield a sufficiently good solution.
Applications.
The HOSVD is most commonly applied to the extraction of relevant information from multi-way arrays.
Circa 2001, Vasilescu reframed the data analysis, recognition and synthesis problems as multilinear tensor problems based on the insight that most observed data are the result of several causal factors of data formation, and are well suited for multi-modal data tensor analysis. The power of the tensor framework was showcased in a visually and mathematically compelling manner by decomposing and representing an image in terms of its causal factors of data formation, in the context of Human Motion Signatures, 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. In multilinear subspace learning, it was applied to modeling tensor objects for gait recognition.
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.