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.

Présenté à:
2015 IEEE Internation Symposium on Information Theory, Hong Kong, China, June 14-19, 2015

 Notice créée le 2015-05-12, modifiée le 2018-03-17

Télécharger le document

Évaluer ce document:

Rate this document:
(Pas encore évalué)