Fixed-point continuation for l1-minimization Methodology and convergenceElaine T. Hale, Wotao Yin, and Yin Zhang
Published in SIAM Journal on Optimization OverviewThis paper presents an algorithm for solving the -regularized minimization problem: where is a differentiable convex function. It is developed by applying operator-splitting and parameter continuation. Operator-splitting results in a ﬁxed-point iteration for any given scalar . Continuation refers to approximately following the solution path as 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 is not strictly convex. In addition, parameter continuation significantly accelerates the practical performance of the algorithm. CitationE.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 papersE.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 |