Reweighted $\ell_1$-Minimization for Sparse Solutions to Underdetermined Linear Systems
Yun-Bin Zhao (y.zhao.2bham.ac.uk)
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 )
Entry Submitted: 03/10/2012
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|