# Square Deal: Lower Bounds and Improved Relaxations for Tensor Recovery

arXiv: https://arxiv.org/abs/1307.5870 · HTML: https://mlsanity.com/paper/1307.5870/

## Key facts

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

## Built on by (most cited first, 30 of 37)

- [Guaranteed Tensor Recovery Fused Low-rankness and Smoothness](https://mlsanity.com/paper/2302.02155/) (2023)
- [Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements](https://mlsanity.com/paper/2104.14526/) (2021)
- [Low-Rank Hankel Tensor Completion for Traffic Speed Estimation](https://mlsanity.com/paper/2105.11335/) (2021)
- [Tensor-on-Tensor Regression: Riemannian Optimization, Over-parameterization, Statistical-computational Gap, and Their Interplay](https://mlsanity.com/paper/2206.08756/) (2022)
- [Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergence](https://mlsanity.com/paper/2104.12031/) (2021)
- [Noisy Tensor Completion via Low-rank Tensor Ring](https://mlsanity.com/paper/2203.08857/) (2022)
- [TenIPS: Inverse Propensity Sampling for Tensor Completion](https://mlsanity.com/paper/2101.00323/) (2021)
- [Low-Tubal-Rank Tensor Recovery via Factorized Gradient Descent](https://mlsanity.com/paper/2401.11940/) (2024)
- [Tensor train completion: local recovery guarantees via Riemannian optimization](https://mlsanity.com/paper/2110.03975/) (2021)
- [Efficient Tensor Robust PCA under Hybrid Model of Tucker and Tensor Train](https://mlsanity.com/paper/2112.10771/) (2021)
- [Beyond the Signs: Nonparametric Tensor Completion via Sign Series](https://mlsanity.com/paper/2102.00384/) (2021)
- [Hankel-structured Tensor Robust PCA for Multivariate Traffic Time Series Anomaly Detection](https://mlsanity.com/paper/2110.04352/) (2021)
- [Nonnegative Tensor Completion via Integer Optimization](https://mlsanity.com/paper/2111.04580/) (2021)
- [Multiway Spherical Clustering via Degree-Corrected Tensor Block Models](https://mlsanity.com/paper/2201.07401/) (2022)
- [Multi-dimensional domain generalization with low-rank structures](https://mlsanity.com/paper/2309.09555/) (2023)
- [Learnable Scaled Gradient Descent for Guaranteed Robust Tensor PCA](https://mlsanity.com/paper/2501.04565/) (2025)
- [Saten: Sparse Augmented Tensor Networks for Post-Training Compression of Large Language Models](https://mlsanity.com/paper/2505.14871/) (2025)
- [Low-rank Tensor Learning with Nonconvex Overlapped Nuclear Norm Regularization](https://mlsanity.com/paper/2205.03059/) (2022)
- [STN: Scalable Tensorizing Networks via Structure-Aware Training and Adaptive Compression](https://mlsanity.com/paper/2205.15198/) (2022)
- [Accelerated Nonnegative Tensor Completion via Integer Programming](https://mlsanity.com/paper/2211.15770/) (2022)
- [Tensor Factorization via Transformed Tensor-Tensor Product for Image Alignment](https://mlsanity.com/paper/2212.05719/) (2022)
- [Under-Counted Tensor Completion with Neural Incorporation of Attributes](https://mlsanity.com/paper/2306.03273/) (2023)
- [Recovering Simultaneously Structured Data via Non-Convex Iteratively Reweighted Least Squares](https://mlsanity.com/paper/2306.04961/) (2023)
- [Tensor Methods in High Dimensional Data Analysis: Opportunities and Challenges](https://mlsanity.com/paper/2405.18412/) (2024)
- [Knowledge Graph Completion by Intermediate Variables Regularization](https://mlsanity.com/paper/2506.02749/) (2025)
- [Multi-modal and frequency-weighted tensor nuclear norm for hyperspectral image denoising](https://mlsanity.com/paper/2106.12489/) (2021)
- [Tensor Full Feature Measure and Its Nonconvex Relaxation Applications to Tensor Recovery](https://mlsanity.com/paper/2109.12257/) (2021)
- [Low-Multi-Rank High-Order Bayesian Robust Tensor Factorization](https://mlsanity.com/paper/2311.05888/) (2023)
- [Revisiting Trace Norm Minimization for Tensor Tucker Completion: A Direct Multilinear Rank Learning Approach](https://mlsanity.com/paper/2409.05139/) (2024)
- [Variational Bayesian Inference for Tensor Robust Principal Component Analysis](https://mlsanity.com/paper/2412.18717/) (2024)

## 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.