mlsanityData to 14 Oct 2026

Square Deal: Lower Bounds and Improved Relaxations for Tensor Recovery

arXiv 1307.5870 ↗First posted 22 Jul 2013stat.ML cs.LGcited by 37

Not on the map. Why?

Abstract (arXiv)

Recovering a low-rank tensor from incomplete information is a recurring problem in signal processing and machine learning. The most popular convex relaxation of this problem minimizes the sum of the nuclear norms of the unfoldings of the tensor. We show that this approach can be substantially suboptimal: reliably recovering a K-way tensor of length n and Tucker rank r from Gaussian measurements requires Omega(r nK-1) observations. In contrast, a certain (intractable) nonconvex formulation needs only O(rK + nrK) observations. We introduce a very simple, new convex relaxation, which partially bridges this gap. Our new formulation succeeds with O(rlfloor K/2 rfloornlceil K/2 rceil) observations. While these results pertain to Gaussian measurements, simulations strongly suggest that the new norm also outperforms the sum of nuclear norms for tensor completion from a random subset of entries. Our lower bound for the sum-of-nuclear-norms model follows from a new result on recovering signals with multiple sparse structures (e.g. sparse, low rank), which perhaps surprisingly demonstrates the significant suboptimality of the commonly used recovery approach via minimizing the sum of individual sparsity inducing norms (e.g. l1, nuclear norm). Our new formulation for low-rank tensor recovery however opens the possibility in reducing the sample complexity by exploiting several structures jointly.

Key facts. Cited by 37 papers in the map (data through 14 Oct 2026). First posted on arXiv 22 Jul 2013.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 11; 2022: 7; 2023: 5; 2024: 4; 2025: 7; 2026: 3.

37 papers.

Sort:

  1. 2023Guaranteed Tensor Recovery Fused Low-rankness and Smoothnesscited by 41
  2. 2021Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurementscited by 28
  3. 2021Low-Rank Hankel Tensor Completion for Traffic Speed Estimationcited by 22
  4. 2022Tensor-on-Tensor Regression: Riemannian Optimization, Over-parameterization, Statistical-computational Gap, and Their Interplaycited by 15
  5. 2021Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergencecited by 13
  6. 2022Noisy Tensor Completion via Low-rank Tensor Ringcited by 13
  7. 2021TenIPS: Inverse Propensity Sampling for Tensor Completioncited by 7
  8. 2024Low-Tubal-Rank Tensor Recovery via Factorized Gradient Descentcited by 7
  9. 2021Tensor train completion: local recovery guarantees via Riemannian optimizationcited by 6
  10. 2021Efficient Tensor Robust PCA under Hybrid Model of Tucker and Tensor Traincited by 6
  11. 2021Beyond the Signs: Nonparametric Tensor Completion via Sign Seriescited by 4
  12. 2021Hankel-structured Tensor Robust PCA for Multivariate Traffic Time Series Anomaly Detectioncited by 4
25 more
  1. 2021Nonnegative Tensor Completion via Integer Optimizationcited by 4
  2. 2022Multiway Spherical Clustering via Degree-Corrected Tensor Block Modelscited by 4
  3. 2023Multi-dimensional domain generalization with low-rank structurescited by 2
  4. 2025Learnable Scaled Gradient Descent for Guaranteed Robust Tensor PCAcited by 2
  5. 2025Saten: Sparse Augmented Tensor Networks for Post-Training Compression of Large Language Modelscited by 2
  6. 2022Low-rank Tensor Learning with Nonconvex Overlapped Nuclear Norm Regularizationcited by 1
  7. 2022STN: Scalable Tensorizing Networks via Structure-Aware Training and Adaptive Compressioncited by 1
  8. 2022Accelerated Nonnegative Tensor Completion via Integer Programmingcited by 1
  9. 2022Tensor Factorization via Transformed Tensor-Tensor Product for Image Alignmentcited by 1
  10. 2023Under-Counted Tensor Completion with Neural Incorporation of Attributescited by 1
  11. 2023Recovering Simultaneously Structured Data via Non-Convex Iteratively Reweighted Least Squarescited by 1
  12. 2024Tensor Methods in High Dimensional Data Analysis: Opportunities and Challengescited by 1
  13. 2025Knowledge Graph Completion by Intermediate Variables Regularizationcited by 1
  14. 2021Multi-modal and frequency-weighted tensor nuclear norm for hyperspectral image denoisingcited by 0
  15. 2021Tensor Full Feature Measure and Its Nonconvex Relaxation Applications to Tensor Recoverycited by 0
  16. 2023Low-Multi-Rank High-Order Bayesian Robust Tensor Factorizationcited by 0
  17. 2024Revisiting Trace Norm Minimization for Tensor Tucker Completion: A Direct Multilinear Rank Learning Approachcited by 0
  18. 2024Variational Bayesian Inference for Tensor Robust Principal Component Analysiscited by 0
  19. 2025Information-Theoretic Guarantees for Recovering Low-Rank Tensors from Symmetric Rank-One Measurementscited by 0
  20. 2025ACT-Tensor: Tensor Completion Framework for Financial Dataset Imputationcited by 0
  21. 2025Efficient Tensor Completion Algorithms for Highly Oscillatory Operatorscited by 0
  22. 2025An Interdisciplinary and Cross-Task Review on Missing Data Imputationcited by 0
  23. 2026Multi-Dimensional Visual Data Recovery: Scale-Aware Tensor Modeling and Accelerated Randomized Computationcited by 0
  24. 2026Low-rank Distributional Matrix Completioncited by 0
  25. 2026Guaranteed Low-Rank Tensor Recovery from Modewise Measurements via Normalized Block-Weighted Riemannian Gradient Descentcited by 0