Higher-Order SVD (HOSVD)

HOSVD extends the classic matrix SVD to Nth-order tensors. Instead of two factor matrices (U, V) and a diagonal matrix of singular values (Σ), HOSVD decomposes a tensor into a core tensor and N orthogonal factor matrices—one for each mode (dimension) of the tensor. This provides a principled framework for analyzing interactions across multiple dimensions simultaneously.

The decomposition produces two key components:

• Factor Matrices: Each is an orthogonal matrix (U^(n)) containing the singular vectors for its corresponding mode. These are analogous to the left/right singular vectors in matrix SVD.
• Core Tensor: A smaller, dense tensor that captures the multilinear interactions between the different modes. It is generally not diagonal, unlike the Σ matrix in standard SVD, reflecting the more complex coupling in higher-order data. The model is: X ≈ G ×₁ U^(1) ×₂ U^(2) ... ×_N U^(N), where ×_n denotes the n-mode product.

A primary application is multilinear dimensionality reduction. By truncating (keeping only the top components of) the factor matrices and corresponding slices of the core tensor, a compressed, low-rank approximation of the original tensor is obtained. This drastically reduces storage and computational costs while preserving the most significant multilinear patterns, making it essential for compressing multi-dimensional model weights or data.

The factor matrices produced by HOSVD are orthogonal, meaning U^(n)ᵀU^(n) = I. This property ensures stability and ease of computation. However, unlike the matrix SVD which provides the optimal rank-R approximation (Eckart–Young theorem), the truncated HOSVD is not necessarily optimal for a given multilinear rank tuple. It serves as an excellent initialization for iterative algorithms like Alternating Least Squares (ALS) that seek the optimal Tucker decomposition.

HOSVD is computationally equivalent to the Tucker decomposition. While Tucker decomposition refers to the general factorization model, HOSVD specifically provides an algorithm to compute it by performing a standard matrix SVD on each mode-n flattened unfolding of the tensor to obtain the factor matrices, then calculating the core tensor. Thus, HOSVD is the standard method to compute the Tucker decomposition.

In on-device model compression, HOSVD is applied to the weight tensors of convolutional or fully connected layers. A 4D convolutional kernel tensor (output_channels × input_channels × height × width) can be decomposed via HOSVD, yielding a much smaller core tensor and factor matrices. This replaces a large parameter block with several smaller ones, reducing memory footprint and enabling faster inference through decomposed operations, especially on hardware with limited resources.

Tucker decomposition is the multilinear factorization framework for which HOSVD provides a specific, orthogonal solution. It expresses an N-dimensional tensor as a core tensor multiplied by a factor matrix along each of its modes (dimensions).

• Core Tensor: Captures the multilinear interactions between the components from each mode.
• Factor Matrices: Represent the principal components in each respective mode space.
• Relation to HOSVD: HOSVD computes the Tucker decomposition where the factor matrices are orthogonal, obtained via the SVD of each mode's matricization, and the core tensor is not diagonal, unlike in CP decomposition.

Canonical Polyadic Decomposition (CPD), also known as PARAFAC or CANDECOMP, is a competing tensor factorization model. It expresses a tensor as a sum of rank-one tensors, each formed by the outer product of vectors from each mode.

• Key Difference from Tucker/HOSVD: CPD uses a diagonal core tensor, meaning each component interacts only with itself across modes. This leads to a more parsimonious model but is often more computationally challenging to fit.
• Applications: Widely used in psychometrics, chemometrics, and for factor analysis of multi-way data where interpretable, independent components are desired.

Tensor-Train (TT) decomposition is a factorization format designed to mitigate the curse of dimensionality for high-order tensors. It represents a tensor as a sequence of 3D core tensors connected in a train-like structure.

• Structure: Each core tensor corresponds to a specific mode and is connected only to its immediate neighbors, drastically reducing the number of parameters from exponential to linear in the tensor order.
• Use Case: Particularly effective for representing very high-dimensional functions and operators, such as those in quantum physics or as replacements for fully-connected layers in neural networks (Tensor-Train Layers).

Singular Value Decomposition (SVD) is the fundamental matrix factorization that HOSVD generalizes to tensors. For a matrix (A \in \mathbb{R}^{m \times n}), SVD is (A = U \Sigma V^T).

• Components: (U) and (V) are orthogonal matrices containing the left and right singular vectors. (\Sigma) is a diagonal matrix of singular values, which indicate the importance of each corresponding vector pair.
• Foundation for HOSVD: HOSVD applies the SVD to each matricization (mode-unfolding) of the tensor. The factor matrices in HOSVD are the matrices of left singular vectors from these SVD operations.

Matricization, or tensor unfolding, is the critical operation that allows linear algebra methods like SVD to be applied to tensors. It reorders the elements of an N-way tensor into a matrix.

• Process: For a given mode (n), all fibers along that mode are aligned as columns (or rows) of a matrix. This matrix is denoted (A_{(n)}).
• Role in HOSVD: HOSVD is computed by performing SVD on the matricization (A_{(n)}) for every mode (n = 1,...,N). The left singular vectors from these SVDs become the orthogonal factor matrices of the decomposition.

The multilinear rank of a tensor is a tuple ((R_1, R_2, ..., R_N)) where (R_n) is the rank of the mode-(n) matricization (A_{(n)}). This is a core concept defining the complexity of a Tucker/HOSVD representation.

• Interpretation: Each (R_n) represents the dimensionality of the subspace needed to span the tensor's fibers in the (n)-th mode.
• Compression: In a truncated HOSVD, the multilinear rank is reduced by keeping only the leading (R_n) singular vectors for each mode, creating a low-rank approximation that compresses the original tensor data.