E.N. Abramova, Yu.A. Yanovichb,c,a
aNational Research University Higher School of Economics, Moscow, 101000 Russia
bSkolkovo Institute of Science and Technology, Moscow, 143026 Russia
cKharkevich Institute for Information Transmission Problems, Russian Academy of Sciences, Moscow, 127051 Russia
Abstract
Real data are usually characterized by high dimensionality. However, real data obtained from real sources, due to the presence of various dependencies between data points and limitations on their possible values, form, as a rule, form a small part of the high-dimensional space of observations. The most common model is based on the hypothesis that data lie on or near a manifold of a smaller dimension. This assumption is called the manifold hypothesis, and inference and calculations under it are called manifold learning.
Grassmann & Stiefel eigenmaps is a manifold learning algorithm. One of its subproblems has been considered in the paper: estimation of smooth vector fields by optimization on the Stiefel group. A two-step algorithm has been introduced to solve the problem. Numerical experiments with artificial data have been performed.
Keywords: manifold learning, dimensionality reduction, vector field estimation, optimization on Stiefel manifold
Acknowledgements. The study by Yu.A. Yanovich was supported by the Russian Science Foundation (project no. 14-50-00150).
References
1. Bellman R.E. Dynamic Programming. Princeton, Princeton Univ. Press, 1957. 339 p.
2. Donoho D.L. High-dimensional data analysis: The curses and blessings of dimensionality. Proc. AMS Conf. on Math Challenges of 21st Century, 2000, pp. 1–33.
3. Seung H.S., Lee D.D. Cognition. The manifold ways of perception. Science, 2000, vol. 290, no. 5500, pp. 2268–2269. doi: 10.1126/science.290.5500.2268.
4. Huo X., Ni X.S., Smith A.K. A survey of manifold-based learning methods. In: Liao T.W., Triantaphyllou E. (Eds.) Recent Advances in Data Mining of Enterprise Data. Singapore, World Sci., 2007, pp. 691–745. doi: 10.1142/9789812779861_0015.
5. Ma Y., Fu Y. Manifold Learning Theory and Applications. London, CRC Press, 2011. 314 p.
6. Tenenbaum J.B., de Silva V., Langford J. A global geometric framework for nonlinear dimensionality reduction. Science, 2000, vol. 290, no. 5500, pp. 2319–2323. doi: 10.1126/science.290.5500.2319.
7. Roweis S.T., Saul L.K. Nonlinear dimensionality reduction by locally linear embedding. Science, 2000, vol. 290, no. 5500, pp. 2323–2326. doi: 10.1126/science.290.5500.2323.
8. Zhang Z., Zha H. Principal manifolds and nonlinear dimension reduction via local tangent space alignment. SIAM J. Sci. Comput., 2004, vol. 26, no. 1, pp. 313–338. doi: 10.1137/S1064827502419154.
9. Belkin M., Niyogi P. Laplacian eigenmaps for dimensionality reduction and data representation. J. Neural Comput., 2003, vol. 15, no. 6, pp. 1373–1396. doi: 10.1162/089976603321780317.
10. Belkin M., Niyogi P. Convergence of Laplacian eigenmaps. Adv. Neural Inf. Process. Syst., 2007, vol. 19, pp. 129–136.
11. Donoho D.L., Grimes C. Hessian eigenmaps: Locally linear embedding techniques for high-dimensional data. Proc. Natl. Acad. Sci. U. S. A., vol. 100, no. 10, pp. 5591–5596. doi: 10.1073/pnas.1031596100.
12. Bernstein A., Kuleshov A.P. Manifold learning: Generalizing ability and tangent proximity. Int. J. Software Inf., 2013, vol. 7, no. 3, pp. 359–390.
13. Bernstein A., Kuleshov A., Yanovich Y. Manifold learning in regression tasks. In: Gammerman A., Vovk V., Papadopoulos H. (Eds.) Statistical Learning and Data Sciences. SLDS 2015. Lecture Notes in Computer Science. Vol. 9047. Cham, Springer, 2015, pp. 414–423. doi: 10.1007/978-3-319-17091-6_36. 2015.
14. Pelletier B. Non-parametric regression estimation on closed Riemannian. J. Nonparametric Stat., 2006, vol. 18, no. 1, pp. 57–67. doi: 10.1080/10485250500504828.
15. Niyogi P., Smale S., Weinberger S. Finding the homology of submanifolds with high confidence from random samples. Discrete Comput. Geom., 2008, vol. 39, no. 1, pp. 419–441. doi: 10.1007/s00454-008-9053-2.
16. Bernstein A.V., Kuleshov A.P., Yanovich Yu.A. Locally isometric and conformal parameterization of image manifold. Proc. 8th Int. Conf. on Machine Vision (ICMV 2015), 2015, vol. 9875, art. 987507, pp. 1–7, doi: 10.1117/12.2228741.
17. Kachan O., Yanovich Y., Abramov E. Vector fields alignment on manifolds via contraction mappings. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2018, vol. 160, no. 2, pp. 300–308.
18. Yanovich Yu. Asymptotic properties of local sampling on manifold. J. Math. Stat., 2016, vol. 12, no. 3, pp. 157–175. doi: 10.3844/jmssp.2016.157.175.
19. Absil P.A., Mahony R., Sepulchre R. Optimization Algorithms on Matrix Manifolds. Princeton, Princeton Univ. Press, 2007. 240 p.
20. Boumal N., Mishra B., Absil P.-A., Sepulchre R. Manopt, a Matlab toolbox for optimization on manifolds. J. Mach. Learn. Res., 2014, vol. 15, no. 1, pp. 1455–1459.
Received
December 8, 2017
Abramov Evgeny Nikolayevich, Graduate Student of the Faculty of Computer Science
National Research University "Higher School of Economics''
ul. Myasnitskaya, 20, Moscow, 101000 Russia
E-mail: petzchner@gmail.com
Yanovich Yury Alexandrovich, Candidate of Physical and Mathematical Sciences, Researcher of the Center for Computational and Data-Intensive Science and Engineering; Researcher of the Intelligent Data Analysis and Predictive Modeling Laboratory; Lecturer of the Faculty of Computer Science
Skolkovo Institute of Science and Technology
ul. Nobelya, 3, Territory of the Innovation Center ``Skolkovo'', Moscow, 143026 Russia
Kharkevich Institute for Information Transmission Problems, Russian Academy of Sciences
Bolshoy Karetny pereulok, 19, str. 1, Moscow, 127051 Russia
National Research University ``Higher School of Economics''
ul. Myasnitskaya, 20, Moscow, 101000 Russia
E-mail: yury.yanovich@iitp.ru
Контент доступен под лицензией Creative Commons Attribution 4.0 License.