论文标题
排名$ 2R $迭代最小二乘：有效地从少数条目中恢复不良条件的低级矩阵
Rank $2r$ iterative least squares: efficient recovery of ill-conditioned low rank matrices from few entries
论文作者
论文摘要
我们提出了一种新的，简单且在计算上有效的迭代方法，以完成低级矩阵完成。我们的方法的灵感来自分解型迭代算法的类别，但与它们的施放方式大不相同。确切地说，鉴于目标等级$ r $，而不是对等级$ r $矩阵的多种层次进行优化，我们允许我们的临时估计矩阵具有特定的过度参数级别$ 2R $结构。我们的算法，表示R2RILS的排名$ 2R $迭代最小二乘，记忆要求较低，并且在每次迭代中，它都可以解决计算上便宜的稀疏最小二乘问题。我们通过其理论分析对等级-1矩阵的简化情况来激励我们的算法。从经验上讲，R2rils能够从很少的观察结果中恢复不良条件的低级矩阵 - 接近信息限制，并且对加性噪声稳定。
We present a new, simple and computationally efficient iterative method for low rank matrix completion. Our method is inspired by the class of factorization-type iterative algorithms, but substantially differs from them in the way the problem is cast. Precisely, given a target rank $r$, instead of optimizing on the manifold of rank $r$ matrices, we allow our interim estimated matrix to have a specific over-parametrized rank $2r$ structure. Our algorithm, denoted R2RILS for rank $2r$ iterative least squares, has low memory requirements, and at each iteration it solves a computationally cheap sparse least-squares problem. We motivate our algorithm by its theoretical analysis for the simplified case of a rank-1 matrix. Empirically, R2RILS is able to recover ill conditioned low rank matrices from very few observations -- near the information limit, and it is stable to additive noise.
