A fast approximation algorithm for tree-sparse recovery

Chinmay Hegde, Piotr Indyk, Ludwig Schmidt

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


    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.
    Number of pages5
    ISBN (Print)9781479951864
    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


    Other2014 IEEE International Symposium on Information Theory, ISIT 2014
    Country/TerritoryUnited States
    CityHonolulu, HI

    ASJC Scopus subject areas

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


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

    Cite this