I. Dassios K. Fountoulakis and J. Gondzio
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.
Key words: compressed sensing, L1-regularization, total variation, second-order methods, perturbation analysis.