论文标题
通过可扩展的二阶方法，以不良条件的矩阵完成逃脱鞍点
Escaping Saddle Points in Ill-Conditioned Matrix Completion with a Scalable Second Order Method
论文作者
论文摘要
我们提出了一种低级矩阵完成的迭代算法，该算法可以解释为迭代重新加权的最小二乘（IRLS）算法，也可以解释为应用于非convex级别级别替代物目标的鞍形的平滑牛顿方法。它结合了先前IRLS方法的有利数据效率，并提高了几个数量级的提高可伸缩性。对于许多接近信息理论限制的样本，我们的方法已经达到了局部二次收敛率。我们在数值实验中显示，与许多最先进的方法不同，我们的方法能够从几个样本中完成非常不良条件的矩阵，其条件数量最高为$ 10^{10} $。
We propose an iterative algorithm for low-rank matrix completion that can be interpreted as both an iteratively reweighted least squares (IRLS) algorithm and a saddle-escaping smoothing Newton method applied to a non-convex rank surrogate objective. It combines the favorable data efficiency of previous IRLS approaches with an improved scalability by several orders of magnitude. Our method attains a local quadratic convergence rate already for a number of samples that is close to the information theoretical limit. We show in numerical experiments that unlike many state-of-the-art approaches, our approach is able to complete very ill-conditioned matrices with a condition number of up to $10^{10}$ from few samples.
