betaFeedback

WorksMathematics

Certifiably Correct Fréchet Means in Orbit Spaces

Abstract

We study Fréchet means in orbit spaces of finite orthogonal group actions. Since computing these means is NP-hard in general, we take inspiration from group synchronization to develop tractable spectral and semidefinite relaxations. Pairwise alignment certifies global optimality and we develop a semidefinite certificate that can extend beyond this condition. For Gaussian data modulo sign, we prove that our certificate succeeds in a high-noise regime where alignment fails. Numerical experiments evaluate these methods in various settings, including summarizing ensembles of districting plans and clustering time series

Introduction

Given a collection of data points x1,…,xnx_1,\ldots,x_n in some space X\mathcal{X}, what point x∈Xx \in\mathcal{X} does a good job of representing the data points? In settings where the space is Euclidean, one is inclined to use the mean 1n∑i=1nxi\frac{1}{n}\sum_{i=1}^{n}x_i, but there are some settings in which the mean fails to capture important features of the data. For example, if each xix_i is a black-and-white image of someone’s face (vectorized so that each coordinate represents a pixel value), then the mean will exhibit some undesirable ghostly features. The issue here is that natural images form a low-dimensional and nonconvex subset of Euclidean space, and thanks to the lack of convexity, sample means fail to look natural. Is there a suitable alternative to the mean in settings where the space is nonconvex?

Recall that, given points x1,…,xnx_1,\ldots,x_n in a Euclidean space VV, the Euclidean mean is the point μ∈V\mu\in V that minimizes the mean squared error:

1n∑i=1n∥xi−μ∥2.\frac{1}{n}\sum_{i=1}^{n}\lVert x_i-\mu\rVert^2.

We can take inspiration from this to treat more general settings in which our space X\mathcal{X} has a notion of distance dXd_{\mathcal{X}}. Define the Fréchet functional F:X→RF:\mathcal{X}\to\mathbb{R} by

F(m)=1n∑i=1ndX(m,xi)2,F(m)=\frac{1}{n}\sum_{i=1}^{n}d_{\mathcal{X}}(m,x_i)^2,

and say μ∈X\mu\in\mathcal{X} is a Fréchet mean of x1,…,xnx_1,\ldots,x_n if μ\mu globally minimizes FF. Unfortunately, thanks to the nonlinear geometry of X\mathcal{X}, there is typically not enough convexity in the Fréchet functional for global minimizers to be easily obtained. As such, one is forced to make do with local minimizers, which are known as Karcher means.

The notion of a Fréchet mean originates in the work of Fréchet [8] and was later developed separately in the Riemannian setting by Karcher and Kendall [15, 17]. These ideas were later adapted to statistical shape analysis, where means on nonlinear and nonconvex shape spaces are a central object of study [16, 20]. In modern data science, Fréchet means arise as Wasserstein barycenters in optimal transport [29, 21], in signal processing [19], and in topological data analysis [27]. The Fréchet mean is useful in practice because it provides a representative point for non-Euclidean data without requiring vector space structure.

In this paper, we are interested in Fréchet means in a certain ubiquitous setting in data science. Suppose our data points are represented by vectors, but with the implicit understanding that there was a non-canonical choice made in the vector representation. For example, a simple unlabeled nn-vertex graph with edge weights might be represented by a weighted adjacency matrix, but only after deciding how to index the vertices. Alternatively, given a biological specimen, a scientist might record the (x,y,z)(x,y,z)-coordinates of nn specified landmarks, but only after deciding on a reference frame. In each of these cases, the choice of representation can be expressed as a group of ambiguities: in the first case, the group SnS_n acts on the adjacency matrix by conjugation, while in the second case, the group SO(3)SO(3) acts on the left of the 3×n3 \times n matrix whose columns give the origin-centered landmark coordinates.

