  


Sparse Approximation via Penalty Decomposition Methods
Zhaosong Lu(zhaosongsfu.ca) Abstract: In this paper we consider sparse approximation problems, that is, general $l_0$ minimization problems with the $l_0$``norm'' of a vector being a part of constraints or objective function. In particular, we first study the firstorder optimality conditions for these problems. We then propose penalty decomposition (PD) methods for solving them in which a sequence of penalty subproblems are solved by a block coordinate descent (BCD) method. Under some suitable assumptions, we establish that any accumulation point of the sequence generated by the PD methods satisfies the firstorder optimality conditions of the problems. Furthermore, for the problems in which the $l_0$ part is the only nonconvex part, we show that such an accumulation point is a local minimizer of the problems. In addition, we show that any accumulation point of the sequence generated by the BCD method is a saddle point of the penalty subproblem. Moreover, for the problems in which the $l_0$ part is the only nonconvex part, we establish that such an accumulation point is a local minimizer of the penalty subproblem. Finally, we test the performance of our PD methods by applying them to sparse logistic regression, sparse inverse covariance selection, and compressed sensing problems. The computational results demonstrate that our methods generally outperform the existing methods in terms of solution quality and/or speed. Keywords: $l_0$ minimization, penalty decomposition methods, block coordinate descent method, compressed sensing, sparse logistic regression, sparse inverse covariance selection Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming ) Category 2: Convex and Nonsmooth Optimization (Nonsmooth Optimization ) Category 3: Nonlinear Optimization (Constrained Nonlinear Optimization ) Citation: Manuscript, Department of Mathematics, Simon Fraser University, 8888 University Drive, Burnaby, BC, V5A 1S6, Canada, May 2012 Download: [PDF] Entry Submitted: 05/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  