论文标题
归纳矩阵完成：没有糟糕的本地最小值和快速算法
Inductive Matrix Completion: No Bad Local Minima and a Fast Algorithm
论文作者
论文摘要
电感矩阵完成（IMC）问题是从少数观察到的条目中恢复低级矩阵，同时将有关其行和列子空间的先验知识结合在一起。在这项工作中，我们为IMC问题做出了三个贡献：（i）我们证明，在适当的条件下，IMC优化景观没有糟糕的本地最小值； （ii）我们得出一个简单的方案，具有理论保证，以估计未知矩阵的排名； （iii）我们提出了GNIMC，这是一种基于高斯 - 纽顿的简单方法来解决IMC问题，分析其运行时并为其提供恢复保证。 GNIMC的保证在几个方面都比其他方法（包括二次收敛速率），更少所需的观察条目以及对错误或与低级别偏差的稳定性更为明显。从经验上讲，鉴于条目在随机下均匀观察到的条目，GNIMC恢复了基础矩阵的速度要快得多，要比几种竞争方法要快得多。
The inductive matrix completion (IMC) problem is to recover a low rank matrix from few observed entries while incorporating prior knowledge about its row and column subspaces. In this work, we make three contributions to the IMC problem: (i) we prove that under suitable conditions, the IMC optimization landscape has no bad local minima; (ii) we derive a simple scheme with theoretical guarantees to estimate the rank of the unknown matrix; and (iii) we propose GNIMC, a simple Gauss-Newton based method to solve the IMC problem, analyze its runtime and derive recovery guarantees for it. The guarantees for GNIMC are sharper in several aspects than those available for other methods, including a quadratic convergence rate, fewer required observed entries and stability to errors or deviations from low-rank. Empirically, given entries observed uniformly at random, GNIMC recovers the underlying matrix substantially faster than several competing methods.
