1. Главная
  2. Ресурсы
  3. Библиотечный поиск
Computing Medians andMeans in HadamardSpaces Miroslav Bačák2014 год

Computing Medians and Means in Hadamard Spaces
статья из журнала

Полный текстСтраница публикацииПубликация в OpenAlex
Аннотация: 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.
Год издания: 2014
Авторы: Miroslav Bačák
Издательство: Society for Industrial and Applied Mathematics
Источник: SIAM Journal on Optimization
Ключевые слова: Point processes and geometric inequalities, Morphological variations and asymmetry, 3D Shape Modeling and Analysis
Другие ссылки: SIAM Journal on Optimization (HTML)
CiteSeer X (The Pennsylvania State University) (PDF)
CiteSeer X (The Pennsylvania State University) (HTML)
arXiv (Cornell University) (PDF)
arXiv (Cornell University) (HTML)