nips nips2005 nips2005-9 nips2005-9-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Zhenyue Zhang, Hongyuan Zha
Abstract: We propose a fast manifold learning algorithm based on the methodology of domain decomposition. Starting with the set of sample points partitioned into two subdomains, we develop the solution of the interface problem that can glue the embeddings on the two subdomains into an embedding on the whole domain. We provide a detailed analysis to assess the errors produced by the gluing process using matrix perturbation theory. Numerical examples are given to illustrate the efficiency and effectiveness of the proposed methods. 1
[1] M. Brand. Charting a manifold. Advances in Neural Information Processing Systems 15, MIT Press, 2003.
[2] D. Donoho and C. Grimes. Hessian Eigenmaps: new tools for nonlinear dimensionality reduction. Proceedings of National Academy of Science, 5591-5596, 2003.
[3] M. Fiedler. A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory. Czech. Math. J. 25:619–637, 1975.
[4] A. George and J. W. Liu. Computer Solution of Large Sparse Positive Definite Matrices. Prentice Hall, 1981.
[5] METIS. http://www-users.cs.umn.edu/∼karypis/metis/.
[6] S. Roweis and L. Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, 290: 2323–2326, 2000.
[7] B. Smith, P. Bjorstad and W. Gropp Domain Decomposition, Parallel Multilevel Methods for Elliptic Partial Differential Equations. Cambridge University Press, 1996.
[8] G.W. Stewart and J.G. Sun. Matrix Perturbation Theory. Academic Press, New York, 1990.
[9] J. Tenenbaum, V. De Silva and J. Langford. A global geometric framework for nonlinear dimension reduction. Science, 290:2319–2323, 2000.
[10] A. Toselli and O. Widlund. Domain Decomposition Methods - Algorithms and Theory. Springer, 2004.
[11] H. Zha and Z. Zhang. Spectral analysis of alignment in manifold learning. Proceedings of IEEE International Conference on Acoustics, Speech, and Signal Processing, (ICASSP), 2005.
[12] Z. Zhang and H. Zha. Principal manifolds and nonlinear dimensionality reduction via tangent space alignment. SIAM J. Scientific Computing. 26:313-338, 2005.