  We propose a general convex optimization problem for computing regularized
geodesic distances. We show that under mild conditions on the regularizer the
problem is well posed. We propose three different regularizers and provide
analytical solutions in special cases, as well as corresponding efficient
optimization algorithms. Additionally, we show how to generalize the approach
to the all pairs case by formulating the problem on the product manifold, which
leads to symmetric distances. Our regularized distances compare favorably to
existing methods, in terms of robustness and ease of calibration.