In general, the data we are interested in lies in a finite-dimensional Hilbert space (V,⟨⋅,⋅⟩)(V,\langle\cdot,\cdot\rangle) with norm ∥⋅∥\|\cdot\| associated with its inner product. In addition, there is a known orthogonal group action G↷VG \curvearrowright V that captures the underlying ambiguity in the vector representation of our data. As such, we think of our data as residing in the orbit space X=V/G\mathcal{X}=V/G consisting of GG-orbits

[x]:=G⋅x for x∈V.[x] := G \cdot x \text{ for } x \in V.

By the orthogonality of the group action, the orbit space can be equipped with the natural quotient metric

d([x],[y]):=inf⁡g∈G∥x−gy∥.(1)d([x],[y]) := \inf_{g \in G} \|x-gy\|. \tag*{(1)}

Unless stated otherwise, we take GG to be finite, in which case the above infimum will be achieved by at least one group element.

Example 1.1. We will consider sign invariance as a running example throughout this work. Here, we take V=RdV=\mathbb{R}^{d} and G={±Id}G=\{\pm I_d\}, which we denote by G=±G=\pm. The metric (1) is then given by d([x],[y])=min⁡{∥x−y∥,∥x+y∥}d([x],[y])=\min\{\|x-y\|,\|x+y\|\}, and the quotient space Rd/±\mathbb{R}^{d}/\pm can be identified with a cone over RPd−1\mathbb{R}P^{d-1}. Figure 1.1 shows the quotient identification and resulting geometry in the special case where d=2d=2.

Illustration of $\mathbb{R}^{2}/\pm$

Figure 1.1. Illustration of R2/±\mathbb{R}^{2}/\pm. Left: The plane with the identification x∼−xx \sim-x shown in color. Right: The quotient space can be visualized as a cone after identifying each direction with its negation, e.g., by discarding the lower halfplane and then gluing the positive horizontal axis to the negative horizontal axis.

As illustrated in Figure 1.1, orbit spaces exhibit a level of nonconvexity that insists upon a theory of Fréchet means. In this setting, it will be convenient to consider Fréchet functional as the GG-invariant functional

F(m)=1n∑i=1nmin⁡g∈G∥m−gxi∥2(2)F(m) = \frac{1}{n}\sum_{i=1}^{n}\min_{g\in G}\lVert m-gx_i\rVert^2 \tag*{(2)}

over VV, rather than a functional over the quotient V/GV/G.

In the next section, we identify basic properties of Fréchet and Karcher means in orbit spaces, including generic uniqueness of the Fréchet mean and NP-hardness of its computation. Section 3 then introduces the notion of alignment and shows that the Euclidean mean of aligned orbit representatives represents a Fréchet mean. Next, Section 4 develops spectral and semidefinite relaxations inspired by group synchronization and derives computable certificates of global optimality. In the sign-invariant setting under a Gaussian model, Section 5 establishes that these certificates succeed well beyond the regime of pairwise alignment. Section 6 numerically evaluates the methods in a variety of settings, and then we conclude with a discussion in Section 7.

The state of play

In this section, we report a few basic results about Fréchet and Karcher means in orbit spaces: Karcher means are Euclidean means, Fréchet means are generically unique, Fréchet means are hard to find in the worst case, and traditional approaches to find such means are insufficient.

Karcher means are Euclidean means

We start with a structure theorem for Karcher means in orbit spaces.

Theorem 2.1. Let [y][y] be a Karcher mean of {[xi]}i=1n\{[x_i]\}_{i=1}^{n}. Then yy is the Euclidean mean of orbit representatives {gixi}i=1n\{g_i x_i\}_{i=1}^{n} for some g1,…,gn∈Gg_1,\ldots,g_n\in G.

To prove this, we will use what is presumably a standard fact from convex analysis:

