Low rank matrix recovery problems, including matrix completion and matrix sensing, appear in a broad range of applications. In this work we present GNMR -- an extremely simple iterative algorithm for low rank matrix recovery, based on a Gauss-Newton linearization. On the theoretical front, we derive recovery guarantees for GNMR in both the matrix sensing and matrix completion settings. Some of these results improve upon the best currently known for other methods. A key property of GNMR is that it implicitly keeps the factor matrices approximately balanced throughout its iterations. On the empirical front, we show that for matrix completion with uniform sampling, GNMR performs better than several popular methods, especially when given very few observations close to the information limit.
翻译:低级矩阵回收问题,包括矩阵完成和矩阵遥感,出现在广泛的应用中。在这项工作中,我们提出了GNMR -- -- 低级矩阵回收的极简单的迭接算法,以高斯-牛顿线性化为基础。在理论方面,我们在矩阵遥感和矩阵完成设置中为GNMR提供回收保证,其中一些结果在目前最熟悉的其他方法基础上有所改进。GNMR的一个关键特性是,它在其迭代中使要素矩阵保持了大致的平衡。在经验方面,我们表明,在统一取样的矩阵完成方面,GNMR的表现优于几种流行的方法,特别是在接近信息限度的观测极少的情况下。