Weighted algorithms for compressed sensing and matrix completion
Weighted algorithms for compressed sensing and matrix completion
复制标题
DOI：
--
复制
发表时间：
2011-07
期刊：
影响因子：
--
通讯作者：
Stéphane Gaïffas;Guillaume Lecué
中科院分区：
文献类型：
--
作者：
Stéphane Gaïffas;Guillaume Lecué
本文研究了用于压缩感知和矩阵补全问题的迭代重加权基追踪算法。第二部分从理论上解释了在压缩感知中，重加权基追踪可以大大提高精确恢复的基追踪。我们展示了一个将权重的准确性与RIP和非相干常数联系起来的条件，这确保了精确的恢复。在第二部分，我们介绍了一种新的基于迭代加权思想的矩阵补全算法。由于加权核范数通常是非凸的，因此它不能很容易地用作目标函数。因此，我们提出了一个新的基于点方程的估计量。我们给出的经验证据表明，这种新算法在模拟和实际矩阵补全问题上比核范数最小化有很大的改进。
This paper is about iteratively reweighted basis-pursuit algorithms for compressed sensing and matrix completion problems. In a rst part, we give a theoretical explanation of the fact that reweighted basis pursuit can improve a lot upon basis pursuit for exact recovery in compressed sensing. We exhibit a condition that links the accuracy of the weights to the RIP and incoherency constants, which ensures exact recovery. In a second part, we introduce a new algorithm for matrix completion, based on the idea of iterative reweighting. Since a weighted nuclear \norm" is typically non-convex, it cannot be used easily as an objective function. So, we dene a new estimator based on a xed-point equation. We give empirical evidences of the fact that this new algorithm leads to strong improvements over nuclear norm minimization on simulated and real matrix completion problems.