Computational Information Geometry Wonderland

I have been interested in finding center points in geometric settings for a few years now. It is a beautiful computational geometry problem, and still remains a challenge to compute exactly in high dimensions nowadays. In the past, I have considered extensions with respect to Bregman divergences. See here [ exact Bregman miniball ] and here [core-set Bregman ball], or even here [exact hyperbolic geometry miniball].

The core-set approach of Badoiu and Clarkson is very elegant as it allows to consider extra high dimensions [trading with slow approximation convergence]. Recently, motivated by applications of symmetric positive definite matrices, we have considered generalizing a geodesic walk algorithm to Riemannian geometries. Here is the manuscript :

On Approximating the Riemannian 1-Center

In this paper, we generalize the simple Euclidean 1-center approximation algorithm of Badoiu and Clarkson (2003) to Riemannian geometries and study accordingly the convergence rate. We then show how to instantiate this generic algorithm to two particular cases: [1] hyperbolic geometry, and [2] Riemannian manifold of symmetric positive definite matrices.

Here is the arXiv paper

Frank.