Fixed-point continuation for l1-minimization Methodology and convergence

Elaine T. Hale, Wotao Yin, and Yin Zhang

Published in SIAM Journal on Optimization

Overview

This paper presents an algorithm for solving the ell_1-regularized minimization problem:

 mathrm{minimize}_x |x|_1 + mu f(x),

where f(x) is a differentiable convex function. It is developed by applying operator-splitting and parameter continuation. Operator-splitting results in a fixed-point iteration for any given scalar mu>0. Continuation refers to approximately following the solution path as mu increases, from 0 to its assigned value.

Although convergence of this algorithm is known, this paper proves two new results: (i) finite convergence for “solution signs” and (ii) q-linear convergence rates even in some cases where f(x) is not strictly convex. In addition, parameter continuation significantly accelerates the practical performance of the algorithm.

Citation

E.T. Hale, W. Yin, and Y. Zhang, Fixed-point continuation for l1-minimization Methodology and convergence, SIAM Journal on Optimization, 19(3), 1107-1130, 2008.

Related papers

E.T. Hale, W. Yin, and Y. Zhang, Fixed-point continuation applied to compressed sensing: implementation and numerical experiments, Journal of Computational Mathematics, 28(2), 170-194, 2010.

Z. Wen, W. Yin, D. Goldfarb, and Y. Zhang, A fast algorithm for sparse reconstruction based on shrinkage, subspace optimization, and continuation, SIAM Journal on Scientific Computing, 32(4), 1832–1857, 2010.

Z. Wen, W. Yin, H. Zhang, and D. Goldfarb, On the convergence of an active-set method for l1 minimization, Optimization Methods and Software, 27(6), 1127-1146, 2011.


« Back