Tensor Rank

The CP rank of a tensor is the smallest number of rank-one tensors whose sum exactly equals the original tensor. A rank-one tensor is the outer product of vectors. For a third-order tensor (\mathcal{X} \in \mathbb{R}^{I \times J \times K}), a rank-one component is (\mathbf{a} \circ \mathbf{b} \circ \mathbf{c}), where (\circ) denotes the outer product. Determining this minimum number is an NP-hard problem, distinguishing it from the straightforward matrix rank.

• Key Property: The CP decomposition is essentially unique under mild conditions, unlike other factorizations.
• Application: Directly minimizing the number of parameters in a weight tensor by approximating it with a low CP rank representation.

A tensor has multiple associated rank concepts. The multilinear rank (or Tucker rank) is a tuple ((R_1, R_2, ..., R_N)), where each (R_n) is the mode-n rank—the dimension of the vector space spanned by the mode-n fibers (columns).

• Mode-n Unfolding: To find (R_n), the tensor is flattened into a matrix along mode (n). (R_n) is the column rank of this matrix.
• Relation to CP Rank: The CP rank is always greater than or equal to the maximum value in the multilinear rank tuple. Optimizing for multilinear rank (via Tucker decomposition) is often more tractable than optimizing for CP rank.

Unlike matrices, which have a single fixed rank for a given size (except for measure-zero sets), tensors exhibit typical rank—the set of ranks occurring with positive probability. For real tensors, there can be multiple typical ranks.

• Example: For (2 \times 2 \times 2) real tensors, both 2 and 3 are typical ranks. A randomly generated tensor will have rank 2 with ~79% probability and rank 3 with ~21% probability.
• Generic Rank: The rank expected for a randomly generated tensor over an algebraically closed field (like complex numbers). This is usually a single value and is often the minimum typical rank over the reals.

A tensor may have a border rank that is strictly lower than its exact CP rank. This means the tensor can be approximated arbitrarily well by a sequence of tensors of lower rank, even if it cannot be expressed exactly at that rank.

• Implication: An approximation with rank (r) might achieve near-zero error, suggesting practical low-rank approximations can exist even when the theoretical minimum exact rank is high.
• Computational Challenge: The existence of border rank makes finding the true CP rank even more difficult, as algebraic methods must distinguish between exact and approximate decomposition.

In low-rank factorization for neural network compression, a large weight matrix (W \in \mathbb{R}^{m \times n}) (a 2nd-order tensor) is replaced by the product of two smaller matrices (W \approx UV^T), where (U \in \mathbb{R}^{m \times r}, V \in \mathbb{R}^{n \times r}), and (r) is the chosen rank.

• Parameter Reduction: Original parameters: (m \times n). After factorization: (r(m + n)). Savings are significant when (r \ll \min(m, n)).
• For Higher-Order Tensors: Convolutional layers can be treated as 4th-order tensors ([output_channels, input_channels, height, width]). Applying CP or Tucker decomposition directly to this tensor can yield extreme compression by exploiting multi-dimensional structure.

Determining the CP rank of a specific tensor is computationally challenging. Key problems are:

• Rank Calculation: Proving a given decomposition is of minimal rank is NP-hard.
• Best Low-Rank Approximation: For a fixed rank (r), finding the optimal CP approximation is often ill-posed; the best approximation may not exist due to border rank, and alternating least squares (ALS) algorithms can converge to degenerate local minima.
• Practical Approach: In machine learning, the target rank (r) is typically a hyperparameter chosen via validation, balancing compression ratio against accuracy drop. Algorithms like ALS or gradient-based methods are used to fit the factor matrices for the chosen (r).

Canonical Polyadic Decomposition (CPD), also known as PARAFAC or CANDECOMP, is the factorization method that directly defines the CP rank. It expresses a given tensor as a sum of rank-one tensors. Each rank-one component is the outer product of vectors from factor matrices corresponding to each mode (dimension) of the tensor.

• Core Concept: The minimum number of terms in this sum is the tensor's CP rank.
• Application: Used in chemometrics, signal processing, and for compressing neural network layers where a weight tensor is approximated by a low-CP-rank decomposition.

Tucker decomposition is a higher-order generalization of singular value decomposition (SVD) for tensors. It factorizes a tensor into a core tensor (which can be dense or sparse) multiplied by a factor matrix along each of its modes.

• Key Difference from CP: Unlike CPD, Tucker allows interactions between all components via the core tensor, offering a more flexible but often larger representation.
• Multilinear Rank: Defined by the ranks of the factor matrices, forming a tuple known as the multilinear rank. This is distinct from the CP rank.
• Use Case: Common in compression techniques like Tucker-format compression for convolutional neural network kernels.

Tensor-train decomposition (TT-decomposition) is a factorization format designed to mitigate the curse of dimensionality. It represents a high-order tensor as a sequence of interconnected lower-order core tensors.

• Structure: A d-dimensional tensor is represented by d core tensors, where each core is connected to its neighbors by specific contraction indices (TT-ranks).
• Storage Efficiency: Total storage scales linearly with the number of dimensions, unlike the exponential scaling of the original tensor.
• Application: Highly effective for compressing fully connected layers in neural networks by treating the weight matrix as a reshaped tensor.

Singular Value Decomposition (SVD) is the foundational matrix factorization from which many tensor concepts are generalized. For any matrix (A \in \mathbb{R}^{m \times n}), SVD provides a factorization (A = U \Sigma V^T), where (U) and (V) are orthogonal matrices and (\Sigma) is a diagonal matrix of singular values.

• Matrix Rank: The number of non-zero singular values equals the matrix rank.
• Low-Rank Approximation: The Eckart–Young theorem proves that the best rank-k approximation (in Frobenius norm) is obtained by truncating the SVD to the k largest singular values.
• Foundation: SVD is the basis for Truncated SVD, a primary technique for compressing linear layers in neural networks.

The nuclear norm (or trace norm) of a matrix is the sum of its singular values. It serves as the convex envelope of the matrix rank function over the unit ball of the spectral norm, making it a critical tool in optimization.

• Role in Optimization: Because rank minimization is NP-hard, the nuclear norm is used as a convex surrogate to encourage low-rank solutions in problems like matrix completion and robust PCA.
• Regularization: Adding a nuclear norm penalty to a loss function promotes factorized, low-rank weight matrices during model training or compression.
• Connection: For tensors, various tensor nuclear norms can be defined, though the theory is more complex than for matrices.

The multilinear rank of a tensor is a tuple of ranks, one for each mode, obtained by considering the matrix rank of the tensor's mode-n unfoldings (matricizations). It is a different and often more tractable concept than the CP rank.

• Definition: For a d-way tensor, the multilinear rank is ((r_1, r_2, ..., r_d)), where (r_n) is the rank of the matrix formed by unfolding the tensor along mode n.
• Tucker Connection: The Tucker decomposition explicitly targets and reveals the multilinear rank via its factor matrices and core tensor.
• Practicality: Determining the multilinear rank is computationally easier than determining the CP rank, making it central to algorithms like Higher-Order SVD (HOSVD).