More Web Proxy on the site http://driver.im/

article

Unsupervised Learning of Image Manifolds by Semidefinite Programming

Authors:

Kilian Q. Weinberger,

Lawrence K. SaulAuthors Info & Claims

International Journal of Computer Vision, Volume 70, Issue 1

Pages 77 - 90

https://doi.org/10.1007/s11263-005-4939-z

Published: 01 October 2006 Publication History

Abstract

Can we detect low dimensional structure in high dimensional data sets of images? In this paper, we propose an algorithm for unsupervised learning of image manifolds by semidefinite programming. Given a data set of images, our algorithm computes a low dimensional representation of each image with the property that distances between nearby images are preserved. More generally, it can be used to analyze high dimensional data that lies on or near a low dimensional manifold. We illustrate the algorithm on easily visualized examples of curves and surfaces, as well as on actual images of faces, handwritten digits, and solid objects.

References

[1]

Belkin, M. and Niyogi, P. 2003. Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computation, 15(6):1373-1396.

Digital Library

[2]

Belongie, S., Malik, J., and Puzicha, J. 2002. Shape matching and object recognition using shape contexts. IEEE Transactions on Pattern Analysis and Machine Intelligence, 24(4):509-522.

Digital Library

[3]

Bengio, Y., Paiement, J.F., and Vincent, P. 2004. Out-of-sample extensions for LLE, Isomap, MDS, eigenmaps, and spectral clustering. Advances in Neural Information Processing Systems 16. Cambridge, MA: MIT Press.

[4]

Beymer, D. and Poggio, T. 1996. Image representation for visual learning. Science, 272, 1905.

[5]

Biswas, P. and Ye, Y. 2003. A distributed method for solving semidefinite programs arising from ad hoc wireless sensor network localization. Stanford University, Department of Electrical Engineering, working paper.

[6]

Blitzer, J., Weinberger, K.Q., Saul, L.K., and Pereira, F.C.N. 2005. Hierarchical distributed representations for statistical language modeling. Advances in Neural and Information Processing Systems. Cambridge, MA: MIT Press.

[7]

Borchers, B. 1999. CSDP, a C library for semidefinite programming. Optimization Methods and Software, 11(1):613-623.

[8]

Bowling, M., Ghodsi, A., and Wilkinson, D. 2005. Action respecting embedding. In Proceedings of the Twenty-second International Conference on Machine Learning (ICML 2005). Bonn, Germany.

[9]

Brand, M. 2003. Charting a manifold. Advances in Neural Information Processing Systems 15, Cambridge, MA: MIT Press, pp. 985-992.

[10]

Burer, S. and Monteiro, R. 2003. A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Mathematical Programming, Series, B95, pp. 329-357.

[11]

Burges, C.J.C. 2005. Geometric methods for feature extraction and dimensional reduction. In L. Rokach and O. Maimon (eds.), Data Mining and Knowledge Discovery Handbook: A Complete Guide for Practitioners and Researchers. Kluwer Academic Publishers.

[12]

Cox, T. and Cox, M. 1994. Multidimensional Scaling. London: Chapman and Hall.

[13]

Donoho, D.L. and Grimes, C.E. 2002. When Does Isomap Recover The Natural Parameterization of Families of Articulated Images? (Technical Report 2002-27). Department of Statistics. Stanford University.

[14]

Donoho, D.L. and Grimes, C.E. 2003. Hessian eigenmaps: locally linear embedding techniques for high-dimensional data. In Proceedings of the National Academy of Arts and Sciences 100, pp. 5591-5596.

[15]

Elgammal, A. and Lee, C. 2004. Separating style and content on a nonlinear manifold. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR 2004), Washington DC, pp. 478-485.

[16]

Fazel, M., Hindi, H., and Boyd, S.P. 2001. A rank minimization heuristic with application to minimum order system approximation. In Proceedings of the American Control Conference, pp. 4734-4739.

[17]

Gordon, S., Goldberger, J., and Greenspan, H. 2003. Applying the information bottleneck principle to unsupervised clustering of discrete and continuous image representations. In Proceedings of the Ninth International Conference on Computer Vision (ICCV 2003), pp. 370-377.

[18]

Ham, J., Lee, D.D., Mika, S., and Schökopf, B. 2003. A kernel view of the dimensionality reduction of manifolds (Technical Report TR-110). Max-Planck-Institut für Biologische Kybernetik, Tübingen.

[19]

Hull, J.J. 1994. A database for handwritten text recognition research. IEEE Transaction on Pattern Analysis and Machine Intelligence 16(5):550-554.

Digital Library

[20]

Jolliffe, I.T. 1986. Principal Component Analysis. New York: Springer-Verlag.

[21]

Lanckriet, G.R.G., Christianini, N., Bartlett, P.L., Ghaoui, L.E., and Jordan, M.I. 2002. Learning the kernel matrix with semidefinite programming. In Proceedings of the Nineteenth International Conference on Machine Learning (ICML 2002), pp. 323- 330.

[22]

