2026-08-01T15:17:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13787 2024-03-06T10:52:57Z ddc:004 open_access

Fréchet Mean and p-Mean on the Unit Circle: Decidability, Algorithm, and Applications to Clustering on the Flat Torus Cazals, Frédéric Delmas, Bernard O'Donnell, Timothee Frechét mean p-mean circular statistics decidability robustness multi-precision angular spaces flat torus clustering molecular conformations The center of mass of a point set lying on a manifold generalizes the celebrated Euclidean centroid, and is ubiquitous in statistical analysis in non Euclidean spaces. In this work, we give a complete characterization of the weighted p-mean of a finite set of angular values on S¹, based on a decomposition of S¹ such that the functional of interest has at most one local minimum per cell. This characterization is used to show that the problem is decidable for rational angular values -a consequence of Lindemann’s theorem on the transcendence of π, and to develop an effective algorithm parameterized by exact predicates. A robust implementation of this algorithm based on multi-precision interval arithmetic is also presented, and is shown to be effective for large values of n and p. We use it as building block to implement the k-means and k-means++ clustering algorithms on the flat torus, with applications to clustering protein molecular conformations. These algorithms are available in the Structural Bioinformatics Library (http://sbl.inria.fr). Our derivations are of interest in two respects. First, efficient p-mean calculations are relevant to develop principal components analysis on the flat torus encoding angular spaces-a particularly important case to describe molecular conformations. Second, our two-stage strategy stresses the interest of combinatorial methods for p-means, also emphasizing the role of numerical issues. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Frédéric Cazals and Bernard Delmas and Timothee O'Donnell 2021 Is Part Of LIPIcs, Volume 190, 19th International Symposium on Experimental Algorithms (SEA 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SEA.2021.15 urn:nbn:de:0030-drops-137870 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2021.15 eng https://creativecommons.org/licenses/by/4.0/legalcode