Approximation-tolerant model-based compressive sensing

Chinmay Hegde, Piotr Indyk, Ludwig Schmidt

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    The goal of sparse recovery is to recover a k-sparse signal x ∈ R n from (possibly noisy) linear measurements of the form y = Ax, where A ∈ Rm×n describes the measurement process. Standard results in compressive sensing show that it is possible to recover the signal x from m = O(k log(n/k)) measurements, and that this bound is tight. The framework of model-based, compressive sensing [BCDH10J overcomes the lower bound and reduces the number of measurements further to O(k) by limiting the supports of x to a subset M of the (n k)possible supports. This has led to many measurement-efficient algorithms for a wide variety of signal models, including block-sparsity and tree-sparsity. Unfortunately, extending the framework to other, more general models has been stymied by the following obstacle: for the framework to apply, one needs an algorithm that, given a signal x, solves the following optimization problem exactly : Arg min Ω ∈ M||x[n]\Ω||2 (here x[n]\Ω denotes the projection of x on coordinates not in Ω). However, an approximation algorithm for this optimization task is not sufficient. Since many problems of this form are not known to have exact polynomial- Time algorithms, this requirement poses an obstacle for extending the framework to a richer class of models. In this paper, we remove this obstacle and show how to extend the model-based compressive sensing framework so that it requires only approximate solutions to the aforementioned optimization problems. Interestingly, our extension requires the existence of approximation algorithms for both the maximization and the minimization variants of the optimization problem. Further, we apply our framework to the Constrained Earth Mover's Distance (CEMD) model introduced in (SHI13], obtaining a sparse recovery scheme that uses significantly less than O(k log(n/k)) measurements. This is the first non-trivial theoretical bound for this model, since the validation of the approach presented in [SHI13) was purely empirical. The result is obtained by designing a novel approximation algorithm for the maximization version of the problem and proving approximation guarantees for the minimization algorithm described ISHI131.

    Original languageEnglish (US)
    Title of host publicationProceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014
    PublisherAssociation for Computing Machinery
    Number of pages18
    ISBN (Print)9781611973389
    StatePublished - 2014
    Event25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014 - Portland, OR, United States
    Duration: Jan 5 2014Jan 7 2014

    Publication series

    NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms


    Other25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014
    Country/TerritoryUnited States
    CityPortland, OR

    ASJC Scopus subject areas

    • Software
    • General Mathematics


    Dive into the research topics of 'Approximation-tolerant model-based compressive sensing'. Together they form a unique fingerprint.

    Cite this