- A Fixed-Point Continuation Method for l_1-Regularized Minimization with Applications to Compressed Sensing Elaine Hale(ehalerice.edu) Wotao Yin(wotao.yinrice.edu) Yin Zhang(yzhangrice.edu) Abstract: We consider solving minimization problems with $\ell_1$-regularization: $$\min \|x\|_1 + \mu f(x),$$ particularly for $f(x) = \frac{1}{2}\|Ax-b\|_M^2$ where $A \in \R^{m \times n}$ with $m < n$. Our goal is to construct efficient and robust algorithms for solving large-scale problems with dense data, and our approach is based on two powerful algorithmic ideas, operator-splitting 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 large-scale problems with noisy data the performance of our algorithm compares favorably with that of several state-of-the-art 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 TR07-07 Download: [PDF]Entry Submitted: 07/16/2007Entry Accepted: 07/16/2007Entry Last Modified: 07/16/2007Modify/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 Programming Society and by the Optimization Technology Center.