  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.
Since a weighted nuclear "norm" is typically non-convex, it cannot be used
easily as an objective function. So, we define a new estimator based on a
fixed-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.
