Tensor rank - Ciallo Wiki

1 Introduction to Tensor Rank

Tensor rank quantifies how “simple” a tensor is in the sense of being expressible using a small number of elementary building blocks. In multilinear algebra, the fundamental objects are tensors—multidimensional arrays whose entries transform in structured ways under changes of coordinates. Unlike matrices, tensors admit several competing rank notions that differ by whether the representation must be exact or whether one may approach the tensor as a limit of simpler ones.

1.1 Tensors and rank-1 (simple) tensors

Let a tensor be an element of a product space such as \( \mathbb{F}^{n_1}\otimes \cdots \otimes \mathbb{F}^{n_d} \), where \(d\) is the order. A rank-1 (or simple) tensor is one that factors completely across modes: \[ x^{(1)}\otimes x^{(2)}\otimes \cdots \otimes x^{(d)}. \] This form captures separability: each mode contributes independently. Rank-1 tensors are the multilinear analogue of rank-1 matrices.

1.2 Canonical polyadic (CP) decomposition connection

A central motivation for defining tensor rank is the canonical polyadic (CP) decomposition (also called PARAFAC). It represents a tensor as a sum of rank-1 terms: \[ \mathcal{T}=\sum_{r=1}^{R} a_r^{(1)}\otimes a_r^{(2)}\otimes \cdots \otimes a_r^{(d)}. \] The smallest such number of summands \(R\) is one of the principal “rank” quantities associated with the tensor.

1.3 Exact rank versus approximation-based notions

Exact rank requires an equality representation by a finite sum of rank-1 tensors. However, many tensors cannot be represented with a small number of rank-1 terms without increasing \(R\). In practice and in theory, it is sometimes more natural to consider sequences of CP decompositions that approach the tensor arbitrarily well. This leads to approximation-based notions such as border rank, which capture how complex a tensor is “in the limit” rather than by exact expression.

2 Formal Definitions

Tensor rank becomes precise once the notion of “representation” is fixed. The definitions below formalize exact CP rank, limiting border rank, and the special relationship to matrix rank for order-2 tensors.

2.1 Rank as the minimal number of rank-1 terms (CP rank)

For a tensor \(\mathcal{T}\in \mathbb{F}^{n_1}\otimes \cdots \otimes \mathbb{F}^{n_d}\), the CP rank (often simply called tensor rank) is \[ \operatorname{rank}_{\mathrm{CP}}(\mathcal{T})=\min\left\{R:\mathcal{T}=\sum_{r=1}^{R} a_r^{(1)}\otimes \cdots \otimes a_r^{(d)}\right\}. \] This is the minimal number of rank-1 terms needed in an exact CP decomposition.

2.2 Border rank and limiting approximations

Border rank measures approximability by rank-\(R\) decompositions. One definition is: \[ \operatorname{brank}(\mathcal{T})=\min\left\{R:\mathcal{T}\ \text{lies in the closure of CP tensors of rank }R\right\}. \] Equivalently, \(\operatorname{brank}(\mathcal{T})\le R\) if there exists a sequence \(\mathcal{T}_k\) expressible with \(R\) rank-1 terms such that \(\mathcal{T}_k\to \mathcal{T}\). Border rank can be strictly smaller than CP rank, reflecting the existence of tensors that are limits of low-rank tensors but not themselves representable with the same number of terms.

2.3 Relation to matrix rank for order-2 tensors

When \(d=2\), a tensor is simply a matrix. Rank-1 tensors correspond to outer products \(u\otimes v\), and the minimal number of such terms equals the usual matrix rank. Therefore, for order-2 tensors, \[ \operatorname{rank}_{\mathrm{CP}}(\mathcal{T}) = \operatorname{rank}(\mathcal{T}) \] in the standard linear algebra sense.

3 Properties and Basic Results

The behavior of tensor rank depends strongly on order \(d\) and the underlying dimensions. Still, several basic properties are robust: invariance under basis changes, useful lower and upper bounds, and structural behavior of typical tensors.

3.1 Invariance under change of basis

Tensor rank is invariant under invertible linear transformations applied independently to each mode. If \(\mathcal{T}\) is mapped to \[ (\!A_1\otimes \cdots \otimes A_d)\mathcal{T} \] with each \(A_i\) invertible, then rank quantities such as CP rank and border rank do not change. Intuitively, a rank-1 decomposition remains a rank-1 decomposition under these mode-wise coordinate changes.

3.2 Rank bounds from dimensions and unfoldings

Direct computation of CP rank is difficult in general, so bounds are central. One standard technique uses unfoldings (matricizations). Reshaping a tensor into a matrix by grouping modes yields an induced matrix. Since any CP decomposition produces a corresponding decomposition for the unfolded matrix, the matrix rank of an unfolding provides a lower bound: \[ \operatorname{rank}_{\mathrm{matrix}}(\text{unfolding of }\mathcal{T}) \le \operatorname{rank}_{\mathrm{CP}}(\mathcal{T}). \] Different unfoldings can give different bounds.

