Fixed-Point Continuation for l1-Minimization: Methodology and Convergence
Lists
Only you see this
Abstract
We present a framework for solving the large-scale $\ell_1$-regularized convex minimization problem:\[ \min\|x\|_1+\mu f(x). \] Our approach is based on two powerful algorithmic ideas: operator-splitting and continuation. Operator-splitting results in a fixed-point algorithm for any given scalar $\mu$; continuation refers to approximately following the path traced by the optimal value of x as $\mu$ increases. In this paper, we study the structure of optimal solution sets, prove finite convergence for important quantities, and establish q-linear convergence rates for the fixed-point algorithm applied to problems with $f(x)$ convex, but not necessarily strictly convex. The continuation framework, motivated by our convergence results, is demonstrated to facilitate the construction of practical algorithms.
BibTeX
@article{hale2008fixed,
author = {Elaine T. Hale and Wotao Yin and Yin Zhang},
title = {{Fixed-Point Continuation for l1-Minimization: Methodology and Convergence}},
journal = {SIAM J. Optim.},
year = {2008},
doi = {10.1137/070698920},
}Loading related content...