Non-convex Recovery of High-Dimensional Low-Rank Tensors

This direction is merged into another direction: tensor decomposition scalability. Its last version stays readable and citable here.

Version 1 of 130 papers31 conceptsfrozen 2026-10-04

Tensors are the natural language for multi-dimensional data, from video sequences and medical imaging to multi-relational social networks. However, as we move from matrices (2D) to tensors (3D+), the mathematical landscape shifts from "easy" convex problems to "hard" non-convex ones.

In the matrix world, we can often find the best low-rank approximation using simple, convex tools. In the tensor world, these problems are typically NP-hard. Yet, a growing body of research shows that we can bypass these theoretical roadblocks using a combination of smart initialization and geometry-aware optimization.

The Non-convexity Trap

The core challenge in tensor recovery—whether it is Tensor completion in hierarchical tensor representations or Multi-relational Learning—is that the objective functions are non-convex. As Holger Rauhut and Reinhold Schneider point out, standard iterative algorithms only guarantee finding the right answer if they start very close to it.

If you start with a random guess, the algorithm is likely to get trapped in a "local minimum"—a point that looks like a solution but is actually just incoherent noise. This sensitivity to starting conditions is a recurring theme across the field, affecting everything from Dictionary Learning to Spatio-Temporal Emotion Estimation.

The Initialization Gap and Warm Starts

To solve the non-convexity problem, researchers use a two-stage strategy:

  1. The Warm Start: Use a computationally cheap, "rough" method to get an initial estimate that is "close enough" to the global optimum.
  2. The Refinement: Use a fast gradient-based method to "polish" that estimate into the final solution.

A popular way to get this warm start is through Spectral Initialization or the Method of Moments. For example, in Sparse and Low-Rank Tensor Estimation via Cubic Sketchings, Botao Hao and Anru R. Zhang use third-order interactions (cubic sketchings) to find a starting point that places the optimization in the "basin of attraction" of the true solution. Once inside this basin, even simple gradient descent is guaranteed to converge.

Leveraging Tensor Geometry

Instead of treating a tensor as a flat vector, we can treat the set of all low-rank tensors as a smooth, curved surface called a Riemannian Manifold.

By restricting the optimization to move only along this manifold, researchers like Jian-Feng Cai have developed algorithms that are both provably accurate and highly efficient. In Provable Near-Optimal Low-Multilinear-Rank Tensor Recovery, this geometric approach allows for the recovery of tensors from a "near-optimal" number of measurements, effectively breaking the curse of dimensionality. This same geometric intuition is applied to Online Tensor Learning to handle streaming data with minimal memory.

Overcoming Ill-Conditioning with ScaledGD

Even with a good start, optimization can be painfully slow if the data is "ill-conditioned" (meaning some components of the tensor are much stronger than others). Standard gradient descent struggles here because it uses the same step size for every component.

Yuejie Chi and Cong Ma 0001 introduced ScaledGD to solve this. As detailed in Scaling and Scalability, this method uses a "preconditioner" to adapt the step size to the local geometry of the tensor. The result is linear convergence that is independent of how messy or ill-conditioned the data is, making it a powerful tool for real-world Uncertainty Quantification.

Why This Matters

The shift toward provable non-convex methods allows us to use tensors in high-stakes applications where we previously relied on simpler, less accurate models.

  • Deep Learning: Jean Kossaifi and colleagues use these decompositions to "unzip" 3D convolutions in Factorized Higher-Order CNNs, making video processing significantly more efficient.
  • Heterogeneous Data: Models like DCOT, proposed by George Michailidis, allow for the analysis of Heterogeneous Data by splitting tensors into shared and group-specific components.
  • Scientific Computing: In High-Dimensional Uncertainty Quantification, Zheng Zhang demonstrates how these methods can predict the performance of complex circuits by treating manufacturing variations as high-dimensional tensor inputs.

By understanding the non-convex landscape and using geometry to navigate it, we can finally harness the full power of multi-dimensional data without getting lost in local minima.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_non_convex_recovery_of_high_dimensional__726da31e,
  title = {Non-convex Recovery of High-Dimensional Low-Rank Tensors},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-convex-recovery-of-high-dimensional-low-rank-tensors/rdr_726da31e564e4c019a1891b2098a5e19},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_non_convex_recovery_of_high_dimensional__726da31e_v1,
  title = {Non-convex Recovery of High-Dimensional Low-Rank Tensors},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-convex-recovery-of-high-dimensional-low-rank-tensors/rdr_726da31e564e4c019a1891b2098a5e19/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}