1 Definition and Basic Properties

1.1 Tensor rank and rank-one components

A tensor is a multi-dimensional array indexed by multiple modes (dimensions). A basic building block for many tensor decompositions is a rank-one tensor, formed as an outer product of vectors—one vector for each mode. The rank-related questions ask how many such simple components are required to reconstruct (exactly or approximately) a given tensor.

1.2 Formal definition of CP rank

Let \( \mathcal{X} \in \mathbb{F}^{I_1 \times \cdots \times I_N} \) be an order-\(N\) tensor over a field \(\mathbb{F}\) (typically \(\mathbb{R}\) or \(\mathbb{C}\)). A CP representation writes \(\mathcal{X}\) as a sum of \(R\) rank-one terms: \[ \mathcal{X}=\sum_{r=1}^{R}\lambda_r\, a^{(1)}_r \circ a^{(2)}_r \circ \cdots \circ a^{(N)}_r, \] where \(a^{(n)}_r \in \mathbb{F}^{I_n}\) and \(\circ\) denotes the outer product. The CP rank of \(\mathcal{X}\), denoted \(\operatorname{rank}_{\mathrm{CP}}(\mathcal{X})\), is the smallest \(R\) for which such an exact representation exists.

1.3 Relation to matrix rank (order-2 case)

For \(N=2\), a tensor is a matrix and the CP model reduces to a sum of outer products of vectors, equivalently a factorization into rank-one matrices. Therefore the CP rank coincides with the usual matrix rank. This is why CP rank is often described as a higher-order generalization of matrix rank.

1.4 Rank bounds and trivial examples

Several elementary bounds follow from dimension counts and structural constraints. For instance, if \(R\) is large enough, an exact representation always exists by taking a basis expansion across modes, but the resulting \(R\) may be far from minimal. Simple tensors formed by a single outer product have CP rank 1. More generally, a tensor whose decomposition uses exactly \(R\) rank-one terms has CP rank at most \(R\) by definition, with equality when no shorter sum exists.

2 CP Decompositions (CANDECOMP/PARAFAC)

2.1 CP representation and notation

The CANDECOMP/PARAFAC family of methods seeks a CP form for a tensor. In matrix form, one often collects the mode vectors into factor matrices: \[ A^{(n)}=[a^{(n)}_1\ \cdots\ a^{(n)}_R], \] so that the CP model can be expressed compactly in terms of these factors and weights \(\lambda_r\). A common convention absorbs weights into one factor matrix by scaling columns, since scaling can be redistributed across modes without changing the sum.

2.2 Uniqueness and scaling/permutation ambiguities

CP decompositions generally have non-uniqueness due to two unavoidable symmetries. First, columns can be permuted simultaneously across all factor matrices, producing the same tensor. Second, each rank-one term can be rescaled: multiplying a column in one factor by a constant and dividing another corresponding column in a different mode by the same constant leaves the outer product unchanged. As a result, “essential uniqueness” typically means uniqueness up to these scaling and permutation degrees of freedom.

2.3 Typical structure for factor matrices and weights

In practice, CP solutions are represented by factor matrices for each mode. The numerical values of the columns influence interpretability (e.g., latent components in machine learning) but also impact stability. Weight parameters \(\lambda_r\) are often optional depending on normalization choices; a typical approach normalizes columns of one factor matrix and transfers all remaining scale into the weights.

2.4 Exact vs. approximate CP decompositions

An exact CP decomposition matches the tensor entries (or a given operator acting on them) with zero error. Approximate CP decompositions target a small residual, often in a least-squares sense: \[

\min_{R,\{a^{(n)}_r\}} \left\|\mathcal{X}-\sum_{r=1}^R \lambda_r \, a^{(1)}_r\circ\cdots\circ a^{(N)}_r\right\|.

\] Approximation matters when data are noisy, incomplete, or when exact rank is difficult to obtain numerically.

2.5 Connection to multilinear models

