Nonconvex Matrix Factorization From Rank-One Measurements
Nonconvex Matrix Factorization From Rank-One Measurements
复制标题
DOI：
10.1109/tit.2021.3050427
复制
发表时间：
2018-02
影响因子：
2.5
通讯作者：
Yuanxin Li;Cong Ma;Yuxin Chen;Yuejie Chi
中科院分区：
文献类型：
--
作者：
Yuanxin Li;Cong Ma;Yuxin Chen;Yuejie Chi
我们考虑从随机排名衡量的低级矩阵的问题，该矩阵涵盖了许多应用，包括协方差草图，相位检索，量子状态层析成像和学习浅层多项式神经网络等。我们的方法是通过量身定制的光谱初始化，通过将非凸形最小二乘损失函数最小化，直接估计低级因子。当真实等级由常数界定时，该算法可以保证将其融合到地面真理（达到全球歧义），并具有近乎最佳的样本复杂性和计算复杂性。据我们所知，这是在这两个指标中都取得近乎最佳性的第一个保证。特别是，近距离计算保证的关键推动因素是一种隐式正则化现象：没有明确的正则化，光谱初始化和梯度下降迭代都会自动保持在与测量矢量不连续的区域内。与先前文献中建议的相比，此功能使人们可以使用更具侵略性的步进尺寸，而无需样品分割。
We consider the problem of recovering low-rank matrices from random rank-one measurements, which spans numerous applications including covariance sketching, phase retrieval, quantum state tomography, and learning shallow polynomial neural networks, among others. Our approach is to directly estimate the low-rank factor by minimizing a nonconvex least-squares loss function via vanilla gradient descent, following a tailored spectral initialization. When the true rank is bounded by a constant, this algorithm is guaranteed to converge to the ground truth (up to global ambiguity) with near-optimal sample complexity and computational complexity. To the best of our knowledge, this is the first guarantee that achieves near-optimality in both metrics. In particular, the key enabler of near-optimal computational guarantees is an implicit regularization phenomenon: without explicit regularization, both spectral initialization and the gradient descent iterates automatically stay within a region incoherent with the measurement vectors. This feature allows one to employ much more aggressive step sizes compared with the ones suggested in prior literature, without the need of sample splitting.