Jonathan A. Kelner, Jerry Li, Allen Liu, Aaron Sidford, Kevin Tian
TL;DR我们提供了一个解决低秩矩阵完成问题的新框架，通过聚合涉及观测的回归问题的解来将矩阵 M 完成，并改进了之前已知的算法的样本复杂度和运行时间。
Abstract
We give a new framework for solving the fundamental problem of low-rank
matrix completion, i.e., approximating a rank-$r$ matrix $\mathbf{M} \in
\mathbb{R}^{m \times n}$ (where $m \ge n$) from random observations. First, we
provide an algorithm which completes $\mathbf{M}$ on $99\%$ of rows and columns
under no further assumptions on $\mathbf{M}$ from $\appr