DocumentCode :
3663049
Title :
Sparse group covers and greedy tree approximations
Author :
Siddhartha Satpathi;Luca Baldassarre;Volkan Cevher
Author_Institution :
Indian Institute of Technology, Kharagpur - India
fYear :
2015
fDate :
6/1/2015 12:00:00 AM
Firstpage :
551
Lastpage :
555
Abstract :
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.
Keywords :
"Approximation methods","Greedy algorithms","Algorithm design and analysis","Approximation algorithms","Heuristic algorithms","Time complexity"
Publisher :
ieee
Conference_Titel :
Information Theory (ISIT), 2015 IEEE International Symposium on
Electronic_ISBN :
2157-8117
Type :
conf
DOI :
10.1109/ISIT.2015.7282515
Filename :
7282515
Link To Document :
بازگشت