Sparse Greedy Matrix Approximation for Machine Learning

In kernel based methods such as Regularization Networks large datasets pose signi- cant problems since the number of basis functions required for an optimal solution equals the number of samples. We present a sparse greedy approximation technique to construct a compressed representation of the design matrix. Experimental results are given and connections to Kernel-PCA, Sparse Kernel Feature Analysis, and Matching Pursuit are pointed out. 1. Introduction Many recent advances in machine learning such as Support Vector Machines Vapnik, 1995, Regularization Networks Girosi et al., 1995, or Gaussian Processes Williams, 1998 are based on kernel methods. Given an m-sample f(x 1 ; y 1 ); : : : ; (x m ; y m )g of patterns x i 2 X and target values y i 2 Y these algorithms minimize the regularized risk functional min f2H R reg f = 1 m m X i=1 c(x i ; y i ; f(x i )) + 2 kfk 2 H : (1) Here H denotes a reproducing kernel Hilbert space (RKHS) Aronszajn, 1950,...