Randomly Initialized Alternating Least Squares: Fast Convergence for Matrix Sensing

Understand

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.