Approximation Algorithms for Model-Based Compressive Sensing

Chinmay Hegde, Piotr Indyk, Ludwig Schmidt

    Research output: Contribution to journalArticlepeer-review


    Compressive sensing (CS) states that a sparse signal can be recovered from a small number of linear measurements, and that this recovery can be performed efficiently in polynomial time. The framework of model-based CS (model-CS) leverages additional structure in the signal and provides new recovery schemes that can reduce the number of measurements even further. This idea has led to measurement-efficient recovery schemes for a variety of signal models. However, for any given model, model-CS requires an algorithm that solves the model-projection problem: given a query signal, report the signal in the model that is closest to the query signal. Often, this optimization can be computationally very expensive. Moreover, an approximation algorithm is not sufficient for this optimization to provably succeed. As a result, the model-projection problem poses a fundamental obstacle for extending model-CS to many interesting classes of models. In this paper, we introduce a new framework that we call approximation-tolerant model-CS. This framework includes a range of algorithms for sparse recovery that require only approximate solutions for the model-projection problem. In essence, our work removes the aforementioned obstacle to model-CS, thereby extending model-CS to a much wider class of signal models. Interestingly, all our algorithms involve both the minimization and the maximization variants of the model-projection problem. We instantiate this new framework for a new signal model that we call the constrained earth mover distance (CEMD) model. This model is particularly useful for signal ensembles, where the positions of the nonzero coefficients do not change significantly as a function of spatial (or temporal) location. We develop novel approximation algorithms for both the maximization and the minimization versions of the model-projection problem via graph optimization techniques. Leveraging these algorithms and our framework results in a nearly sample-optimal sparse recovery scheme for the CEMD model.

    Original languageEnglish (US)
    Article number7161330
    Pages (from-to)5129-5147
    Number of pages19
    JournalIEEE Transactions on Information Theory
    Issue number9
    StatePublished - Sep 1 2015


    • Compressed sensing
    • approximation algorithms
    • combinatorial optimization

    ASJC Scopus subject areas

    • Information Systems
    • Computer Science Applications
    • Library and Information Sciences


    Dive into the research topics of 'Approximation Algorithms for Model-Based Compressive Sensing'. Together they form a unique fingerprint.

    Cite this