Edinburgh Research Explorer

Phase transitions for greedy sparse approximation algorithms

Research output: Contribution to journalArticle

Related Edinburgh Organisations

Open Access permissions



Original languageEnglish
Pages (from-to)188-203
Number of pages16
JournalApplied and Computational Harmonic Analysis
Issue number2
Publication statusPublished - Mar 2011


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 to have optimal-order uniform recovery guarantees using the ubiquitous Restricted Isometry Property (RIP) (Candes and Tao (2005) [11]). However, without specifying a matrix, or class of matrices, it is unclear when the RIP-based sufficient conditions on the algorithm are satisfied. Bounds on RIP constants can be inserted into the algorithms RIP-based conditions, translating the conditions into requirements on the signal's sparsity level, length, and number of measurements. We illustrate this approach for Gaussian matrices on three of the state-of-the-art greedy algorithms: CoSaMP (Needell and Tropp (2009) [29]), Subspace Pursuit (SP) (Dai and Milenkovic (2009) [13]) and Iterative Hard Thresholding (IHT) (Blumensath and Davies (2009) [8]). Designed to allow a direct comparison of existing theory, our framework implies that, according to the best available analysis on these three algorithms, IHT requires the fewest number of compressed sensing measurements, has the best proven stability bounds, and has the lowest per iteration computational cost. (C) 2010 Elsevier Inc. All rights reserved.

    Research areas

  • Compressed sensing, Greedy algorithms, Sparse solutions to underdetermined systems, Restricted isometry property, Phase transitions, Gaussian matrices, INVERSE PROBLEMS, SIGNAL RECOVERY, RECONSTRUCTION, PURSUIT, PROJECTION, POLYTOPES, DIMENSION, EQUATIONS, SYSTEMS

Download statistics

No data available

ID: 543705