Weighted algorithms for compressed sensing and matrix completion

Understand

This paper is about iteratively reweighted basis-pursuit algorithms for compressed sensing and matrix completion problems.

• In a first 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.