Lemma 2.2. Given convex functions f1,…,fn:V→Rf_1,\ldots,f_n: V\to\mathbb{R}, suppose x0∈Vx_0\in V is a local minimizer of f=min⁡ifif=\min_i f_i. Then x0x_0 is also a global minimizer of fi⋆f_{i^\star} for each i⋆∈argmin⁡ifi(x0)i^\star\in\operatorname{argmin}_i f_i(x_0).

Proof. We prove the contrapositive. Suppose x0∈Vx_0\in V is not a global minimizer of fi⋆f_{i^\star} for some i⋆∈argmin⁡ifi(x0)i^\star\in\operatorname{argmin}_i f_i(x_0). Select any x1x_1 satisfying fi⋆(x1)<fi⋆(x0)f_{i^\star}(x_1)<f_{i^\star}(x_0) and for each t∈(0,1)t\in(0,1), put xt:=(1−t)x0+tx1x_t:=(1-t)x_0+tx_1. Then for every t∈(0,1)t\in(0,1), we have

min⁡ifi(xt)≤fi⋆(xt)≤(1−t)fi⋆(x0)+tfi⋆(x1)<fi⋆(x0)=f(x0).\min_i f_i(x_t)\le f_{i^\star}(x_t)\le(1-t)f_{i^\star}(x_0)+tf_{i^\star}(x_1)<f_{i^\star}(x_0)=f(x_0).

Taking tt arbitrarily small, it follows that x0x_0 is not a local minimizer of ff.

Proof of Theorem 2.1. The Fréchet functional (1.2) can be written as

F(m)=min⁡g1,…,gn∈G1n∑i=1n∥m−gixi∥2.F(m)=\min_{g_1,\ldots,g_n\in G}\frac{1}{n}\sum_{i=1}^{n}\lVert m-g_i x_i\rVert^2.

In particular, FF is the minimum of finitely many convex functions. Lemma 2.2 then gives that any local minimizer of FF must be a global minimizer of some

m⟼1n∑i=1n∥m−gixi∥2,m\longmapsto\frac{1}{n}\sum_{i=1}^{n}\lVert m-g_i x_i\rVert^2,

i.e., the Euclidean mean of {gixi}i=1n\{g_i x_i\}_{i=1}^{n}.

Theorem 2.1 suggests an alternating algorithm to find Fréchet means: alternate between (1) finding closest orbit representatives {gixi}i=1n\{g_i x_i\}_{i=1}^{n} to mm and (2) computing the Euclidean mean of {gixi}i=1n\{g_i x_i\}_{i=1}^{n}. This amounts to running the kk-means iteration with k=∣G∣k = \lvert G\rvert on \{g x_i\}_{i=1}^{n}_{i=1,g\in G} after initializing with a GG-orbit of proto-centroids. This approach, sometimes referred to as the “max-max” algorithm, is investigated in [6]. Unfortunately, such alternating algorithms are known to get stuck in local minimizers, and accordingly, we do not analyze this iteration in this paper.

The Fréchet mean is generically unique

Next, we show that the Fréchet mean is unique for generic data:

Theorem 2.3. Fix any finite G≤O(V)G \le O(V). For generic {xi}i=1n⊂V\{x_i\}_{i=1}^{n} \subset V, the Fréchet mean of {[xi]}i=1n⊂V/G\{[x_i]\}_{i=1}^{n} \subset V/G is unique.

The generic condition is meant in the semi-algebraic sense and, as such, the datasets {xi}i=1n\{x_i\}_{i=1}^{n} with multiple Fréchet means form a Lebesgue null set in VnV^n. Still, as the following example illustrates, uniqueness need not hold for arbitrary data.

Example 2.4. Let u,v∈Rdu, v \in\mathbb{R}^{d} be nonzero orthogonal vectors, and consider their sign-invariant orbits [u],[v]∈Rd/±[u], [v] \in\mathbb{R}^{d}/\pm. This two-point dataset has two different Fréchet means in orbit space: [u+v2]\left[\frac{u+v}{2}\right] and [u−v2]\left[\frac{u-v}{2}\right]. Meanwhile, any perturbation that makes the vectors non-orthogonal results in a dataset with a unique Fréchet mean.