CP decompositions provide a structured multilinear model: each mode contributes a set of latent factors, and the tensor is reconstructed by combining corresponding components across modes. This perspective links CP rank to low-dimensional representations and to parameter efficiency in applications such as system identification and embedding models.

3 Existence, Finiteness, and Computability

3.1 Existence of a CP decomposition of a given rank

Given an integer \(R\), the question “does there exist a CP decomposition with at most \(R\) components?” is an algebraic feasibility problem. One searches for factor vectors that satisfy a set of polynomial equations implied by matching tensor entries. Existence is guaranteed for some sufficiently large \(R\) by general construction arguments, but for minimal \(R\) the answer depends on the tensor’s structure.

3.2 When CP rank is finite

For real or complex tensors, CP rank is always finite: since tensors form finite-dimensional spaces, there exist decompositions with a finite number of rank-one terms. However, the minimal number—CP rank—can be difficult to determine and may be much larger than ranks suggested by intuition from low-order cases.

3.3 Decision vs. optimization formulations

Two related viewpoints appear in the literature. In decision form, one asks whether \(\operatorname{rank}_{\mathrm{CP}}(\mathcal{X}) \le R\). In optimization form, one minimizes a residual norm over all CP models with a specified number of components. Optimization may yield a best approximation even when an exact rank-\(R\) representation does not exist, reflecting subtle issues around limits of sequences of decompositions.

3.4 Computational complexity overview

Computing CP rank is generally hard. Even deciding whether a tensor has rank at most \(R\) can be computationally difficult as order and dimension increase. As a result, practical methods typically focus on constructing good decompositions for a chosen \(R\) rather than computing the provably minimal rank.

3.5 Numerical stability considerations

Estimating a CP decomposition involves nonconvex optimization in factor variables. Finite precision arithmetic can produce large cancellations or unstable scaling across modes, especially when components are near-degenerate. Stabilization strategies include normalization, regularization, and robust initialization, but they do not remove the intrinsic nonconvexity of the problem.

4 Algorithms for Estimating or Constructing CP Rank

4.1 Alternating least squares (ALS) intuition

A widely used approach is alternating least squares. For fixed factors in all but one mode, the remaining mode’s factor matrix can be updated by solving a linear least-squares problem. Then the algorithm cycles to the next mode. This reduces the original nonconvex problem to a sequence of convex subproblems, though the overall process can still converge to suboptimal stationary points.

4.2 Gradient-based methods

Gradient-based optimization treats CP fitting as differentiable with respect to factor entries (subject to the chosen loss function). Methods such as projected gradient variants (for constraints) or adaptive optimizers can handle large-scale problems, though they may be sensitive to learning rates and to the conditioning of the gradients. Like ALS, convergence is not guaranteed to the global optimum.

4.3 Rank-increment strategies (searching for minimal rank)

Because minimal CP rank is hard to compute directly, one often searches over \(R\). A typical workflow increases the number of components until the approximation error stops improving substantially or until the fitted model matches a target tolerance. This heuristic resembles model selection: it trades off expressive power against complexity.

4.4 Handling constraints and regularization

Real applications often require constraints on factors: nonnegativity, sparsity, smoothness, or bounds on entries. Regularization terms can discourage overfitting (e.g., penalizing large factor norms) and improve numerical conditioning. Constraints are typically enforced either by modifying the optimization step (e.g., nonnegativity via multiplicative updates or projections) or by using penalty terms.

4.5 Dealing with local minima and initialization

Both ALS and gradient methods may get trapped in local minima or saddle points. Initialization strategies include random starts, SVD-based heuristics for special cases, and careful scaling of factors. Multiple restarts and selection by best residual are common. Even then, degenerate solutions can appear when components collapse or when the model is overparameterized.

5 CP Rank and Approximation Theory

5.1 Best low-rank approximation vs. infimum

For a fixed \(R\), one considers minimizing the approximation error over all CP models with \(R\) components. The minimal achievable error may exist as an actual optimum, or one may only obtain an infimum approached by sequences of parameters without convergence. This distinction is central in tensor approximation theory, where limits can behave differently from the matrix case.

