  


Reweighted $\ell_1$Minimization for Sparse Solutions to Underdetermined Linear Systems
YunBin 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 socalled 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\`esWakinBoyd method and the recent $\ell_p$quasinormbased 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/2012 Modify/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  