Optimization Online


Reweighted $\ell_1$-Minimization for Sparse Solutions to Underdetermined Linear Systems

Yun-Bin Zhao (y.zhao.2***at***bham.ac.uk)
Duan Li (dli***at***se.cuhk.edu.hk)

Abstract: Numerical experiments have indicated that the reweighted $\ell_1$-minimization performs exceptionally well in locating sparse solutions of underdetermined linear systems of equations. Thus it is important to carry out a further investigation of this class of methods. In this paper, we point out 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 Range Space Property (RSP) of matrices, and prove that if $A^T$ has this property, the reweighted $\ell_1$-algorithms 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 (based on the RSP) for Cand\`es-Wakin-Boyd method and the recent $\ell_p$-quasi-norm-based reweighted $\ell_1$-minimization can be obtained as special cases of the general framework.

Keywords: Reweighted $\ell_1$-minimization, sparse solution, underdetermined linear system, concave minimization, merit function for sparsity, compressive sensing.

Category 1: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Category 2: Linear, Cone and Semidefinite Programming (Linear Programming )

Category 3: Applications -- Science and Engineering (Basic Sciences Applications )


Download: [PDF]

Entry Submitted: 03/10/2012
Entry Accepted: 03/10/2012
Entry Last Modified: 10/09/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society