Matrix-free Interior Point Method for Compressed Sensing Problems / A Second order Method for Compressed Sensing with Coherent and Redundant Dictionaries - implementation -

Kimon Fountoulakis sent me the following:

Dear Igor, 

I would like to inform you about two recent papers that we have written with I. Dassios, J. Gondzio and P. Zhlobich. Both papers discuss some new algorithms for compressed sensing (they use the 2nd-order methods with inexact search directions computed by the Krylov subspace methods).

The first paper: 

http://link.springer.com/article/10.1007/s12532-013-0063-6#page-1 

or 

http://www.maths.ed.ac.uk/~gondzio/reports/mfCS.pdf 

focuses on the solution of the synthesis formulation using a primal-dual interior point method with a provably effective preconditioning technique. The software for this algorithm as well as scripts that reproduce the numerical experiments can be found  in the following link: 

http://www.maths.ed.ac.uk/ERGO/mfipmcs/ 

The second paper: 

http://www.maths.ed.ac.uk/~gondzio/reports/2ndOrderCS.pdf 

focuses on the solution of the analysis formulation for coherent and redundant dictionaries using a primal-dual Newton conjugate gradients method. It provides convergence analysis and suggests a provably effective preconditioning technique. The software for the algorithm and the scripts that reproduce the numerical experiments can be found in: 

http://www.maths.ed.ac.uk/ERGO/pdNCG/ 

Our aim was to develop robust algorithms that can manage even pathological cases with the minimum computational cost. Higher-order methods provide such safeguards but with the cost of slightly higher computational effort per iteration. We show that an approximate 2nd order information can be used, even for large scale problems, and the resulting algorithms deliver an approximate solution in competitive time. Occasionally they are faster than the best first-order methods. 

All the best,

Kimon

=================

Kimon Fountoulakis

School of Mathematics

The University of Edinburgh

James Clerk Maxwell Building

King's Buildings, EH9 3JZ Edinburgh, UK.

E-mail: K.Fountoulakis@sms.ed.ac.uk

Website: http://www.maths.ed.ac.uk/~kfount/

here are the papers: Matrix-free Interior Point Method for Compressed Sensing Problems by Kimon Fountoulakis, Jacek Gondzio, Pavel Zhlobich

We consider a class of optimization problems for sparse signal reconstruction which arise in the field of Compressed Sensing (CS). A plethora of approaches and solvers exist for such problems, for example GPSR, FPC AS, SPGL1, NestA, `1 `s, PDCO to mention a few. CS applications lead to very well conditioned optimization problems and therefore can be solved easily by simple first-order methods. Interior point methods (IPMs) rely on the Newton method hence they use the second-order information. They have numerous advantageous features and one clear drawback: being the second-order approach they need to solve linear equations and this operation has (in the general dense case) an O(n3) computational complexity. Attempts have been made to specialize IPMs to sparse reconstruction problems and they have led to interesting developments implemented in `1 `s and PDCO softwares. We go a few steps further. First, we use the matrixfree IPM, an approach which redesigns IPM to avoid the need to explicitly formulate (and store) the Newton equation systems. Secondly, we exploit the special features of the signal processing matrices within the matrix-free IPM. Two such features are of particular interest: an excellent conditioning of these matrices and the ability to perform inexpensive (low complexity) matrix-vector multiplications with them. Computational experience with large scale one-dimensional signals confirms that the new approach is efficient and compares favorably with other
state-of-the-art solvers on certain problems.

A Second order Method for Compressed Sensing with Coherent and Redundant Dictionaries by Ioannis Dassios, Kimon Fountoulakis, and Jacek 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 speciaized 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.

Join the CompressiveSensing subreddit or the Google+ Community and post there !

Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.