LOW-RANK MATRIX RECOVERY VIA ITERATIVELY REWEIGHTED LEAST SQUARES MINIMIZATION
LOW-RANK MATRIX RECOVERY VIA ITERATIVELY REWEIGHTED LEAST SQUARES MINIMIZATION
复制标题
DOI：
10.1137/100811404
复制
发表时间：
2011-01-01
影响因子：
3.1
通讯作者：
Ward, Rachel
中科院分区：
文献类型：
--
作者：
Fornasier, Massimo;Rauhut, Holger;Ward, Rachel
我们提出并分析了一种迭代加权最小二乘算法的有效实现，用于从少量线性测量中恢复矩阵。该算法设计用于同时提升最小核范数和近似低秩解。在假设线性测量满足压缩感知中已知零空间性质的适当推广的前提下，该算法保证迭代恢复任何误差为最佳k-秩近似数量级的矩阵。在某些相关的情况下，例如，对于矩阵补全问题，我们的算法版本可以利用Woodbury矩阵恒等式，这使我们能够加快求解每次迭代所需的最小二乘问题。我们提出的数值实验证实了该算法在解决矩阵补全问题方面的鲁棒性，并且我们证明了它与最近在文献中提出的其他技术相比的竞争力。
We present and analyze an efficient implementation of an iteratively reweighted least squares algorithm for recovering a matrix from a small number of linear measurements. The algorithm is designed for the simultaneous promotion of both a minimal nuclear norm and an approximately low-rank solution. Under the assumption that the linear measurements fulfill a suitable generalization of the null space property known in the context of compressed sensing, the algorithm is guaranteed to recover iteratively any matrix with an error of the order of the best k-rank approximation. In certain relevant cases, for instance, for the matrix completion problem, our version of this algorithm can take advantage of the Woodbury matrix identity, which allows us to expedite the solution of the least squares problems required at each iteration. We present numerical experiments which confirm the robustness of the algorithm for the solution of matrix completion problems, and we demonstrate its competitiveness with respect to other techniques proposed recently in the literature.