Optimization Online


Phase Transitions for Greedy Sparse Approximation Algorithms

Jeffrey Blanchard(jeff***at***math.grinnell.edu)
Coralia Cartis(coralia.cartis***at***ed.ac.uk)
Jared Tanner(jared.tanner***at***ed.ac.uk)
Andrew Thompson (a.thompson-8***at***sms.ed.ac.uk)

Abstract: A major enterprise in compressed sensing and sparse approximation is the design and analysis of computationally tractable algorithms for recovering sparse, exact or approximate, solutions of underdetermined linear systems of equations. Many such algorithms have now been proven using the ubiquitous Restricted Isometry Property (RIP) [9] to have optimal-order uniform recovery guarantees. However, it is unclear when the RIP-based sufficient conditions on the algorithm are satisfied. We present a framework in which this task can be achieved; translating these conditions for Gaussian measurement matrices into requirements on the signalís sparsity level, size and number of measurements. We illustrate this approach on three of the state-of-the-art greedy algorithms: CoSaMP [27], Subspace Pursuit (SP) [11] and Iterated Hard Thresholding (IHT) [6]. Designed to allow a direct comparison of existing theory, our framework implies that IHT, the lowest of the three in computational cost, also requires fewer compressed sensing measurements than CoSaMP and SP.

Keywords: Compressed sensing, sparse approximation, restricted isometry property, phase transitions

Category 1: Applications -- Science and Engineering

Citation: Technical Report, School of Mathematics, University of Edinburgh, 2009

Download: [PDF]

Entry Submitted: 08/28/2009
Entry Accepted: 08/28/2009
Entry Last Modified: 08/28/2009

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 Programming Society