Convergence of an inertial proximal method for l1-regularized least-squares

Patrick R. Johnstone, Pierre Moulin

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

A fast, low-complexity, algorithm for solving the ℓ1-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 ℓ1-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.

Original languageEnglish (US)
Title of host publication2015 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2015 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages3566-3570
Number of pages5
ISBN (Electronic)9781467369978
DOIs
StatePublished - Aug 4 2015
Event40th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2015 - Brisbane, Australia
Duration: Apr 19 2014Apr 24 2014

Publication series

NameICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings
Volume2015-August
ISSN (Print)1520-6149

Other

Other40th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2015
CountryAustralia
CityBrisbane
Period4/19/144/24/14

Keywords

  • Inertial forward-backward proximal splitting
  • compressed sensing
  • deconvolution
  • gradient descent with momentum
  • heavy ball method

ASJC Scopus subject areas

  • Software
  • Signal Processing
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Convergence of an inertial proximal method for l<sub>1</sub>-regularized least-squares'. Together they form a unique fingerprint.

Cite this