Kernel matching pursuit is a greedy algorithm for building an approximation of a discriminant function as a linear combination of some basis functions selected from a kernel-induced dictionary. Here we propose a modification of the kernel matching pursuit algorithm that aims at making the method practical for large datasets. Starting from an approximating algorithm, the weak greedy algorithm, we introduce a stochastic method for reducing the search space at each iteration. Then we study the implications of using an approximate algorithm and we show how one can control the trade-off between the accuracy and the need for resources. Finally, we present some experiments performed on a large dataset that support our approach and illustrate its applicability.
Matthieu Wyart, Carolina Brito Carvalho dos Santos
Fabio Nobile, Yoshihito Kazashi, Fabio Zoccolan
Paolo Ricci, Justin Richard Ball, Louis Nicolas Stenger, Rogério Manuel Cabete De Jesus Jorge, Baptiste Jimmy Frei, Antoine Cyril David Hoffmann