# Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements

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

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- Builds on 58 of its 86 references that are in the map.
- First posted on arXiv 29 Apr 2021.

## Builds on (most cited first, 30 of 58)

- [Tensor Decomposition for Signal Processing and Machine Learning](https://mlsanity.com/paper/1607.01668/) (2016)
- [Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview](https://mlsanity.com/paper/1809.09573/) (2018)
- [Phase Retrieval via Wirtinger Flow: Theory and Algorithms](https://mlsanity.com/paper/1407.1065/) (2014)
- [Spectral Methods for Data Science: A Statistical Perspective](https://mlsanity.com/paper/2012.08496/) (2020)
- [Guaranteed Matrix Completion via Non-convex Factorization](https://mlsanity.com/paper/1411.8003/) (2014)
- [Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrieval](https://mlsanity.com/paper/1803.07726/) (2018)
- [Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent](https://mlsanity.com/paper/2005.08898/) (2020)
- [Exact tensor completion using t-SVD](https://mlsanity.com/paper/1502.04689/) (2015)
- [Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees](https://mlsanity.com/paper/1509.03025/) (2015)
- [Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution](https://mlsanity.com/paper/1711.10467/) (2017)
- [Novel methods for multilinear data completion and de-noising based on tensor-SVD](https://mlsanity.com/paper/1407.1785/) (2014)
- [Tensor SVD: Statistical and Computational Limits](https://mlsanity.com/paper/1703.02724/) (2017)
- [Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems](https://mlsanity.com/paper/1505.05114/) (2015)
- [An Optimal Statistical and Computational Framework for Generalized Tensor Estimation](https://mlsanity.com/paper/2002.11255/) (2020)
- [Non-square matrix sensing without spurious local minima via the Burer-Monteiro approach](https://mlsanity.com/paper/1609.03240/) (2016)
- [Square Deal: Lower Bounds and Improved Relaxations for Tensor Recovery](https://mlsanity.com/paper/1307.5870/) (2013)
- [Global Guarantees for Enforcing Deep Generative Priors by Empirical Risk](https://mlsanity.com/paper/1705.07576/) (2017)
- [Nonconvex Low-Rank Tensor Completion from Noisy Data](https://mlsanity.com/paper/1911.04436/) (2019)
- [Deep Networks and the Multiple Manifold Problem](https://mlsanity.com/paper/2008.11245/) (2020)
- [Robust Low-rank Tensor Recovery: Models and Algorithms](https://mlsanity.com/paper/1311.6182/) (2013)
- [On Tensor Completion via Nuclear Norm Minimization](https://mlsanity.com/paper/1405.1773/) (2014)
- [Provable Tensor Factorization with Missing Data](https://mlsanity.com/paper/1406.2784/) (2014)
- [Low-rank matrix recovery with composite optimization: good conditioning and rapid convergence](https://mlsanity.com/paper/1904.10020/) (2019)
- [Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow](https://mlsanity.com/paper/1605.08285/) (2016)
- [From Symmetry to Geometry: Tractable Nonconvex Problems](https://mlsanity.com/paper/2007.06753/) (2020)
- [Low-Rank Matrix Recovery with Scaled Subgradient Methods: Fast and Robust Convergence Without the Condition Number](https://mlsanity.com/paper/2010.13364/) (2020)
- [Spectral algorithms for tensor completion](https://mlsanity.com/paper/1612.07866/) (2016)
- [On Polynomial Time Methods for Exact Low Rank Tensor Completion](https://mlsanity.com/paper/1702.06980/) (2017)
- [Harnessing Structures in Big Data via Guaranteed Low-Rank Matrix Estimation](https://mlsanity.com/paper/1802.08397/) (2018)
- [Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method](https://mlsanity.com/paper/1511.04777/) (2015)

## Built on by (most cited first, 28 of 28)

- [Riemannian Preconditioned LoRA for Fine-Tuning Foundation Models](https://mlsanity.com/paper/2402.02347/) (2024)
- [The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensing](https://mlsanity.com/paper/2302.01186/) (2023)
- [Provable Tensor-Train Format Tensor Completion by Riemannian Optimization](https://mlsanity.com/paper/2108.12163/) (2021)
- [Tensor-on-Tensor Regression: Riemannian Optimization, Over-parameterization, Statistical-computational Gap, and Their Interplay](https://mlsanity.com/paper/2206.08756/) (2022)
- [Fast and Provable Tensor Robust Principal Component Analysis via Scaled Gradient Descent](https://mlsanity.com/paper/2206.09109/) (2022)
- [A Stronger Mixture of Low-Rank Experts for Fine-Tuning Foundation Models](https://mlsanity.com/paper/2502.15828/) (2025)
- [Guaranteed Nonconvex Factorization Approach for Tensor Train Recovery](https://mlsanity.com/paper/2401.02592/) (2024)
- [Tensor Principal Component Analysis in High Dimensional CP Models](https://mlsanity.com/paper/2108.04428/) (2021)
- [Deep Unfolded Tensor Robust PCA with Self-supervised Learning](https://mlsanity.com/paper/2212.11346/) (2022)
- [Deflated HeteroPCA: Overcoming the curse of ill-conditioning in heteroskedastic PCA](https://mlsanity.com/paper/2303.06198/) (2023)
- [Low-Tubal-Rank Tensor Recovery via Factorized Gradient Descent](https://mlsanity.com/paper/2401.11940/) (2024)
- [Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled Gradient Descent, Even with Overparameterization](https://mlsanity.com/paper/2310.06159/) (2023)
- [Generalized Parallel Scaling with Interdependent Generations](https://mlsanity.com/paper/2510.01143/) (2025)
- [Behind the Scenes of Gradient Descent: A Trajectory Analysis via Basis Function Decomposition](https://mlsanity.com/paper/2210.00346/) (2022)
- [Computational and Statistical Guarantees for Tensor-on-Tensor Regression with Tensor Train Decomposition](https://mlsanity.com/paper/2406.06002/) (2024)
- [A Scalable Factorization Approach for High-Order Structured Tensor Recovery](https://mlsanity.com/paper/2506.16032/) (2025)
- [Guaranteed Sampling Flexibility for Low-tubal-rank Tensor Completion](https://mlsanity.com/paper/2406.11092/) (2024)
- [On the Benefits of Weight Normalization for Overparameterized Matrix Sensing](https://mlsanity.com/paper/2510.01175/) (2025)
- [Robust Low-rank Tensor Train Recovery](https://mlsanity.com/paper/2410.15224/) (2024)
- [Efficiency of First-Order Methods for Low-Rank Tensor Recovery with the Tensor Nuclear Norm Under Strict Complementarity](https://mlsanity.com/paper/2308.01677/) (2023)
- [Efficient Low-Tubal-Rank Tensor Estimation via Alternating Preconditioned Gradient Descent](https://mlsanity.com/paper/2512.07490/) (2025)
- [Matrix Completion with Graph Information: A Provable Nonconvex Optimization Approach](https://mlsanity.com/paper/2502.08536/) (2025)
- [Accelerating Large-Scale Regularized High-Order Tensor Recovery](https://mlsanity.com/paper/2506.09594/) (2025)
- [An Interdisciplinary and Cross-Task Review on Missing Data Imputation](https://mlsanity.com/paper/2511.01196/) (2025)
- [StoTAM: Stochastic Alternating Minimization for Tucker-Structured Tensor Sensing](https://mlsanity.com/paper/2601.13522/) (2026)
- [Multi-Dimensional Visual Data Recovery: Scale-Aware Tensor Modeling and Accelerated Randomized Computation](https://mlsanity.com/paper/2602.12982/) (2026)
- [Structured Adaptive Tensor Prediction for Streaming Data](https://mlsanity.com/paper/2606.10085/) (2026)
- [Tensor Completion using Subspace Information](https://mlsanity.com/paper/2609.24501/) (2026)

## Abstract (arXiv)

Tensors, which provide a powerful and flexible model for representing multi-attribute data and multi-way interactions, play an indispensable role in modern data science across various fields in science and engineering. A fundamental task is to faithfully recover the tensor from highly incomplete measurements in a statistically and computationally efficient manner. Harnessing the low-rank structure of tensors in the Tucker decomposition, this paper develops a scaled gradient descent (ScaledGD) algorithm to directly recover the tensor factors with tailored spectral initializations, and shows that it provably converges at a linear rate independent of the condition number of the ground truth tensor for two canonical problems -- tensor completion and tensor regression -- as soon as the sample size is above the order of n3/2 ignoring other parameter dependencies, where n is the dimension of the tensor. This leads to an extremely scalable approach to low-rank tensor estimation compared with prior art, which suffers from at least one of the following drawbacks: extreme sensitivity to ill-conditioning, high per-iteration costs in terms of memory and computation, or poor sample complexity guarantees. To the best of our knowledge, ScaledGD is the first algorithm that achieves near-optimal statistical and computational complexities simultaneously for low-rank tensor completion with the Tucker decomposition. Our algorithm highlights the power of appropriate preconditioning in accelerating nonconvex statistical estimation, where the iteration-varying preconditioners promote desirable invariance properties of the trajectory with respect to the underlying symmetry in low-rank tensor factorization.