mlsanityData to 7 Oct 2026

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

arXiv 2104.14526 ↗First posted 29 Apr 2021cs.LG cs.IT eess.SPcited by 28

Not on the map. Why?

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.

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

Builds on

58 of 86 references.

References · 58

  1. 2016Tensor Decomposition for Signal Processing and Machine Learningcited by 223
  2. 2018Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overviewcited by 159
  3. 2014Phase Retrieval via Wirtinger Flow: Theory and Algorithmscited by 123
  4. 2020Spectral Methods for Data Science: A Statistical Perspectivecited by 111
  5. 2014Guaranteed Matrix Completion via Non-convex Factorizationcited by 81
  6. 2018Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrievalcited by 71
  7. 2015Exact tensor completion using t-SVDcited by 70
  8. 2020Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descentcited by 70
  9. 2015Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guaranteescited by 68
  10. 2017Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolutioncited by 63
  11. 2014Novel methods for multilinear data completion and de-noising based on tensor-SVDcited by 56
  12. 2017Tensor SVD: Statistical and Computational Limitscited by 52
38 more
  1. 2015Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systemscited by 50
  2. 2020An Optimal Statistical and Computational Framework for Generalized Tensor Estimationcited by 39
  3. 2016Non-square matrix sensing without spurious local minima via the Burer-Monteiro approachcited by 38
  4. 2013Square Deal: Lower Bounds and Improved Relaxations for Tensor Recoverycited by 37
  5. 2017Global Guarantees for Enforcing Deep Generative Priors by Empirical Riskcited by 37
  6. 2019Nonconvex Low-Rank Tensor Completion from Noisy Datacited by 35
  7. 2020Deep Networks and the Multiple Manifold Problemcited by 35
  8. 2013Robust Low-rank Tensor Recovery: Models and Algorithmscited by 33
  9. 2014On Tensor Completion via Nuclear Norm Minimizationcited by 32
  10. 2014Provable Tensor Factorization with Missing Datacited by 31
  11. 2019Low-rank matrix recovery with composite optimization: good conditioning and rapid convergencecited by 31
  12. 2016Solving Systems of Random Quadratic Equations via Truncated Amplitude Flowcited by 28
  13. 2020From Symmetry to Geometry: Tractable Nonconvex Problemscited by 28
  14. 2016Spectral algorithms for tensor completioncited by 27
  15. 2017On Polynomial Time Methods for Exact Low Rank Tensor Completioncited by 27
  16. 2020Low-Rank Matrix Recovery with Scaled Subgradient Methods: Fast and Robust Convergence Without the Condition Numbercited by 27
  17. 2018Harnessing Structures in Big Data via Guaranteed Low-Rank Matrix Estimationcited by 25
  18. 2015Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Methodcited by 24
  19. 2016Non-Convex Projected Gradient Descent for Generalized Low-Rank Tensor Regressioncited by 23
  20. 2017Statistically Optimal and Computationally Efficient Low Rank Tensor Completion from Noisy Entriescited by 23
  21. 2018Guaranteed Recovery of One-Hidden-Layer Neural Networks via Cross Entropycited by 22
  22. 2017On the Optimization Landscape of Tensor Decompositionscited by 21
  23. 2013Low-Rank Matrix and Tensor Completion via Adaptive Samplingcited by 19
  24. 2015Complete Dictionary Recovery over the Spherecited by 19
  25. 2016Low-rank tensor completion: a Riemannian manifold preconditioning approachcited by 19
  26. 2016Low-tubal-rank Tensor Completion using Alternating Minimizationcited by 18
  27. 2018Subgradient Descent Learns Orthogonal Dictionariescited by 17
  28. 2018Exact Low Tubal Rank Tensor Recovery from Gaussian Measurementscited by 16
  29. 2020Tensor Completion Made Practicalcited by 15
  30. 2017Exact tensor completion with sum-of-squarescited by 14
  31. 2019ISLET: Fast and Optimal Low-rank Tensor Regression via Importance Sketchingcited by 14
  32. 2018Nonconvex Matrix Factorization from Rank-One Measurementscited by 13
  33. 2020Uncertainty quantification for nonconvex tensor completion: Confidence intervals, heteroscedasticity and optimalitycited by 13
  34. 2021Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergencecited by 13
  35. 2017Model-free Nonconvex Matrix Completion: Local Minima Analysis and Applications in Memory-efficient Kernel PCAcited by 12
  36. 2020Inference for Low-rank Tensors -- No Need to Debiascited by 12
  37. 2018Sparse and Low-rank Tensor Estimation via Cubic Sketchingscited by 11
  38. 2020Learning Mixtures of Low-Rank Modelscited by 11

