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

From MaRDI portal
scientific article
Language Label Description Also known as
English
Enhancing sparsity by reweighted \(\ell _{1}\) minimization
scientific article

    Statements

    Enhancing sparsity by reweighted \(\ell _{1}\) minimization (English)
    0 references
    0 references
    0 references
    0 references
    14 October 2009
    0 references
    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.
    0 references
    0 references
    0 references
    0 references
    0 references
    signal theory
    0 references
    sparsity
    0 references
    sparse signal recovery
    0 references
    \(\ell_1\) minimization
    0 references
    weighted \(\ell_1\) minimization
    0 references
    iterative algorithm
    0 references
    majorization-minimization algorithm
    0 references
    compressive sensing
    0 references
    statistical estimation
    0 references
    error correction
    0 references
    magnetic resonance imaging
    0 references
    image processing
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references