mlsanityData to 7 Oct 2026

Guaranteed Matrix Completion via Non-convex Factorization

arXiv 1411.8003 ↗First posted 28 Nov 2014cs.LGcited by 81

Not on the map. Why?

Abstract (arXiv)

Matrix factorization is a popular approach for large-scale matrix completion. The optimization formulation based on matrix factorization can be solved very efficiently by standard algorithms in practice. However, due to the non-convexity caused by the factorization model, there is a limited theoretical understanding of this formulation. In this paper, we establish a theoretical guarantee for the factorization formulation to correctly recover the underlying low-rank matrix. In particular, we show that under similar conditions to those in previous works, many standard optimization algorithms converge to the global optima of a factorization formulation, and recover the true low-rank matrix. We study the local geometry of a properly regularized factorization formulation and prove that any stationary point in a certain local region is globally optimal. A major difference of our work from the existing results is that we do not need resampling in either the algorithm or its analysis. Compared to other works on nonconvex optimization, one extra difficulty lies in analyzing nonconvex constrained optimization when the constraint (or the corresponding regularizer) is not "consistent" with the gradient direction. One technical contribution is the perturbation analysis for non-symmetric matrix factorization.

Key facts. Cited by 81 papers in the map (data through 7 Oct 2026). First posted on arXiv 28 Nov 2014.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 23; 2022: 15; 2023: 10; 2024: 14; 2025: 16; 2026: 3.

81 papers.

Sort:

By area:

  1. 2021Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorizationcited by 44
  2. 2023Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Timecited by 31
  3. 2021Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurementscited by 28
  4. 2023Implicit bias of SGD in L2-regularized linear DNNs: One-way jumps from high to low rankcited by 28
  5. 2024Weight decay induces low-rank attention layerscited by 27
  6. 2024Compressible Dynamics in Deep Overparameterized Low-Rank Learning & Adaptationcited by 26
  7. 2022Convergence of gradient descent for deep neural networkscited by 24
  8. 2021Improving Fairness for Data Valuation in Horizontal Federated Learningcited by 22
  9. 2021Inference for Heteroskedastic PCA with Missing Datacited by 21
  10. 2021Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact Recoverycited by 21
  11. 2022Preconditioned Gradient Descent for Overparameterized Nonconvex Burer--Monteiro Factorization with Global Optimality Certificationcited by 21
  12. 2023The Law of Parsimony in Gradient Descent for Learning Deep Linear Networkscited by 19
38 more
  1. 2022Fair and efficient contribution valuation for vertical federated learningcited by 18
  2. 2022Personalized PCA: Decoupling Shared and Unique Featurescited by 17
  3. 2021Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergencecited by 13
  4. 2021A Scalable Second Order Method for Ill-Conditioned Matrix Completion from Few Samplescited by 13
  5. 2021Submodular + Concavecited by 13
  6. 2022Improved Global Guarantees for the Nonconvex Burer--Monteiro Factorization via Rank Overparameterizationcited by 13
  7. 2022Matrix Completion with Cross-Concentrated Sampling: Bridging Uniform Sampling and CUR Samplingcited by 12
  8. 2025Preconditioned Gradient Descent for Over-Parameterized Nonconvex Matrix Factorizationcited by 12
  9. 2021Implicit Regularization in Matrix Sensing via Mirror Descentcited by 11
  10. 2022Randomly Initialized Alternating Least Squares: Fast Convergence for Matrix Sensingcited by 11
  11. 2021Multi-source Learning via Completion of Block-wise Overlapping Noisy Matricescited by 10
  12. 2021GNMR: A provable one-line algorithm for low rank matrix recoverycited by 10
  13. 2021Private Alternating Least Squares: Practical Private Matrix Completion with Tighter Ratescited by 10
  14. 2021Time Series Forecasting via Learning Convolutionally Low-Rank Modelscited by 9
  15. 2022A Novel Stochastic Gradient Descent Algorithm for Learning Principal Subspacescited by 7
  16. 2021Crowdsourcing via Annotator Co-occurrence Imputation and Provable Symmetric Nonnegative Matrix Factorizationcited by 6
  17. 2022Accelerating SGD for Highly Ill-Conditioned Huge-Scale Online Matrix Completioncited by 6
  18. 2023Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled Gradient Descent, Even with Overparameterizationcited by 6
  19. 2021Fast quantum state reconstruction via accelerated non-convex programmingcited by 5
  20. 2022Accelerating nuclear-norm regularized low-rank matrix optimization through Burer-Monteiro decompositioncited by 5
  21. 2023Fast and Accurate Estimation of Low-Rank Matrices from Noisy Measurements via Preconditioned Non-Convex Gradient Descentcited by 5
  22. 2022Tensor Completion with Provable Consistency and Fairness Guarantees for Recommender Systemscited by 4
  23. 2022Robust Matrix Completion with Heavy-tailed Noisecited by 4
  24. 2022Rank-1 Matrix Completion with Gradient Descent and Small Random Initializationcited by 4
  25. 2023Matrix Completion in Almost-Verification Timecited by 4
  26. 2024Symmetric Matrix Completion with ReLU Samplingcited by 4
  27. 2024Computational and Statistical Guarantees for Tensor-on-Tensor Regression with Tensor Train Decompositioncited by 4
  28. 2025Efficient Over-parameterized Matrix Sensing from Noisy Measurements via Alternating Preconditioned Gradient Descentcited by 4
  29. 2021Riemannian Perspective on Matrix Factorizationcited by 3
  30. 2021Exact Linear Convergence Rate Analysis for Low-Rank Symmetric Matrix Completion via Gradient Descentcited by 3
  31. 2021Sharp Global Guarantees for Nonconvex Low-rank Recovery in the Noisy Overparameterized Regimecited by 3
  32. 2021On Geometric Connections of Embedded and Quotient Geometries in Riemannian Fixed-rank Matrix Optimizationcited by 3
  33. 2023Gradient-Based Spectral Embeddings of Random Dot Product Graphscited by 3
  34. 2024Non-convex matrix sensing: Breaking the quadratic rank barrier in the sample complexitycited by 3
  35. 2024Sample-Efficient Geometry Reconstruction from Euclidean Distances using Non-Convex Optimizationcited by 3
  36. 2025One Rank at a Time: Cascading Error Dynamics in Sequential Learningcited by 3
  37. 2021Beyond Procrustes: Balancing-Free Gradient Descent for Asymmetric Low-Rank Matrix Sensingcited by 2
  38. 2021On Asymptotic Linear Convergence of Projected Gradient Descent for Constrained Least Squarescited by 2

50 most cited of 81 All 81 (JSON)