Reweighted \ell_1-minimization for sparse solutions to underdetermined linear systems,

Yun-Bin Zhao, D Li

Research output: Contribution to journalArticlepeer-review

66 Citations (Scopus)
354 Downloads (Pure)


Numerical experiments have indicated that the reweighted $\ell_1$-minimization performs exceptionally well in locating sparse solutions of underdetermined linear systems of equations. We show that reweighted $\ell_1$-methods are intrinsically associated with the minimization of the so-called merit functions for sparsity, which are essentially concave approximations to the cardinality function. Based on this observation, we further show that a family of reweighted $\ell_1$-algorithms can be systematically derived from the perspective of concave optimization through the linearization technique. In order to conduct a unified convergence analysis for this family of algorithms, we introduce the concept of the range space property (RSP) of a matrix and prove that if its adjoint has this property, the reweighted $\ell_1$-algorithm can find a sparse solution to the underdetermined linear system provided that the merit function for sparsity is properly chosen. In particular, some convergence conditions for the Candès--Wakin--Boyd method and the recent $\ell_p$-quasi-norm-based reweighted $\ell_1$-method can be obtained as special cases of the general framework.

Read More:
Original languageEnglish
Article number1
Pages (from-to)1065–1088
Number of pages24
JournalSIAM Journal on Optimization
Issue number3
Publication statusPublished - 2012


  • Reweighted ℓ1-minimization, sparse solution, underdetermined linear system, concave minimization, merit function for sparsity, compressed sensing


Dive into the research topics of 'Reweighted \ell_1-minimization for sparse solutions to underdetermined linear systems,'. Together they form a unique fingerprint.

Cite this