Sparse Group Covers and Greedy Tree Approximations

We consider the problem of finding a K-sparse approximation of a signal, such that the support of the approximation is the union of sets from a given collection, a.k.a. group structure. This problem subsumes the one of finding K-sparse tree approximations. We discuss the tractability of this problem, present a polynomial-time dynamic program for special group structures and propose two novel greedy algorithms with efficient implementations. The first is based on submodular function maximization with knapsack constraints. For the case of tree sparsity, its approximation ratio of 1-1/e is better than current state-of-the-art approximate algorithms. The second algorithm leverages ideas from the greedy algorithm for the Budgeted Maximum Coverage problem and obtains excellent empirical performance, shown by computing the full Pareto frontier of the tree approximations of the wavelet coefficients of an image.


Presented at:
2015 IEEE Internation Symposium on Information Theory, Hong Kong, China, June 14-19, 2015
Year:
2015
Keywords:
Laboratories:




 Record created 2015-05-12, last modified 2018-03-17

Preprint:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)