To prove Theorem 2.3, we will use the following lemma, originally observed in [6]. We provide a proof here for completeness.

Lemma 2.5. Fix any finite G≤O(V)G \le O(V) and {xi}i=1n⊂V\{x_i\}_{i=1}^{n} \subset V. Then any two Fréchet means of {[xi]}i=1n⊂V/G\{[x_i]\}_{i=1}^{n} \subset V/G have the same norm.

Proof. Given m∈Vm \in V, write m=∥m∥m^m = \lVert m\rVert\hat{m}, where ∥m^∥=1\lVert\hat{m}\rVert= 1. Then the Fréchet functional (1.2) can be written as

F(m)=∥m∥2−2n∥m∥∑i=1nmax⁡g∈G⟨m^,gxi⟩+1n∑i=1n∥xi∥2.(3)F(m) = \lVert m\rVert^2 - \frac{2}{n}\lVert m\rVert\sum_{i=1}^{n}\max_{g\in G}\langle\hat{m},gx_i\rangle+ \frac{1}{n}\sum_{i=1}^{n}\lVert x_i\rVert^2. \tag*{(3)}

We decompose the minimization over mm as

min⁡m∈VF(m)=min⁡m^∈S(V)min⁡∥m∥F(∥m∥m^).\min_{m\in V} F(m) = \min_{\hat{m}\in S(V)}\min_{\lVert m\rVert} F(\lVert m\rVert\hat{m}).

