When we model data using matrices, we face a fundamental geometric boundary: the rank of a matrix cannot exceed its physical dimensions. If a data matrix $M \in \mathbb{R}^{d \times d}$ is formed by a combination of $r$ latent factors, and $r > d$, the individual factors become linearly dependent. Consequently, we lose the ability to uniquely identify them; infinitely many combinations of vectors can produce the exact same matrix.
Tensors break this dimensionality barrier. A third-order tensor $T \in \mathbb{R}^{d \times d \times d}$ can be uniquely decomposed into a sum of $r$ rank-one components—written as $T = \sum_{i=1}^r u_i \otimes v_i \otimes w_i$—even when the number of components $r$ is significantly larger than the dimension $d$. This is known as the overcomplete regime.
The mathematical promise of overcomplete tensors is vast: they allow us to isolate more hidden features, topics, or signals than we have dimensions of observation. However, turning this theoretical uniqueness into practical algorithms has historically run into a severe computational bottleneck.
The Flattening Bottleneck: Why Standard Linear Algebra Fails
The standard toolkit of data science relies heavily on matrix operations like the Singular Value Decomposition (SVD). To apply these tools to a tensor, the intuitive first step is to "unfold" or flatten the multi-dimensional array into a large matrix. For instance, a $d \times d \times d$ tensor can be reshaped into a highly unbalanced $d \times d^2$ matrix.
As Ge et al. demonstrated, this flattening operation destroys the very multi-way structural dependencies that make overcomplete recovery possible. A $d \times d^2$ matrix has a maximum row rank of $d$. If the underlying tensor has a rank $r > d$, the flattened matrix completely obscures the higher-rank signal, rendering it mathematically impossible to certify or extract the original components using standard matrix factorization.
This created a frustrating paradox outlined by Bhaskara et al.: while information theory guarantees that an overcomplete tensor's decomposition is unique up to a threshold of $r \approx d^{1.5}$, classical polynomial-time algorithms remained strictly trapped in the undercomplete regime where $r \le d$.
Tensor (d x d x d) ───Flattening───► Unbalanced Matrix (d x d²)
[Unique if r > d] [Rank capped at d: Signal Lost]
Bridging the Gap with Sum-of-Squares
To extract components when $r > d$, algorithms must exploit the tensor's global algebraic structure without collapsing it into a standard matrix. The first major breakthrough to achieve this in polynomial time utilized the Sum-of-Squares (SoS) hierarchy.
Work by Barak et al. and Ma et al. reframed tensor decomposition as a continuous optimization problem over a sphere. Instead of searching for components greedily, the SoS framework constructs a sequence of increasingly powerful semidefinite programming (SDP) relaxations.
The intuition behind why SoS succeeds where SVD fails lies in its ability to inspect higher-order polynomial constraints. By evaluating the tensor's properties through the lens of degree-6 polynomials, the algorithm implicitly tests for global consistency across all three modes simultaneously. Barak et al. proved that this approach successfully completes and decomposes noisy tensors up to the algorithmic threshold of $r = \tilde{O}(d^{1.5})$, finally matching the regime where the decomposition is theoretically unique.
Tensor Lifting: Amplifying the Spectral Gap
While the SoS hierarchy provided the first provable guarantees for overcomplete recovery, solving massive semidefinite programs is computationally expensive. To make overcomplete tensor decomposition practical, researchers developed a technique known as tensor lifting.
The core idea of lifting, analyzed by Hopkins et al. and Ding et al., is to map the lower-order tensor into a much higher-dimensional matrix representation—not by flattening, but by forming Kronecker products of the tensor with itself.
For example, if we lift a 3rd-order tensor to a 6th-order representation, we can partition its entries into a symmetric matrix of size $d^3 \times d^3$. In this massive ambient space, the maximum possible rank is $d^3$, which is vastly larger than our target rank of $r \approx d^{1.5}$.
$$\text{Ambient Dimension } (d^3) \gg \text{Overcomplete Rank } (d^{1.5}) \gg \text{Base Dimension } (d)$$
By expanding the ambient space, the latent components—which were crowded and linearly dependent in the original $d$-dimensional space—become nearly orthogonal. As Ding et al. explained, this dramatic expansion amplifies the spectral gap between the true signal components and the random cross-talk noise. Consequently, simple, fast power iterations or spectral updates can cleanly isolate the hidden factors in nearly linear time, bypassing the need for slow SDP solvers.
Incoherence and the Nonconvex Landscape
If we move away from convex relaxations and spectral lifting, can we solve overcomplete problems directly using fast, nonconvex optimization like gradient descent or alternating updates?
The challenge with direct nonconvex optimization is the optimization landscape: overcomplete regimes introduce complex algebraic dependencies that typically create a minefield of spurious local minima. However, the landscape becomes remarkably benign if the latent factors satisfy an incoherence condition.
As formalized by Anandkumar et al., incoherence means that while the latent vectors $u_i, u_j$ cannot be strictly orthogonal (since there are more vectors than dimensions), their maximum mutual correlation is strictly bounded. If you pick the components randomly, they are naturally incoherent.
When this condition holds, Ge et al. demonstrated that the optimization landscape undergoes a structural shift. Under a warm start or a smart initialization, every local maximum corresponds to an approximate global maximum—meaning it perfectly aligns with one of the true latent components.
Complementing this perspective, Li et al. showed that this behavior can be viewed as a continuous super-resolution problem. Because the incoherent components act like isolated "spikes" on a high-dimensional sphere, iterative algorithms can track and isolate them one by one without getting trapped by the cross-talk of neighboring factors.
Key Foundational Work
Tensor decompositions for learning latent variable models (2012) — contributed 1 concept elements to this direction.
Information Theoretic Bounds for Tensor Rank Minimization over Finite Fields (2011) — contributed 1 concept elements to this direction.