论文标题
随机初始化交替的最小二乘：矩阵传感的快速收敛
Randomly Initialized Alternating Least Squares: Fast Convergence for Matrix Sensing
论文作者
论文摘要
我们考虑从随机线性测量结果重建等级矩阵的问题，该任务出现在信号处理，统计和机器学习中的各种问题中。在本文中，我们专注于交替的最小二乘法（ALS）方法。尽管该算法已经在许多以前的工作中进行了研究，但其中大多数仅显示从接近True解决方案的初始化中的收敛性，因此需要精心设计的初始化方案。但是，由于它是模型不合时宜的，因此从业人员通常首选随机初始化。在本文中，我们表明，具有随机初始化的ALS将$ o（\ log n + \ log（1/\ varepsilon）中的$ \ varepsilon $ -Accuracy收敛到真实解决方案，仅使用接近最佳的样品进行迭代，如果我们假设我们假设要测量的矩阵属于I.I.D。高斯和按$ n $的地方表示环境维度。我们证明的关键是观察到，ALS迭代的轨迹仅在非常温和地取决于随机测量矩阵的某些条目。数值实验证实了我们的理论预测。
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.
