Tucker Decomposition

Unlike matrix factorization, Tucker decomposition captures interactions across multiple modes (dimensions) simultaneously. A tensor X of size I₁ × I₂ × ... × I_N is decomposed into a core tensor G of size R₁ × R₂ × ... × R_N and a set of factor matrices A⁽ⁿ⁾ for each mode n. The model is expressed as:

X ≈ G ×₁ A⁽¹⁾ ×₂ A⁽²⁾ × ... ×_N A⁽ᴺ⁾

where ×_n denotes the n-mode product. The factor matrices are typically orthogonal and contain the principal components for each mode, while the core tensor governs the interaction strength between these components.

The core tensor's dimensions (R₁, R₂, ..., R_N) are the Tucker ranks or multilinear ranks. Each R_n can be independently chosen and is less than or equal to the original dimension I_n. This allows for:

• Asymmetric compression: Different levels of reduction per mode based on data intrinsic dimensionality.
• Controlled approximation: The full tensor has ∏ I_n elements, while the compressed representation has ∏ R_n + Σ(I_n × R_n) elements. For large tensors, choosing R_n << I_n leads to massive parameter reduction.
• The optimal low-rank approximation in the Frobenius norm is given by the Higher-Order SVD (HOSVD), which truncates the factor matrices and core tensor.

The core tensor is the compressed, latent representation of the original data. Its entries indicate the magnitude of interaction between the components (columns) of the different factor matrices.

• A dense core tensor allows any factor in one mode to interact with any factor in another, providing full expressivity but at a cost of ∏ R_n parameters.
• If the core tensor is super-diagonal (non-zero only when all indices are equal), the Tucker model reduces to Canonical Polyadic Decomposition (CPD).
• The core's size determines the trade-off between compression ratio and reconstruction fidelity. In deep learning, a Tucker-decomposed layer replaces a large weight tensor with this smaller core and factor matrices, drastically reducing FLOPs.

The Higher-Order SVD (HOSVD) is a specific, computationally efficient algorithm to compute a Tucker decomposition.

1. Unfolding: For each mode n, the tensor is unfolded into a matrix.
2. SVD: The left singular vectors of this matrix form the factor matrix A⁽ⁿ⁾.
3. Core Calculation: The core tensor is computed as G = X ×₁ A⁽¹⁾ᵀ ×₂ A⁽²⁾ᵀ × ... ×_N A⁽ᴺ⁾ᵀ. HOSVD provides a good initial approximation but is not optimal in the least-squares sense. It is often followed by Alternating Least Squares (ALS) refinement (Tucker-ALS) to minimize the reconstruction error ‖X - Ĝ‖².

Tucker decomposition is a powerful tool for neural network compression, particularly for layers with high-dimensional weight tensors (e.g., convolutional and fully connected layers).

• Convolutional Layer Compression: A 4D kernel tensor (output_ch × input_ch × height × width) can be Tucker-decomposed. Common strategies include compressing the input/output channel modes, reducing the kernel from ~I×O×H×W to a core of size R_I×R_O×H×W and two factor matrices.
• Parameter Reduction: Leads to significant reductions in model size and inference time. For example, applying Tucker decomposition to VGG-16 can achieve ~3x compression with <1% accuracy drop.
• Co-design with Hardware: The resulting structure of smaller dense operations (factor matrix multiplies and small convolutions on the core) is highly amenable to acceleration on modern NPUs and GPUs.

While powerful, Tucker decomposition presents unique computational challenges:

• Exponential Core Growth: The number of parameters in the core tensor grows exponentially with the tensor order N (∏ R_n). This curse of dimensionality limits its direct application to very high-order tensors.
• Choice of Ranks: Selecting the optimal multilinear ranks (R₁, ..., R_N) is a non-trivial model selection problem, often addressed via heuristics, validation, or rank adaptation algorithms.
• Alternative Formats: For very high-order data, the Tensor-Train (TT) decomposition is often preferred as it avoids the large core by representing the tensor as a chain of 3D core tensors, leading to linear scaling in N.
• Despite these challenges, for low-order tensors (N=3,4,5) common in machine learning, Tucker offers an excellent balance of expressivity and compression.

Higher-Order SVD (HOSVD) is the specific algorithm that computes the Tucker decomposition. It is a multilinear generalization of the matrix SVD. The process involves:

• Flattening the tensor along each mode to create a series of matrix "unfoldings."
• Performing a standard Singular Value Decomposition (SVD) on each of these matrix unfoldings to obtain the orthogonal factor matrices.
• Forming the core tensor by projecting the original tensor onto the subspace defined by these factor matrices. HOSVD provides a computationally tractable way to obtain a Tucker decomposition, though it does not necessarily yield the optimal decomposition for a given core size.

Canonical Polyadic Decomposition (CPD), also known as PARAFAC, is a fundamental and constrained alternative to Tucker decomposition for tensors. Key differentiators include:

• It expresses a tensor as a sum of rank-one tensors, each formed by the outer product of vectors from each mode.
• Unlike Tucker, it uses a diagonal core tensor, meaning interactions are only between corresponding components across modes.
• This results in a more parsimonious (often more compressed) representation but can be numerically unstable and harder to compute.
• CPD is widely used in chemometrics and signal processing where the underlying factors are assumed to be non-mixing.

Tensor-Train Decomposition is a factorization format designed to combat the curse of dimensionality for very high-order tensors. It represents an N-dimensional tensor as a sequence of 3D core tensors.

• Each core is connected to its neighbors via contracted indices, forming a train-like chain.
• The storage requirement scales linearly with the number of dimensions, unlike the exponential scaling of a full tensor.
• While Tucker is effective for low-order tensors (e.g., 3D or 4D), Tensor-Train is preferred for compressing the weight tensors of deep neural networks, which can be reformulated as very high-dimensional arrays.

Singular Value Decomposition (SVD) is the foundational matrix factorization upon which Tucker decomposition is built. For a matrix (A \in \mathbb{R}^{m \times n}), SVD is (A = U \Sigma V^T).

• (U) and (V) are orthogonal factor matrices containing left and right singular vectors.
• (\Sigma) is a diagonal matrix of singular values (analogous to a 2D core tensor).
• Truncated SVD, which keeps only the top-k singular values/vectors, is the direct 2D equivalent of using a Tucker decomposition for compression. Tucker generalizes this structure to N dimensions, replacing the diagonal core with a full (but small) N-dimensional core tensor.

Alternating Least Squares (ALS) is the dominant optimization algorithm for computing tensor decompositions like Tucker and CPD when a perfect factorization does not exist. The procedure is:

1. Initialize factor matrices and the core tensor randomly.
2. Alternate by fixing all but one factor (or the core) and solving a linear least-squares problem to update the free component.
3. Iterate until convergence. For Tucker decomposition, this is often called the Tucker-ALS algorithm. It is more flexible than HOSVD and can achieve a better fit for a given core size, but it is iterative and computationally heavier.

The multilinear rank of a tensor is the tuple of the ranks of its mode unfoldings. For a 3D tensor, it is a triplet ((R_1, R_2, R_3)).

• This is a core concept in Tucker decomposition, as the dimensions of the core tensor are exactly the multilinear rank.
• It is distinct from the CP rank (the minimum number of rank-one components).
• Choosing the multilinear rank is a critical compression hyperparameter: a smaller rank yields greater compression but higher approximation error. Determining the optimal rank often involves analyzing the singular value decay in each mode's unfolding.