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.

提出了一个迭代算法，用于低秩矩阵完成，可以解释为迭代重新加权最小二乘（IRLS）算法和应用于非凸秩代理目标的鞍点逃逸平滑牛顿方法，它结合了先前IRLS方法的有利数据效率与几个数量级的可伸缩性的改进。我们的方法在样本数量接近信息理论极限时就达到了局部二次收敛速度，并在数值实验中表明，与许多现有方法不同，我们的方法能够在样本很少的情况下完成条件数高达$10^{10}$的非常病态的矩阵。

用可扩展的二阶方法逃避病态矩阵补全中的鞍点