50 most cited of 58 All 58 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 4; 2023: 4; 2024: 6; 2025: 8; 2026: 4.

28 papers.

Sort:

By area:

  1. 2024Riemannian Preconditioned LoRA for Fine-Tuning Foundation Modelscited by 51
  2. 2023The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensingcited by 32
  3. 2021Provable Tensor-Train Format Tensor Completion by Riemannian Optimizationcited by 17
  4. 2022Tensor-on-Tensor Regression: Riemannian Optimization, Over-parameterization, Statistical-computational Gap, and Their Interplaycited by 15
  5. 2022Fast and Provable Tensor Robust Principal Component Analysis via Scaled Gradient Descentcited by 11
  6. 2025A Stronger Mixture of Low-Rank Experts for Fine-Tuning Foundation Modelscited by 9
  7. 2024Guaranteed Nonconvex Factorization Approach for Tensor Train Recoverycited by 8
  8. 2021Tensor Principal Component Analysis in High Dimensional CP Modelscited by 7
  9. 2022Deep Unfolded Tensor Robust PCA with Self-supervised Learningcited by 7
  10. 2023Deflated HeteroPCA: Overcoming the curse of ill-conditioning in heteroskedastic PCAcited by 7
  11. 2024Low-Tubal-Rank Tensor Recovery via Factorized Gradient Descentcited by 7
  12. 2023Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled Gradient Descent, Even with Overparameterizationcited by 6
16 more
  1. 2025Generalized Parallel Scaling with Interdependent Generationscited by 6
  2. 2022Behind the Scenes of Gradient Descent: A Trajectory Analysis via Basis Function Decompositioncited by 4
  3. 2024Computational and Statistical Guarantees for Tensor-on-Tensor Regression with Tensor Train Decompositioncited by 4
  4. 2025A Scalable Factorization Approach for High-Order Structured Tensor Recoverycited by 4
  5. 2024Guaranteed Sampling Flexibility for Low-tubal-rank Tensor Completioncited by 3
  6. 2025On the Benefits of Weight Normalization for Overparameterized Matrix Sensingcited by 3
  7. 2024Robust Low-rank Tensor Train Recoverycited by 2
  8. 2023Efficiency of First-Order Methods for Low-Rank Tensor Recovery with the Tensor Nuclear Norm Under Strict Complementaritycited by 1
  9. 2025Efficient Low-Tubal-Rank Tensor Estimation via Alternating Preconditioned Gradient Descentcited by 1
  10. 2025Matrix Completion with Graph Information: A Provable Nonconvex Optimization Approachcited by 0
  11. 2025Accelerating Large-Scale Regularized High-Order Tensor Recoverycited by 0
  12. 2025An Interdisciplinary and Cross-Task Review on Missing Data Imputationcited by 0
  13. 2026StoTAM: Stochastic Alternating Minimization for Tucker-Structured Tensor Sensingcited by 0
  14. 2026Multi-Dimensional Visual Data Recovery: Scale-Aware Tensor Modeling and Accelerated Randomized Computationcited by 0
  15. 2026Structured Adaptive Tensor Prediction for Streaming Datacited by 0
  16. 2026Tensor Completion using Subspace Informationcited by 0