# Randomly Initialized Alternating Least Squares: Fast Convergence for Matrix Sensing

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 62 references that are in the map.
- First posted on arXiv 25 Apr 2022.

## Builds on (most cited first, 24 of 24)

- [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)
- [Matrix Completion has No Spurious Local Minimum](https://mlsanity.com/paper/1605.07272/) (2016)
- [Matrix Completion and Low-Rank SVD via Fast Alternating Least Squares](https://mlsanity.com/paper/1410.2596/) (2014)
- [Low-rank Solutions of Linear Matrix Equations via Procrustes Flow](https://mlsanity.com/paper/1507.03566/) (2015)
- [A Geometric Analysis of Phase Retrieval](https://mlsanity.com/paper/1602.06664/) (2016)
- [Guaranteed Matrix Completion via Non-convex Factorization](https://mlsanity.com/paper/1411.8003/) (2014)
- [Global Optimality of Local Search for Low Rank Matrix Recovery](https://mlsanity.com/paper/1605.07221/) (2016)
- [Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction](https://mlsanity.com/paper/2106.15013/) (2021)
- [Gradient Descent Can Take Exponential Time to Escape Saddle Points](https://mlsanity.com/paper/1705.10412/) (2017)
- [Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrieval](https://mlsanity.com/paper/1803.07726/) (2018)
- [Phase Retrieval using Alternating Minimization](https://mlsanity.com/paper/1306.0160/) (2013)
- [Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization](https://mlsanity.com/paper/1902.07698/) (2019)
- [Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems](https://mlsanity.com/paper/1505.05114/) (2015)
- [Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization](https://mlsanity.com/paper/2106.14289/) (2021)
- [Algorithmic Regularization in Model-free Overparametrized Asymmetric Matrix Factorization](https://mlsanity.com/paper/2203.02839/) (2022)
- [Understanding Alternating Minimization for Matrix Completion](https://mlsanity.com/paper/1312.0925/) (2013)
- [Near-optimal bounds for phase synchronization](https://mlsanity.com/paper/1703.06605/) (2017)
- [Phase Retrieval from Coded Diffraction Patterns](https://mlsanity.com/paper/1310.3240/) (2013)
- [Fast matrix completion without the condition number](https://mlsanity.com/paper/1407.4070/) (2014)
- [Phase retrieval with random Gaussian sensing vectors by alternating projections](https://mlsanity.com/paper/1609.03088/) (2016)
- [Nonconvex Matrix Factorization from Rank-One Measurements](https://mlsanity.com/paper/1802.06286/) (2018)
- [Model-free Nonconvex Matrix Completion: Local Minima Analysis and Applications in Memory-efficient Kernel PCA](https://mlsanity.com/paper/1711.01742/) (2017)
- [Proof methods for robust low-rank matrix recovery](https://mlsanity.com/paper/2106.04382/) (2021)

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

- [The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensing](https://mlsanity.com/paper/2302.01186/) (2023)
- [Efficient and Robust Regularized Federated Recommendation](https://mlsanity.com/paper/2411.01540/) (2024)
- [Efficient Over-parameterized Matrix Sensing from Noisy Measurements via Alternating Preconditioned Gradient Descent](https://mlsanity.com/paper/2502.00463/) (2025)
- [Asymptotic Dynamics of Alternating Minimization for Bilinear Regression](https://mlsanity.com/paper/2402.04751/) (2024)
- [Non-convex matrix sensing: Breaking the quadratic rank barrier in the sample complexity](https://mlsanity.com/paper/2408.13276/) (2024)
- [Interacting Particle Systems on Networks: joint inference of the network and the interaction kernel](https://mlsanity.com/paper/2402.08412/) (2024)
- [Acceleration and Implicit Regularization in Gaussian Phase Retrieval](https://mlsanity.com/paper/2311.12888/) (2023)
- [Learning Multi-type heterogeneous interacting particle systems](https://mlsanity.com/paper/2602.03954/) (2026)
- [Implicit Balancing and Regularization: Generalization and Convergence Guarantees for Overparameterized Asymmetric Matrix Sensing](https://mlsanity.com/paper/2303.14244/) (2023)
- [End-to-End Personalization: Unifying Recommender Systems with Large Language Models](https://mlsanity.com/paper/2508.01514/) (2025)
- [Core-elements Subsampling for Alternating Least Squares](https://mlsanity.com/paper/2509.18024/) (2025)

## Abstract (arXiv)

We consider the problem of reconstructing rank-one matrices from random linear measurements, a task that appears in a variety of problems in signal processing, statistics, and machine learning. In this paper, we focus on the Alternating Least Squares (ALS) method. While this algorithm has been studied in a number of previous works, most of them only show convergence from an initialization close to the true solution and thus require a carefully designed initialization scheme. However, random initialization has often been preferred by practitioners as it is model-agnostic. In this paper, we show that ALS with random initialization converges to the true solution with varepsilon-accuracy in O(log n + log (1/varepsilon))  iterations using only a near-optimal amount of samples, where we assume the measurement matrices to be i.i.d. Gaussian and where by n we denote the ambient dimension. Key to our proof is the observation that the trajectory of the ALS iterates only depends very mildly on certain entries of the random measurement matrices. Numerical experiments corroborate our theoretical predictions.