Lee, D.D., and Seung, H.S. 1999. Learning the parts of objects with nonnegative matrix factorization. Nature, 401:788-791.

[23]

Lee, K., Ho, J., Yang, M.-H., and Kriegman, D. 2003. Videobased face recognition using probabilistic appearance manifolds. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR 2003), pp. 313-320.

[24]

Lu, H., Fainman, Y., and Hecht-Nielsen, R. 1998. Image manifolds, Applications of Artificial Neural Networks in Image Processing III, Proceedings of SPIE, Bellingham, WA: SPIE, pp. 52-63.

[25]

Nash, J. 1956. The imbedding problem for riemannian manifolds. Annals of Mathematics pp. 20-63.

[26]

Ng, A.Y., Jordan, M., and Weiss, Y. 2002. On spectral clustering: analysis and an algorithm. Advances in Neural Information Processing Systems 14 Cambridge, MA: MIT Press, pp. 849-856.

[27]

Pless, R. 2004. Differential structure in non-linear image embedding functions. Proceedings of the IEEE Workshop on Articulated and Non-Rigid Motion, Washington, D.C. pp. 10-17.

[28]

Pless, R. and Simon, I. 2002. Embedding images in non-flat spaces. In Proceedings of the Conference on Imaging Science Systems and Technology pp. 182-188.

[29]

Roweis, S.T. and Saul, L.K. 2000). Nonlinear dimensionality reduction by locally linear embedding. Science, 290:2323-2326.

[30]

Saul, L.K. and Roweis, S.T. 2003. Think globally, fit locally: unsupervised learning of low dimensional manifolds. Journal of Machine Learning Research, 4:119-155.

Digital Library

[31]

Schökopf, B. and Smola, A.J. 2002. Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. Cambridge, MA: MIT Press.

[32]

Schökopf, B., Smola, A.J., and Müller, K.R. 1998. Nonlinear component analysis as a kernel eigenvalue problem. Neural Computation, 10:1299-1319.

Digital Library

[33]

Seung, H.S. and Lee, D.D. 2000. The manifold ways of perception, Science, 290:2268-2269.

[34]

Sha, F. and Saul, L.K. 2005. Analysis and extension of spectral methods for nonlinear dimensionality reduction. In Proceedings of the Twenty-second International Conference on Machine Learning (ICML 2005). Bonn, Germany.

[35]

Shi, J. and Malik, J. 2000. Normalized cuts and image segmentation. In IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), pp. 888-905.

[36]

Simard, P.Y., LeCun, Y., and Decker, J. 1993. Efficient pattern recognition using a new transformation distance. Advances in Neural Information Processing Systems, San Mateo, CA: Morgan Kaufman, pp. 50-58.

[37]

Souvenir, R. and Pless, R. 2005. Isomap and non-parametric models of image deformation. In Proceedings of the IEEE Workshop on Motion and Video Computing, Breckenridge, CO., pp. 195- 200.

[38]

Sun, J., Boyd, S., Xiao, L., and Diaconis, P. 2004. The fastest mixing Markov process on a graph and a connection to a maximum variance unfolding problem. Submitted to SIAM Review.

[39]

Tenenbaum, J.B., de Silva, V., and Langford, J.C. 2000. A global geometric framework for nonlinear dimensionality reduction. Science, 290:2319-2323.

[40]

Turk, M. and Pentland, A. 1991. Eigenfaces for recognition. Journal of Cognitive Neuroscience, 3(1):71-86.

Digital Library

[41]

Vandenberghe, L. and Boyd, S.P. 1996. Semidefinite programming. SIAM Review, 38(1):49-95.

Digital Library

[42]

Vapnik, V. 1998. Statistical Learning Theory. N.Y.: Wiley.

[43]

Weinberger, K.Q., Packer, B.D., and Saul, L.K. 2005. Nonlinear dimensionality reduction by semidefinite programming and kernel matrix factorization. In Proceedings of the Tenth International Workshop on Artificial Intelligence and Statistics. Barbados, West Indies.

[44]

Weinberger, K.Q. and Saul, L.K. 2004. Unsupervised learning of image manifolds by semidefinite programming. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR-04), Washington D.C, pp. 988- 995.

[45]

Weinberger, K.Q., Sha, F., and Saul, L.K. 2004. Learning a kernel matrix for nonlinear dimensionality reduction. In Proceedings of the Twenty First International Conference on Machine Learning (ICML-04), Banff, Canada, pp. 839-846.

[46]

Zha, H. and Zhang, Z. 2003. Isometric embedding and continuum Isomap. In Proceedings of the Twentieth International Conference on Machine Learning (ICML 2003), pp. 864- 871.

[47]

Zhang, Z. and Zha, H. 2004. Principal manifolds and nonlinear dimensionality reduction by local tangent space alignment. SIAM Journal of Scientific Computing, 26:313-338.

Digital Library

Cited By

