Title: Fast and Robust Shortest Paths on Manifolds Learned from Data,
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.