Fast and Robust Shortest Paths on Manifolds Learned from Data

Georgios Arvanitidis, Soren Hauberg, Philipp Hennig, Michael Schober
Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, PMLR 89:1506-1515, 2019.

Abstract

We propose a fast, simple and robust algorithm for computing shortest paths and distances on Riemannian manifolds learned from data. This amounts to solving a system of ordinary differential equations (ODEs) subject to boundary conditions. Here standard solvers perform poorly because they require well-behaved Jacobians of the ODE, and usually, manifolds learned from data imply unstable and ill-conditioned Jacobians. Instead, we propose a fixed-point iteration scheme for solving the ODE that avoids Jacobians. This enhances the stability of the solver, while reduces the computational cost. In experiments involving both Riemannian metric learning and deep generative models we demonstrate significant improvements in speed and stability over both general-purpose state-of-the-art solvers as well as over specialized solvers.

Cite this Paper

BibTeX
@InProceedings{pmlr-v89-arvanitidis19a, title = {Fast and Robust Shortest Paths on Manifolds Learned from Data}, author = {Arvanitidis, Georgios and Hauberg, Soren and Hennig, Philipp and Schober, Michael}, booktitle = {Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics}, pages = {1506--1515}, year = {2019}, editor = {Chaudhuri, Kamalika and Sugiyama, Masashi}, volume = {89}, series = {Proceedings of Machine Learning Research}, month = {16--18 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v89/arvanitidis19a/arvanitidis19a.pdf}, url = {https://proceedings.mlr.press/v89/arvanitidis19a.html}, abstract = {We propose a fast, simple and robust algorithm for computing shortest paths and distances on Riemannian manifolds learned from data. This amounts to solving a system of ordinary differential equations (ODEs) subject to boundary conditions. Here standard solvers perform poorly because they require well-behaved Jacobians of the ODE, and usually, manifolds learned from data imply unstable and ill-conditioned Jacobians. Instead, we propose a fixed-point iteration scheme for solving the ODE that avoids Jacobians. This enhances the stability of the solver, while reduces the computational cost. In experiments involving both Riemannian metric learning and deep generative models we demonstrate significant improvements in speed and stability over both general-purpose state-of-the-art solvers as well as over specialized solvers.} }
Endnote
%0 Conference Paper %T Fast and Robust Shortest Paths on Manifolds Learned from Data %A Georgios Arvanitidis %A Soren Hauberg %A Philipp Hennig %A Michael Schober %B Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Masashi Sugiyama %F pmlr-v89-arvanitidis19a %I PMLR %P 1506--1515 %U https://proceedings.mlr.press/v89/arvanitidis19a.html %V 89 %X We propose a fast, simple and robust algorithm for computing shortest paths and distances on Riemannian manifolds learned from data. This amounts to solving a system of ordinary differential equations (ODEs) subject to boundary conditions. Here standard solvers perform poorly because they require well-behaved Jacobians of the ODE, and usually, manifolds learned from data imply unstable and ill-conditioned Jacobians. Instead, we propose a fixed-point iteration scheme for solving the ODE that avoids Jacobians. This enhances the stability of the solver, while reduces the computational cost. In experiments involving both Riemannian metric learning and deep generative models we demonstrate significant improvements in speed and stability over both general-purpose state-of-the-art solvers as well as over specialized solvers.
APA
Arvanitidis, G., Hauberg, S., Hennig, P. & Schober, M.. (2019). Fast and Robust Shortest Paths on Manifolds Learned from Data. Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 89:1506-1515 Available from https://proceedings.mlr.press/v89/arvanitidis19a.html.

Related Material