3.3 Typical rank and generic behavior (informal discussion)

For large classes of tensors, the rank tends not to be small. Although exact “typical rank” statements depend on the field and dimensions, many results in algebraic geometry show that most tensors in a parameter space have rank equal to a characteristic value, and lower-rank tensors form lower-dimensional varieties. This means that small rank can be exceptional rather than typical.

3.4 Subadditivity and behavior under tensor sum

Tensor rank satisfies general inequalities under addition. While the rank of a sum can increase, one always has an upper bound based on the ranks of the addends: \[ \operatorname{rank}_{\mathrm{CP}}(\mathcal{S}+\mathcal{T}) \le \operatorname{rank}_{\mathrm{CP}}(\mathcal{S})+\operatorname{rank}_{\mathrm{CP}}(\mathcal{T}), \] since concatenating CP decompositions yields a valid (not necessarily minimal) CP representation. Border rank has analogous subadditivity properties in an approximate or closure sense, though the exact form can be more delicate.

4 Tensor Decomposition Methods

Because CP rank is hard to compute exactly, algorithms usually aim to find decompositions with a prescribed number of components and to fit parameters to data. The most widely used families rely on iterative optimization.

4.1 Alternating least squares (ALS) overview

ALS addresses the optimization problem associated with fitting a CP model. For an order-\(d\) tensor \(\mathcal{T}\), one seeks vectors (or factor matrices) \(a_r^{(i)}\) that minimize the discrepancy between \(\mathcal{T}\) and its CP reconstruction. ALS alternates updates: it fixes all factors except those for one mode, then solves a least-squares problem to update that mode’s factors. This cycling repeats until the fit stops improving.

4.2 Variants for constrained or regularized decompositions

Pure least-squares fitting can overfit or become unstable. Common variants introduce regularization terms (e.g., penalizing large norms), constraints (nonnegativity, sparsity), or structural restrictions (symmetry or sharing parameters across modes). These additions can improve interpretability and robustness, particularly in applications where factors represent physical quantities or latent features.

4.3 Initialization strategies and convergence considerations

ALS is nonconvex, so it may converge to local minima or saddle points. Initialization matters: random starts, spectral heuristics, or informed guesses derived from partial SVDs can substantially affect outcomes. Convergence is typically monitored via objective decrease, factor change, or reconstruction error. Even when the objective decreases, numerical issues can arise from scaling indeterminacies inherent in CP models.

4.4 Uniqueness and identifiability in practice

Even when a decomposition exists, one may ask whether it is essentially unique—up to permutation of components and rescaling. Identifiability depends on algebraic conditions relating factor ranks and dimensions. In practice, uniqueness supports the interpretation of recovered factors as meaningful latent components rather than artifacts of the optimization path.

5 Computational Aspects

Computation of tensor rank combines theoretical hardness with practical strategies that exploit relaxations, bounds, and numerical methods.

5.1 Hardness of exact tensor rank determination

Determining the exact CP rank is generally computationally intractable. The difficulty stems from the nonconvex nature of CP decompositions and the exponential growth of parameters with tensor order and dimension. As a result, research often focuses on approximation, bounds, or special cases where structure simplifies the problem.

5.2 Using flattenings for rank lower bounds

Flattening-based methods provide tractable lower bounds by converting the tensor-rank question into matrix rank computations. One computes matrix ranks of different unfoldings and uses them as constraints on the number of CP components. While useful, these bounds are not always tight; tensors can have low CP rank with higher unfolding ranks, and conversely unfoldings may not capture the true minimal number of components.

5.3 Rank upper bounds via explicit constructions

Upper bounds can be produced by exhibiting an explicit CP decomposition. Such constructions may come from:

known algebraic structures (e.g., polynomial or structured tensors),
symmetries that reduce the parameter count,
numerical decompositions with a chosen component number \(R\).

Even if the computed decomposition is not proven minimal, it certifies \(\operatorname{rank}_{\mathrm{CP}}(\mathcal{T})\le R\).

5.4 Numerical issues: ill-conditioning and scaling indeterminacies

CP models have inherent scaling freedoms: one can multiply a component vector in one mode by a scalar and compensate by dividing in another mode without changing the overall rank-1 term. Iterative algorithms can exploit this flexibility in numerically unstable ways, leading to large intermediate values and ill-conditioned least-squares subproblems. Regularization, normalization of factors, and robust stopping rules are common countermeasures.

6 Applications

Tensor rank and decompositions appear in diverse scientific and engineering contexts. The main theme is that a low-rank structure can reduce the number of parameters while preserving salient relationships across multiple modes of data.

6.1 Data compression and model simplification

A CP model with small rank can compress a high-dimensional dataset by storing only factor matrices rather than the full tensor. This reduces memory requirements and can accelerate downstream computation. In many pipelines, tensor rank serves as a proxy for the intrinsic degrees of freedom of the system being measured.

