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/2007
Entry Accepted: 07/16/2007
Entry Last Modified: 07/16/2007

Modify/Update this entry