Canonical Polyadic Decomposition (CPD)

CPD expresses an N-way tensor as a sum of R rank-one tensors. Each rank-one component is formed by the outer product of N factor vectors. For a 3D tensor X, this is: X ≈ Σᵣ aᵣ ∘ bᵣ ∘ cᵣ, where '∘' denotes the outer product. This structure is inherently multilinear, meaning the relationship between the tensor and each factor matrix is linear when the others are held fixed. The number of components R is the CP rank of the approximation.

A key theoretical advantage of CPD over other decompositions like Tucker is its property of essential uniqueness. Under mild conditions (e.g., sufficient rank R), the factor matrices are unique up to:

• Column scaling and permutation: The order of components can be changed, and factors can be rescaled as long as the product remains constant (e.g., scaling a column of factor matrix A by 2 while scaling the corresponding column of factor matrix B by 0.5).
• There is no rotational ambiguity, unlike in matrix factorizations. This makes CPD well-suited for blind source separation and interpretable factor analysis, where the goal is to recover underlying, meaningful components.

Fitting a CPD model is a non-convex optimization problem, typically solved using Alternating Least Squares (ALS) or gradient-based methods. Challenges include:

• Choosing the Rank (R): There is no direct algorithm to determine the true CP rank; it is often selected via heuristics or validation.
• Swamps and Degeneracy: Optimization can encounter slow convergence (swamps) or degenerate solutions where factor norms grow excessively while their product remains finite.
• Ill-Posedness for High Ranks: The best rank-R approximation may not exist (a tensor may be arbitrarily well approximated by a lower-rank tensor). Despite this, efficient algorithms like CP-ALS are widely used in practice.

CPD performs multilinear dimensionality reduction, capturing interactions across all modes (dimensions) simultaneously. This contrasts with linear methods like PCA or SVD applied to a flattened matrix, which lose multi-way structure. For example, in a user-item-time tensor, CPD can jointly factor users, items, and temporal patterns into latent factors. The compression is achieved because the number of parameters grows linearly with the number of modes and rank (O(R * Σ dimensions)), rather than exponentially with the size of the full tensor.

CPD is one of two primary tensor decomposition families:

• CPD / PARAFAC: Sum of rank-one tensors. Favored for its uniqueness and interpretability.
• Tucker Decomposition: Involves a core tensor multiplied by factor matrices. It is more flexible (allowing interaction between different components across modes) but lacks uniqueness without constraints. Higher-Order SVD (HOSVD) is a specific, constrained form of Tucker decomposition. CPD can be seen as a special case of Tucker where the core tensor is super-diagonal (non-zero only when all indices are equal).

CPD's uniqueness and multi-way modeling make it powerful for:

• Chemometrics: Analyzing fluorescence excitation-emission data to identify pure chemical components.
• Neuroimaging: Decomposing EEG/MEG data into spatial, temporal, and spectral components to isolate neural sources.
• Recommender Systems: Modeling user-item-context interactions for context-aware recommendations.
• Knowledge Graph Embeddings: Representing entities and relations as vectors (e.g., in the RESCAL model, a form of CPD).
• Signal Processing: Blind source separation of multi-channel audio or communications signals.

The CP rank of a tensor is the minimum number of rank-one tensors required to exactly represent it as their sum. This is the central concept CPD aims to discover. Unlike matrix rank, determining tensor rank is NP-hard, making CPD computation challenging. The rank defines the model's complexity and compression factor in applications like neural network layer factorization.

A more flexible tensor factorization than CPD. Tucker decomposition expresses a tensor as a core tensor multiplied by a factor matrix along each mode. Unlike CPD's sum of rank-one components, Tucker uses a multilinear product, allowing different numbers of factors per mode. It is a higher-order generalization of Singular Value Decomposition (SVD) and is foundational for Higher-Order SVD (HOSVD).

The predominant optimization algorithm for fitting a CPD model. ALS solves the non-convex factorization problem by:

• Fixing all but one factor matrix.
• Solving a linear least-squares problem for the remaining matrix.
• Alternating through each mode iteratively. While efficient, ALS can converge to local minima and may require regularization or careful initialization.

The fundamental matrix factorization underpinning many low-rank concepts. For a matrix M, SVD yields M = U Σ V^T, where U and V are orthogonal and Σ is diagonal with singular values. The Eckart–Young theorem proves truncated SVD provides the optimal low-rank matrix approximation. SVD is a two-dimensional (matrix) case, while CPD generalizes decomposition to higher-order tensors.

Historical synonyms for Canonical Polyadic Decomposition. PARAFAC (Parallel Factors) originated in psychometrics, while CANDECOMP (Canonical Decomposition) came from phonetics. All three terms—CPD, PARAFAC, CANDECOMP—refer to the same underlying mathematical model: expressing a tensor as a sum of rank-one components. The convergence of these independent discoveries highlights the method's fundamental utility.

The branch of algebra dealing with tensors (multi-way arrays). CPD is a core operation within multilinear algebra, which provides the notation and theoretical framework for tensor manipulations. Key concepts include:

• Mode-n product: Multiplying a tensor by a matrix along a specific dimension.
• Kruskal form: A concise notation for the CPD model.
• Uniqueness properties: Conditions under which CPD factors are unique up to scaling/permutation, a significant advantage over matrix decompositions.