Abstract
Spectral manifold learning techniques have recently found extensive applications in machine vision. The common strategy of spectral algorithms for manifold learning is exploiting the local relationships in a symmetric adjacency graph, which is typically constructed using k -nearest neighborhood (k-NN) criterion. In this paper, with our focus on locally linear embedding as a powerful and well-known spectral technique, shortcomings of k-NN for construction of the adjacency graph are first illustrated, and then a new criterion, namely k/K-nearest neighborhood (k/K-NN) is introduced to overcome these drawbacks. The proposed criterion involves finding the sparsest representation of each sample in the dataset, and is realized by modifying Robust-SL0, a recently proposed algorithm for sparse approximate representation. k/K-NN criterion gives rise to a modified spectral manifold learning technique, namely Sparse-LLE, which demonstrates remarkable improvement over conventional LLE through our experiments.
Preview
Unable to display preview. Download preview PDF.
References
Saul, L.K., Weinberger, K.Q., Ham, J.H., Sha, F., Lee, D.D.: Spectral methods for dimensionality reduction. In: Chapelle, O., Schölkopf, B., Zien, A. (eds.) Semisupervised Learning. MIT Press, Cambridge (2006)
Roweis, S., Saul, L.: Nonlinear dimensionality reduction by locally linear embedding. Science 290, 2323–2326 (2000)
Lebanon, G.: Riemannian geometry and statistical machine learning. Doctoral Thesis, School of Computer Science, Carnegie Mellon University (2005)
Lin, T., Zha, H., Lee, S.U.: Riemannian manifold learning for nonlinear dimensionality reduction. In: Leonardis, A., Bischof, H., Pinz, A. (eds.) ECCV 2006. LNCS, vol. 3951, pp. 44–55. Springer, Heidelberg (2006)
Eftekhari, A., Babaie-Zadeh, M., Jutten, C., Abrishami Moghaddam, H.: Robust-SL0 for stable sparse representation in noisy settings. In: Int. Conf. Acoustics, Speech, and Signal Proc. (accepted, 2009)
van der Maaten, L.J.P., Postma, E.O., van den Herik, H.J.: Dimensionality reduction: a comparative review. Submitted to Neurocomputing (2009)
Bernstein, M., de Silva, V., Langford, J.C., Tenenbaum, J.B.: Graph approximations to geodesics on embedded manifolds. Technical Report, Stanford University (2000)
Georghiades, A.S., Belhumeur, P.N., Kriegman, D.J.: From few to many: illumination cone models for face recognition under variable lighting and pose. IEEE Trans. Pattern Anal. Mach. Intell. 23, 643–660 (2001)
VARIA database, http://www.varpa.es/varia.html
Farzin, H., Abrishami, H.: A novel retinal identification system. EURASIP Jr. on Advances in Signal Proc. (2008)
Eftekhari, A., Abrishami Mohgaddam, H.: k/K-nearest neighborhood criterion for improvement of locally linear embedding, Technical report, http://nasim.kntu.ac.ir/MS/a_eftekhari
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Eftekhari, A., Abrishami-Moghaddam, H., Babaie-Zadeh, M. (2009). k/K-Nearest Neighborhood Criterion for Improvement of Locally Linear Embedding. In: Jiang, X., Petkov, N. (eds) Computer Analysis of Images and Patterns. CAIP 2009. Lecture Notes in Computer Science, vol 5702. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-03767-2_98
Download citation
DOI: https://doi.org/10.1007/978-3-642-03767-2_98
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-03766-5
Online ISBN: 978-3-642-03767-2
eBook Packages: Computer ScienceComputer Science (R0)