A Second-Order Method for Compressed Sensing Problems with Coherent and Redundant Dictionaries

John Dassios, Kimon Fountoulakis, Jacek Gondzio

Research output: Working paper

Abstract

In this paper we are interested in the solution of Compressed Sensing (CS)
problems where the signals to be recovered are sparse in coherent and
redundant dictionaries. CS problems of this type are convex with non-smooth
and non-separable regularization term, therefore a specialized solver
is required. We propose a primal-dual Newton Conjugate Gradients (pdNCG)
method.
We prove global convergence and fast local rate of convergence for pdNCG.
Moreover, well-known properties of CS problems are exploited for the
development of provably effective preconditioning techniques that speed-up
the approximate solution of linear systems which arise. Numerical results
are presented on CS problems which demonstrate the performance of pdNCG
compared to a state-of-the-art existing solver.
Original languageEnglish
Place of PublicationSchool of Mathematics
Number of pages26
Publication statusPublished - 16 May 2014

Publication series

NameERGO Technical Report

Keywords

  • compressed sensing, L1-regularization, total variation, second-order methods, perturbation analysis.

Fingerprint

Dive into the research topics of 'A Second-Order Method for Compressed Sensing Problems with Coherent and Redundant Dictionaries'. Together they form a unique fingerprint.

Cite this