Convergence of an inertial proximal method for l1-regularized least-squares
Patrick R. Johnstone, Pierre Moulin
Abstract
A fast, low-complexity, algorithm for solving the ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> -regularized least-squares problem is devised and analyzed. Our algorithm, which we call the Inertial Iterative Soft-Thresholding Algorithm (I-ISTA), incorporates inertia into a forward-backward proximal splitting framework. We show that the iterates of I-ISTA converge linearly to a minimum with a better rate of convergence than the well-known Iterative Shrinkage/Soft-Thresholding Algorithm (ISTA) for solving ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> -regularized least-squares. The improvement in convergence rate over ISTA is significant on ill-conditioned problems and is gained with minor additional computations. We conduct numerical experiments which show that I-ISTA converges more quickly than ISTA and two other computationally comparable algorithms on compressed sensing and deconvolution problems.
BibTeX
@inproceedings{icassp2015_convergenceofani,
title = {Convergence of an inertial proximal method for l1-regularized least-squares},
author = {Patrick R. Johnstone and Pierre Moulin},
booktitle = {ICASSP 2015},
year = {2015}
}