Computing Medians and Means in Hadamard Spaces

The geometric median as well as the Fréchet mean of points in a Hadamard space are important in both theory and applications. Surprisingly, no algorithms for their computation are hitherto known. To address this issue, we use a splitting version of the proximal point algorithm for minimizing a sum of convex functions and prove that this algorithm produces a sequence converging to a minimizer of the objective function, which extends a recent result of Bertsekas [Math. Program., 129 (2011), pp. 163--195] into Hadamard spaces. The method is quite robust, and not only does it yield algorithms for the median and the mean, but also it applies to various other optimization problems. We, moreover, show that another algorithm for computing the Fréchet mean can be derived from the law of large numbers due to Sturm [Ann. Probab., 30 (2002), pp. 1195--1222]. In applications, computing medians and means is probably most needed in tree space, which is an instance of a Hadamard space, invented by Billera, Holmes, and Vogtmann [Adv. in Appl. Math., 27 (2001), pp. 733--767] as a tool for averaging phylogenetic trees. Since there now exists a polynomial-time algorithm for computing geodesics in tree space due to Owen and Provan [IEEE/ACM Trans. Comput. Biol. Bioinform., 8 (2011), pp. 2--13], we obtain efficient algorithms for computing medians and means of trees, which can be directly used in practice.