Zhang LZhou YYang YGao X(2024)Meta Invariance Defense Towards Generalizable Robustness to Unknown Adversarial AttacksIEEE Transactions on Pattern Analysis and Machine Intelligence10.1109/TPAMI.2024.338574546:10(6669-6687)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1109/TPAMI.2024.3385745
Chen YMancini MZhu XAkata Z(2024)Semi-Supervised and Unsupervised Deep Visual Learning: A SurveyIEEE Transactions on Pattern Analysis and Machine Intelligence10.1109/TPAMI.2022.320157646:3(1327-1347)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1109/TPAMI.2022.3201576
Zhang ZSchomaker L(2024)Optimizing and interpreting the latent space of the conditional text-to-image GANsNeural Computing and Applications10.1007/s00521-023-09185-636:5(2549-2572)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1007/s00521-023-09185-6
Show More Cited By

Index Terms

Unsupervised Learning of Image Manifolds by Semidefinite Programming
1. Computing methodologies
  1. Computer graphics
    1. Shape modeling
      1. Parametric curve and surface models
      2. Volumetric models
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Combining local and global information for nonlinear dimensionality reduction

Nonlinear dimensionality reduction is a challenging problem encountered in a variety of high dimensional data analysis, including machine learning, pattern recognition, scientific visualization, and neural computation. Based on the different geometric ...
Unsupervised Segmentation of Non-Intersecting Manifolds
IAIT '21: Proceedings of the 12th International Conference on Advances in Information Technology

Manifold learning has been an important research area as from literature it is evident that patterns in most real-life data sets can be embedded in low-dimensional space while maintaining the original structure of high-dimensional space. This work ...
Riemannian Manifold Learning

Recently, manifold learning has been widely exploited in pattern recognition, data analysis, and machine learning. This paper presents a novel framework, called Riemannian manifold learning (RML), based on the assumption that the input high-dimensional ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image International Journal of Computer Vision

International Journal of Computer Vision Volume 70, Issue 1

October 2006

99 pages

ISSN:0920-5691

Issue’s Table of Contents

Copyright © Copyright © 2006 Springer Science + Business Media, LLC.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 October 2006

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

124
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zhang LZhou YYang YGao X(2024)Meta Invariance Defense Towards Generalizable Robustness to Unknown Adversarial AttacksIEEE Transactions on Pattern Analysis and Machine Intelligence10.1109/TPAMI.2024.338574546:10(6669-6687)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1109/TPAMI.2024.3385745
Chen YMancini MZhu XAkata Z(2024)Semi-Supervised and Unsupervised Deep Visual Learning: A SurveyIEEE Transactions on Pattern Analysis and Machine Intelligence10.1109/TPAMI.2022.320157646:3(1327-1347)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1109/TPAMI.2022.3201576
Zhang ZSchomaker L(2024)Optimizing and interpreting the latent space of the conditional text-to-image GANsNeural Computing and Applications10.1007/s00521-023-09185-636:5(2549-2572)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1007/s00521-023-09185-6
Chen SZhao HHuynh VPhung DCai J(2024)Neural Topic Model with Distance AwarenessPattern Recognition10.1007/978-3-031-78189-6_22(337-352)Online publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1007/978-3-031-78189-6_22
Nowak RMałkowski ACieślak DSokół PWawrzyński P(2024)Graph Vertex Embeddings: Distance, Regularization and Community DetectionComputational Science – ICCS 202410.1007/978-3-031-63778-0_4(43-57)Online publication date: 2-Jul-2024
https://dl.acm.org/doi/10.1007/978-3-031-63778-0_4
Cong JYan XChen RGao MAn BTang HWang YWang P(2023)Profile evaluation of rail joint in a 3‐m wavelength based on unsupervised learningComputer-Aided Civil and Infrastructure Engineering10.1111/mice.1294538:13(1834-1856)Online publication date: 6-Aug-2023
https://dl.acm.org/doi/10.1111/mice.12945
Yao MHe DLi XLi FXiong Z(2023)Toward Interactive Self-Supervised DenoisingIEEE Transactions on Circuits and Systems for Video Technology10.1109/TCSVT.2023.325262933:10(5360-5374)Online publication date: 1-Oct-2023
https://dl.acm.org/doi/10.1109/TCSVT.2023.3252629
Yan SLv LYan X(2023)Neural representations for quality-related kernel learning and fault detectionSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-022-07022-x27:18(13543-13551)Online publication date: 1-Sep-2023
https://dl.acm.org/doi/10.1007/s00500-022-07022-x
Njah HJamoussi SMahdi W(2022)Interpretable Bayesian network abstraction for dimension reductionNeural Computing and Applications10.1007/s00521-022-07810-435:14(10031-10049)Online publication date: 21-Sep-2022
https://dl.acm.org/doi/10.1007/s00521-022-07810-4
Alawadi SFernández-Delgado MMera DBarro S(2022)Polynomial Kernel Discriminant Analysis for 2D visualization of classification problemsNeural Computing and Applications10.1007/s00521-017-3290-331:8(3515-3531)Online publication date: 10-Mar-2022
https://dl.acm.org/doi/10.1007/s00521-017-3290-3
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents