Computing medians and means in Hadamard spaces

摘要: The geometric median as well the Frechet mean of points in an Hadamard space are important both theory and applications. Surprisingly, no algorithms for their computation hitherto known. To address this issue, we use a split version proximal point algorithm minimizing sum convex functions prove that produces sequence converging to minimizer objective function, which extends recent result D. Bertsekas (2001) into spaces. method is quite robust not only does it yield mean, but also applies various other optimization problems. We moreover show another computing can be derived from law large numbers due K.-T. Sturm (2002). In applications, medians means probably most needed tree space, instance invented by Billera, Holmes, Vogtmann tool averaging phylogenetic trees. It turns out, however, used model numerous tree-like structures. Since there now exists polynomial-time geodesics M. Owen S. Provan (2011), obtain efficient means, directly practice.