In two-dimensional data analysis, the concept of matrix rank is exceptionally well-behaved. If you want to find the best low-rank approximation of a matrix, you compute its Singular Value Decomposition (SVD) and truncate the smallest singular values. If you want to recover a missing matrix under a low-rank constraint, you can relax the non-convex rank function to the convex nuclear norm, which can be solved efficiently in polynomial time.
As soon as you extend your data structure to three or more dimensions—moving from matrices to tensors—this mathematical paradise collapses. As surveyed by Bader et al. and Mandic et al., determining the canonical rank of a higher-order tensor is an NP-hard problem. This computational intractability is not just a theoretical curiosity; it introduces a fundamental bottleneck across machine learning, signal processing, and data recovery, forcing a complete reimagining of how we exploit multi-dimensional structures.
Why Tensor Rank is Geometrically Hard
To understand why tensor rank is so difficult to compute, we must look at how the geometric properties of linear algebra break down in multilinear algebra.
In a matrix, a rank-$r$ representation is a sum of $r$ orthogonal rank-one components. These components are nested: the optimal rank-1 approximation is always a subset of the optimal rank-2 approximation. Furthermore, the space of matrices of a given rank is closed, meaning a sequence of rank-$r$ matrices will always converge to a matrix of rank $r$ or less.
Tensors obey none of these rules. In the canonical polyadic (CP) decomposition—which defines tensor rank as the minimum number of rank-one tensors needed to sum to the target tensor—the components do not have to be orthogonal. This leads to several mathematical pathologies:
- Non-nestedness: The best rank-1 approximation of a tensor is generally not part of its best rank-2 approximation.
- Ill-posedness: The space of tensors of a given rank is not closed. You can have a sequence of rank-2 tensors that converges to a rank-3 tensor, meaning the optimal low-rank approximation might not even exist.
- Spectral Intractability: Finding even the single best rank-one component of a tensor (Tensor PCA) is NP-hard in the worst case, as detailed by Richard et al.. Tensors lack easily computable spectral properties, and determining tensor eigenvalues is computationally expensive (Ouerfelli et al.).
This complexity is so deep-seated that Ji et al. even leverage the hardness of deciding tensor equivalence (the tensor isomorphism problem) as a core primitive for post-quantum cryptography.
The Failure of Naive Convex Relaxations
For matrices, the standard workaround for NP-hard rank minimization is to use the nuclear norm (the sum of singular values) as a convex surrogate. For tensors, researchers initially attempted to replicate this success by flattening or "unfolding" the tensor along each of its modes into large matrices, and then minimizing the sum of the nuclear norms (SNN) of these matricizations.
However, this naive relaxation introduces severe statistical inefficiencies. Mu et al. demonstrated that the SNN approach is fundamentally limited when dealing with low-order tensors (such as 3-way arrays). Unfolding a balanced $d \times d \times d$ tensor yields an unbalanced $d \times d^2$ matrix. The nuclear norm of such an unbalanced matrix fails to tightly constrain the tensor's true degrees of freedom, meaning the algorithm requires an unnecessarily large number of data samples to achieve accurate recovery.
To bypass this, Mu et al. introduced "Square Reshaping," a method that groups tensor modes to create more balanced matrices, drastically reducing the sample complexity required for tensor recovery. Other approaches, such as the subspace norm proposed by Zheng et al., attempt to bridge the gap by interpolating between fast-but-loose convex relaxations and accurate-but-intractable non-convex formulations.
Canonical CP Rank (NP-Hard)
│
├──► Strategy 1: Matrix Unfolding (e.g., SNN) ──► Suboptimal sample complexity due to unbalanced dimensions
│
├──► Strategy 2: Alternative Ranks ───────────► Tucker Rank (ScaledGD) or Tubal Rank (t-SVD)
│
└──► Strategy 3: Non-Convex Optimization ─────► Embrace rugged landscape via Implicit Regularization or Orthogonalized ALS
Redefining Rank: Tractable Tensor Formats
Because the canonical CP rank is computationally intractable, a major direction in modern tensor research is to change the definition of rank entirely, opting for alternative tensor formats that admit polynomial-time algorithms while still capturing multi-way correlations.
The Tucker Format and ScaledGD
The Tucker decomposition can be thought of as a principal component analysis for tensors, decomposing an array into a smaller "core tensor" multiplied by a factor matrix along each mode. While calculating the exact Tucker rank remains challenging, its optimization landscape is much more manageable than CP. Tong et al. demonstrated that by using a preconditioned non-convex gradient descent algorithm called ScaledGD, one can achieve provable, statistically near-optimal low-rank tensor completion in linear time, completely independent of the tensor's condition number.
The Tensor-SVD (t-SVD) and Tubal Rank
A more radical algebraic workaround is the tensor-SVD (t-SVD) framework. Designed primarily for 3D tensors, t-SVD treats the tensor as a matrix of "tubes" (vectors along the third dimension) and defines tensor multiplication via circular convolution. This allows operations to be mapped into the Fourier domain, where the tensor splits into a series of independent matrix operations.
The resulting metric, known as tubal rank, avoids the mathematical pathologies of CP rank entirely. As proven by Zhang et al., Lu, and Ng, the tensor nuclear norm derived from t-SVD is fully convex. It yields exact, order-optimal recovery guarantees for tensor completion and Tensor Robust Principal Component Analysis (TRPCA) without requiring expensive or heuristic approximations.
Navigating the Non-Convex Landscape
Rather than relaxing the problem or changing the format, another school of thought embraces the non-convexity of CP decomposition directly. The traditional workhorse for this is Alternating Least Squares (ALS), which updates one factor matrix while keeping the others fixed. However, because the underlying problem is NP-hard, standard ALS frequently gets trapped in local optima.
To prevent this, Sharan introduced Orthogonalized ALS, which injects a periodic orthogonalization step into the optimization loop, forcing the algorithm out of local traps and ensuring reliable convergence even in the presence of noise.
Surprisingly, despite the worst-case NP-hardness, simple non-convex algorithms often perform remarkably well in practice. Theoretical insights explain this paradox through two mechanisms:
- Benign Optimization Landscapes: Kileel et al. provided a landscape analysis for an improved power method, proving that under mild conditions, the optimization landscape becomes "clean"—meaning all high-value local maxima correspond exactly to the true underlying tensor components.
- Implicit Regularization: Razin et al. proved that gradient descent applied to an unconstrained tensor factorization exhibits an implicit regularization effect. Much like in deep learning, the optimization path naturally and greedily prioritizes low-rank solutions, explaining why non-convex gradient flow can successfully generalize on structured datasets despite the lack of explicit constraints.
Exceptions and Frontiers
The rule of tensor NP-hardness does have fascinating exceptions. Huang et al. proved that if you evaluate a nonnegative tensor using Kullback-Leibler (KL) divergence rather than standard Euclidean square loss, finding the rank-one principal component is not NP-hard and can be solved exactly in closed form.
Where classical algorithms hit an absolute wall—such as in discrete Boolean tensor networks—researchers are shifting toward alternative computing paradigms. Pelofske et al. demonstrated that mapping Boolean tensor decompositions to quantum annealers allows classical combinatorial bottlenecks to be bypassed, while Tresp et al. utilize quantum SVD algorithms to accelerate tensor operations on massive knowledge graphs.
Ultimately, the field of tensor decomposition is defined by this tension: while multi-way arrays offer unparalleled expressive power, their inherent NP-hardness requires a careful balancing act between algebraic definitions, statistical efficiency, and optimization landscapes.
Key Foundational Work
Most Tensor Problems Are NP-Hard (2009) — contributed 4 concept elements to this direction.
Tensor Decompositions and Applications (2009) — contributed 2 concept elements to this direction.