Multi-modal observations—such as time, sensor channel, and subject identity—can be organized as tensors. Decomposing them can separate latent factors that explain variation across each mode, producing features that are often more interpretable than those obtained by single-mode methods.

6.3 Parameter reduction in polynomial and multilinear models

Polynomials and multilinear maps can be represented or approximated using tensor decompositions. When the associated coefficient tensor has low rank, evaluation and learning tasks may be simplified. This can also help control overfitting by restricting the model to a low-complexity family.

6.4 Connections to latent-variable models

Low-rank tensor structure frequently corresponds to latent-variable assumptions, where observed quantities are generated by a small number of underlying components. In such settings, tensor decompositions can act as a method for recovering latent factors, supporting both prediction and interpretation.

Several closely connected concepts help bound tensor rank, enable alternative decompositions, or provide relaxations that make rank estimation more tractable.

7.1 Tensor flattenings and induced matrix ranks

Flattening (matricization) converts a tensor into a matrix by combining modes. The induced matrix rank is computationally accessible and supplies lower bounds for CP rank. Flattenings also allow the use of matrix tools—such as SVD and rank-revealing factorizations—as diagnostic instruments.

7.2 Tucker rank and multilinear ranks

Tucker decomposition expresses a tensor as a core tensor multiplied by factor matrices along each mode. The Tucker rank is the tuple of ranks of these factor matrices (multilinear ranks). Unlike CP rank, Tucker rank typically fits into a more balanced parameterization and can be easier to compute or control, though it measures a different notion of complexity.

7.3 Tensor nuclear norms and convex relaxations

Direct rank minimization is nonconvex. Convex relaxations often replace rank with norms designed to encourage low rank in the matrix or tensor setting. Various tensor nuclear norm surrogates exist, and they can be used in optimization problems where one prefers convex objectives with computable guarantees, at the cost of potentially looser approximations.

7.4 Strassen-style border rank intuition (high level)

Border rank can be understood through the idea of “degenerating” families of decompositions. Intuitively, some tensors behave as though they were generated by a small rank model, but only after allowing parameters to blow up or cancel in the limit. This intuition is related to classical phenomena where limiting behavior reveals structure not visible in exact finite representations.

8 Worked Examples

Concrete examples clarify how rank, unfoldings, and border rank differ, and how decompositions can be interpreted.

8.1 Order-3 tensors with small ranks

Consider an order-3 tensor built explicitly as a sum of a few rank-1 terms. One can directly verify that the CP rank is at most the number of summands by construction. Often, one checks whether fewer components suffice by comparing unfolding ranks or by attempting a smaller CP fit and observing inconsistency.

8.2 Rank checks via unfoldings

For a tensor \(\mathcal{T}\in \mathbb{F}^{n_1}\otimes \mathbb{F}^{n_2}\otimes \mathbb{F}^{n_3}\), unfolding into a matrix such as \((n_1)\times (n_2 n_3)\) yields a matrix rank lower bound. If this unfolding rank equals, say, \(R\), then CP rank cannot be smaller than \(R\). Using multiple unfoldings can tighten the bound by capturing different mode interactions.

8.3 Demonstrating difference between rank and border rank

To illustrate the gap, one can consider a tensor obtained as a limit of CP decompositions with \(R\) components, where the limiting tensor cannot be represented with \(R\) components exactly. In practice, numerical experiments may show convergence of a CP fit as iteration increases or parameters approach extremes, while exact reconstruction with \(R\) components remains impossible—manifesting the distinction between approximate and exact notions.

8.4 Interpreting a decomposition in an application context

Suppose a learned CP model yields factor vectors that align with known structure (e.g., components correlate with specific sensor groups or time patterns). The factors then serve as interpretable summaries of the data. The number of components provides a complexity measure: too few components underfit, while too many may capture noise or spurious effects.

9 Further Reading

Tensor rank sits at the intersection of multilinear algebra, algebraic geometry, and numerical computation. The topics below provide pathways into theory, surveys of methods, and practical tools.

9.1 Foundational references in multilinear algebra

Foundational texts cover tensors, multilinear maps, CP and Tucker decompositions, and the geometric viewpoint that underlies rank and border rank. These works establish the basic definitions and classical properties used across the literature.

9.2 Survey articles on tensor decompositions and rank

Surveys summarize known results about identifiability, typical behavior, bounds, and computational approaches. They also contrast CP and Tucker notions and discuss how flattenings and convex relaxations relate to rank questions.

9.3 Software and libraries for tensor rank experiments

Numerical libraries implement CP (and related) algorithms such as ALS and more advanced variants, supporting experimentation with rank approximations, model selection, and diagnostic checks like unfolding spectra. For serious rank studies, these tools are often paired with symbolic or algebraic computation packages for verification in small cases.