Enhancing sparsity by reweighted \(\ell _{1}\) minimization (Q734955)

In this nice paper, the authors study a new method for sparse signal recovery that outperforms (unweighted) \(\ell_1\)minimization in the sense that substantially fewer measurements are needed for exact recovery. Let \(\Phi\) be a real \(m\times n\) matrix with \(m<n\). The authors would want to recover a (sparse) signal \(x_0 \in {\mathbb R}^n\) from given data \(y = \Phi x_0\) by solving a weighted \(\ell_1\) minimization problem \[ \min_{x\in {\mathbb R}^n} \sum_{i=1}^n w_i\,|x_i| \;\mathrm{subject to}\; y=\Phi x\,, \] where \(w_i\) are positive weights and \(x = (x_i)_{i=1}^n\in {\mathbb R}^n\). The authors propose a simple iterative algorithm that alternates between estimating \(x_0\) and redefining the weights. The weights are stepwise computed from the current solution. The number of iterations is typically very low. This iterative algorithm falls in the general class of majorization-minimization algorithms. Numerous experiments demonstrate the performance and applicability of this algorithm in sparse signal recovery, compressive sensing, statistical estimation, error correction, and magnetic resonance imaging. This paper closes with discussions of related work and possible future directions.