  


A FixedPoint Continuation Method for l_1Regularized Minimization with Applications to Compressed Sensing
Elaine Hale(ehalerice.edu) Abstract: We consider solving minimization problems with $\ell_1$regularization: $$\min \x\_1 + \mu f(x),$$ particularly for $f(x) = \frac{1}{2}\Axb\_M^2$ where $A \in \R^{m \times n}$ with $m < n$. Our goal is to construct efficient and robust algorithms for solving largescale problems with dense data, and our approach is based on two powerful algorithmic ideas, operatorsplitting and continuation. Theoretical contributions of the paper include the establishment of $q$linear rate of convergence for our algorithm applied to objectives with convex, but not necessarily strictly convex, $f$. We present numerical results on solving compressed sensing problems of various types, showing that on largescale problems with noisy data the performance of our algorithm compares favorably with that of several stateoftheart algorithms. Keywords: $\ell_1$ regularization, fixed point algorithm, $q$linear convergence, continuation, compressed sensing. Category 1: Convex and Nonsmooth Optimization (Convex Optimization ) Category 2: Convex and Nonsmooth Optimization (Nonsmooth Optimization ) Category 3: Applications  Science and Engineering (Other ) Citation: Rice CAAM Technical Report TR0707 Download: [PDF] Entry Submitted: 07/16/2007 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  