The Computational Limits of Low Rank Tensor Recovery

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2253 papers319 conceptsfrozen 2026-10-04

In the transition from two-dimensional matrices to multi-way arrays—or tensors—our most reliable mathematical intuitions often fail. While we can efficiently find the "best" low-rank approximation of a matrix using the Singular Value Decomposition (SVD), doing the same for a 3D or 4D tensor is a mathematical minefield. This research direction explores the fundamental computational and statistical boundaries of recovering structure from high-dimensional data.

The Ambiguity of Tensor Rank

For a matrix, rank is a simple, well-behaved property: it is the number of linearly independent rows or columns. However, as Ryota Tomioka, Hisashi Kashima, and Kohei Hayashi point out in On the extension of trace norm to tensors, higher-order tensors lack a single, well-defined rank. Instead, they possess a distinct rank for every possible "unfolding" or mode.

This isn't just a semantic problem; it’s a computational one. Determining the exact "canonical rank" of a tensor is an NP-hard problem. As kim batselier and Ngai Wong argue in A Constructive Algorithm for Decomposing a Tensor into a Finite Sum of Orthonormal Rank-1 Terms, this intractability forces researchers to rely on heuristics or upper bounds. Unlike matrices, where we can use the nuclear norm as a convex surrogate for rank, tensors require more complex regularizers to fill in missing data, a challenge highlighted by Gonzalo Mateos and Georgios B. Giannakis in Rank Regularization and Bayesian Inference for Tensor Completion and Extrapolation.

The Computational-Statistical Gap

One of the most striking findings in this field is the "gap" between what is mathematically possible and what is computationally feasible. In A statistical model for tensor PCA, Andrea Montanari and Emile Richard demonstrate that there are regimes where a signal exists within a noisy tensor, but no polynomial-time algorithm can extract it.

This gap has profound implications for machine learning. Marco Mondelli and Andrea Montanari established a formal link between training two-layer neural networks and tensor decomposition in On the Connection Between Learning Two-Layers Neural Networks and Tensor Decomposition. They showed that the difficulty of learning network weights is intrinsically tied to the NP-hardness of identifying latent structures in high-dimensional tensors.

Strategies for Recovery

To bypass the NP-hardness of the general problem, researchers have developed several specialized frameworks:

  1. Convex Relaxations: Methods like the "scaled latent nuclear norm" used by Xiawei Guo and James Kwok in Efficient Sparse Low-Rank Tensor Completion Using the Frank-Wolfe Algorithm attempt to make the optimization landscape manageable.
  2. Tensor Train (TT) and Tucker Formats: These formats compress tensors into a series of smaller cores. Arvind V. Mahankali and Ziyu Zhang explore these in Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions as a way to combat the "curse of dimensionality."
  3. Greedy and Iterative Methods: Algorithms like Higher order Matching Pursuit (HoMP), introduced by Yuning Yang and Johan A. K. Suykens in Higher order Matching Pursuit for Low Rank Tensor Learning, avoid expensive SVDs by iteratively finding approximate rank-one components.

Geometry and Eigenvalues

The geometry of tensors is fundamentally different from matrices. In Tensors, Bernd Sturmfels and colleagues explain that finding the closest rank-one approximation involves navigating complex algebraic varieties (Segre and Veronese).

Furthermore, tensor eigenvalues are not linear. Jackson R. Mayo and Grey Ballard note in Computing Tensor Eigenvalues: Theory and Practice that computing these requires solving systems of non-linear equations, leading to a massive number of potential "eigenpairs" that grow rapidly with the tensor's order.

Why It Works (and When It Doesn't)

The success of these methods often depends on the "best rank-one approximation ratio"—a measure of how much energy a single component can capture. Tasuku Soma and Yuji Nakatsukasa proved in On orthogonal tensors and best rank-one approximation ratio that this ratio is optimized only for "orthogonal" tensors.

While general tensor completion remains NP-hard, specific structures offer hope. For instance, Michael R. Lyu and Zenglin Xu showed in Exact and Stable Recovery of Pairwise Interaction Tensors that "Pairwise Interaction Tensors" can be recovered with mathematical certainty, providing a rare island of tractability in a notoriously difficult field.

Papers in this version

Showing 60 of 253 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 198 papers
  2. Version 1 · 2026-10-04 · 253 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_tensor_rank_np_hardness_87c8a9a1,
  title = {tensor rank NP-hardness},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/tensor-rank-np-hardness/rdr_87c8a9a1b2574742b89fa1a817d05d26},
  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_the_computational_limits_of_low_rank_ten_87c8a9a1_v1,
  title = {The Computational Limits of Low Rank Tensor Recovery},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/the-computational-limits-of-low-rank-tensor-recovery/rdr_87c8a9a1b2574742b89fa1a817d05d26/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}