Abstract: Our goal is to improve the training and prediction time of Nystrom method, which is a widely-used technique for generating low-rank kernel matrix approximations. When applying the Nystrom approximation for large-scale applications, both training and prediction time is
dominated by computing kernel values between a data point and all landmark points. With m landmark points, this computation requires O(md) time (flops), where d is the input dimension. In this paper, we propose the use of a family of fast transforms to generate structured landmark
points for Nystrom approximation. By exploiting fast transforms, e.g., Haar transform and Hadamard transform, our modified Nystrom method requires only O(m) or O(mlog d) time to compute the kernel values between a given data point m landmark points. This improvement in time complexity can significantly speed up kernel approximation and benefit prediction speed in kernel machines. For instance, on the webspam data (more than 300,000 data points), our proposed algorithm enables kernel SVM prediction to deliver 98% accuracy and the resulting
prediction time is 1000 times faster than LIBSVM and only 10 times slower than linear SVM prediction (which yields only 91% accuracy).
Download: pdf, slides
Citation
- Computationally Efficient Nystrom Approximation using Fast Transforms (pdf, slides, software)
S. Si, C. Hsieh, I. Dhillon.
In International Conference on Machine Learning (ICML), pp. 2655-2663, June 2016.
Bibtex: