Title: Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection

Authors: A. Das and D. Kempe


We study the problem of selecting a subset of k random variables from a large set, in order to obtain the best linear prediction of another vari- able of interest. This problem can be viewed in the context of both feature selection and sparse approximation. We analyze the performance of widely used greedy heuristics, using insights from the maximization of submodular functions and spectral analysis. We introduce the submod- ularity ratio as a key quantity to help understand why greedy algorithms perform well even when the variables are highly correlated. Using our techniques, we obtain the strongest known ap- proximation guarantees for this problem, both in terms of the submodularity ratio and the small- est k-sparse eigenvalue of the covariance ma- trix. We also analyze greedy algorithms for the dictionary selection problem, and significantly improve the previously known guarantees. Our theoretical analysis is complemented by experi- ments on real-world and synthetic data sets; the experiments show that the submodularity ratio is a stronger predictor of the performance of greedy algorithms than other spectral parameters.

Full Text: [PDF]

Accessibility at Yale   Inference, Information, and Decision Group at Yale