References

  1. [1]Emmanuel Abbe, Afonso S. Bandeira, Annina Bracher, and Amit Singer. Decoding binary node labels from censored edge measurements: Phase transition and efficient recovery. IEEE Transactions on Network Science and Engineering, 1(1):10–22, 2014.arxiv.org/abs/1404.4749
  2. [2]Boris Alexeev, Wenyan Luo, Dustin G. Mixon, and Yan X Zhang. On the clustering behavior of sliding windows. arXiv preprint arXiv:2503.14393, 2025.arxiv.org/abs/2503.14393
  3. [3]Afonso S. Bandeira. A note on probably certifiably correct algorithms. Comptes Rendus Mathématique, 354(3):329–333, 2016.arxiv.org/abs/1509.00824
  4. [4]Afonso S. Bandeira, Nicolas Boumal, and Amit Singer. Tightness of the maximum likelihood semidefinite relaxation for angular synchronization. Mathematical Programming, 163(1–2):145–167, May 2017.DOI
  5. [5]Dany R. DeFord, Gregory Herschlag, and Jonathan C. Mattingly. A cycle walk for sampling measures on spanning forests for redistricting. arXiv preprint arXiv:2509.08629, 2025.arxiv.org/abs/2509.08629
  6. [6]Loïc Devilliers, Stéphanie Allassonnière, Alain Trové, and Xavier Pennec. Inconsistency of template estimation by minimizing of the variance/pre-variance in the quotient space. Entropy, 19(6):288, June 2017.DOI
  7. [7]Loïc Devilliers, Stéphanie Allassonnière, Alain Trouvé, and Xavier Pennec. Template estimation in computational anatomy: Fréchet means top and quotient spaces are not consistent. SIAM Journal on Imaging Sciences, 10(3):1139–1169, 2017.arxiv.org/abs/1608.03703
  8. [8]Maurice Fréchet. Les éléments aléatoires de nature quelconque dans un espace distancié. Annales de l’Institut Henri Poincaré, 10(4):215–310, 1948.
  9. [9]Tingran Gao and Zhizhen Zhao. Multi-frequency phase synchronization. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 2132–2141. PMLR, 2019.arxiv.org/abs/1901.08235
  10. [10]M. R. Garey, D. S. Johnson, and L. Stockmeyer. Some simplified NP-complete graph problems. Theoretical Computer Science, 1(3):237–267, 1976.DOI
  11. [11]Colin Goodall. Procrustes methods in the statistical analysis of shape. Journal of the Royal Statistical Society: Series B (Methodological), 53(2):285–321, 1991.DOI
  12. [12]John C. Gower. Generalized Procrustes analysis. Psychometrika, 40(1):33–51, 1975.
  13. [13]David Groisser. Newton’s method, zeroes of vector fields, and the Riemannian center of mass. Advances in Applied Mathematics, 33(1):95–135, 2004.DOI
  14. [14]Stephan F. Huckemann. On the meaning of mean shape: Manifold stability, locus and the two sample test. Annals of the Institute of Statistical Mathematics, 64(6):1227–1259, 2012.
  15. [15]Hermann Karcher. Riemannian center of mass and mollifier smoothing. Communications on Pure and Applied Mathematics, 30(5):509–541, 1977.DOI
  16. [16]David G. Kendall. A survey of the statistical theory of shape. Statistical Science, 4(2):87–99, 1989.
  17. [17]Wilfrid S. Kendall. Probability, convexity, and harmonic maps with small image I: Uniqueness and fine existence. Proceedings of the London Mathematical Society, s3-61(2):371–406, 1990.
  18. [18]Eamon Keogh and Jessica Lin. Clustering of time-series subsequences is meaningless: implications for previous and future research. Knowledge and Information Systems, 8(2):154–177, 2005.
  19. [19]Sebastian Kurtek, Anuj Srivastava, and Wei Wu. Signal estimation under random time-warpings and nonlinear signal alignment. In Advances in Neural Information Processing Systems, volume 24, pages 675–683, 2011.
  20. [20]Huiling Le and Alfred Kume. The Fréchet mean shape and the shape of the means. Advances in Applied Probability, 32(1):101–113, 2000.DOI
  21. [21]Tom Needham and Thomas Weihgill. Geometric averages of partitioned datasets. SIAM Journal on Applied Algebra and Geometry, 7(1):104–132, 2023.arxiv.org/abs/2107.03460
  22. [22]Xavier Pennec. Intrinsic statistics on Riemannian manifolds: Basic tools for geometric measurements. Journal of Mathematical Imaging and Vision, 25(1):127–154, July 2006.DOI
  23. [23]Daniel Pizarro and Adrien Bartoli. Global optimization for optimal generalized Procrustes analysis. In CVPR 2011, pages 2409–2415. IEEE, 2011.DOI
  24. [24]Naoki Saito. Local Feature Extraction and Its Applications Using a Library of Bases. PhD thesis, Yale University, December 1994.
  25. [25]Amit Singer. Angular synchronization by eigenvectors and semidefinite programming. Applied and Computational Harmonic Analysis, 30(1):20–36, 2011.arxiv.org/abs/0905.3174
  26. [26]CBF dataset. Time Series Classification website, https://timeseriesclassification.com/description.php?Dataset=CBF. Accessed 29 April 2026.
  27. [27]Katharine Turner, Yuriy Mileyko, Sayan Mukherjee, and John Harer. Fréchet means for distributions of persistence diagrams. Discrete & Computational Geometry, 52(1):44–70, 2014.
  28. [28]Patrick Wagner, Nils Strothoff, Ralf-Dieter Bouss eljot, Wojciech Samek, and Tobias Schaeffer. PTB-XL, a large publicly available electrocardiography dataset. PhysioNet, November 2022. Version 1.0.3.
  29. [29]Yoav Zemel and Victor M. Panaretos. Fréchet means and Procrustes analysis in Wasserstein space. Bernoulli, 25(2):932–976, 2019.arxiv.org/abs/1701.06876

Paper details

vlnc:W_quqqxptk
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 11

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

ChatGPT-6 Pro

View statement
Looking for related papers…
Contents