### 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 language | English (US) |
---|---|

Title of host publication | 2014 IEEE International Symposium on Information Theory, ISIT 2014 |

Publisher | Institute of Electrical and Electronics Engineers Inc. |

Pages | 1842-1846 |

Number of pages | 5 |

ISBN (Print) | 9781479951864 |

DOIs | |

State | Published - 2014 |

Event | 2014 IEEE International Symposium on Information Theory, ISIT 2014 - Honolulu, HI, United States Duration: Jun 29 2014 → Jul 4 2014 |

### Publication series

Name | IEEE International Symposium on Information Theory - Proceedings |
---|---|

ISSN (Print) | 2157-8095 |

### Other

Other | 2014 IEEE International Symposium on Information Theory, ISIT 2014 |
---|---|

Country | United States |

City | Honolulu, HI |

Period | 6/29/14 → 7/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

*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