A fast approximation algorithm for tree-sparse recovery

Chinmay Hegde, Piotr Indyk, Ludwig Schmidt

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

    Abstract

    Sparse signals whose nonzeros obey a tree-like structure occur in a range of applications such as image modeling, genetic data analysis, and compressive sensing. An important problem encountered in recovering signals is that of optimal tree-projection, i.e., finding the closest tree-sparse signal for a given query signal. However, this problem can be computationally very demanding: for optimally projecting a length-n signal onto a tree with sparsity k, the best existing algorithms incur a high runtime of O(nk). This can often be impractical. We suggest an alternative approach to tree-sparse recovery. Our approach is based on a specific approximation algorithm for tree-projection and provably has a near-linear runtime of O(n log(kr)) and a memory cost of O(n), where r is the dynamic range of the signal. We leverage this approach in a fast recovery algorithm for tree-sparse compressive sensing that scales extremely well to high-dimensional datasets. Experimental results on several test cases demonstrate the validity of our approach.

    Original languageEnglish (US)
    Title of host publication2014 IEEE International Symposium on Information Theory, ISIT 2014
    PublisherInstitute of Electrical and Electronics Engineers Inc.
    Pages1842-1846
    Number of pages5
    ISBN (Print)9781479951864
    DOIs
    StatePublished - 2014
    Event2014 IEEE International Symposium on Information Theory, ISIT 2014 - Honolulu, HI, United States
    Duration: Jun 29 2014Jul 4 2014

    Publication series

    NameIEEE International Symposium on Information Theory - Proceedings
    ISSN (Print)2157-8095

    Other

    Other2014 IEEE International Symposium on Information Theory, ISIT 2014
    CountryUnited States
    CityHonolulu, HI
    Period6/29/147/4/14

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Information Systems
    • Modeling and Simulation
    • Applied Mathematics

    Fingerprint Dive into the research topics of 'A fast approximation algorithm for tree-sparse recovery'. Together they form a unique fingerprint.

  • Cite this

    Hegde, C., Indyk, P., & Schmidt, L. (2014). A fast approximation algorithm for tree-sparse recovery. In 2014 IEEE International Symposium on Information Theory, ISIT 2014 (pp. 1842-1846). [6875152] (IEEE International Symposium on Information Theory - Proceedings). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT.2014.6875152