mlsanityData to 7 Oct 2026

Understanding Alternating Minimization for Matrix Completion

arXiv 1312.0925 ↗First posted 3 Dec 2013cs.LG cs.DS stat.MLcited by 32

Not on the map. Why?

Abstract (arXiv)

Alternating Minimization is a widely used and empirically successful heuristic for matrix completion and related low-rank optimization problems. Theoretical guarantees for Alternating Minimization have been hard to come by and are still poorly understood. This is in part because the heuristic is iterative and non-convex in nature. We give a new algorithm based on Alternating Minimization that provably recovers an unknown low-rank matrix from a random subsample of its entries under a standard incoherence assumption. Our results reduce the sample size requirements of the Alternating Minimization approach by at least a quartic factor in the rank and the condition number of the unknown matrix. These improvements apply even if the matrix is only close to low-rank in the Frobenius norm. Our algorithm runs in nearly linear time in the dimension of the matrix and, in a broad range of parameters, gives the strongest sample bounds among all subquadratic time algorithms that we are aware of. Underlying our work is a new robust convergence analysis of the well-known Power Method for computing the dominant singular vectors of a matrix. This viewpoint leads to a conceptually simple understanding of Alternating Minimization. In addition, we contribute a new technique for controlling the coherence of intermediate solutions arising in iterative algorithms based on a smoothed analysis of the QR factorization. These techniques may be of interest beyond their application here.

Key facts. Cited by 32 papers in the map (data through 7 Oct 2026). First posted on arXiv 3 Dec 2013.

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2021: 8; 2022: 8; 2023: 5; 2024: 8; 2025: 3.

32 papers.

Sort:

  1. 2021Large Learning Rate Tames Homogeneity: Convergence and Balancing Effectcited by 48
  2. 2021On the computational and statistical complexity of over-parameterized matrix sensingcited by 31
  3. 2023Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Timecited by 31
  4. 2022Transformers from an Optimization Perspectivecited by 27
  5. 2022Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the O(ε-7/4) Complexitycited by 17
  6. 2021Noisy Gradient Descent Converges to Flat Minima for Nonconvex Matrix Factorizationcited by 15
  7. 2022Randomly Initialized Alternating Least Squares: Fast Convergence for Matrix Sensingcited by 11
  8. 2021GNMR: A provable one-line algorithm for low rank matrix recoverycited by 10
  9. 2022Convergence and Recovery Guarantees of the K-Subspaces Method for Subspace Clusteringcited by 9
  10. 2022A Novel Stochastic Gradient Descent Algorithm for Learning Principal Subspacescited by 7
  11. 2022Accelerating SGD for Highly Ill-Conditioned Huge-Scale Online Matrix Completioncited by 6
  12. 2022Tensor Completion with Provable Consistency and Fairness Guarantees for Recommender Systemscited by 4
20 more
  1. 2022Robust Matrix Completion with Heavy-tailed Noisecited by 4
  2. 2023Matrix Completion in Almost-Verification Timecited by 4
  3. 2024Riemannian Optimization for Non-convex Euclidean Distance Geometry with Global Recovery Guaranteescited by 4
  4. 2021Riemannian Perspective on Matrix Factorizationcited by 3
  5. 2021Exact Linear Convergence Rate Analysis for Low-Rank Symmetric Matrix Completion via Gradient Descentcited by 3
  6. 2021Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimizationcited by 3
  7. 2024LEARNER: A Transfer Learning Method for Low-Rank Matrix Estimationcited by 3
  8. 2023Disjunctive Branch-and-Bound for Certifiably Optimal Low-Rank Matrix Completioncited by 2
  9. 2023One-sided Matrix Completion from Two Observations Per Rowcited by 2
  10. 2024Learning a Single Neuron Robustly to Distributional Shifts and Adversarial Label Noisecited by 2
  11. 2021Robust Matrix Factorization with Grouping Effectcited by 0
  12. 2023An Admissible Shift-Consistent Method for Recommender Systemscited by 0
  13. 2024Randomized Approach to Matrix Completion: Applications in Recommendation Systems and Image Inpaintingcited by 0
  14. 2024Efficient Federated Low Rank Matrix Completioncited by 0
  15. 2024Tailed Low-Rank Matrix Factorization for Similarity Matrix Completioncited by 0
  16. 2024A Learned Proximal Alternating Minimization Algorithm and Its Induced Network for a Class of Two-block Nonconvex and Nonsmooth Optimizationcited by 0
  17. 2024Matrix Completion via Residual Spectral Matchingcited by 0
  18. 2025Fast exact recovery of noisy matrix from few entries: the infinity norm approachcited by 0
  19. 2025Provable Non-Convex Euclidean Distance Matrix Completion: Geometry, Reconstruction, and Robustnesscited by 0
  20. 2025An Interdisciplinary and Cross-Task Review on Missing Data Imputationcited by 0