Alignment of vector fields on manifolds via contraction mappings

O.N. Kachana, Yu.A. Yanovicha,b,c, E.N. Abramovc

aSkolkovo Institute of Science and Technology, Moscow, 143026 Russia

bKharkevich Institute for Information Transmission Problems, Russian Academy of Sciences, Moscow, 127051 Russia

cNational Research University Higher School of Economics, Moscow, 101000 Russia

Full text PDF

Abstract

According to the manifold hypothesis, high-dimensional data can be viewed and meaningfully represented as a lower-dimensional manifold embedded in a higher dimensional feature space. Manifold learning is a part of machine learning where an intrinsic data representation is uncovered based on the manifold hypothesis.

Many manifold learning algorithms were developed. The one called Grassmann & Stiefel eigenmaps (GSE) has been considered in the paper. One of the GSE subproblems is tangent space alignment. The original solution to this problem has been formulated as a generalized eigenvalue problem. In this formulation, it is plagued with numerical instability, resulting in suboptimal solutions to the subproblem and manifold reconstruction problem in general.

We have proposed an iterative algorithm to directly solve the tangent spaces alignment problem. As a result, we have obtained a significant gain in algorithm efficiency and time complexity. We have compared the performance of our method on various model data sets to show that our solution is on par with the approach to vector fields alignment formulated as an optimization on the Stiefel group.

Keywords: manifold learning, dimensionality reduction, numerical optimization, vector field estimation

Acknowledgements. The study was supported by the Russian Science Foundation (project no. 14-50-00150).

References

1. Giraud Ch. Introduction to High-Dimensional Statistics. New York, Chapman and Hall/CRC, 2014. 270 p.

2. Donoho D.L. High-dimensional data analysis: The curses and blessings of dimensionality.  AMS Conf. on Math Challenges of 21st Century, 2000, pp. 1–31.

3. Ezuz D., Solomon J., Kim V.G., Ben-Chen M. GWCNN: A metric alignment layer for deep shape analysis. Comput. Graphics Forum, 2017, vol. 36, no. 5, pp. 49–57. doi: 10.1111/cgf.13244.

4. Qiu A., Lee A., Tan M., Chung M.K. Manifold learning on brain functional networks in aging.  Med. Image Anal., 2015, vol. 20, no. 1, pp. 52–60. doi: 10.1016/j.media.2014.10.006.

5. Bronstein M.M., Bruna J., LeCun Y., Szlam A., Vandergheynst P. Geometric deep learning: Going beyond Euclidean data.  IEEE Signal Process. Mag., 2017, vol. 34, no. 4, pp. 18–42. doi: 10.1109/MSP.2017.2693418.

6. Xu C., Govindarajan L.N., Zhang Y., Cheng L., Lie-X: Depth image based articulated object pose estimation, tracking, and action recognition on lie groups.  Int. J. Comput. Vision, 2017, vol. 123, no. 3, pp. 454–478. doi: 10.1007/s11263-017-0998-6.

7. Seung H.S., Lee D.D. COognition. The manifold ways of perception.  Science, 2000, vol. 290, no. 5500, pp. 2268–2269. doi: 10.1126/science.290.5500.2268.

8. Zeestraten M.J.A., Havoutis I., Silverio J., Calinon S., Caldwell D.G. An approach for imitation learning on riemannian manifolds.  IEEE Rob. and Autom. Lett., 2017, vol. 2, no. 3, pp. 1240–1247. doi: 10.1109/LRA.2017.2657001.

9. Klingensmith M., Koval M.C., Srinivasa S.S., Pollard N.S., Kaess M. The manifold particle filter for state estimation on high-dimensional implicit manifolds.  2017 IEEE Int. Conf. on Robotics and Automation (ICRA). Singapore, 2017, pp. 4673–4680. doi: 10.1109/ICRA.2017.7989543.

10. Bush K., Pineau J. Manifold embeddings for model-based reinforcement learning under partial observability. In: Bengio Y., Schuurmans D., Lafferty J.D., Williams C.K.I., Culotta A. (Eds.) Advances in Neural Information Processing Systems. Curran Associates, Inc., 2009, pp. 189–197.

11. Brahma P., Wu D., She Y., Why deep learning works: A manifold disentanglement perspective.  IEEE Trans. Neural Networks and Learn. Syst., 2016, vol. 27, no. 10, pp. 1997–2008. doi: 10.1109/TNNLS.2015.2496947.

12. Belkin M., Niyogi P. Laplacian Eigenmaps for dimensionality reduction and data representation.  Neural Comput., 2003, vol. 15, no. 6, pp. 1373–1396. doi: 10.1162/089976603321780317.

13. 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.

14. Zhang Z., Zha H. Principal manifolds and nonlinear dimensionality reduction via tangent space alignment.  SIAM J. Sci. Comput., 2004, vol. 26, no. 1, p. 313–338. doi: 10.1137/S1064827502419154.

15. Bernstein A., Kuleshov A.P. Manifold learning: Generalizing ability and tangent proximity. Int. J. Software Inf., 2013, vol. 7, no. 3, pp. 359–390.

16. Bernstein A., Kuleshov A., Yanovich Y., Manifold learning in regression tasks. In:  Lecture Notes in Computer Science, 2015, vol. 9047, pp. 414–423.

17. Bernstein A.V., Kuleshov A.P., Yanovich Yu.A. Locally isometric and conformal parameterization of image manifold. Proc. 8th Int. Conf. on Machine Vision. Verikas A., Radeva P., Nikolaev D. (Eds.). Vol. 987507. Barcelona, 2015, pp. 1–7. doi: 10.1117/12.2228741.

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. Yanovich Yu. Asymptotic properties of nonparametric estimation on manifold.  Proc. 6th Workshop on Conformal and Probabilistic Prediction and Applications, PMLR, 2017, vol. 60, pp. 18–38.

20. Bernstein A., Burnaev E., Erofeev P. Comparative study of nonlinear methods for manifold learning.  Proc. Conf. ``Information Technologies and Systems'', 2012, pp. 85–91.

21. Bishop C.M. Pattern Recognition and Machine Learning. New York, Springer, 2006. xx, 738 p.

22. Golub G.H., van Loan Ch.F. Matrix Computations. Baltimore, Johns Hopkins Univ. Press, 1996. 694 p.

23. Abramov E., Yanovich Yu. Smooth vector fields estimation on manifolds by optimization on Stiefel group.  Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2018, vol. 160, no. 2, pp. 220–228.

Received

October 11, 2017

 

For citation: Kachan O.N., Yanovich Yu.A., Abramov E.N. Alignment of vector fields on manifolds via contraction mappings. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2018, vol. 160, no. 2, pp. 300–308.

 

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