Improved Nyström Low-rank Approximation for

Scalable Manifold Learning

Manifold learning (or dimension reduction) algorithms rely heavily on the eigenvalue decomposition of the kernel matrix. The cubical complexity is a big hindrance to large scale problems. The Nyström method [1,2] is a popular sampling-based approach for computing large scale kernel eigen-systems. However, the optimal sampling is still an open problem.

We find that the Nyström low-rank approximation quality depends crucially on the encoding powers of the landmak points in representing the data . Our error analysis suggests the use of k-means clustering centers as the landmark points. We call this Improved Nyström low-rank approximation and apply it to several important manifold learning algorithms, i.e., kernel PCA, Laplacian Eigenmap, and Multidimensional Scaling. The matlab codes can be downloaded here. A brief summary is as follows.

Table1: Improved Nyström low-rank approximation for manifold learning and dimension reduction.

 Algorithms Matlab function Specifications Kernel PCA V = INys_KPCA(data, kernel, m ); V: top m eigenvectors/embeddings computed; data: n-by-dim dta matrix; kernel: kernel.type: 'pol' or 'rbf';              kernel.para: d in the polynomial kernel ^d;                                     b in the rbf kernel exp(-||x||^2/b); m: number of landmark points (m << n). Laplacian Eigenmap    Spectral Clustering Normalized Cut V = INys_SpectrEmbed(data, kernel, m ); Multi-dimensional Scaling V = INys_MDS(data, m );

Results: all results are computed by using only m = 30 landmark points. Codes are in matlab (not fully optimized) and run on a core(TM)-dual PC with 2.13GHz CPU.

 Data1: IJCNN1 (100000 x 22) Data2: MNIST digit1 (6742 x 784) Data3: Isomap face image (4096 x 698)   Kernel PCA  3.7sec Kernel PCA  3.8sec Kernel PCA  3.5sec   Laplacian Eigenmap  3.5sec Laplacian Eigenmap  4.1sec Laplacian Eigenmap  4.3sec   Multidimensional Scaling  3.7sec Multidimensional Scaling  2.5sec Multidimensional Scaling  1.4sec

Reference

 C. Fowlkes, S. Belongie, F. Chung, and J. Malik. Spectral grouping using the Nyström method. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(2):214–225, 2004.

 C. Williams, M, Seeger. Using the Nyström method to speed up kernel machines. Advances in Neural Information Processing Systems 13 (pp. 682 – 688), 2001.

 K. Zhang, I. Tsang, J. Kwok. Improved Nyström Low Rank Approximation and Error Analysis. In the 25th International Conference on Machine Learning (ICML 2008).