Abstract

This paper addresses the issue of numerical computation in machine learning domains where one needs to evaluate similarity metrics. Examples of these domains include dimensionality reduction with kernels, spectral clustering and Gaussian processes. The paper presents a solution strategy based on Krylov subspace iteration and fast N-body learning methods. The main benefit of this strategy is that it is very general and easy to adapt to new domains involving similarity metrics. The experiments show significant gains in computation and storage on datasets arising in image segmentation, object detection and dimensionality reduction. The paper also presents theoretical bounds on the stability of these iterative methods.