Inner Product Laplacian Embedding Based on Semidefinite Programming

Xianhua Zeng
DOI: 10.4236/jsip.2011.23027                

Abstract

This paper proposes an inner product Laplacian embedding algorithm based on semi-definite programming, named as IPLE algorithm. The new algorithm learns a geodesic distance-based kernel matrix by using semi-definite programming under the constraints of local contraction. The criterion function is to make the neighborhood points on manifold as close as possible while the geodesic distances between those distant points are preserved. The IPLE algorithm sufficiently integrates the advantages of LE, ISOMAP and MVU algorithms. The comparison experiments on two image datasets from COIL-20 images and USPS handwritten digit images are performed by applying LE, ISOMAP, MVU and the proposed IPLE. Experimental results show that the intrinsic low-dimensional coordinates obtained by our algorithm preserve more information according to the fraction of the dominant eigenvalues and can obtain the better comprehensive performance in clustering and manifold structure.

Keywords

Inner Product, Semi-Definite Programming, Geodesic Distance, Laplacian Matrix

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	J. Tenenbaum, V. D. Silva and J. Langford, “A Global Geometric Framework for Nonlinear Dimensionality Reduction,” Science, Vol. 290, No. 5500, 2000, pp. 2319-2323. doi:10.1126/science.290.5500.2319
[2]	M. Belkin and P. Niyogi, “Laplacian Eigenmaps for Dimensionality Reduction and Data Representation,” Technical Report, University of Chicago, Chicago, 2001.
[3]	K. Q. Weinberger and L. K. Saul, “An Introduction to Nonlinear Dimensionality Reduction by Maximum Variance Unfolding,” AAAI Press, Boston, 2006.
[4]	H. Choi and S. Choi, “Kernel Isomap,” Electronics Letters, Vol. 40, No. 25, 2005, pp. 1612-1613. doi:10.1049/el:20046791
[5]	M. Belkin, “Problems of Learning on Manifolds,” Ph.D. Dissertation, University of Chicago, Chicago, 2003.
[6]	K. Q. Weinberger, “Metric Learning with Convex Optimization,” Ph.D. Dissertation, University of Pennsylvania, Philadephia, 2007.
[7]	K. Q. Weinberger, F. Sha and L. K. Saul, “Learning a Kernel Matrix for Nonlinear Dimensionality Reduction,” Proceedings of the 21st International Conference on Machine Learning, Banff, 4-8 July 2004, pp. 839-846.
[8]	K. Q. Weinberger, B. D. Packer and L. K. Saul, “Nonlinear Dimensionality Reduction by Semidefinite Programming and Kernel Matrix Factorization,” Proceedings of the 10th International Workshop on Artificial Intelligence and Statistics, Barbados, 6-8 January 2005, pp. 381-388.
[9]	K. Q. Weinberger and L. K. Saul, “An Introduction to Nonlinear Dimensionality Reduction by Maximum Variance Unfolding,” AAAI Press, Boston, 2006.
[10]	L. F. Sha and K. Saul, “Analysis and Extension of Spectral Methods for Nonlinear Dimensionality Reduction,” Proceedings of the 22nd International Conference on Machine Learning, Bonn, Vol. 15, 7-11 August 2005, pp. 721-728. doi:10.1145/1102351.1102450
[11]	L. Yang, “Building k Edge-Disjoint Spanning Trees of Minimum Total Length for Isometric Data Embedding,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 27, No. 10, 2005, pp. 1680-1683. doi:10.1109/TPAMI.2005.192
[12]	M. Belkin and P. Niyogi. “Semi-Supervised Learning on Riemannian Manifolds,” Machine Learning Journal, Vol. 56, No. 1-3, 2004, pp. 209-239. doi:10.1023/B:MACH.0000033120.25363.1e
[13]	E. W. Dijkstra, “A Note on Two Problems in Connexion with Graphs,” Numerische MathematiK, Vol. 1, No. 1, 1959, pp. 269-271. doi:10.1007/BF01386390
[14]	USPS Handwritten Digit Dataset, 2010. http://cs.nyu.edu/~roweis/data.html
[15]	COILT20 Database, 2010. http://www1.cs.columbia.edu/CAVE/software/softlib/coil-20.php
[16]	B. Borchers, “CSDP, a C Library for Semidefinite Programming,” Optimization Methods and Software, Vol. 11-2, No. 1-4, 1999, pp. 613-623. doi:10.1080/10556789908805765
[17]	Z. H. Zhou and J. Wang, “Machine Learning and Its Application2007,” Tsinghua University Press, Beijing, 2007.
[18]	Z. Y. Zhang, H. Y. Zha and M. Zhang, “Spectral Methods for Semi-Supervised Manifold Learning,” IEEE Conference on Computer Vision and Pattern Recognition, Anchorage, 24-26 June 2008, pp. 1-6.
[19]	X. H. Zeng, L. Gan and J. Wang, “A Semidefinite Programming Embedding Framework for Local Preserving Manifold Learning,” Chinese Conference on Pattern Recognition, Chongqing, 21-23 October 2010, pp. 257-261. doi:10.1109/CCPR.2010.5659162
[20]	O. Arandjelovic, “Unfolding a Face: From Singular to Manifold,” 9th Asian Conference on Computer Vision, Xi’an, 23-27 September 2009, pp. 203-213.
[21]	E. L. Hu, S. C. Chen and X. S. Yin, “Manifold Contraction for Semi-Supervised Classification,” Science in China, Vol. 53, No. 6, 2010, pp. 1170-1187.
[22]	D. Zhao and L. Yang, “Incremental Isometric Embedding of High Dimensional Data Using Connected Neighborhood Graphs,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 31, No. 1, 2009, pp. 86-98. doi:10.1109/TPAMI.2008.34
[23]	M. H. C. Law and A. K. Jain, “Incremental Nonlinear Dimensionality Reduction by Manifold Learning,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 28, No. 3, 2006, pp. 377-391. doi:10.1109/TPAMI.2006.56