Nonlinear Dimensionality Reduction by Semidefinite Programming and Kernel Matrix Factorization.
Kilian Q. Weinberger, Benjamin Packer, Lawrence K. Saul · 2005
We describe an algorithm for nonlinear dimensionality reduction based on semidefinite programming and kernel matrix factorization. The algorithm learns a kernel matrix for high dimensional data that lies on or near a low dimensional manifold. In earlier work, the kernel matrix was learned by maximizing the variance in feature space while preserving the distances and angles between nearest neighbors. In this paper, adapting recent ideas from semi-supervised learning on graphs, we show that the full kernel matrix can be very well approximated by a product of smaller matrices. Representing the kernel matrix in this way, we can reformulate the semidefinite program in terms of a much smaller submatrix of inner products between randomly chosen landmarks. The new framework leads to order-of-magnitude reductions in computation time and makes it possible to study much larger problems in manifold learning. 1
Cited by 150 works.
Authors
References
- Nonlinear Dimensionality Reduction by Locally Linear Embedding
- A Global Geometric Framework for Nonlinear Dimensionality Reduction
- Nonlinear Component Analysis as a Kernel Eigenvalue Problem
- An Introduction to Support Vector Machines
- Laplacian Eigenmaps for Dimensionality Reduction and Data Representation
- Semidefinite Programming
- Semi-supervised learning using Gaussian fields and harmonic functions
- Learning with Local and Global Consistency
- A database for handwritten text recognition research
- Partially labeled classification with Markov Random Walks