Inner Product Laplacian Embedding Based on Semidefinite Programming
- 1
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.
- 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
- M. Belkin and P. Niyogi, “Laplacian Eigenmaps for Dimensionality Reduction and Data Representation,” Technical Report, University of Chicago, Chicago, 2001.
- K. Q. Weinberger and L. K. Saul, “An Introduction to Nonlinear Dimensionality Reduction by Maximum Variance Unfolding,” AAAI Press, Boston, 2006.
- H. Choi and S. Choi, “Kernel Isomap,” Electronics Letters, Vol. 40, No. 25, 2005, pp. 1612-1613. doi:10.1049/el:20046791
- M. Belkin, “Problems of Learning on Manifolds,” Ph.D. Dissertation, University of Chicago, Chicago, 2003.
- K. Q. Weinberger, “Metric Learning with Convex Optimization,” Ph.D. Dissertation, University of Pennsylvania, Philadephia, 2007.
- 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.
- 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.
- K. Q. Weinberger and L. K. Saul, “An Introduction to Nonlinear Dimensionality Reduction by Maximum Variance Unfolding,” AAAI Press, Boston, 2006.
- 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
- 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
- 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
- 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