- Reweighted $\ell_1$-Minimization for Sparse Solutions to Underdetermined Linear Systems Yun-Bin Zhao (y.zhao.2bham.ac.uk) Duan Li (dlise.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 ) Citation: Download: [PDF]Entry Submitted: 03/10/2012Entry Accepted: 03/10/2012Entry Last Modified: 10/09/2012Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.