Randomly Initialized Alternating Least Squares: Fast Convergence for Matrix Sensing
Authors:
- 6 September 2023
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Mathematics of Data Science
- Vol. 5 (3) , 774-799
Abstract
We consider the problem of reconstructing rank-1 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 [Formula: see text]-accuracy in [Formula: see text] iterations using only a near-optimal number of samples, where we assume the measurement matrices to be i.i.d. Gaussian and where by [Formula: see text] we denote the ambient dimension. We observe that the convergence occurs in two phases. In the first phase, the iterates starting from random initialization become gradually more aligned with the true signal, and in the second phase the iterates converge linearly. Key to our proof is the observation that in the first phase the trajectory of the ALS iterates depends only very mildly on certain entries of the random measurement matrices. Numerical experiments corroborate our theoretical predictions.Keywords
All Related Versions
Funding Information
- National Science Foundation (CCF 19-43201)
This publication has 44 references indexed in Scilit:
- Phase retrieval from coded diffraction patternsApplied and Computational Harmonic Analysis, 2015
- A Partial Derandomization of PhaseLift Using Spherical DesignsJournal of Fourier Analysis and Applications, 2014
- PhaseLift: Exact and Stable Signal Recovery from Magnitude Measurements via Convex ProgrammingCommunications on Pure and Applied Mathematics, 2012
- Low-rank Matrix Recovery via Iteratively Reweighted Least Squares MinimizationSIAM Journal on Optimization, 2011
- Robust principal component analysis?Journal of the ACM, 2011
- Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm MinimizationSIAM Review, 2010
- Exact Matrix Completion via Convex OptimizationFoundations of Computational Mathematics, 2009
- Phase retrieval algorithms: a comparisonApplied Optics, 1982
- Principal Component Analysis of Three-Mode Data by Means of Alternating Least Squares AlgorithmsPsychometrika, 1980
- Numerical methods for computing angles between linear subspacesMathematics of Computation, 1973