Optimization Online


Matrix-free Interior Point Method for Compressed Sensing Problems

Kimon Fountoulakis (K.Fountoulakis***at***sms.ed.ac.uk)
Jacek Gondzio (J.Gondzio***at***ed.ac.uk)
Pavel Zhlobich (P.Zhlobich***at***ed.ac.uk)

Abstract: 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, l1 ls, 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(n^3) computational complexity. Attempts have been made to specialize IPMs to sparse reconstruction problems and they have led to interesting developments implemented in l1 ls and PDCO softwares. We go a few steps further. First, we use the matrix-free 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.

Keywords: Matrix-free Interior Point, Preconditioned Conjugate Gradient, Compressed Sensing, Compressive Sampling, l1-regularization

Category 1: Applications -- Science and Engineering

Citation: Technical Report ERGO 12-006, School of Mathematics and Maxwell Institute, The University of Edinburgh, Mayfield Road, Edinburgh EH9 3JZ, United Kingdom, June/2012

Download: [PDF]

Entry Submitted: 08/27/2012
Entry Accepted: 08/27/2012
Entry Last Modified: 11/16/2013

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