A kernel view of the dimensionality reduction of manifolds

ABSTRACT

We interpret several well-known algorithms for dimensionality reduction of manifolds as kernel methods. Isomap, graph Laplacian eigenmap, and locally linear embedding (LLE) all utilize local neighborhood information to construct a global embedding of the manifold. We show how all three algorithms can be described as kernel PCA on specially constructed Gram matrices, and illustrate the similarities and differences between the algorithms with representative examples.

REFERENCES

• 1: Aldous, D., & Fill, J. (2002). Reversible Markov chains and random walks on graphs. In preparation.
• 2: Mikhail Belkin , Partha Niyogi, Laplacian Eigenmaps for dimensionality reduction and data representation, Neural Computation, v.15 n.6, p.1373-1396, June 2003 [doi>10.1162/089976603321780317]
• 3: Bengio, Y., Paiement, J.-F., & Vincent, P. (2004). Out-of-sample extension for lle, isomap, mds, eigenmaps, and spectral clustering. Advances in Neural Information Processing Systems 15. MIT Press.
• 4: Fan Chung , S.-T. Yau, Discrete Green's functions, Journal of Combinatorial Theory Series A, v.91 n.1-2, p.191-214, July-Aug. 2000 [doi>10.1006/jcta.2000.3094]
• 5: Cox, T., & Cox, M. (1994). Multidimensional scaling. London: Chapman and Hall.
• 6: de Silva, V., & Tenenbaum, J. (2002). Global versus local methods in nonlinear dimensionality reduction. Advances in Neural Information Processing Systems, 15.
• 7: Grimes, C., & Donoho, D. (2002). When does isomap recover the natural parameterization of families of articulated images? (Technical Report 27). Stanford University.
• 8: Risi Imre Kondor , John D. Lafferty, Diffusion Kernels on Graphs and Other Discrete Input Spaces, Proceedings of the Nineteenth International Conference on Machine Learning, p.315-322, July 08-12, 2002
• 9: Roweis, S., & Saul, L. (2000). Nonlinear dimensionality reduction by locally linear embedding. Science, 290, 2323--2326.
• 10: Bernhard Schölkopf , Alexander Smola , Klaus-Robert Müller, Nonlinear component analysis as a kernel eigenvalue problem, Neural Computation, v.10 n.5, p.1299-1319, July 1, 1998 [doi>10.1162/089976698300017467]
• 11: Schölkpf, B., & Smola, A. J. (2002). Learning with kernels. Cambridge, MA: MIT Press.
• 12: Tenenbaum, J., de Silva, V., & Langford, J. (2000). A global geometric framework for nonlinear dimensionality reduction. Science, 290, 2319--2323.
• 13: Yair Weiss, Segmentation Using Eigenvectors: A Unifying View, Proceedings of the International Conference on Computer Vision-Volume 2, p.975, September 20-25, 1999
• 14: Williams, C. K. I. (2001). On a connection between kernel PCA and metric multidimensional scaling. Advances in Neural Information Processing Systems 13. MIT Press.