E.N. Abramov^a*, Yu.A. Yanovich^b,c,a**

^a National Research University Higher School of Economics, Moscow, 101000 Russia

^b Skolkovo Institute of Science and Technology, Moscow, 143026 Russia

^c Kharkevich Institute for Information Transmission Problems, Russian Academy of Sciences, Moscow, 127051 Russia

E-mail: *petzchner@gmail.com, **ostroukhova.ei@gmail.com

Received December 8, 2017

Full text PDF

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.

For  citation:  Abramov  E.N.,  Yanovich  Yu.A.  Estimation  of  smooth  vector  fields on manifolds by optimization on Stiefel group. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2018, vol. 160, no. 2, pp. 220–228.

The content is available under the license Creative Commons Attribution 4.0 License.