mlsanityData to 7 Oct 2026

Randomly Initialized Alternating Least Squares: Fast Convergence for Matrix Sensing

arXiv 2204.11516 ↗First posted 25 Apr 2022cs.LG cs.IT eess.SPcited by 11

Not on the map. Why?

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.

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

Builds on

24 of 62 references.

References · 24

  1. 2018Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overviewcited by 159
  2. 2016Matrix Completion has No Spurious Local Minimumcited by 124
  3. 2014Phase Retrieval via Wirtinger Flow: Theory and Algorithmscited by 123
  4. 2014Matrix Completion and Low-Rank SVD via Fast Alternating Least Squarescited by 104
  5. 2015Low-rank Solutions of Linear Matrix Equations via Procrustes Flowcited by 97
  6. 2016A Geometric Analysis of Phase Retrievalcited by 92
  7. 2014Guaranteed Matrix Completion via Non-convex Factorizationcited by 81
  8. 2016Global Optimality of Local Search for Low Rank Matrix Recoverycited by 81
  9. 2021Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstructioncited by 77
  10. 2017Gradient Descent Can Take Exponential Time to Escape Saddle Pointscited by 74
  11. 2018Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrievalcited by 71
  12. 2013Phase Retrieval using Alternating Minimizationcited by 58
12 more
  1. 2019Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimizationcited by 58
  2. 2015Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systemscited by 50
  3. 2021Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorizationcited by 44
  4. 2022Algorithmic Regularization in Model-free Overparametrized Asymmetric Matrix Factorizationcited by 34
  5. 2013Understanding Alternating Minimization for Matrix Completioncited by 32
  6. 2017Near-optimal bounds for phase synchronizationcited by 32
  7. 2013Phase Retrieval from Coded Diffraction Patternscited by 26
  8. 2014Fast matrix completion without the condition numbercited by 17
  9. 2016Phase retrieval with random Gaussian sensing vectors by alternating projectionscited by 15
  10. 2018Nonconvex Matrix Factorization from Rank-One Measurementscited by 13
  11. 2017Model-free Nonconvex Matrix Completion: Local Minima Analysis and Applications in Memory-efficient Kernel PCAcited by 12
  12. 2021Proof methods for robust low-rank matrix recoverycited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 3; 2024: 4; 2025: 3; 2026: 1.

11 papers.

  1. 2023The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensingcited by 32
  2. 2024Efficient and Robust Regularized Federated Recommendationcited by 4
  3. 2025Efficient Over-parameterized Matrix Sensing from Noisy Measurements via Alternating Preconditioned Gradient Descentcited by 4
  4. 2024Asymptotic Dynamics of Alternating Minimization for Bilinear Regressioncited by 3
  5. 2024Non-convex matrix sensing: Breaking the quadratic rank barrier in the sample complexitycited by 3
  6. 2024Interacting Particle Systems on Networks: joint inference of the network and the interaction kernelcited by 2
  7. 2023Acceleration and Implicit Regularization in Gaussian Phase Retrievalcited by 1
  8. 2026Learning Multi-type heterogeneous interacting particle systemscited by 1
  9. 2023Implicit Balancing and Regularization: Generalization and Convergence Guarantees for Overparameterized Asymmetric Matrix Sensingcited by 0
  10. 2025End-to-End Personalization: Unifying Recommender Systems with Large Language Modelscited by 0
  11. 2025Core-elements Subsampling for Alternating Least Squarescited by 0