## 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.

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 language | English |
---|---|

Place of Publication | School of Mathematics |

Number of pages | 26 |

Publication status | Published - 16 May 2014 |

### Publication series

Name | ERGO Technical Report |
---|

## Keywords

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