5.2 Error metrics (Frobenius norm and others)

The Frobenius norm is common because it yields a least-squares objective over all entries. Other choices include weighted losses (for missing data), masked norms, or metrics tailored to applications (e.g., relative error). The choice of norm affects both theoretical properties and how algorithms behave numerically.

5.3 Overfitting and underfitting in low-rank models

With too small \(R\), the model cannot represent the tensor’s structure, leading to underfitting (large residual error). With too large \(R\), the algorithm may match noise or artifacts, causing overfitting in predictive settings, especially under incomplete or noisy observations. Regularization and validation-based rank selection help mitigate these effects.

5.4 Model selection using rank

Rank selection aims to balance fit and complexity. Common criteria include validation error on held-out entries, penalized objectives (e.g., adding a complexity penalty), and criteria based on changes in residual as \(R\) grows. Because CP fitting is nonconvex and may have variability across runs, model selection often incorporates stability assessments.

5.5 Practical trade-offs between rank and accuracy

In computational pipelines, increasing \(R\) typically improves approximation quality but raises runtime and memory costs: factor matrices grow linearly with \(R\), and intermediate computations scale accordingly. Practical systems therefore use adaptive strategies—fit at a modest rank, then enlarge if justified by error reduction or by interpretability needs.

6 Identifiability and Generic Properties

6.1 Generic rank and “almost everywhere” behavior

Many identifiability results are stated for “generic” tensors, meaning the property holds for all tensors except those in a lower-dimensional exceptional set (in algebraic or measure-theoretic senses). Under generic conditions, the CP rank and the structure of decompositions exhibit more regular behavior than in worst-case or structured special cases.

6.2 Conditions for essential uniqueness

Essential uniqueness means that any CP decomposition with \(R\) components agrees with the original one up to scaling and permutation. Sufficient conditions depend on properties of the factor matrices, often measured through ranks of the factor matrices or their column “spread.” When these conditions hold, the decomposition becomes identifiable, enabling interpretation and reliable recovery from data.

6.3 Kruskal-type criteria (overview level)

A classic line of results uses Kruskal ranks—an index related to the maximal number of columns that are linearly independent in a specific combinatorial sense. Such criteria provide inequalities involving the Kruskal ranks of the factors across modes that guarantee essential uniqueness. While not necessary in general, these rules of thumb are widely referenced because they can be checked from estimated factors.

6.4 Effects of noise on identifiability

With noisy data, exact identifiability is replaced by approximate identifiability: multiple decompositions may fit within the noise level. Noise can also perturb Kruskal ranks and violate uniqueness conditions. Practical approaches therefore rely on robust loss functions, constraints, and diagnostic checks (e.g., examining residuals, component stability across restarts).

6.5 Impact of tensor dimensions on identifiability

As the number of modes and the sizes of dimensions change, identifiability conditions may become easier or harder to satisfy. Larger mode sizes can increase the flexibility of factors and potentially improve uniqueness, while imbalanced dimensions can lead to near-degeneracies. Dimensionality also affects the degrees of freedom of the CP model, influencing the balance between overparameterization and recoverability.

7 Special Cases and Examples

7.1 Small-dimensional tensors (order-3 and beyond)

For order-3 tensors, CP decompositions are often studied because they represent the simplest genuinely multilinear setting beyond matrices. Yet even in low order, the gap between CP rank and “intuitive” degrees of freedom can be significant. Worked examples commonly illustrate how the same tensor may admit multiple decompositions when uniqueness conditions fail.

7.2 Symmetric tensors and their CP rank

If a tensor is symmetric across modes, additional structure can be exploited. Symmetric CP decompositions use identical or appropriately constrained factor vectors across modes, often reducing the effective parameter space. The CP rank of a symmetric tensor can differ from the rank of an associated general tensor, and the relationship between symmetric and nonsymmetric decompositions is an area of study.

7.3 Sparse structure and structured low-rank

