Optimization Online


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

Ioannis Dassios (idassios***at***ed.ac.uk)
Kimon Fountoulakis (K.Fountoulakis***at***sms.ed.ac.uk)
Jacek Gondzio (J.Gondzio***at***ed.ac.uk)

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.

Keywords: compressed sensing, l1-analysis, total-variation, second-order methods, perturbation analysis

Category 1: Convex and Nonsmooth Optimization

Category 2: Nonlinear Optimization (Unconstrained Optimization )

Category 3: Applications -- Science and Engineering

Citation: Technical Report ERGO-14-007

Download: [PDF]

Entry Submitted: 05/16/2014
Entry Accepted: 05/16/2014
Entry Last Modified: 05/30/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society