UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

A primal dual active set with continuation algorithm for the l0-regularized optimization problem

Jiao, Y; Jin, B; Lu, X; (2015) A primal dual active set with continuation algorithm for the l0-regularized optimization problem. Applied and Computational Harmonic Analysis , 39 (3) pp. 400-426. 10.1016/j.acha.2014.10.001. Green open access

[thumbnail of pdasc_revised.pdf]
Preview
Text
pdasc_revised.pdf
Available under License : See the attached licence file.

Download (698kB)

Abstract

We develop a primal dual active set with continuation algorithm for solving the ℓ0-regularized least-squares problem that frequently arises in compressed sensing. The algorithm couples the primal dual active set method with a continuation strategy on the regularization parameter. At each inner iteration, it first identifies the active set from both primal and dual variables, and then updates the primal variable by solving a (typically small) least-squares problem defined on the active set, from which the dual variable can be updated explicitly. Under certain conditions on the sensing matrix, i.e., mutual incoherence property or restricted isometry property, and the noise level, a finite step global convergence of the overall algorithm is established. Extensive numerical examples are presented to illustrate the efficiency and accuracy of the algorithm and its convergence behavior.

Type: Article
Title: A primal dual active set with continuation algorithm for the l0-regularized optimization problem
Open access status: An open access version is available from UCL Discovery
DOI: 10.1016/j.acha.2014.10.001
Publisher version: http://dx.doi.org/10.1016/j.acha.2014.10.001
Language: English
Additional information: This is the author’s version of a work that was accepted for publication in Applied and Computational Harmonic Analysis. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Applied and Computational Harmonic Analysis, http://dx.doi.org/10.1016/j.acha.2014.10.001
Keywords: Primal dual active set algorithm, Coordinatewise minimizer, Continuation strategy, Global convergence
UCL classification: UCL
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science
URI: https://discovery.ucl.ac.uk/id/eprint/1452209
Downloads since deposit
49Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item