# Understanding Alternating Minimization for Matrix Completion

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

## Key facts

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

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

- [Large Learning Rate Tames Homogeneity: Convergence and Balancing Effect](https://mlsanity.com/paper/2110.03677/) (2021)
- [On the computational and statistical complexity of over-parameterized matrix sensing](https://mlsanity.com/paper/2102.02756/) (2021)
- [Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time](https://mlsanity.com/paper/2302.11068/) (2023)
- [Transformers from an Optimization Perspective](https://mlsanity.com/paper/2205.13891/) (2022)
- [Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the O(ε-7/4) Complexity](https://mlsanity.com/paper/2201.11411/) (2022)
- [Noisy Gradient Descent Converges to Flat Minima for Nonconvex Matrix Factorization](https://mlsanity.com/paper/2102.12430/) (2021)
- [Randomly Initialized Alternating Least Squares: Fast Convergence for Matrix Sensing](https://mlsanity.com/paper/2204.11516/) (2022)
- [GNMR: A provable one-line algorithm for low rank matrix recovery](https://mlsanity.com/paper/2106.12933/) (2021)
- [Convergence and Recovery Guarantees of the K-Subspaces Method for Subspace Clustering](https://mlsanity.com/paper/2206.05553/) (2022)
- [A Novel Stochastic Gradient Descent Algorithm for Learning Principal Subspaces](https://mlsanity.com/paper/2212.04025/) (2022)
- [Accelerating SGD for Highly Ill-Conditioned Huge-Scale Online Matrix Completion](https://mlsanity.com/paper/2208.11246/) (2022)
- [Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimization](https://mlsanity.com/paper/2108.01772/) (2021)
- [Tensor Completion with Provable Consistency and Fairness Guarantees for Recommender Systems](https://mlsanity.com/paper/2204.01815/) (2022)
- [Robust Matrix Completion with Heavy-tailed Noise](https://mlsanity.com/paper/2206.04276/) (2022)
- [Matrix Completion in Almost-Verification Time](https://mlsanity.com/paper/2308.03661/) (2023)
- [Riemannian Optimization for Non-convex Euclidean Distance Geometry with Global Recovery Guarantees](https://mlsanity.com/paper/2410.06376/) (2024)
- [Riemannian Perspective on Matrix Factorization](https://mlsanity.com/paper/2102.00937/) (2021)
- [Exact Linear Convergence Rate Analysis for Low-Rank Symmetric Matrix Completion via Gradient Descent](https://mlsanity.com/paper/2102.02396/) (2021)
- [LEARNER: A Transfer Learning Method for Low-Rank Matrix Estimation](https://mlsanity.com/paper/2412.20605/) (2024)
- [Disjunctive Branch-and-Bound for Certifiably Optimal Low-Rank Matrix Completion](https://mlsanity.com/paper/2305.12292/) (2023)
- [One-sided Matrix Completion from Two Observations Per Row](https://mlsanity.com/paper/2306.04049/) (2023)
- [Learning a Single Neuron Robustly to Distributional Shifts and Adversarial Label Noise](https://mlsanity.com/paper/2411.06697/) (2024)
- [Robust Matrix Factorization with Grouping Effect](https://mlsanity.com/paper/2106.13681/) (2021)
- [An Admissible Shift-Consistent Method for Recommender Systems](https://mlsanity.com/paper/2307.08857/) (2023)
- [Randomized Approach to Matrix Completion: Applications in Recommendation Systems and Image Inpainting](https://mlsanity.com/paper/2403.01919/) (2024)
- [Efficient Federated Low Rank Matrix Completion](https://mlsanity.com/paper/2405.06569/) (2024)
- [Tailed Low-Rank Matrix Factorization for Similarity Matrix Completion](https://mlsanity.com/paper/2409.19550/) (2024)
- [A Learned Proximal Alternating Minimization Algorithm and Its Induced Network for a Class of Two-block Nonconvex and Nonsmooth Optimization](https://mlsanity.com/paper/2411.06333/) (2024)
- [Matrix Completion via Residual Spectral Matching](https://mlsanity.com/paper/2412.10005/) (2024)
- [Fast exact recovery of noisy matrix from few entries: the infinity norm approach](https://mlsanity.com/paper/2501.19224/) (2025)

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