Optimization Online


A Fixed-Point Continuation Method for l_1-Regularized Minimization with Applications to Compressed Sensing

Elaine Hale(ehale***at***rice.edu)
Wotao Yin(wotao.yin***at***rice.edu)
Yin Zhang(yzhang***at***rice.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/2007
Entry Accepted: 07/16/2007
Entry Last Modified: 07/16/2007

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society