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.

提出了一种新的、简单的、计算效率高的迭代方法，用于矩阵完成的低秩分解。该方法能快速稳定地从非常少的观测数据中重建病态矩阵，并对加性噪声具有稳定性。