%Krause ICML2010 - Submodular dictionary selection for sparse representation.pdf

Submodular Dictionary Selection for Sparse Representation Andreas Krause krausea@caltech.edu California Institute of Technology, Computing and Mathematical Sciences Department Volkan Cevher volkan.cevher@{epfl,idiap}.ch Ecole Polytechnique Federale de Lausanne, STI-IEL-LIONS Idiap Research Institute Abstract We develop an efficient learning framework to construct signal dictionaries for sparse represen- tation by selecting the dictionary columns from multiple candidate bases. By sparse, we mean that only a few dictionary elements, compared to the ambient signal dimension, can exactly repre- sent or well-approximate the signals of interest. We formulate both the selection of the dictionary columns and the sparse representation of signals as a joint combinatorial optimization problem. The proposed combinatorial objective maximizes variance reduction over the set of training signals by constraining the size of the dictionary as well as the number of dictionary columns that can be used to represent each signal. We show that if the available dictionary column vectors are inco- herent, our objective function satisfies approxi- mate submodularity. We exploit this property to develop SDSOMP and SDSMA, two greedy algo- rithms with approximation guarantees. We also describe how our learning framework enables dic- tionary selection for structured sparse represen- tations, e.g., where the sparse coefficients occur in restricted patterns. We evaluate our approach on synthetic signals and natural images for rep- resentation and inpainting problems. 1. Introduction An important problem in machine learning, signal pro- cessing and computational neuroscience is to deter- mine a dictionary of basis functions for sparse rep- resentation of signals. A signal y ∈ Rd has a sparse representation with y = Dα in a dictionary D ∈ Rd×n, when k  d coefficients of α can exactly represent or well-approximate y. Myriad applications in data anal- ysis and processing–from deconvolution to data mi