Tensors with sparse patterns (many zeros) may admit low CP rank, but sparsity can also create ambiguity and degeneracy in decomposition. Structured low-rank models may combine CP structure with sparsity-promoting regularization to recover interpretable components while maintaining computational tractability.

7.4 How CP rank changes under reshaping

Reshaping can change the problem. While matrix rank behaves predictably under certain algebraic transformations, CP rank depends on the chosen mode grouping because rank-one terms are defined with respect to the tensor’s mode structure. Consequently, reshaping into a different tensor order can increase or decrease the CP rank of the same underlying data array.

7.5 Worked toy examples (lightweight demonstrations)

Toy examples often choose tensors built from a known sum of a few outer products. These demonstrations show: (i) how the number of components corresponds to the rank when constructed exactly, (ii) how adding noise yields an approximate low-rank fit rather than an exact CP rank, and (iii) how algorithms can recover factors up to scaling and permutation when uniqueness conditions are satisfied.

8 Applications in Applied Mathematics and Beyond

8.1 Signal processing and multiway data

Many sensing systems produce multiway measurements: time-frequency-channel data, multi-sensor arrays, or spatiotemporal observations. CP models provide a compact representation by decomposing the signal into interpretable latent components across modes, such as shared temporal patterns and spatial signatures.

8.2 Machine learning: embeddings and feature learning

In machine learning, CP decompositions relate to representing higher-order interactions efficiently. Factor matrices define embeddings for entities or features, and the CP structure models how interactions combine across multiple modes. This viewpoint supports parameter reduction compared with fully connected tensor models.

8.3 Scientific computing: model reduction and system identification

In scientific workflows, large-scale dynamical or parameterized models can be approximated by low-rank tensor surrogates. CP representations can reduce storage and accelerate repeated evaluations, while also enabling system identification by fitting decompositions to observed responses.

8.4 Chemometrics and spectroscopy (overview)

Spectroscopic and chemical datasets are often naturally multiway, with samples, wavelengths, and experimental conditions forming tensor modes. CP decompositions can separate latent chemical contributions and yield compact models for calibration, classification, or denoising.

8.5 Recommender systems and interaction modeling

User-item interactions with additional context (time, location, item attributes) can be arranged as tensors of higher order. CP rank provides a mechanism for modeling multi-way relationships with a controlled number of latent factors, potentially improving generalization while reducing the parameter count.

9.1 Tucker rank vs. CP rank

Tucker decomposition represents a tensor using a core tensor multiplied by factor matrices along each mode. Tucker rank refers to the multilinear ranks of the core’s dimensions, while CP rank counts rank-one outer-product terms. These notions measure different kinds of low-complexity structure and are not directly comparable in general.

9.2 Border rank and approximation limits (overview)

Border rank refines CP rank by allowing limits of CP decompositions. A tensor may not have CP rank \(R\), yet it can be approximated arbitrarily well by tensors of CP rank \(R\). This phenomenon connects to the “best approximation vs. infimum” distinction and to instability in algorithms that approach degenerate solutions.

9.3 Tensor nuclear norms (conceptual comparison)

Tensor nuclear norms are attempts to generalize matrix nuclear norms to higher-order tensors. Unlike CP rank, these norms are often defined via convex or variational relaxations. They can be used as proxies for low-rank structure, though their relationship to CP rank depends on the chosen definition and may not align with CP rank exactly.

9.4 Multilinear rank and factorization differences

Multilinear rank captures the ranks of mode unfoldings under matricization, or equivalently the dimensions of the Tucker core along each mode. CP rank instead focuses on expressing the tensor as sums of rank-one outer products. The difference highlights that “low rank” can mean multiple structural properties.

9.5 “Tensor rank” in different conventions

In practice, “tensor rank” can refer to CP rank, tensor (n-mode) unfolding rank, multilinear rank, or ranks under other decomposition models. Conventions differ across fields, so specifying whether the definition is CP-based, Tucker-based, or unfolding-based is essential when comparing results.