TY - GEN

T1 - A fast approximation algorithm for tree-sparse recovery

AU - Hegde, Chinmay

AU - Indyk, Piotr

AU - Schmidt, Ludwig

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84906569134&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84906569134&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2014.6875152

DO - 10.1109/ISIT.2014.6875152

M3 - Conference contribution

AN - SCOPUS:84906569134

SN - 9781479951864

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 1842

EP - 1846

BT - 2014 IEEE International Symposium on Information Theory, ISIT 2014

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2014 IEEE International Symposium on Information Theory, ISIT 2014

Y2 - 29 June 2014 through 4 July 2014

ER -