FoCM 2014 conference

Workshop C4 - Numerical Linear Algebra

December 19, 18:00 ~ 18:30 - Room B11

Approximation with cross-kernel matrices, and Ideal PCA

Franz Király

University College London, United Kingdom   -

We describe how cross-kernel matrices, that is, kernel matrices between the data and a custom chosen set of `feature spanning points' can be used for learning. At the core is a Nyström-type relation which allows to numerically approximate kernel matrices in terms of cross-kernel matrices. We demonstrate how cross-kernel matrices (A) provide a universal speed-up of kernel learning algorithms through replacing kernel matrices with cross-kernel matrices that scale linearly in the data, and (B) allow learning of features which approximately vanish on the data. We further give an algorithm, called ideal principal component analysis (IPCA), which we derive as the cross-kernel variant of kernel PCA, serving as an exemplification of both the new features and the speed-up to linear runtime. We conclude with some open questions regarding the approximating properties of cross-kernel matrices.

Joint work with Louis Theran, Martin Kreuzer.

View abstract PDF