Fei Sha
ABSTRACT
Many unsupervised algorithms for nonlinear dimensionality reduction, such as locally linear embedding (LLE) and Laplacian eigenmaps, are derived from the spectral decompositions of sparse matrices. While these algorithms aim to preserve certain proximity relations on average, their embeddings are not explicitly designed to preserve local features such as distances or angles. In this paper, we show how to construct a low dimensional embedding that maximally preserves angles between nearby data points. The embedding is derived from the bottom eigenvectors of LLE and/or Laplacian eigenmaps by solving an additional (but small) problem in semidefinite programming, whose size is independent of the number of data points. The solution obtained by semidefinite programming also yields an estimate of the data's intrinsic dimensionality. Experimental results on several data sets demonstrate the merits of our approach.
- Belkin, M., & Niyogi, P. (2003). Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computation, 15(6), 1373--1396. Google Scholar
Digital Library
- Brand, M. (2003). Charting a manifold. Advances in Neural Information Processing Systems 15 (pp. 985--992). Cambridge, MA: MIT Press.Google Scholar
- Burges, C. J. C. (2005). Geometric methods for feature extraction and dimensional reduction. In L. Rokach and O. Maimon (Eds.), Data mining and knowledge discovery handbook: A complete guide for practitioners and researchers. Kluwer Academic Publishers.Google Scholar
- Chung, F. R. K. (1997). Spectral graph theory. American Mathematical Society.Google Scholar
- de Silva, V., & Tenenbaum, J. B. (2003). Global versus local methods in nonlinear dimensionality reduction. Advances in Neural Information Processing Systems 15 (pp. 721--728). Cambridge, MA: MIT Press.Google Scholar
- Donoho, D. L., & Grimes, C. E. (2002). When does Isomap recover the natural parameterization of families of articulated images? (Technical Report 2002--27). Department of Statistics, Stanford University.Google Scholar
- Donoho, D. L., & Grimes, C. E. (2003). Hessian eigenmaps: locally linear embedding techniques for high-dimensional data. Proceedings of the National Academy of Arts and Sciences, 100, 5591--5596.Google ScholarCross Ref
- Johnson, W., & Lindenstrauss, J. (1984). Extensions of lipschitz maps into a hilbert space. Contemporary Mathematics, 189--206.Google Scholar
- Magen, A. (2002). Dimensionality reductions that preserve volumes and distance to affine spaces, and their algorithmic applications. In J. Rolim and S. Vadhan (Eds.), Randomization and approximation techniques: Sixth international workshop, RANDOM 2002. Springer-Verlag. Google ScholarDigital Library
- Roweis, S. T., & Saul, L. K. (2000). Nonlinear dimensionality reduction by locally linear embedding. Science, 290, 2323--2326.Google ScholarCross Ref
- Saul, L. K., & Roweis, S. T. (2003). Think globally, fit locally: unsupervised learning of low dimensional manifolds. Journal of Machine Learning Research, 4, 119--155. Google ScholarDigital Library
- Tenenbaum, J. B., de Silva, V., & Langford, J. C. (2000). A global geometric framework for nonlinear dimensionality reduction. Science, 290, 2319--2323.Google ScholarCross Ref
- Vandenberghe, L., & Boyd, S. P. (1996). Semidefinite programming. SIAM Review, 38(1), 49--95. Google ScholarDigital Library
- Weinberger, K. Q., & Saul, L. K. (2004). Unsupervised learning of image manifolds by semidefinite programming. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR-04) (pp. 988--995). Washington D.C. Google ScholarDigital Library
- Analysis and extension of spectral methods for nonlinear dimensionality reduction
Recommendations
Semi-supervised nonlinear dimensionality reduction
ICML '06: Proceedings of the 23rd international conference on Machine learningThe problem of nonlinear dimensionality reduction is considered. We focus on problems where prior information is available, namely, semi-supervised dimensionality reduction. It is shown that basic nonlinear dimensionality reduction algorithms, such as ...
Linear Dimensionality Reduction via a Heteroscedastic Extension of LDA: The Chernoff Criterion
Abstract--We propose an eigenvector-based heteroscedastic linear dimension reduction (LDR) technique for multiclass data. The technique is based on a heteroscedastic two-class technique which utilizes the so-called Chernoff criterion, and successfully ...
Local Fisher discriminant analysis for supervised dimensionality reduction
ICML '06: Proceedings of the 23rd international conference on Machine learningDimensionality reduction is one of the important preprocessing steps in high-dimensional data analysis. In this paper, we consider the supervised dimensionality reduction problem where samples are accompanied with class labels. Traditional Fisher ...
Comments