HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Fréchet mean and $p$-mean on the unit circle: decidability, algorithm, and applications to clustering on the flat torus

Abstract : 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^1$ , based on a decomposition of $S^1$ 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.
Document type :
Conference papers
Complete list of metadata

Contributor : Frederic Cazals Connect in order to contact the contributor
Submitted on : Friday, March 26, 2021 - 7:20:10 PM
Last modification on : Friday, January 21, 2022 - 3:08:36 AM
Long-term archiving on: : Sunday, June 27, 2021 - 7:16:12 PM


Files produced by the author(s)


  • HAL Id : hal-03183028, version 1



Frédéric Cazals, B Delmas, Timothee O'Donnell. Fréchet mean and $p$-mean on the unit circle: decidability, algorithm, and applications to clustering on the flat torus. SEA 2021 - 19th Symposium on Experimental Algorithms, Jun 2021, Sophia Antipolis, France. ⟨hal-03183028⟩



Record views


Files downloads