Improved Nystrom Kernel Low-rank Approximation

efficient, self-complete implementation of improved Nystrom low-rank approximation

Matlab Package for Improved Nystrom Low-rank Approximation
Kai Zhang {[e-mail]}

Introduction

This package is a matlab implementation of the improved Nystrom Low-rank approximation that is widely used in large scale machine learning and data mining problems. The package does not require any specific function, toolbox, or library.

The Improved Nystrom method uses K-means clustering centers as the landmark points, which can greatly improve approximation quality of the kernel matrix. Efficiency of the kmeans step therefore should be taken into account. Considering that the kmeans function in matlab is very inefficient, I wrote a faster one (eff_kmeans.m); the number of K-means iterations should be a small number, e.g. 5.

The main features of this LLSVM include:
1. Improved Nystrom low-rank approximation of kernel matrix (RBF, linear, or polynomial kernel)
2. Large scale KPCA, Laplacian Eigenmap / spectral clustering, and MDS via improved Nystrom low-rank approximation
If you have any suggestion or bug findings, please email to [e-mail]. Thank you!

Citations

Kai Zhang, Ivor W. Tsang, James T. Kwok. Improved Nystrom Low Rank Approximation and Error Analysis. In the 25th International Conference on Machine Learning (ICML 2008), Helsinki, Finland, June 2008.

Kai Zhang and James T. Kwok, Clustered Nyström Method for Large Scale Manifold Learning and Dimension Reduction, IEEE Transactions on Neural Networks, Volume: 21 , Issue: 10 Page(s): 1576 - 1587, 2010.

Copyright: All rights reserved by the author.

How to Use
Usage: simply run demo.m to see the results.