  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.
