无需考虑条件数的快速矩阵填充

Jul, 2014

Fast matrix completion without the condition number

Moritz Hardt, Mary Wootters

TL;DR本文介绍了第一种算法，可在多项式时间和样本复杂度内完成矩阵补全，其复杂度与矩阵的秩成正比，与矩阵的维度成线性关系，与矩阵的条件数成对数关系，并基于交替最小化扩展算法，对标准假设下受噪声影响的情况也有理论保证。

Abstract

We give the first algorithm for matrix completion whose running time and sample complexity is polynomial in the rank of the unknown target matrix, linear in the dimension of the matrix, and logarithmic in the con