Robust non-linear dimensionality reduction using successive 1-dimensional Laplacian Eigenmaps

ABSTRACT

Non-linear dimensionality reduction of noisy data is a challenging problem encountered in a variety of data analysis applications. Recent results in the literature show that spectral decomposition, as used for example by the Laplacian Eigenmaps algorithm, provides a powerful tool for non-linear dimensionality reduction and manifold learning. In this paper, we discuss a significant shortcoming of these approaches, which we refer to as the repeated eigendirections problem. We propose a novel approach that combines successive 1-dimensional spectral embeddings with a data advection scheme that allows us to address this problem. The proposed method does not depend on a non-linear optimization scheme; hence, it is not prone to local minima. Experiments with artificial and real data illustrate the advantages of the proposed method over existing approaches. We also demonstrate that the approach is capable of correctly learning manifolds corrupted by significant amounts of noise.

REFERENCES

• 1: Suyash P. Awate , Ross T. Whitaker, Unsupervised, Information-Theoretic, Adaptive Image Filtering for Image Restoration, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.28 n.3, p.364-376, March 2006 [doi>10.1109/TPAMI.2006.64]
• 2: Balasubramanian, M., & Schwartz, E. L. (2002). The isomap algorithm and topological stability. Science, 295.
• 3: 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]
• 4: Yoshua Bengio , Olivier Delalleau , Nicolas Le Roux , Jean-François Paiement , Pascal Vincent , Marie Ouimet, Learning Eigenfunctions Links Spectral Embedding and Kernel PCA, Neural Computation, v.16 n.10, p.2197-2219, October 2004 [doi>10.1162/0899766041732396]
• 5: Christopher M. Bishop, Neural Networks for Pattern Recognition, Oxford University Press, Inc., New York, NY, 1995
• 6: Chung, F. R. K. (1994). Spectral graph theory. AMS.
• 7: Cox, T. F., & Cox, M. A. A. (1994). Multidimensional scaling. Monographs on Statistics and Applied Probability 59. London: Chapman and Hall.
• 8: Das, P., Moll, M., Stamati, H., Kavraki, L. E., & Clementi, C. (2006). Low-dimensional, free-energy landscapes of protein-folding reactions by nonlinear dimensionality reduction. PNAS, 103, 9885--9890.
• 9: Donoho, D., & Grimes, C. (2003). Hessian eigenmaps: locally linear embedding techniques for high dimensional data. Proc. of N. A. of Sciences, 100, 5591--5596.
• 10: Gámez, A. J., Zhou, C. S., Timmermann, A., & Kurths, J. (2004). Nonlinear dimensionality reduction in climate data. Nonlinear Processes in Geophysics, 11, 393--398.
• 11: Hinton, G., & Roweis, S. T. (2002). Stochastic neighbor embedding. NIPS (pp. 833--840).
• 12: Hinton, G. E., & Salakhutdinov, R. R. (2006). Reducing the dimensionality of data with neural networks. Science, 313, 504--507.
• 13: Jolliffe, I. T. (1986). Principal component analysis. Springer-Verlag.
• 14: Teuvo Kohonen, Self-organizing maps, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 15: John A. Lee , Michel Verleysen, Nonlinear Projection with the Isotop Method, Proceedings of the International Conference on Artificial Neural Networks, p.933-938, August 28-30, 2002
• 16: Lin, T., Zha, H., & Lee, S. U. (2006). Riemannian manifold learning for nonlinear dimensionality reduction. ECCV.
• 17: Lluis Garrido, Sergio Gomez, J. R. (1999). Non-linear dimensionality reduction with input distances preservation. ANN.
• 18: Thomas Martinetz , Klaus Schulten, Topology representing networks, Neural Networks, v.7 n.3, p.507-522, 1994 [doi>10.1016/0893-6080(94)90109-0]
• 19: Parzen, E. (1962). On the estimation of a probability density function and the mode. AMS, 33, 1065--1076.
• 20: Perantonis, J. S., & v. Virvilis (1999). Dimensionality reduction using a novel neural network based feature extraction method. IJCNN, 2, 1195--1198.
• 21: William H. Press , Saul A. Teukolsky , William T. Vetterling , Brian P. Flannery, Numerical recipes in C (2nd ed.): the art of scientific computing, Cambridge University Press, New York, NY, 1992
• 22: Roweis, S., & Saul, L. (2000). Nonlinear dimensionality reduction by locally linear embedding. Science, 290.
• 23: 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]
• 24: Jianbo Shi , Jitendra Malik, Normalized Cuts and Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.8, p.888-905, August 2000 [doi>10.1109/34.868688]
• 25: Tenenbaum, J. B., de Silva, V., & Langford, J. C. (2000). A global geometric framework for nonlinear dimensionality reduction. Science, 290, 2319--2323.
• 26: Michail Vlachos , Carlotta Domeniconi , Dimitrios Gunopulos , George Kollios , Nick Koudas, Non-linear dimensionality reduction techniques for classification and visualization, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775143]
• 27: Kilian Q. Weinberger , Fei Sha , Lawrence K. Saul, Learning a kernel matrix for nonlinear dimensionality reduction, Proceedings of the twenty-first international conference on Machine learning, p.106, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015345]
• 28: Arthur G. Werschulz, The computational complexity of differential and integral equations: an information-based approach, Oxford University Press, Inc., New York, NY, 1991
• 29: Yang, J., Li, F., & Wang, J. (2005). A better scaled local tangent space alignment algorithm (pp. 1006--1011.).
• 30: Jieping Ye , Ravi Janardan , Qi Li, GPCA: an efficient dimension reduction scheme for image compression and retrieval, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014092]
• 31: Zhenyue Zhang , Hongyuan Zha, Principal Manifolds and Nonlinear Dimensionality Reduction via Tangent Space Alignment, SIAM Journal on Scientific Computing, v.26 n.1, p.313-338, 2005 [doi>10.1137/S1064827502419154]