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, [1] but it was L. R. Tucker who developed for third-order tensors the general Tucker decomposition in the 1960s, [2] [3] [4] further advocated by L. De Lathauwer et al. [5] 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. [6] [7] [8] Robust and L1-norm-based variants of HOSVD have also been proposed. [9] [10] [11] [12]
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 denote the standard mode-m flattening of , so that the left index of corresponds to the 'th index and the right index of corresponds to all other indices of combined. Let be a unitary matrix containing a basis of the left singular vectors of the 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 [5] of is the decomposition The above construction shows that every tensor has a 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 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 .
The multilinear rank [1] of is denoted with rank-. The multilinear rank is a tuple in where . Not all tuples in are multilinear ranks. [13] The multilinear ranks are bounded by and it satisfy the constraint must hold. [13]
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.
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 .
Let be a tensor with a rank-, where contains the reals as a subset.
The strategy for computing the Multilinear SVD and the M-mode SVD was introduced in the 1960s by L. R. Tucker, [3] further advocated by L. De Lathauwer et al., [5] and by Vasilescu and Terzopulous. [8] [6] 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 [6] [8] with the name M-mode SVD. It is a parallel computation that employs the matrix SVD to compute the orthonormal mode matrices.
A strategy that is significantly faster when some or all consists of interlacing the computation of the core tensor and the factor matrices, as follows: [14] [15] [16]
The HOSVD can be computed in-place via the Fused In-place Sequentially Truncated Higher Order Singular Value Decomposition (FIST-HOSVD) [16] algorithm by overwriting the original tensor by the HOSVD core tensor, significantly reducing the memory consumption of computing HOSVD.
In applications, such as those mentioned below, a common problem consists of approximating a given tensor by one with a reduced multilinear rank. Formally, if the multilinear rank of is denoted by , then computing the optimal that approximates for a given reduced is a nonlinear non-convex -optimization problem where is the reduced multilinear rank with , and the norm 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 classicallytruncated 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
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, [18] face recognition—TensorFaces [19] [20] and computer graphics—TensorTextures. [21]
The HOSVD has been successfully applied to signal processing and big data, e.g., in genomic signal processing. [22] [23] [24] These applications also inspired a higher-order GSVD (HO GSVD) [25] and a tensor GSVD. [26]
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. [27]
It is also used in tensor product model transformation-based controller design. [28] [29]
The concept of HOSVD was carried over to functions by Baranyi and Yam via the TP model transformation. [28] [29] This extension led to the definition of the HOSVD-based canonical form of tensor product functions and Linear Parameter Varying system models [30] 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 [31] and was successfully applied to in silico drug discovery from gene expression. [32]
L1-Tucker is the L1-norm-based, robust variant of Tucker decomposition. [10] [11] L1-HOSVD is the analogous of HOSVD for the solution to L1-Tucker. [10] [12]
In mathematics, a product is the result of multiplication, or an expression that identifies objects to be multiplied, called factors. For example, 21 is the product of 3 and 7, and is the product of and . When one factor is an integer, the product is called a multiple.
In mathematics, a tensor is an algebraic object that describes a multilinear relationship between sets of algebraic objects related to a vector space. Tensors may map between different objects such as vectors, scalars, and even other tensors. There are many types of tensors, including scalars and vectors, dual vectors, multilinear maps between vector spaces, and even some operations such as the dot product. Tensors are defined independent of any basis, although they are often referred to by their components in a basis related to a particular coordinate system; those components form an array, which can be thought of as a high-dimensional matrix.
In mathematics, the tensor product of two vector spaces V and W is a vector space to which is associated a bilinear map that maps a pair to an element of denoted .
In linear algebra, the singular value decomposition (SVD) is a factorization of a real or complex matrix into a rotation, followed by a rescaling followed by another rotation. It generalizes the eigendecomposition of a square normal matrix with an orthonormal eigenbasis to any matrix. It is related to the polar decomposition.
In mathematics, the exterior algebra or Grassmann algebra of a vector space is an associative algebra that contains which has a product, called exterior product or wedge product and denoted with , such that for every vector in The exterior algebra is named after Hermann Grassmann, and the names of the product come from the "wedge" symbol and the fact that the product of two elements of is "outside"
In mathematics, the Kronecker product, sometimes denoted by ⊗, is an operation on two matrices of arbitrary size resulting in a block matrix. It is a specialization of the tensor product from vectors to matrices and gives the matrix of the tensor product linear map with respect to a standard choice of basis. The Kronecker product is to be distinguished from the usual matrix multiplication, which is an entirely different operation. The Kronecker product is also sometimes called matrix direct product.
In abstract algebra and multilinear algebra, a multilinear form on a vector space over a field is a map
In mathematics, Hochschild homology (and cohomology) is a homology theory for associative algebras over rings. There is also a theory for Hochschild homology of certain functors. Hochschild cohomology was introduced by Gerhard Hochschild (1945) for algebras over a field, and extended to algebras over more general rings by Henri Cartan and Samuel Eilenberg (1956).
In multilinear algebra, the tensor rank decomposition or rank-R decomposition is the decomposition of a tensor as a sum of R rank-1 tensors, where R is minimal. Computing this decomposition is an open problem.
In multilinear algebra, a reshaping of tensors is any bijection between the set of indices of an order- tensor and the set of indices of an order- tensor, where . The use of indices presupposes tensors in coordinate representation with respect to a basis. The coordinate representation of a tensor can be regarded as a multi-dimensional array, and a bijection from one set of indices to another therefore amounts to a rearrangement of the array elements into an array of a different shape. Such a rearrangement constitutes a particular kind of linear map between the vector space of order- tensors and the vector space of order- tensors.
In mathematics, the tensor product (TP) model transformation was proposed by Baranyi and Yam as key concept for higher-order singular value decomposition of functions. It transforms a function into TP function form if such a transformation is possible. If an exact transformation is not possible, then the method determines a TP function that is an approximation of the given function. Hence, the TP model transformation can provide a trade-off between approximation accuracy and complexity.
Multilinear subspace learning is an approach for disentangling the causal factor of data formation and performing dimensionality reduction. The Dimensionality reduction can be performed on a data tensor that contains a collection of observations have been vectorized, or observations that are treated as matrices and concatenated into a data tensor. Here are some examples of data tensors whose observations are vectorized or whose observations are matrices concatenated into data tensor images (2D/3D), video sequences (3D/4D), and hyperspectral cubes (3D/4D).
Multilinear principal component analysis (MPCA) is a multilinear extension of principal component analysis (PCA) that is used to analyze M-way arrays, also informally referred to as "data tensors". M-way arrays may be modeled by linear tensor models, such as CANDECOMP/Parafac, or by multilinear tensor models, such as multilinear principal component analysis (MPCA) or multilinear independent component analysis (MICA). The origin of MPCA can be traced back to the tensor rank decomposition introduced by Frank Lauren Hitchcock in 1927; to the Tucker decomposition; and to Peter Kroonenberg's "3-mode PCA" work. In 2000, De Lathauwer et al. restated Tucker and Kroonenberg's work in clear and concise numerical computational terms in their SIAM paper entitled "Multilinear Singular Value Decomposition", (HOSVD) and in their paper "On the Best Rank-1 and Rank-(R1, R2, ..., RN ) Approximation of Higher-order Tensors".
Based on the key idea of higher-order singular value decomposition (HOSVD) in tensor algebra, Baranyi and Yam proposed the concept of HOSVD-based canonical form of TP functions and quasi-LPV system models. Szeidl et al. proved that the TP model transformation is capable of numerically reconstructing this canonical form.
In algebraic geometry, a derived scheme is a homotopy-theoretic generalization of a scheme in which classical commutative rings are replaced with derived versions such as cdgas, commutative simplicial rings, or commutative ring spectra.
Multiway data analysis is a method of analyzing large data sets by representing a collection of observations as a multiway array, . The proper choice of data organization into (C+1)-way array, and analysis techniques can reveal patterns in the underlying data undetected by other methods.
In multilinear algebra, applying a map that is the tensor product of linear maps to a tensor is called a multilinear multiplication.
In multilinear algebra, mode-m flattening, also known as matrixizing, matricizing, or unfolding, is an operation that reshapes a multi-way array into a matrix denoted by .
L1-norm principal component analysis (L1-PCA) is a general method for multivariate data analysis. L1-PCA is often preferred over standard L2-norm principal component analysis (PCA) when the analyzed data may contain outliers.
Tensor informally refers in machine learning to two different concepts that organize and represent data. Data may be organized in a multidimensional array (M-way array) that is informally referred to as a "data tensor"; however in the strict mathematical sense, a tensor is a multilinear mapping over a set of domain vector spaces to a range vector space. Observations, such as images, movies, volumes, sounds, and relationships among words and concepts, stored in an M-way array ("data tensor") may be analyzed either by artificial neural networks or tensor methods.