Introduction
Given a collection of data points x 1 , … , x n x_1,\ldots,x_n x 1 , … , x n in some space X \mathcal{X} X , what point x ∈ X x \in\mathcal{X} x ∈ X does a good job of representing the data points? In settings where the space is Euclidean, one is inclined to use the mean 1 n ∑ i = 1 n x i \frac{1}{n}\sum_{i=1}^{n}x_i n 1 ∑ 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 x i x_i x 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 x 1 , … , x n x_1,\ldots,x_n x 1 , … , x n in a Euclidean space V V V , the Euclidean mean is the point μ ∈ V \mu\in V μ ∈ V that minimizes the mean squared error:
1 n ∑ i = 1 n ∥ x i − μ ∥ 2 . \frac{1}{n}\sum_{i=1}^{n}\lVert x_i-\mu\rVert^2. n 1 i = 1 ∑ n ∥ x i − μ ∥ 2 .
We can take inspiration from this to treat more general settings in which our space X \mathcal{X} X has a notion of distance d X d_{\mathcal{X}} d X . Define the Fréchet functional F : X → R F:\mathcal{X}\to\mathbb{R} F : X → R by
F ( m ) = 1 n ∑ i = 1 n d X ( m , x i ) 2 , F(m)=\frac{1}{n}\sum_{i=1}^{n}d_{\mathcal{X}}(m,x_i)^2, F ( m ) = n 1 i = 1 ∑ n d X ( m , x i ) 2 ,
and say μ ∈ X \mu\in\mathcal{X} μ ∈ X is a Fréchet mean of x 1 , … , x n x_1,\ldots,x_n x 1 , … , x n if μ \mu μ globally minimizes F F F . Unfortunately, thanks to the nonlinear geometry of X \mathcal{X} 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 n n n -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) ( x , y , z ) -coordinates of n n n 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 S n S_n S n acts on the adjacency matrix by conjugation, while in the second case, the group S O ( 3 ) SO(3) S O ( 3 ) acts on the left of the 3 × n 3 \times n 3 × 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) ( V , ⟨ ⋅ , ⋅ ⟩) with norm ∥ ⋅ ∥ \|\cdot\| ∥ ⋅ ∥ associated with its inner product. In addition, there is a known orthogonal group action G ↷ V G \curvearrowright V G ↷ 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 X = V / G consisting of G G G -orbits
[ x ] : = G ⋅ x for x ∈ V . [x] := G \cdot x \text{ for } x \in V. [ x ] := G ⋅ x for x ∈ 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 − g y ∥ . (1) d([x],[y]) := \inf_{g \in G} \|x-gy\|. \tag*{(1)} d ([ x ] , [ y ]) := g ∈ G inf ∥ x − g y ∥. (1)
Unless stated otherwise, we take G G G 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 = R d V=\mathbb{R}^{d} V = R d and G = { ± I d } G=\{\pm I_d\} G = { ± I d } , which we denote by G = ± G=\pm G = ± . The metric (1) is then given by d ( [ x ] , [ y ] ) = min { ∥ x − y ∥ , ∥ x + y ∥ } d([x],[y])=\min\{\|x-y\|,\|x+y\|\} d ([ x ] , [ y ]) = min { ∥ x − y ∥ , ∥ x + y ∥ } , and the quotient space R d / ± \mathbb{R}^{d}/\pm R d / ± can be identified with a cone over R P d − 1 \mathbb{R}P^{d-1} R P d − 1 . Figure 1.1 shows the quotient identification and resulting geometry in the special case where d = 2 d=2 d = 2 .
Figure 1.1. Illustration of R 2 / ± \mathbb{R}^{2}/\pm R 2 / ± . Left: The plane with the identification x ∼ − x x \sim-x x ∼ − 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 G G G -invariant functional
F ( m ) = 1 n ∑ i = 1 n min g ∈ G ∥ m − g x i ∥ 2 (2) F(m) = \frac{1}{n}\sum_{i=1}^{n}\min_{g\in G}\lVert m-gx_i\rVert^2 \tag*{(2)} F ( m ) = n 1 i = 1 ∑ n g ∈ G min ∥ m − g x i ∥ 2 (2)
over V V V , rather than a functional over the quotient V / G V/G V / 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] [ y ] be a Karcher mean of { [ x i ] } i = 1 n \{[x_i]\}_{i=1}^{n} {[ x i ] } i = 1 n . Then y y y is the Euclidean mean of orbit representatives { g i x i } i = 1 n \{g_i x_i\}_{i=1}^{n} { g i x i } i = 1 n for some g 1 , … , g n ∈ G g_1,\ldots,g_n\in G g 1 , … , g n ∈ G .
To prove this, we will use what is presumably a standard fact from convex analysis:
Lemma 2.2. Given convex functions f 1 , … , f n : V → R f_1,\ldots,f_n: V\to\mathbb{R} f 1 , … , f n : V → R , suppose x 0 ∈ V x_0\in V x 0 ∈ V is a local minimizer of f = min i f i f=\min_i f_i f = min i f i . Then x 0 x_0 x 0 is also a global minimizer of f i ⋆ f_{i^\star} f i ⋆ for each i ⋆ ∈ argmin i f i ( x 0 ) i^\star\in\operatorname{argmin}_i f_i(x_0) i ⋆ ∈ argmin i f i ( x 0 ) .
Proof. We prove the contrapositive. Suppose x 0 ∈ V x_0\in V x 0 ∈ V is not a global minimizer of f i ⋆ f_{i^\star} f i ⋆ for some i ⋆ ∈ argmin i f i ( x 0 ) i^\star\in\operatorname{argmin}_i f_i(x_0) i ⋆ ∈ argmin i f i ( x 0 ) . Select any x 1 x_1 x 1 satisfying f i ⋆ ( x 1 ) < f i ⋆ ( x 0 ) f_{i^\star}(x_1)<f_{i^\star}(x_0) f i ⋆ ( x 1 ) < f i ⋆ ( x 0 ) and for each t ∈ ( 0 , 1 ) t\in(0,1) t ∈ ( 0 , 1 ) , put x t : = ( 1 − t ) x 0 + t x 1 x_t:=(1-t)x_0+tx_1 x t := ( 1 − t ) x 0 + t x 1 . Then for every t ∈ ( 0 , 1 ) t\in(0,1) t ∈ ( 0 , 1 ) , we have
min i f i ( x t ) ≤ f i ⋆ ( x t ) ≤ ( 1 − t ) f i ⋆ ( x 0 ) + t f i ⋆ ( x 1 ) < f i ⋆ ( x 0 ) = f ( x 0 ) . \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). i min f i ( x t ) ≤ f i ⋆ ( x t ) ≤ ( 1 − t ) f i ⋆ ( x 0 ) + t f i ⋆ ( x 1 ) < f i ⋆ ( x 0 ) = f ( x 0 ) .
Taking t t t arbitrarily small, it follows that x 0 x_0 x 0 is not a local minimizer of f f f .
Proof of Theorem 2.1. The Fréchet functional (1.2) can be written as
F ( m ) = min g 1 , … , g n ∈ G 1 n ∑ i = 1 n ∥ m − g i x i ∥ 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. F ( m ) = g 1 , … , g n ∈ G min n 1 i = 1 ∑ n ∥ m − g i x i ∥ 2 .
In particular, F F F is the minimum of finitely many convex functions. Lemma 2.2 then gives that any local minimizer of F F F must be a global minimizer of some
m ⟼ 1 n ∑ i = 1 n ∥ m − g i x i ∥ 2 , m\longmapsto\frac{1}{n}\sum_{i=1}^{n}\lVert m-g_i x_i\rVert^2, m ⟼ n 1 i = 1 ∑ n ∥ m − g i x i ∥ 2 ,
i.e., the Euclidean mean of { g i x i } i = 1 n \{g_i x_i\}_{i=1}^{n} { 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 { g i x i } i = 1 n \{g_i x_i\}_{i=1}^{n} { g i x i } i = 1 n to m m m and (2) computing the Euclidean mean of { g i x i } i = 1 n \{g_i x_i\}_{i=1}^{n} { g i x i } i = 1 n . This amounts to running the k k k -means iteration with k = ∣ G ∣ k = \lvert G\rvert k = ∣ G ∣ on \{g x_i\}_{i=1}^{n}_{i=1,g\in G} after initializing with a G G G -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) G ≤ O ( V ) . For generic { x i } i = 1 n ⊂ V \{x_i\}_{i=1}^{n} \subset V { x i } i = 1 n ⊂ V , the Fréchet mean of { [ x i ] } i = 1 n ⊂ V / G \{[x_i]\}_{i=1}^{n} \subset V/G {[ x i ] } i = 1 n ⊂ V / G is unique.
The generic condition is meant in the semi-algebraic sense and, as such, the datasets { x i } i = 1 n \{x_i\}_{i=1}^{n} { x i } i = 1 n with multiple Fréchet means form a Lebesgue null set in V n V^n V n . Still, as the following example illustrates, uniqueness need not hold for arbitrary data.
Example 2.4. Let u , v ∈ R d u, v \in\mathbb{R}^{d} u , v ∈ R d be nonzero orthogonal vectors, and consider their sign-invariant orbits [ u ] , [ v ] ∈ R d / ± [u], [v] \in\mathbb{R}^{d}/\pm [ u ] , [ v ] ∈ R d / ± . This two-point dataset has two different Fréchet means in orbit space: [ u + v 2 ] \left[\frac{u+v}{2}\right] [ 2 u + v ] and [ u − v 2 ] \left[\frac{u-v}{2}\right] [ 2 u − v ] . 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) G ≤ O ( V ) and { x i } i = 1 n ⊂ V \{x_i\}_{i=1}^{n} \subset V { x i } i = 1 n ⊂ V . Then any two Fréchet means of { [ x i ] } i = 1 n ⊂ V / G \{[x_i]\}_{i=1}^{n} \subset V/G {[ x i ] } i = 1 n ⊂ V / G have the same norm.
Proof. Given m ∈ V m \in V m ∈ V , write m = ∥ m ∥ m ^ m = \lVert m\rVert\hat{m} m = ∥ m ∥ m ^ , where ∥ m ^ ∥ = 1 \lVert\hat{m}\rVert= 1 ∥ m ^ ∥ = 1 . Then the Fréchet functional (1.2) can be written as
F ( m ) = ∥ m ∥ 2 − 2 n ∥ m ∥ ∑ i = 1 n max g ∈ G ⟨ m ^ , g x i ⟩ + 1 n ∑ i = 1 n ∥ x i ∥ 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)} F ( m ) = ∥ m ∥ 2 − n 2 ∥ m ∥ i = 1 ∑ n g ∈ G max ⟨ m ^ , g x i ⟩ + n 1 i = 1 ∑ n ∥ x i ∥ 2 . (3)
We decompose the minimization over m m m as
min m ∈ V F ( 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}). m ∈ V min F ( m ) = m ^ ∈ S ( V ) min ∥ m ∥ min F (∥ m ∥ m ^ ) .
For fixed m ^ \hat{m} m ^ , F F F is quadratic in ∥ m ∥ \lVert m\rVert ∥ m ∥ and so is minimized at
∥ m ∥ = ( 1 n ∑ i = 1 n max g ∈ G ⟨ m ^ , g x i ⟩ ) + , \lVert m\rVert= \left(\frac{1}{n}\sum_{i=1}^{n}\max_{g\in G}\langle\hat{m},gx_i\rangle\right)_{+}, ∥ m ∥ = ( n 1 i = 1 ∑ n g ∈ G max ⟨ m ^ , g x i ⟩ ) + ,
where ( x ) + : = max { x , 0 } (x)_{+} := \max\{x,0\} ( x ) + := max { x , 0 } . Substituting back into (2.1), the minimization reduces to
min m ∈ V F ( m ) = − max m ^ ∈ S ( V ) ( 1 n ∑ i = 1 n max g ∈ G ⟨ m ^ , g x i ⟩ ) + 2 + 1 n ∑ i = 1 n ∥ x i ∥ 2 . \min_{m\in V} F(m) = -\max_{\hat{m}\in S(V)}\left(\frac{1}{n}\sum_{i=1}^{n}\max_{g\in G}\langle\hat{m},gx_i\rangle\right)_{+}^{2} + \frac{1}{n}\sum_{i=1}^{n}\lVert x_i\rVert^2. m ∈ V min F ( m ) = − m ^ ∈ S ( V ) max ( n 1 i = 1 ∑ n g ∈ G max ⟨ m ^ , g x i ⟩ ) + 2 + n 1 i = 1 ∑ n ∥ x i ∥ 2 .
Therefore the minimum of F F F determines ( 1 n ∑ i = 1 n max g ∈ G ⟨ m ^ , g x i ⟩ ) + 2 \left(\frac{1}{n}\sum_{i=1}^{n}\max_{g\in G}\langle\hat{m},gx_i\rangle\right)_{+}^{2} ( n 1 ∑ i = 1 n max g ∈ G ⟨ m ^ , g x i ⟩ ) + 2 , which in turn determines the norm ∥ m ∥ \lVert m\rVert ∥ m ∥ .
Proof of Theorem 2.3. Denote the Fréchet functional for { x i } i = 1 n \{x_i\}_{i=1}^{n} { x i } i = 1 n at m m m by
F ( m ; { x i } ) : = 1 n ∑ i = 1 n min g ∈ G ∥ m − g x i ∥ 2 . F(m;\{x_i\}) := \frac{1}{n}\sum_{i=1}^{n}\min_{g\in G}\lVert m-gx_i\rVert^2. F ( m ; { x i }) := n 1 i = 1 ∑ n g ∈ G min ∥ m − g x i ∥ 2 .
Letting g = ( g 1 , … , g n ) ∈ G n \mathbf{g}=(g_1,\ldots,g_n)\in G^n g = ( g 1 , … , g n ) ∈ G n denote a choice of group elements, we reduce the problem to minimizing over the finite set G n G^n G n :
min m ∈ V F ( m ; { x i } ) = min m ∈ V min g ∈ G n 1 n ∑ i = 1 n ∥ m − g i x i ∥ 2 = min g ∈ G n min m ∈ V 1 n ∑ i = 1 n ∥ m − g i x i ∥ 2 = min g ∈ G n 1 n ∑ i = 1 n ∥ ( 1 n ∑ j = 1 n g j x j ) − g i x i ∥ 2 = : min g ∈ G n F ( g ; { x i } i = 1 n ) . \begin{aligned}
\min_{m\in V}F(m;\{x_i\})&=\min_{m\in V}\min_{\mathbf{g}\in G^n}\frac{1}{n}\sum_{i=1}^{n}\lVert m-g_ix_i\rVert^2\\
&=\min_{\mathbf{g}\in G^n}\min_{m\in V}\frac{1}{n}\sum_{i=1}^{n}\lVert m-g_ix_i\rVert^2\\
&=\min_{\mathbf{g}\in G^n}\frac{1}{n}\sum_{i=1}^{n}\left\lVert\left(\frac{1}{n}\sum_{j=1}^{n}g_jx_j\right)-g_ix_i\right\rVert^2\\
&=:\min_{\mathbf{g}\in G^n}F(\mathbf{g};\{x_i\}_{i=1}^n).
\end{aligned} m ∈ V min F ( m ; { x i }) = m ∈ V min g ∈ G n min n 1 i = 1 ∑ n ∥ m − g i x i ∥ 2 = g ∈ G n min m ∈ V min n 1 i = 1 ∑ n ∥ m − g i x i ∥ 2 = g ∈ G n min n 1 i = 1 ∑ n ( n 1 j = 1 ∑ n g j x j ) − g i x i 2 =: g ∈ G n min F ( g ; { x i } i = 1 n ) .
The functional g ↦ F ( g ; { x i } i = 1 n ) \mathbf{g}\mapsto F(\mathbf{g};\{x_i\}_{i=1}^n) g ↦ F ( g ; { x i } i = 1 n ) is invariant under the diagonal action h ⋅ g = ( h g 1 , … , h g n ) h\cdot\mathbf{g}=(hg_1,\ldots,hg_n) h ⋅ g = ( h g 1 , … , h g n ) , so without loss of generality we fix the representative by taking g 1 = I g_1=I g 1 = I and restrict to { I } × G n − 1 \{I\}\times G^{n-1} { I } × G n − 1 . Next consider the collection of data for which two distinct sets of group elements attain the Fréchet mean:
N = ⋃ g ≠ h ∈ { I } × G n − 1 { { x i } i = 1 n : F ( g ; { x i } ) = F ( h ; { x i } ) = min a ∈ G n F ( a ; { x i } ) } . (4) N=\bigcup_{\mathbf{g}\ne\mathbf{h}\in\{I\}\times G^{n-1}}\left\{\{x_i\}_{i=1}^n:F(\mathbf{g};\{x_i\})=F(\mathbf{h};\{x_i\})=\min_{\mathbf{a}\in G^n}F(\mathbf{a};\{x_i\})\right\}. \tag*{(4)} N = g = h ∈ { I } × G n − 1 ⋃ { { x i } i = 1 n : F ( g ; { x i }) = F ( h ; { x i }) = a ∈ G n min F ( a ; { x i }) } . (4)
For any distinct g , h \mathbf{g},\mathbf{h} g , h attaining the Fréchet mean,
∥ 1 n ∑ j = 1 n g j x j ∥ 2 − ∥ 1 n ∑ j = 1 n h j x j ∥ 2 = 0. \left\lVert\frac{1}{n}\sum_{j=1}^{n}g_jx_j\right\rVert^2-\left\lVert\frac{1}{n}\sum_{j=1}^{n}h_jx_j\right\rVert^2=0. n 1 j = 1 ∑ n g j x j 2 − n 1 j = 1 ∑ n h j x j 2 = 0.
by Lemma 2.5 . Expanding and subtracting the squared norms in F F F then shows that
{ { x i } i = 1 n : F ( g ; { x i } ) = F ( h ; { x i } ) } ⊆ ker K g , h , \left\{\{x_i\}_{i=1}^n:F(\mathbf{g};\{x_i\})=F(\mathbf{h};\{x_i\})\right\}\subseteq\ker K_{\mathbf{g},\mathbf{h}}, { { x i } i = 1 n : F ( g ; { x i }) = F ( h ; { x i }) } ⊆ ker K g , h ,
where
K g , h ( { x i } i = 1 n ) : = ∑ i , j ⟨ x j , ( g j − 1 g i − h j − 1 h i ) x i ⟩ . K_{\mathbf{g},\mathbf{h}}(\{x_i\}_{i=1}^n):=\sum_{i,j}\langle x_j,(g_j^{-1}g_i-h_j^{-1}h_i)x_i\rangle. K g , h ({ x i } i = 1 n ) := i , j ∑ ⟨ x j , ( g j − 1 g i − h j − 1 h i ) x i ⟩ .
For a fixed g , h \mathbf{g},\mathbf{h} g , h , K g , h K_{\mathbf{g},\mathbf{h}} K g , h defines a polynomial functional on V n V^n V n . We now show that K g , h K_{\mathbf{g},\mathbf{h}} K g , h is nontrivial. Since g ≠ h \mathbf{g}\ne\mathbf{h} g = h there is some index j ≥ 2 j\ge2 j ≥ 2 with g j ≠ h j g_j\ne h_j g j = h j . Then the ( 1 , j ) (1,j) ( 1 , j ) and ( j , 1 ) (j,1) ( j , 1 ) terms yield
2 ⟨ x 1 , ( g j − h j ) x j ⟩ , 2\langle x_1,(g_j-h_j)x_j\rangle, 2 ⟨ x 1 , ( g j − h j ) x j ⟩ ,
which is a nonzero quadratic form, and so x 1 , x j x_1,x_j x 1 , x j can be chosen to make it nonzero; letting x k = 0 x_k=0 x k = 0 for k ∉ { 1 , j } k\notin\{1,j\} k ∈ / { 1 , j } yields a nonzero point in the image of K g , h K_{\mathbf{g},\mathbf{h}} K g , h . Hence K g , h K_{\mathbf{g},\mathbf{h}} K g , h is not identically zero, and as such, ker K g , h \ker K_{\mathbf{g},\mathbf{h}} ker K g , h is a proper algebraic subset of V n V^n V n . By (4) , N N N is contained in a finite union of proper algebraic subsets. Thus, the Fréchet mean is generically unique.
Computing the Fréchet mean is NP-hard
Although the Fréchet mean is generically unique, it is in general NP-hard to find, even in the special case of R d / ± \mathbb{R}^d/\pm R d / ± .
Proposition 2.6. Computing the Fréchet mean in R d / ± \mathbb{R}^d/\pm R d / ± is NP-hard when the dimension d d d is part of the input.
(Despite this result, it may be the case that computing the Fréchet mean in R d / ± \mathbb{R}^d/\pm R d / ± is tractable for any fixed d d d . We do not approach this problem here.)
Proof of Proposition 2.6 . We prove the result by reduction from MaxCut, a well-known NP-hard problem [10 ] . Given a graph H H H with n n n vertices and d d d edges, consider an oriented edge-vertex incidence matrix X ∈ R d × n X \in\mathbb{R}^{d \times n} X ∈ R d × n ; to be explicit, if edge i i i is incident to vertices j j j and k k k with j < k j < k j < k , then we may define X X X by X i j = 1 X_{ij}=1 X ij = 1 , X i k = − 1 X_{ik}=-1 X ik = − 1 , and X i l = 0 X_{il}=0 X i l = 0 for all l ∉ { j , k } l \notin\{j,k\} l ∈ / { j , k } . Then the Laplacian of H H H is given by L = X T X L=X^{\mathsf{T}}X L = X T X . Recall that
MaxCut ( H ) = max ϵ ∈ { ± 1 } n 1 4 ϵ T L ϵ = 1 4 max ϵ ∈ { ± 1 } n ∥ X ϵ ∥ 2 . \operatorname{MaxCut}(H)=\max_{\epsilon\in\{\pm1\}^{n}}\frac{1}{4}\epsilon^{\mathsf{T}}L\epsilon=\frac{1}{4}\max_{\epsilon\in\{\pm1\}^{n}}\lVert X\epsilon\rVert^{2}. MaxCut ( H ) = ϵ ∈ { ± 1 } n max 4 1 ϵ T L ϵ = 4 1 ϵ ∈ { ± 1 } n max ∥ X ϵ ∥ 2 .
Let x i x_i x i denote the i i i th column of X X X . Then the Fréchet functional associated with x 1 , … , x n x_1,\ldots,x_n x 1 , … , x n satisfies
F ( m ) = 1 n ∑ i = 1 n min { ∥ m − x i ∥ 2 , ∥ m + x i ∥ 2 } = min ϵ ∈ { ± 1 } n 1 n ∑ i = 1 n ∥ m − ϵ i x i ∥ 2 , F(m)=\frac{1}{n}\sum_{i=1}^{n}\min\{\lVert m-x_i\rVert^{2},\lVert m+x_i\rVert^{2}\}=\min_{\epsilon\in\{\pm1\}^{n}}\frac{1}{n}\sum_{i=1}^{n}\lVert m-\epsilon_i x_i\rVert^{2}, F ( m ) = n 1 i = 1 ∑ n min {∥ m − x i ∥ 2 , ∥ m + x i ∥ 2 } = ϵ ∈ { ± 1 } n min n 1 i = 1 ∑ n ∥ m − ϵ i x i ∥ 2 ,
and so
min m ∈ R d F ( m ) = min m ∈ R d min ϵ ∈ { ± 1 } n 1 n ∑ i = 1 n ∥ m − ϵ i x i ∥ 2 = min ϵ ∈ { ± 1 } n min m ∈ R d 1 n ∑ i = 1 n ∥ m − ϵ i x i ∥ 2 . \min_{m\in\mathbb{R}^{d}}F(m)=\min_{m\in\mathbb{R}^{d}}\min_{\epsilon\in\{\pm1\}^{n}}\frac{1}{n}\sum_{i=1}^{n}\lVert m-\epsilon_i x_i\rVert^{2}=\min_{\epsilon\in\{\pm1\}^{n}}\min_{m\in\mathbb{R}^{d}}\frac{1}{n}\sum_{i=1}^{n}\lVert m-\epsilon_i x_i\rVert^{2}. m ∈ R d min F ( m ) = m ∈ R d min ϵ ∈ { ± 1 } n min n 1 i = 1 ∑ n ∥ m − ϵ i x i ∥ 2 = ϵ ∈ { ± 1 } n min m ∈ R d min n 1 i = 1 ∑ n ∥ m − ϵ i x i ∥ 2 .
For a fixed ϵ \epsilon ϵ , the minimizer of 1 n ∑ i = 1 n ∥ m − ϵ i x i ∥ 2 \frac{1}{n}\sum_{i=1}^{n}\lVert m-\epsilon_i x_i\rVert^{2} n 1 ∑ i = 1 n ∥ m − ϵ i x i ∥ 2 is given by the Euclidean mean 1 n X ϵ \frac{1}{n}X\epsilon n 1 X ϵ , in which case
1 n ∑ i = 1 n ∥ 1 n X ϵ − ϵ i x i ∥ 2 = ∥ 1 n X ϵ ∥ 2 − 2 ⟨ 1 n X ϵ , 1 n ∑ i = 1 n ϵ i x i ⟩ + 1 n ∑ i = 1 n ∥ ϵ i x i ∥ 2 = 1 n ∑ i = 1 n ∥ x i ∥ 2 − 1 n 2 ∥ X ϵ ∥ 2 . \begin{aligned}
\frac{1}{n}\sum_{i=1}^{n}\left\lVert\frac{1}{n}X\epsilon-\epsilon_i x_i\right\rVert^{2}=\left\lVert\frac{1}{n}X\epsilon\right\rVert^{2}-2\left\langle\frac{1}{n}X\epsilon,\frac{1}{n}\sum_{i=1}^{n}\epsilon_i x_i\right\rangle+\frac{1}{n}\sum_{i=1}^{n}\lVert\epsilon_i x_i\rVert^{2} \\
&=\frac{1}{n}\sum_{i=1}^{n}\lVert x_i\rVert^{2}-\frac{1}{n^{2}}\lVert X\epsilon\rVert^{2}.
\end{aligned} n 1 i = 1 ∑ n n 1 X ϵ − ϵ i x i 2 = n 1 X ϵ 2 − 2 ⟨ n 1 X ϵ , n 1 i = 1 ∑ n ϵ i x i ⟩ + n 1 i = 1 ∑ n ∥ ϵ i x i ∥ 2 = n 1 i = 1 ∑ n ∥ x i ∥ 2 − n 2 1 ∥ X ϵ ∥ 2 .
Overall,
min m ∈ R d F ( m ) = min ϵ ∈ { ± 1 } n ( 1 n ∑ i = 1 n ∥ x i ∥ 2 − 1 n 2 ∥ X ϵ ∥ 2 ) = 1 n ∑ i = 1 n ∥ x i ∥ 2 − 1 n 2 max ϵ ∈ { ± 1 } n ∥ X ϵ ∥ 2 . \min_{m\in\mathbb{R}^{d}}F(m)=\min_{\epsilon\in\{\pm1\}^{n}}\left(\frac{1}{n}\sum_{i=1}^{n}\lVert x_i\rVert^{2}-\frac{1}{n^{2}}\lVert X\epsilon\rVert^{2}\right)=\frac{1}{n}\sum_{i=1}^{n}\lVert x_i\rVert^{2}-\frac{1}{n^{2}}\max_{\epsilon\in\{\pm1\}^{n}}\lVert X\epsilon\rVert^{2}. m ∈ R d min F ( m ) = ϵ ∈ { ± 1 } n min ( n 1 i = 1 ∑ n ∥ x i ∥ 2 − n 2 1 ∥ X ϵ ∥ 2 ) = n 1 i = 1 ∑ n ∥ x i ∥ 2 − n 2 1 ϵ ∈ { ± 1 } n max ∥ X ϵ ∥ 2 .
It follows that
MaxCut ( H ) = 1 4 max ϵ ∈ { ± 1 } n ∥ X ϵ ∥ 2 = n 2 4 ( 1 n ∑ i = 1 n ∥ x i ∥ 2 − min m ∈ R d F ( m ) ) . \operatorname{MaxCut}(H)=\frac{1}{4}\max_{\epsilon\in\{\pm1\}^{n}}\lVert X\epsilon\rVert^{2}=\frac{n^{2}}{4}\left(\frac{1}{n}\sum_{i=1}^{n}\lVert x_i\rVert^{2}-\min_{m\in\mathbb{R}^{d}}F(m)\right). MaxCut ( H ) = 4 1 ϵ ∈ { ± 1 } n max ∥ X ϵ ∥ 2 = 4 n 2 ( n 1 i = 1 ∑ n ∥ x i ∥ 2 − m ∈ R d min F ( m ) ) .
Thus, globally minimizing the Fréchet functional for R d / ± \mathbb{R}^{d}/\pm R d / ± yields MaxCut ( H ) \operatorname{MaxCut}(H) MaxCut ( H ) . □
The Riemannian approach to Fréchet means is limited
Traditionally, Fréchet means are computed using tools from Riemannian geometry [22 , 13 ] . We can transfer these ideas to the orbit-space setting, but first, we need to wrestle with certain singularities. For example, Figure 1.1 illustrates how the origin of R 2 \mathbb{R}^{2} R 2 becomes a cone-point singularity in the orbit space R 2 / ± \mathbb{R}^{2}/\pm R 2 / ± . Here, the origin is special because it has a nontrivial stabilizer. In general, we say x ∈ V x \in V x ∈ V is an irregular point of the G G G -action if it is fixed by some non-identity element of G G G , and otherwise, it is regular .
Note that regularity is defined as a property of points in V V V and not V / G V/G V / G . Regularity is still well defined on orbits; if x ∈ V x \in V x ∈ V is irregular and fixed by some g ∈ G g \in G g ∈ G then for y = h x ∈ [ x ] y=hx \in[x] y = h x ∈ [ x ] we have that ( h g h − 1 ) y = y (hgh^{-1})y=y ( h g h − 1 ) y = y , and hence y y y is also irregular. In our setting, regularity is a generic condition on points in V V V since the set of irregular points is exactly a finite union of fixed-point subspaces.
Irregular points mark a warping of the geometry of V V V in the quotient metric. If a point x ∈ V x \in V x ∈ V is irregular, then locally the space is not Euclidean and instead shares the geometry of V / Stab ( x ) V/\operatorname{Stab}(x) V / Stab ( x ) where Stab ( x ) : = { g ∈ G : g x = x } \operatorname{Stab}(x):=\{g \in G:gx=x\} Stab ( x ) := { g ∈ G : g x = x } . These irregularities give the orbit space V / G V/G V / G a global orbifold structure rather than one of a traditional manifold. Despite this, after removing irregular points, V / G V/G V / G is a flat Riemannian manifold whose induced Riemannian distance agrees locally with the quotient metric d V / G d_{V/G} d V / G . In particular, the space can be locally identified with V V V . This structure gives the possibility of finding the Fréchet mean by gradient descent. In fact, we can transfer a classical result from Kendall [17 ] to obtain a light guarantee on the nonexistence of spurious local minima of the Fréchet functional.
Proposition 2.7. Fix any finite nontrivial G ≤ O ( V ) G \le O(V) G ≤ O ( V ) , a regular point y ∈ V y \in V y ∈ V , and orbits { [ x i ] } i = 1 n ⊂ V / G \{[x_i]\}_{i=1}^{n} \subset V/G {[ x i ] } i = 1 n ⊂ V / G such that
max i ∈ { 1 , … , n } min p ∈ [ x i ] ∥ p − y ∥ < r : = 1 2 min g ∈ G g ≠ I dist ( y , ( y − g y ) ⊥ ) , \max_{i\in\{1,\ldots,n\}}\min_{p\in[x_i]}\|p-y\| < r := \frac{1}{2}\min_{\substack{g\in G\\g\ne I}}\operatorname{dist}\left(y,(y-gy)^\perp\right), i ∈ { 1 , … , n } max p ∈ [ x i ] min ∥ p − y ∥ < r := 2 1 g ∈ G g = I min dist ( y , ( y − g y ) ⊥ ) , where dist ( x , S ) \operatorname{dist}(x,S) dist ( x , S ) denotes the minimum Euclidean distance between the point x x x and the subspace S S S . Then there is exactly one Karcher mean of { [ x i ] } i = 1 n \{[x_i]\}_{i=1}^{n} {[ x i ] } i = 1 n contained in the image of the open ball B ( y , r ) ⊂ V B(y,r) \subset V B ( y , r ) ⊂ V under the quotient map.
Proof. Since y y y is regular and any irregular point lies in some ( y − g y ) ⊥ (y-gy)^\perp ( y − g y ) ⊥ , the choice of r r r gives that B ( y , r ) B(y,r) B ( y , r ) contains no irregular points and
g B ( y , r ) ∩ B ( y , r ) = ∅ for all g ≠ I . gB(y,r) \cap B(y,r) = \varnothing\qquad\text{for all } g \ne I. g B ( y , r ) ∩ B ( y , r ) = ∅ for all g = I .
In particular, the quotient map π : B ( y , r ) → B ~ ⊂ V / G \pi:B(y,r)\to\widetilde{B}\subset V/G π : B ( y , r ) → B ⊂ V / G is injective and B ~ \widetilde{B} B inherits a flat Riemannian structure.
We next show that every pair of points in B ~ \widetilde{B} B is joined by a unique minimizing geodesic that remains in the ball. Let p , q ∈ B ( y , r ) p,q \in B(y,r) p , q ∈ B ( y , r ) . For every g ≠ I g \ne I g = I ,
∥ p − g q ∥ ≥ ∥ y − g y ∥ − ∥ p − y ∥ − ∥ g q − g y ∥ = ∥ y − g y ∥ − ∥ p − y ∥ − ∥ q − y ∥ > 4 r − 2 r = 2 r , \begin{aligned}
\|p-gq\| &\ge\|y-gy\|-\|p-y\|-\|gq-gy\| \\
&=\|y-gy\|-\|p-y\|-\|q-y\|>4r-2r=2r,
\end{aligned} ∥ p − g q ∥ ≥ ∥ y − g y ∥ − ∥ p − y ∥ − ∥ g q − g y ∥ = ∥ y − g y ∥ − ∥ p − y ∥ − ∥ q − y ∥ > 4 r − 2 r = 2 r ,
whereas ∥ p − q ∥ ≤ ∥ p − y ∥ + ∥ q − y ∥ < 2 r \|p-q\|\le\|p-y\|+\|q-y\|<2r ∥ p − q ∥ ≤ ∥ p − y ∥ + ∥ q − y ∥ < 2 r . Thus, d ( [ p ] , [ q ] ) = ∥ p − q ∥ d([p],[q])=\|p-q\| d ([ p ] , [ q ]) = ∥ p − q ∥ , and this distance is uniquely attained by the identity. Taking p = y p=y p = y shows that B ~ \widetilde{B} B is the geodesic ball of radius r r r about [ y ] [y] [ y ] . Hence the unique geodesic from [ p ] [p] [ p ] to [ q ] [q] [ q ] lifts to the line segment between p p p and q q q , which remains in B ( y , r ) B(y,r) B ( y , r ) .
By hypothesis, the support of the data lies within B ~ \widetilde{B} B . This is a regular geodesic ball: its sectional curvature is zero, and its radius is smaller than the injectivity radius at [ y ] [y] [ y ] . Thus Theorem 7.3 of [17 ] gives uniqueness of a Karcher mean within B ~ \widetilde{B} B . Existence follows by taking the Euclidean mean of the representatives in B ( y , r ) B(y,r) B ( y , r ) . □ \square □
Here is one interpretation of this result: If we initialize gradient descent of the Fréchet functional at a regular point y y y that satisfies the hypothesis of Proposition 2.7, and if the iteration stays in the ball B ( y , r ) B(y,r) B ( y , r ) , then it converges to the unique local minimizer in that ball. Much like Theorem 2.1 , the Karcher mean in the ball is represented by the Euclidean mean of the points p i ∈ [ x i ] ∩ B ( y , r ) p_i\in[x_i]\cap B(y,r) p i ∈ [ x i ] ∩ B ( y , r ) . By requiring r r r to be small, we ensure that the quotient map preserves pairwise distances. In the next section, we formalize this alignment property, identify a multitude of sets that satisfy this property, and prove that it guarantees global optimality of the Euclidean mean.
Alignment
The previous section identified some algorithmic difficulties with computing Fréchet means. In this section, we identify a family of problem instances for which computing the Fréchet mean is utterly painless.
Introduction to aligned and alignable sets
We start with a definition:
Definition 3.1. A set S ⊆ V S \subseteq V S ⊆ V is aligned with respect to G G G if for every x , y ∈ S x,y \in S x , y ∈ S ,
d ( [ x ] , [ y ] ) = ∥ x − y ∥ . d([x],[y]) = \lVert x-y\rVert. d ([ x ] , [ y ]) = ∥ x − y ∥ . Alternatively stated, S S S is aligned when the quotient map V → V / G V \to V/G V → V / G restricts to an isometric embedding of S S S .3 As we will soon see, since aligned data exhibits identical geometry to the corresponding points in orbit space, when computing Fréchet means, one may equivalently work directly with the original data, which is easier thanks to its Euclidean setting.
For shorthand, we will say two points x , y ∈ V x,y \in V x , y ∈ V are aligned if the set { x , y } \{x,y\} { x , y } is aligned, and a sequence { x i } i = 1 n \{x_i\}_{i=1}^{n} { x i } i = 1 n of points in V V V is aligned if the underlying set { x 1 , … , x n } \{x_1,\ldots,x_n\} { x 1 , … , x n } is aligned. Two points are aligned precisely when the minimum in their quotient distance is attained by the identity group element. We say that a set is maximally aligned if it is aligned and not strictly contained in any other aligned set. Some examples follow below.
Example 3.2. Let G = S d G=S_d G = S d act on V = R d V=\mathbb{R}^d V = R d by coordinate permutations. Two points are aligned precisely when the vector entries are sorted in the same order. More generally, when G ≤ O ( V ) G \leq O(V) G ≤ O ( V ) is a reflection group, then the closure of any Weyl chamber is a maximally aligned set.
Example 3.3. Suppose g ∈ S O ( 2 ) g \in SO(2) g ∈ S O ( 2 ) has order k > 1 k>1 k > 1 acting canonically on V = R 2 V=\mathbb{R}^2 V = R 2 . Then the maximally aligned sets with respect to G = ⟨ g ⟩ G=\langle g\rangle G = ⟨ g ⟩ are the convex cones of angular width π k \frac{\pi}{k} k π .
Example 3.4. Consider G = ± G=\pm G = ± acting on V = R 3 V=\mathbb{R}^3 V = R 3 . Both the nonnegative octant and the “ice cream cone”
{ ( x 1 , x 2 , x 3 ) ∈ R 3 : x 1 2 + x 2 2 ≤ x 3 } \left\{(x_1,x_2,x_3)\in\mathbb{R}^3:\sqrt{x_1^2+x_2^2}\leq x_3\right\} { ( x 1 , x 2 , x 3 ) ∈ R 3 : x 1 2 + x 2 2 ≤ x 3 } form maximally aligned sets. Despite the fact that both aligned sets are maximal, they are distinct in structure; see Figure 3.1 for an illustration.
Figure 3.1. The nonnegative orthant (left) and the ice cream cone (right) form maximally aligned sets in V = R 3 V = \mathbb{R}^{3} V = R 3 under the action of G = ± G = \pm G = ± ; see Example 3.4 . For the sake of illustration, we display cross sections with the planes x 1 + x 2 + x 3 = 1 x_{1} + x_{2} + x_{3} = 1 x 1 + x 2 + x 3 = 1 and x 3 = 1 x_{3} = 1 x 3 = 1 , respectively.
We suspect it would be nontrivial to find a nice description of all maximally aligned sets, but we can say they are all closed convex cones.
Proposition 3.5. For G ≤ O ( V ) G \leq O(V) G ≤ O ( V ) , every set in V V V that is maximally aligned with respect to G G G is a closed convex cone.
Proof. Suppose S S S is maximally aligned, and let C ⊇ S C \supseteq S C ⊇ S denote the topological closure of its conic hull. Since G G G is orthogonal, the alignment of S S S is equivalent to
⟨ x , ( I − g ) y ⟩ ≥ 0 for all x , y ∈ S , g ∈ G . \langle x,(I-g)y\rangle\geq0 \qquad\text{for all }x,y\in S,\ g\in G. ⟨ x , ( I − g ) y ⟩ ≥ 0 for all x , y ∈ S , g ∈ G . This inequality is preserved under nonnegative linear combinations and limits in x x x and y y y , so it holds for any x , y ∈ C x,y \in C x , y ∈ C as well. Thus C C C is aligned, and so the maximality of S S S gives S = C S=C S = C .
Next, we formalize the idea that changing orbit representatives can transform a non-aligned set into an aligned set.
Definition 3.6. A set S ⊆ V S \subseteq V S ⊆ V is alignable with respect to G G G if for every x ∈ S x \in S x ∈ S there exists g x ∈ G g_x \in G g x ∈ G such that the set { g x x : x ∈ S } \{g_x x : x \in S\} { g x x : x ∈ S } is aligned.
Importantly, not every set is alignable. For example, the points
( 2 , 0 ) , ( − 1 , 3 ) , ( − 1 , − 3 ) (2,0), \qquad(-1,\sqrt{3}), \qquad(-1,-\sqrt{3}) ( 2 , 0 ) , ( − 1 , 3 ) , ( − 1 , − 3 )
are not alignable with respect to ± \pm ± . (This is straightforward to verify.) Meanwhile, when a generic set S S S is alignable, it is easy to find aligned orbit representatives: simply align all of the points to any chosen member of S S S . For example, the points
( 1 , 0 ) , ( − 1 , − 1 ) , ( − 1 , − 2 ) (1,0), \qquad(-1,-1), \qquad(-1,-2) ( 1 , 0 ) , ( − 1 , − 1 ) , ( − 1 , − 2 )
are not aligned with respect to ± \pm ± , but they become aligned once we negate the second and third vectors so that they both have a positive inner product with the first vector. This reduces general alignment to a pairwise alignment problem. The following examples illustrate how the computational complexity of pairwise alignment is sensitive to the group.
Example 3.7. Let G = C d G = C_d G = C d act on V = R d V = \mathbb{R}^{d} V = R d as cyclic permutations of coordinates. Two vectors x x x and y y y are aligned precisely when their circular cross correlation peaks at k = 0 k = 0 k = 0 . In terms of the discrete Fourier transform F \mathcal{F} F and entrywise product ∘ \circ ∘ , this is equivalent to F − 1 ( F ( x ) ∘ F ( y ) ) \mathcal{F}^{-1}(\mathcal{F}(x)\circ\mathcal{F}(y)) F − 1 ( F ( x ) ∘ F ( y )) being maximized at the zeroth entry. Thus, the fast Fourier transform offers an efficient method for pairwise alignment in this setting.
Example 3.8. Let G = S n G = S_n G = S n act on V = R n × n V = \mathbb{R}^{n \times n} V = R n × n by conjugation. Any method of pairwise alignment in this setting could be used to decide whether a graph contains a Hamiltonian circuit (by aligning an n n n -cycle’s adjacency matrix to that of the graph). As such, the alignment problem in this case is NP-hard.
Aligned sets have easy-to-compute Fréchet means
Aligned sets correspond to easy instances of geometric problems in the quotient space, since (typically hard) quotient geometry is identical to the original (easy) Euclidean geometry. We are now ready to make this explicit: It is easy to compute the Fréchet mean of aligned data.
Theorem 3.9. Suppose { x i } i = 1 n ⊂ V \{x_i\}_{i=1}^n \subset V { x i } i = 1 n ⊂ V is aligned with respect to G ≤ O ( V ) G \le O(V) G ≤ O ( V ) , and let μ ∈ V \mu\in V μ ∈ V denote its Euclidean mean. Then [ μ ] ∈ V / G [\mu] \in V/G [ μ ] ∈ V / G is a Fréchet mean of { [ x i ] } i = 1 n \{[x_i]\}_{i=1}^n {[ x i ] } i = 1 n .
Proof. First, we recall a standard result about mean squared displacement: For every z 1 , … , z n ∈ V z_1,\ldots,z_n \in V z 1 , … , z n ∈ V with centroid μ ∈ V \mu\in V μ ∈ V , it holds that
∥ z i − z j ∥ 2 = ∥ ( z i − μ ) − ( z j − μ ) ∥ 2 = ∥ z i − μ ∥ 2 − 2 ⟨ z i − μ , z j − μ ⟩ + ∥ z j − μ ∥ 2 \lVert z_i-z_j\rVert^2=\lVert(z_i-\mu)-(z_j-\mu)\rVert^2=\lVert z_i-\mu\rVert^2-2\langle z_i-\mu,z_j-\mu\rangle+\lVert z_j-\mu\rVert^2 ∥ z i − z j ∥ 2 = ∥( z i − μ ) − ( z j − μ ) ∥ 2 = ∥ z i − μ ∥ 2 − 2 ⟨ z i − μ , z j − μ ⟩ + ∥ z j − μ ∥ 2
and so the mean squared displacement has the symmetrized form:
1 2 n 2 ∑ i , j = 1 n ∥ z i − z j ∥ 2 = 1 2 n ∑ i = 1 n ∥ z i − μ ∥ 2 − ⟨ 1 n ∑ i = 1 n ( z i − μ ) , 1 n ∑ j = 1 n ( z j − μ ) ⟩ + 1 2 n ∑ j = 1 n ∥ z j − μ ∥ 2 = 1 n ∑ i = 1 n ∥ z i − μ ∥ 2 . \begin{aligned}
\frac{1}{2n^2}\sum_{i,j=1}^{n}\lVert z_i-z_j\rVert^2
&=\frac{1}{2n}\sum_{i=1}^{n}\lVert z_i-\mu\rVert^2-\left\langle\frac{1}{n}\sum_{i=1}^{n}(z_i-\mu),\frac{1}{n}\sum_{j=1}^{n}(z_j-\mu)\right\rangle+\frac{1}{2n}\sum_{j=1}^{n}\lVert z_j-\mu\rVert^2\\
&=\frac{1}{n}\sum_{i=1}^{n}\lVert z_i-\mu\rVert^2.
\end{aligned} 2 n 2 1 i , j = 1 ∑ n ∥ z i − z j ∥ 2 = 2 n 1 i = 1 ∑ n ∥ z i − μ ∥ 2 − ⟨ n 1 i = 1 ∑ n ( z i − μ ) , n 1 j = 1 ∑ n ( z j − μ ) ⟩ + 2 n 1 j = 1 ∑ n ∥ z j − μ ∥ 2 = n 1 i = 1 ∑ n ∥ z i − μ ∥ 2 .
We now use this to prove our result. Since every Karcher mean is a Euclidean mean by Theorem 2.1 , it follows that F F F is minimized by a point of the form m = 1 n ∑ j = 1 n g j x j m=\frac{1}{n}\sum_{j=1}^{n}g_jx_j m = n 1 ∑ j = 1 n g j x j , where g 1 , … , g n ∈ G g_1,\ldots,g_n\in G g 1 , … , g n ∈ G together minimize the quantity
F ( m ) = 1 n ∑ i = 1 n ∥ g i x i − 1 n ∑ j = 1 n g j x j ∥ 2 = 1 2 n 2 ∑ i , j = 1 n ∥ g i x i − g j x j ∥ 2 ≥ 1 2 n 2 ∑ i , j = 1 n d ( [ x i ] , [ x j ] ) 2 . F(m)=\frac{1}{n}\sum_{i=1}^{n}\left\lVert g_ix_i-\frac{1}{n}\sum_{j=1}^{n}g_jx_j\right\rVert^2=\frac{1}{2n^2}\sum_{i,j=1}^{n}\lVert g_ix_i-g_jx_j\rVert^2\ge\frac{1}{2n^2}\sum_{i,j=1}^{n}d([x_i],[x_j])^2. F ( m ) = n 1 i = 1 ∑ n g i x i − n 1 j = 1 ∑ n g j x j 2 = 2 n 2 1 i , j = 1 ∑ n ∥ g i x i − g j x j ∥ 2 ≥ 2 n 2 1 i , j = 1 ∑ n d ([ x i ] , [ x j ] ) 2 .
Since { x i } i = 1 n \{x_i\}_{i=1}^n { x i } i = 1 n is aligned by assumption, equality in the lower bound is achieved by g 1 = ⋯ = g n = I g_1=\cdots=g_n=I g 1 = ⋯ = g n = I . Thus, F F F is minimized by μ \mu μ , as claimed. □
We note that the converse of Theorem 3.9 is far from true. In particular, given any non-alignable { y i } i = 1 n \{y_i\}_{i=1}^n { y i } i = 1 n , select μ \mu μ so that [ μ ] [\mu] [ μ ] is the Fréchet mean of { [ y i ] } i = 1 n \{[y_i]\}_{i=1}^n {[ y i ] } i = 1 n . Since every Fréchet mean is a Karcher mean, and furthermore by Theorem 2.1 , every Karcher mean is a Euclidean mean, it follows that there exist g 1 , … , g n ∈ G g_1,\ldots,g_n\in G g 1 , … , g n ∈ G for which μ = 1 n ∑ i = 1 n g i y i \mu=\frac{1}{n}\sum_{i=1}^{n}g_iy_i μ = n 1 ∑ i = 1 n g i y i . Now, define x i : = g i y i x_i:=g_iy_i x i := g i y i for each i i i . Since { y i } i = 1 n \{y_i\}_{i=1}^n { y i } i = 1 n was not alignable by assumption, it follows that { x i } i = 1 n \{x_i\}_{i=1}^n { x i } i = 1 n is not aligned, and yet it satisfies the conclusion of Theorem 3.9 .
A generalization of these ideas was studied in [7 ] , where the authors consider noisy data generated around a template in V V V , which they project into the quotient space V / G V/G V / G . Under this setup, they investigate the consistency of the Fréchet mean, specifically, when does the mean of data in V V V correspond to the Fréchet mean in V / G V/G V / G ? By Theorem 3.9 , the Fréchet mean is consistent if the support of the distribution is aligned, but what if it isn’t? Is it necessary or sufficient for every point in the support of the distribution to be aligned to the mean? The authors proved necessity under mild conditions, but left sufficiency open. Below, we present an example that disproves sufficiency.
Example 3.10. We consider an explicit example with V = R 2 V=\mathbb{R}^2 V = R 2 and G = ± G=\pm G = ± . Put
x 1 : = ( ϵ , 1 ) , x 2 : = ( ϵ , − 1 ) , x 3 : = ( 3 , 0 ) . x_1:=(\epsilon,1),\qquad x_2:=(\epsilon,-1),\qquad x_3:=(3,0). x 1 := ( ϵ , 1 ) , x 2 := ( ϵ , − 1 ) , x 3 := ( 3 , 0 ) .
Each of these points is aligned to the Euclidean centroid ( 1 + 2 3 ϵ , 0 ) (1+\frac{2}{3}\epsilon,0) ( 1 + 3 2 ϵ , 0 ) , and yet the Fréchet functional is smaller at ( 1 , 2 3 ) (1,\frac{2}{3}) ( 1 , 3 2 ) when ϵ > 0 \epsilon>0 ϵ > 0 is sufficiently small. Thus, the Fréchet mean is inconsistent despite each x i x_i x i being aligned to the Euclidean centroid.
Synchronization relaxations of the Fréchet objective
While alignment allows us to compute a Fréchet mean, in this section, we explore how to compute a Fréchet mean when data is not alignable. By Theorem 2.1 , computing a Fréchet mean is equivalent to finding orbit representatives that are optimal in some sense, so we can express our problem as an optimization over the group.
We state our results for x i ∈ R d x_i \in\mathbb{R}^d x i ∈ R d for the sake of readability, though they extend directly to x i ∈ R d × p x_i \in\mathbb{R}^{d \times p} x i ∈ R d × p with p > 1 p>1 p > 1 and G ≤ O ( d ) G \le O(d) G ≤ O ( d ) acting on the left.
Theorem 4.1. Fix any compact G ≤ O ( d ) G \le O(d) G ≤ O ( d ) and x 1 , … , x n ∈ R d x_1,\ldots,x_n \in\mathbb{R}^d x 1 , … , x n ∈ R d . Every Fréchet mean of { [ x i ] } i = 1 n \{[x_i]\}_{i=1}^n {[ x i ] } i = 1 n is given by the orbit of 1 n ∑ i = 1 n g i x i \frac{1}{n}\sum_{i=1}^n g_i x_i n 1 ∑ i = 1 n g i x i , where g 1 , … , g n ∈ G g_1,\ldots,g_n \in G g 1 , … , g n ∈ G together form any solution to the program
m a x i m i z e ∑ i , j = 1 n ⟨ x i x j T , g i T g j ⟩ F subject to g 1 , … , g n ∈ G . (5) \mathop{\mathrm{maximize}}\ \sum_{i,j=1}^{n}\langle x_i x_j^{\mathsf T},g_i^{\mathsf T}g_j\rangle_F \quad\text{subject to}\quad g_1,\ldots,g_n\in G. \tag*{(5)} maximize i , j = 1 ∑ n ⟨ x i x j T , g i T g j ⟩ F subject to g 1 , … , g n ∈ G . (5)
Proof. As in the proof of Theorem 3.9 , we seek g 1 , … , g n ∈ G g_1,\ldots,g_n \in G g 1 , … , g n ∈ G that minimize
∑ i , j = 1 n ∥ g i x i − g j x j ∥ 2 . \sum_{i,j=1}^{n}\lVert g_i x_i-g_j x_j\rVert^2. i , j = 1 ∑ n ∥ g i x i − g j x j ∥ 2 .
Expanding the square, this is equivalent to maximizing the sum of cross terms:
∑ i , j = 1 n ⟨ g i x i , g j x j ⟩ = ∑ i , j = 1 n ⟨ x i x j T , g i T g j ⟩ F . \sum_{i,j=1}^{n}\langle g_i x_i,g_j x_j\rangle=\sum_{i,j=1}^{n}\langle x_i x_j^{\mathsf T},g_i^{\mathsf T}g_j\rangle_F. i , j = 1 ∑ n ⟨ g i x i , g j x j ⟩ = i , j = 1 ∑ n ⟨ x i x j T , g i T g j ⟩ F .
We observe that (5) is similar to the objective found in the group synchronization problem [25 , 4 ] , where the goal is to recover group elements g 1 , … , g n ∈ G g_1,\ldots,g_n \in G g 1 , … , g n ∈ G that best fit noisy measurements of pairwise relations g i j ≈ g i g j − 1 g_{ij}\approx g_i g_j^{-1} g ij ≈ g i g j − 1 . Assuming an orthogonal group action, the synchronization problem can be formalized as
m i n i m i z e ∑ i , j = 1 n ∥ g i j − g i g j T ∥ F 2 subject to g 1 , … , g n ∈ G . \mathop{\mathrm{minimize}}\ \sum_{i,j=1}^{n}\lVert g_{ij}-g_i g_j^{\mathsf T}\rVert_F^2 \quad\text{subject to}\quad g_1,\ldots,g_n\in G. minimize i , j = 1 ∑ n ∥ g ij − g i g j T ∥ F 2 subject to g 1 , … , g n ∈ G .
Expanding the Frobenius norm and applying the orthogonality of G G G gives
m a x i m i z e ∑ i , j = 1 n ⟨ g i j , g i g j T ⟩ F subject to g 1 , … , g n ∈ G . (6) \mathop{\mathrm{maximize}}\ \sum_{i,j=1}^{n}\langle g_{ij},g_i g_j^{\mathsf T}\rangle_F \quad\text{subject to}\quad g_1,\ldots,g_n\in G. \tag*{(6)} maximize i , j = 1 ∑ n ⟨ g ij , g i g j T ⟩ F subject to g 1 , … , g n ∈ G . (6)
The following subsections exploit the similarity between (5) and (6) to transfer ideas from group synchronization to Fréchet means. We present spectral and semidefinite methods for the general setting in Sections 4.1 and 4.2, and then we give specialized methods for G = ± G=\pm G = ± in Section 4.3 and for general cyclic actions in Section 4.4.
Spectral Relaxation
Given M ∈ R n d × n d M\in\mathbb{R}^{nd\times nd} M ∈ R n d × n d , let M [ i j ] M_{[ij]} M [ ij ] denote the ( i , j ) (i,j) ( i , j ) th d × d d\times d d × d block of M M M . For G ≤ O ( d ) G\le O(d) G ≤ O ( d ) , consider the program
m a x i m i z e ∑ i , j = 1 n ⟨ M [ i j ] , g i T g j ⟩ F subject to g 1 , … , g n ∈ G . \mathop{\mathrm{maximize}}\ \sum_{i,j=1}^{n}\langle M_{[ij]},g_i^{\mathsf T}g_j\rangle_F \quad\text{subject to}\quad g_1,\ldots,g_n\in G. maximize i , j = 1 ∑ n ⟨ M [ ij ] , g i T g j ⟩ F subject to g 1 , … , g n ∈ G .
For example, the program (5) takes this form once we put x : = [ x 1 ; ⋯ ; x n ] ∈ R n d x := [x_1;\cdots;x_n] \in\mathbb{R}^{nd} x := [ x 1 ; ⋯ ; x n ] ∈ R n d and M : = x x T M := xx^{\mathsf{T}} M := x x T . We may reformulate this program as
maximize ⟨ M , Y ⟩ F subject to Y = [ g 1 T ⋮ g n T ] [ g 1 ⋯ g n ] , g 1 , … , g n ∈ G . (7) \begin{aligned}
\text{maximize}\quad& \langle M,Y\rangle_F \\
\text{subject to}\quad& Y =
\begin{bmatrix}
g_1^{\mathsf{T}}\\
\vdots\\
g_n^{\mathsf{T}}
\end{bmatrix}
[g_1\cdots g_n],\qquad g_1,\ldots,g_n\in G. \tag*{(7)}
\end{aligned} maximize subject to ⟨ M , Y ⟩ F Y = g 1 T ⋮ g n T [ g 1 ⋯ g n ] , g 1 , … , g n ∈ G . (7)
Considering Y Y Y is n n n times a rank-d d d orthogonal projection matrix, one might consider the spectral relaxation
maximize ⟨ M , n P ⟩ F subject to P 2 = P T = P , rank P = d . (8) \begin{aligned}
\text{maximize}\quad& \langle M,nP\rangle_F \\
\text{subject to}\quad& P^2=P^{\mathsf{T}}=P,\qquad\operatorname{rank}P=d. \tag*{(8)}
\end{aligned} maximize subject to ⟨ M , n P ⟩ F P 2 = P T = P , rank P = d . (8)
By the von Neumann trace inequality, the solution to (8) is given by the orthogonal projection onto the top d d d eigenvectors of (the symmetric part of) M M M . Next, we may round a solution P P P of (8) to a feasible point of (7) by first writing Z T Z = n P Z^{\mathsf{T}}Z=nP Z T Z = n P for some Z ∈ R d × n d Z\in\mathbb{R}^{d\times nd} Z ∈ R d × n d , and then for some appropriate choice of Q ∈ O ( d ) Q\in O(d) Q ∈ O ( d ) , rounding each d × d d\times d d × d block of Q Z QZ QZ to the nearest element of G G G .
Unfortunately, our intended use case takes M M M to be the rank-1 matrix x x T xx^{\mathsf{T}} x x T , thereby making this spectral relaxation degenerate (though such degeneracy may not be an issue in the setting where x i ∈ R d × p x_i\in\mathbb{R}^{d\times p} x i ∈ R d × p with p ≥ d p\ge d p ≥ d ). To avoid this rank-1 degeneracy, we are inclined to pass to a nearby synchronization problem: Take M [ i j ] M_{[ij]} M [ ij ] to be the group element closest to x i x j T x_i x_j^{\mathsf{T}} x i x j T in Frobenius norm. This group element g i j g_{ij} g ij happens to be the g ∈ G g\in G g ∈ G that maximizes ⟨ x i , g x j ⟩ \langle x_i,gx_j\rangle ⟨ x i , g x j ⟩ , i.e., that aligns x j x_j x j to x i x_i x i . As a more refined approach, one might take M [ i j ] M_{[ij]} M [ ij ] to be a nonnegative multiple of a group element that is closest to x i x j T x_i x_j^{\mathsf{T}} x i x j T in Frobenius norm; modulo a constant factor, this takes M [ i j ] M_{[ij]} M [ ij ] to be the positive part ⟨ x i , g i j x j ⟩ + \langle x_i,g_{ij}x_j\rangle_+ ⟨ x i , g ij x j ⟩ + times the closest group element g i j g_{ij} g ij . See Algorithm 4.1 for a complete description of our spectral relax-and-round algorithm.
Semidefinite Relaxation
We return to the program (7) with M = x x T M=xx^{\mathsf{T}} M = x x T , the feasibility region of which consists of all Y ∈ R n d × n d Y\in\mathbb{R}^{nd\times nd} Y ∈ R n d × n d such that
Y [ i i ] = I d for all i , Y [ i j ] ∈ G for all i , j , Y ⪰ 0 , rank ( Y ) = d . Y_{[ii]}=I_d\ \text{for all }i,\qquad Y_{[ij]}\in G\ \text{for all }i,j,\qquad Y\succeq0,\qquad\operatorname{rank}(Y)=d. Y [ ii ] = I d for all i , Y [ ij ] ∈ G for all i , j , Y ⪰ 0 , rank ( Y ) = d .
To obtain a convex relaxation, we discard the rank constraint and replace Y [ i j ] ∈ G Y_{[ij]}\in G Y [ ij ] ∈ G with Y [ i j ] ∈ Conv G Y_{[ij]}\in\operatorname{Conv}G Y [ ij ] ∈ Conv G , the convex hull of G ⊆ R d × d G\subseteq\mathbb{R}^{d\times d} G ⊆ R d × d :
Fréchet Mean SDP:
maximize ⟨ x x T , Y ⟩ F subject to Y [ i i ] = I d for all i , Y [ i j ] ∈ Conv G for all i , j , Y ⪰ 0. (9) \begin{aligned}
\text{maximize}\quad& \langle xx^{\mathsf{T}},Y\rangle_F \\
\text{subject to}\quad& Y_{[ii]}=I_d\ \text{for all }i,\qquad Y_{[ij]}\in\operatorname{Conv}G\ \text{for all }i,j,\qquad Y\succeq0. \tag*{(9)}
\end{aligned} maximize subject to ⟨ x x T , Y ⟩ F Y [ ii ] = I d for all i , Y [ ij ] ∈ Conv G for all i , j , Y ⪰ 0. (9)
Unlike the spectral relaxation, the semidefinite relaxation is frequently tight in practice, meaning the solution to the SDP is feasible in (7) and exactly solves (5) . When the relaxation is not tight, we may apply a rounding procedure to extract a feasible solution to the original problem, much like in the spectral method.
Taking a step back, we note that, given { x i } i = 1 n ⊂ R d \{x_i\}_{i=1}^n\subset\mathbb{R}^d { x i } i = 1 n ⊂ R d and { g i } i = 1 n ⊂ G \{g_i\}_{i=1}^n\subset G { g i } i = 1 n ⊂ G , it is sometimes computationally feasible to determine whether the Fréchet mean of 1 n ∑ i = 1 n g i x i \frac{1}{n}\sum_{i=1}^n g_i x_i n 1 ∑ i = 1 n g i x i is the Fréchet mean of { [ x i ] } i = 1 n \{[x_i]\}_{i=1}^n {[ x i ] } i = 1 n . For example, this occurs when { g i x i } i = 1 n \{g_i x_i\}_{i=1}^n { g i x i } i = 1 n is aligned as in Section 3. Alternatively, this holds when the matrix Y Y Y defined by Y [ i j ] = g i T g j Y_{[ij]}=g_i^{\mathsf{T}}g_j Y [ ij ] = g i T g j solves the Fréchet mean SDP (9) . In general, given a candidate solution to a semidefinite program, one may certify its optimality using the dual program . In Appendix A, we prove the following:
Algorithm 4.1 Spectral Method for the Fréchet Mean in V / G V/G V / G
Input: x 1 , … , x n ∈ R d × p x_1,\ldots,x_n \in\mathbb{R}^{d\times p} x 1 , … , x n ∈ R d × p , finite G ≤ O ( d ) G \le O(d) G ≤ O ( d ) , T max ∈ N T_{\max} \in\mathbb{N} T m a x ∈ N
Output: Member of R d × p \mathbb{R}^{d\times p} R d × p whose G G G -orbit is an approximate Fréchet mean
if p < d p<d p < d then
Synchronization Approximation:
for i = 1 , … , n i=1,\ldots,n i = 1 , … , n do
M i i = ∥ x i ∥ F 2 I d M_{ii}=\lVert x_i\rVert_F^2 I_d M ii = ∥ x i ∥ F 2 I d
end for
for 1 ≤ i < j ≤ n 1\le i<j\le n 1 ≤ i < j ≤ n do
g i j ∈ arg max g ∈ G ⟨ x i , g x j ⟩ g_{ij}\in\operatorname*{arg\,max}_{g\in G}\langle x_i,gx_j\rangle g ij ∈ arg max g ∈ G ⟨ x i , g x j ⟩
M i j = ⟨ x i , g i j x j ⟩ + g i j M_{ij}=\langle x_i,g_{ij}x_j\rangle+g_{ij} M ij = ⟨ x i , g ij x j ⟩ + g ij
M j i = M i j T M_{ji}=M_{ij}^{T} M j i = M ij T
end for
else
x = [ x 1 ; … ; x n ] ∈ R n d × p \mathbf{x}=[x_1;\ldots;x_n]\in\mathbb{R}^{nd\times p} x = [ x 1 ; … ; x n ] ∈ R n d × p
M = x x T M=\mathbf{x}\mathbf{x}^{T} M = x x T
end if
Compute rank-d d d spectral factor Y ∈ R n d × d Y\in\mathbb{R}^{nd\times d} Y ∈ R n d × d of M M M
Procrustes-Based Rounding to G n G^n G n
Let Y 1 Y_1 Y 1 be the first d × d d\times d d × d block of Y Y Y
Compute SVD Y 1 = U Σ V T Y_1=U\Sigma V^{T} Y 1 = U Σ V T , set W = U V T W=UV^{T} W = U V T
for i = 1 i=1 i = 1 to n n n do
g i ∈ arg min g ∈ G ∥ Y i W − g T ∥ F g_i\in\operatorname*{arg\,min}_{g\in G}\lVert Y_iW-g^{T}\rVert_F g i ∈ arg min g ∈ G ∥ Y i W − g T ∥ F
end for
for t = 1 t=1 t = 1 to T max T_{\max} T m a x do
C = ∑ i = 1 n Y i T g i T C=\sum_{i=1}^{n}Y_i^{T}g_i^{T} C = ∑ i = 1 n Y i T g i T
Compute SVD C = U Σ V T C=U\Sigma V^{T} C = U Σ V T , set W n e w = U V T W_{\mathrm{new}}=UV^{T} W new = U V T
for i = 1 i=1 i = 1 to n n n do
g i ∈ arg min g ∈ G ∥ Y i W n e w − g T ∥ F g_i\in\operatorname*{arg\,min}_{g\in G}\lVert Y_iW_{\mathrm{new}}-g^{T}\rVert_F g i ∈ arg min g ∈ G ∥ Y i W new − g T ∥ F
end for
W ← W n e w W\leftarrow W_{\mathrm{new}} W ← W new
end for
return 1 n ∑ i = 1 n g i x i \frac{1}{n}\sum_{i=1}^{n}g_ix_i n 1 ∑ i = 1 n g i x i
Lemma 4.2. The dual program of (9) is
min W ⪰ x x T max H ∈ H ⟨ H , W ⟩ F (10) \min_{W\succeq xx^{T}}\ \max_{H\in\mathcal{H}}\langle H,W\rangle_F \tag*{(10)} W ⪰ x x T min H ∈ H max ⟨ H , W ⟩ F (10) where H \mathcal{H} H consists of all symmetric H ∈ R n d × n d H\in\mathbb{R}^{nd\times nd} H ∈ R n d × n d such that
H [ i i ] = I d for all i , H [ i j ] ∈ G for all i , j . H_{[ii]}=I_d\ \text{for all }i,\qquad H_{[ij]}\in G\ \text{for all }i,j. H [ ii ] = I d for all i , H [ ij ] ∈ G for all i , j .
Given a candidate solution ( g 1 , … , g n ) (g_1,\ldots,g_n) ( g 1 , … , g n ) to (5) , then by renaming x i ← g i x i x_i\leftarrow g_ix_i x i ← g i x i , we may establish the optimality of ( g 1 , … , g n ) (g_1,\ldots,g_n) ( g 1 , … , g n ) by showing that 1 n 1 n 1 n T ⊗ I d \frac{1}{n}\mathbf{1}_n\mathbf{1}_n^{T}\otimes I_d n 1 1 n 1 n T ⊗ I d is a solution to the Fréchet mean SDP (9) . In what follows, we obtain a dual certificate to this effect by appealing to Lemma 4.2 .
Theorem 4.3. Suppose there exists a W ∈ R n d × n d W \in\mathbb{R}^{nd \times nd} W ∈ R n d × n d such that
W ⪰ x x T , I d ∈ arg max g ∈ G ⟨ g , W [ i j ] ⟩ F for all i < j , ⟨ 1 n 1 n T ⊗ I d , W ⟩ F = ⟨ 1 n 1 n T ⊗ I d , x x T ⟩ F . (11) \begin{aligned}
W &\succeq xx^{\mathsf{T}}, \qquad I_d \in\underset{g \in G}{\operatorname{arg\,max}}\langle g,W_{[ij]}\rangle_F \quad\text{for all } i<j,\\
\langle1_n1_n^{\mathsf{T}}\otimes I_d,W\rangle_F &= \langle1_n1_n^{\mathsf{T}}\otimes I_d,xx^{\mathsf{T}}\rangle_F. \tag*{(11)}
\end{aligned} W ⟨ 1 n 1 n T ⊗ I d , W ⟩ F ⪰ x x T , I d ∈ g ∈ G arg max ⟨ g , W [ ij ] ⟩ F for all i < j , = ⟨ 1 n 1 n T ⊗ I d , x x T ⟩ F . (11) Then the G G G -orbit of the mean of { x i } i = 1 n ⊂ R d \{x_i\}_{i=1}^n \subset\mathbb{R}^d { x i } i = 1 n ⊂ R d is a Fréchet mean of { [ x i ] } i = 1 n ⊂ R d / G \{[x_i]\}_{i=1}^n \subset\mathbb{R}^d/G {[ x i ] } i = 1 n ⊂ R d / G .
Proof. Suppose there exists such a W W W . The first condition in (11) makes W W W dual feasible. Since every H ∈ H H \in\mathcal{H} H ∈ H has diagonal blocks I d I_d I d , the second condition determines the dual value at W W W :
max H ∈ H ⟨ H , W ⟩ F = ⟨ 1 n 1 n T ⊗ I d , W ⟩ F . \max_{H \in\mathcal{H}}\langle H,W\rangle_F=\langle1_n1_n^{\mathsf{T}}\otimes I_d,W\rangle_F. H ∈ H max ⟨ H , W ⟩ F = ⟨ 1 n 1 n T ⊗ I d , W ⟩ F .
The third condition in (11) gives that the primal value at Y : = 1 n 1 n T ⊗ I d Y:=1_n1_n^{\mathsf{T}}\otimes I_d Y := 1 n 1 n T ⊗ I d equals the dual value at W W W . By weak duality, it follows that Y Y Y is primal optimal. Since (9) is a relaxation of (5) , we conclude that g 1 = ⋯ = g n = I d g_1=\cdots=g_n=I_d g 1 = ⋯ = g n = I d solves the latter problem, and the result follows.
When { x i } i = 1 n \{x_i\}_{i=1}^n { x i } i = 1 n is aligned, one may take W = x x T W=xx^{\mathsf{T}} W = x x T in Theorem 4.3 . Indeed, the first and third conditions of (11) are immediate, while the second condition concerns the quantity
⟨ g , W [ i j ] ⟩ F = ⟨ g , x i x j T ⟩ F = ⟨ x i , g x j ⟩ , \langle g,W_{[ij]}\rangle_F=\langle g,x_ix_j^{\mathsf{T}}\rangle_F=\langle x_i,gx_j\rangle, ⟨ g , W [ ij ] ⟩ F = ⟨ g , x i x j T ⟩ F = ⟨ x i , g x j ⟩ ,
which, for aligned data, is maximized by g = I d g=I_d g = I d . When { x i } i = 1 n \{x_i\}_{i=1}^n { x i } i = 1 n is not aligned, then W = x x T W=xx^{\mathsf{T}} W = x x T does not satisfy the second condition of (11) , but sometimes, an appropriate perturbation does. We take this approach to prove the following weaker guarantee.
Corollary 4.4. Fix any finite nontrivial G ≤ O ( d ) G\leq O(d) G ≤ O ( d ) and { x i } i = 1 n ⊂ R d \{x_i\}_{i=1}^n\subset\mathbb{R}^d { x i } i = 1 n ⊂ R d . Define the signed adjacency matrix A ∈ R n × n A\in\mathbb{R}^{n\times n} A ∈ R n × n by
A i j = min g ∈ G ∖ { I d } ⟨ x i , x j ⟩ − ⟨ x i , g x j ⟩ d − Tr g , A_{ij}=\min_{g\in G\setminus\{I_d\}}\frac{\langle x_i,x_j\rangle-\langle x_i,gx_j\rangle}{d-\operatorname{Tr}g}, A ij = g ∈ G ∖ { I d } min d − Tr g ⟨ x i , x j ⟩ − ⟨ x i , g x j ⟩ , and let L L L denote the corresponding graph Laplacian L = diag ( A 1 n ) − A L=\operatorname{diag}(A1_n)-A L = diag ( A 1 n ) − A . If L ⪰ 0 L\succeq0 L ⪰ 0 , then the G G G -orbit of the mean of { x i } i = 1 n ⊂ R d \{x_i\}_{i=1}^n\subset\mathbb{R}^d { x i } i = 1 n ⊂ R d is a Fréchet mean of { [ x i ] } i = 1 n ⊂ R d / G \{[x_i]\}_{i=1}^n\subset\mathbb{R}^d/G {[ x i ] } i = 1 n ⊂ R d / G .
Proof. By Theorem 4.3 , it suffices to construct W W W satisfying (11) . Define
W : = ( L ⊗ I d ) + x x T . W:=(L\otimes I_d)+xx^{\mathsf{T}}. W := ( L ⊗ I d ) + x x T .
The first condition in (11) follows from our assumption that L ⪰ 0 L\succeq0 L ⪰ 0 . For the second condition, fix i < j i<j i < j and g ∈ G ∖ { I d } g\in G\setminus\{I_d\} g ∈ G ∖ { I d } . Then
⟨ I d , W [ i j ] ⟩ F − ⟨ g , W [ i j ] ⟩ F = ⟨ I d − g , x i x j T − A i j I d ⟩ F = ⟨ x i , x j ⟩ − ⟨ x i , g x j ⟩ − A i j ( d − Tr g ) ≥ 0 , \begin{aligned}
\langle I_d,W_{[ij]}\rangle_F-\langle g,W_{[ij]}\rangle_F=\langle I_d-g,x_ix_j^{\mathsf{T}}-A_{ij}I_d\rangle_F \\
&=\langle x_i,x_j\rangle-\langle x_i,gx_j\rangle-A_{ij}(d-\operatorname{Tr}g)\geq0,
\end{aligned} ⟨ I d , W [ ij ] ⟩ F − ⟨ g , W [ ij ] ⟩ F = ⟨ I d − g , x i x j T − A ij I d ⟩ F = ⟨ x i , x j ⟩ − ⟨ x i , g x j ⟩ − A ij ( d − Tr g ) ≥ 0 ,
where the inequality follows from the definition of A A A . This establishes the second condition in (11) . Finally, the third condition follows from the fact that 1 n ∈ ker L 1_n\in\ker L 1 n ∈ ker L :
⟨ W − x x T , 1 n 1 n T ⊗ I d ⟩ F = ⟨ L ⊗ I d , 1 n 1 n T ⊗ I d ⟩ F = ⟨ L , 1 n 1 n T ⟩ F ⟨ I d , I d ⟩ F = 0. \langle W-xx^{\mathsf{T}},1_n1_n^{\mathsf{T}}\otimes I_d\rangle_F=\langle L\otimes I_d,1_n1_n^{\mathsf{T}}\otimes I_d\rangle_F=\langle L,1_n1_n^{\mathsf{T}}\rangle_F\langle I_d,I_d\rangle_F=0. ⟨ W − x x T , 1 n 1 n T ⊗ I d ⟩ F = ⟨ L ⊗ I d , 1 n 1 n T ⊗ I d ⟩ F = ⟨ L , 1 n 1 n T ⟩ F ⟨ I d , I d ⟩ F = 0.
Overall, W W W satisfies (11) , and so we are done.
Corollary 4.4 gives a closed-form spectral test to certify that the orbit of the Euclidean mean is a Fréchet mean; this is inspired by the probably certifiably correct algorithms introduced in [3 ] . The underlying signed adjacency matrix is also interpretable to some extent. Indeed, since g g g is an isometry, we have
⟨ x i , x j ⟩ − ⟨ x i , g x j ⟩ = 1 2 ( ∥ x i − g x j ∥ 2 − ∥ x i − x j ∥ 2 ) . \langle x_i,x_j\rangle-\langle x_i,gx_j\rangle= \frac{1}{2}\left(\lVert x_i-gx_j\rVert^2-\lVert x_i-x_j\rVert^2\right). ⟨ x i , x j ⟩ − ⟨ x i , g x j ⟩ = 2 1 ( ∥ x i − g x j ∥ 2 − ∥ x i − x j ∥ 2 ) .
and so A i j A_{ij} A ij is nonnegative precisely when x i x_i x i and x j x_j x j are aligned. More generally, we can think of A i j A_{ij} A ij as quantifying the alignment between x i x_i x i and x j x_j x j . If { x i } i = 1 n \{x_i\}_{i=1}^{n} { x i } i = 1 n is aligned, then A A A is entrywise nonnegative, and so L ⪰ 0 L \succeq0 L ⪰ 0 . Meanwhile, this positive semidefiniteness will survive a small amount of pairwise misalignment. See Figure 4.1 for an illustration of this phenomenon and § 5 for a theoretical treatment.
Figure 4.1. Three random draws of 100 Gaussian data points in R 2 \mathbb{R}^{2} R 2 . In (a), the data is aligned with respect to G = ± G = \pm G = ± . In (b), the data is not aligned, but the spectral test in Corollary 4.4 certifies that the Fréchet mean still coincides with the Euclidean mean. In (c), the Fréchet mean in R 2 / ± \mathbb{R}^{2}/\pm R 2 / ± does not coincide with the Euclidean mean, as the red point must first be negated. See § 5 for a theoretical treatment of this phenomenon.
Relaxations for Sign Invariance
In the special case where G = ± G = \pm G = ± , the Fréchet objective (5) can be reformulated as
maximize ϵ 1 , … , ϵ n ∈ { ± 1 } ⟨ X T X , ϵ ϵ T ⟩ F (12) \underset{\epsilon_1,\ldots,\epsilon_n\in\{\pm1\}}{\operatorname{maximize}}\ \langle X^{T}X,\epsilon\epsilon^{T}\rangle_{F} \tag*{(12)} ϵ 1 , … , ϵ n ∈ { ± 1 } maximize ⟨ X T X , ϵ ϵ T ⟩ F (12)
where the i i i th column of X ∈ R d × n X \in\mathbb{R}^{d\times n} X ∈ R d × n is x i x_i x i . This formulation specializes (7) by exploiting the fact that G G G acts by scalars.4
We state our results for the finite group G = ± G = \pm G = ± , although the same scalar formulation has a complex analog with G = S 1 G = S^{1} G = S 1 acting by scalar multiplication on V = C d V = \mathbb{C}^{d} V = C d . For normalized landmark data, this complex Fréchet mean problem is a special case of Generalized Procrustes Analysis (GPA) [12 ] . The connection between Procrustes alignment and Fréchet means has been noted previously [14 ] and has been approached using spectral and semidefinite methods in [11 , 23 ] . These problems also resemble angular synchronization [25 ] and O ( 1 ) O(1) O ( 1 ) -synchronization [1 ] , which can be approached similarly. With this in mind, we develop relaxations of (12) .
Spectral Relaxation for Sign Invariance
We obtain a spectral relaxation by changing the constraint in (12) to ∥ ϵ ∥ 2 = n \lVert\epsilon\rVert^2=n ∥ ϵ ∥ 2 = n . The solution to this relaxation is then the top eigenvector of the Gram matrix X T X X^{\mathsf{T}}X X T X . Rounding this top eigenvector v v v to a feasible point of (12) then gives the approximate solution ϵ i = sgn v i \epsilon_i=\operatorname{sgn}v_i ϵ i = sgn v i .
Semidefinite Relaxation for Sign Invariance
Writing Z = ϵ ϵ T Z=\epsilon\epsilon^{\mathsf{T}} Z = ϵ ϵ T , the feasibility region of (12) consists of all Z ∈ R n × n Z\in\mathbb{R}^{n\times n} Z ∈ R n × n such that
diag Z = 1 n , Z ⪰ 0 , rank Z = 1. \operatorname{diag} Z=\mathbf{1}_n,\qquad Z\succeq0,\qquad\operatorname{rank}Z=1. diag Z = 1 n , Z ⪰ 0 , rank Z = 1.
By dropping the rank-1 constraint, we obtain the following:
Sign-Invariant Fréchet Mean SDP:
maximize Z ⟨ X T X , Z ⟩ F subject to diag Z = 1 n , Z ⪰ 0. (13) \underset{Z}{\operatorname{maximize}}\quad\langle X^{\mathsf{T}}X,Z\rangle_F\qquad\text{subject to}\qquad\operatorname{diag} Z=\mathbf{1}_n,\qquad Z\succeq0. \tag*{(13)} Z maximize ⟨ X T X , Z ⟩ F subject to diag Z = 1 n , Z ⪰ 0. (13)
When the solution to (13) has rank 1, it also solves the original problem (12) . Otherwise, we can round to the feasibility region of (12) by taking the entrywise sign of the top eigenvector of the SDP solution.
When Z = 1 n 1 n T Z=\mathbf{1}_n\mathbf{1}_n^{\mathsf{T}} Z = 1 n 1 n T is optimal for (13) , the Euclidean mean determines a Fréchet mean. Similar to Theorem 4.3 , one may use duality to characterize this situation:
Proposition 4.5 (Lemma 4.4 in [4 ] ). The matrix Z = 1 n 1 n T Z=\mathbf{1}_n\mathbf{1}_n^{\mathsf{T}} Z = 1 n 1 n T optimizes (13) if and only if diag ( X T X 1 n ) − X T X ⪰ 0 \operatorname{diag}(X^{\mathsf{T}}X\mathbf{1}_n)-X^{\mathsf{T}}X\succeq0 diag ( X T X 1 n ) − X T X ⪰ 0 .
Observe that the ( ⇐ ) (\Leftarrow) ( ⇐ ) direction follows from Corollary 4.4 since A = 1 d X T X A=\frac{1}{d}X^{\mathsf{T}}X A = d 1 X T X , while the ( ⇒ ) (\Rightarrow) ( ⇒ ) direction is unique to the sign-invariant setting.
Relaxations for Cyclic Actions
In this section, we consider G = C k G=C_k G = C k acting orthogonally on R d \mathbb{R}^d R d and on the left of R d × p \mathbb{R}^{d\times p} R d × p . For example, the group might act by cyclic permutations, as in shape analysis (see § 6.4 ) or time series data (see § 6.7 ). Sign-invariant data can also be viewed as a special case of this setting, and the following relaxations reduce to those previously discussed in § 4.3 .
Letting g g g denote (the representation of) a generator of C k C_k C k , diagonalizing over C \mathbb{C} C gives g = U D U ∗ g=UDU^* g = U D U ∗ for some unitary matrix U U U and some diagonal matrix D D D whose diagonal entries { ω m } m = 1 d \{\omega_m\}_{m=1}^d { ω m } m = 1 d are k k k th roots of unity. For each i ∈ { 1 , … , n } i\in\{1,\ldots,n\} i ∈ { 1 , … , n } , we are given x i ∈ R d × p x_i\in\mathbb{R}^{d\times p} x i ∈ R d × p . Transform the data as z i = U ∗ x i z_i=U^*x_i z i = U ∗ x i . 5 Then given g 1 , … , g n ∈ C k g_1,\ldots,g_n\in C_k g 1 , … , g n ∈ C k , we write g i = U D k i U ∗ g_i=UD^{k_i}U^* g i = U D k i U ∗ for some k i ∈ { 0 , … , k − 1 } k_i\in\{0,\ldots,k-1\} k i ∈ { 0 , … , k − 1 } , and the objective (5) becomes
∑ i , j = 1 n ⟨ x i x j T , g i T g j ⟩ F = ∑ i , j = 1 n ⟨ z i z j ∗ , D k j − k i ⟩ F = ∑ i , j = 1 n ∑ m = 1 d ( z i z j ∗ ) m m ω m k j − k i . \sum_{i,j=1}^{n}\langle x_i x_j^{\mathsf{T}},g_i^{\mathsf{T}}g_j\rangle_F
=\sum_{i,j=1}^{n}\langle z_i z_j^*,D^{k_j-k_i}\rangle_F
=\sum_{i,j=1}^{n}\sum_{m=1}^{d}(z_i z_j^*)_{mm}\omega_m^{k_j-k_i}. i , j = 1 ∑ n ⟨ x i x j T , g i T g j ⟩ F = i , j = 1 ∑ n ⟨ z i z j ∗ , D k j − k i ⟩ F = i , j = 1 ∑ n m = 1 ∑ d ( z i z j ∗ ) mm ω m k j − k i .
Writing Z m = [ ( z i z j ∗ ) m m ] i , j = 1 n Z_m=[(z_i z_j^*)_{mm}]_{i,j=1}^{n} Z m = [( z i z j ∗ ) mm ] i , j = 1 n for each m ∈ { 1 , … , d } m\in\{1,\ldots,d\} m ∈ { 1 , … , d } , then (5) reduces to
maximize k 1 , … , k n ∑ m = 1 d ⟨ Z m , [ ω m k j − k i ] i , j = 1 n ⟩ F subject to k 1 , … , k n ∈ Z / k Z . (14) \underset{k_1,\ldots,k_n}{\operatorname{maximize}}\quad\sum_{m=1}^{d}\left\langle Z_m,[\omega_m^{k_j-k_i}]_{i,j=1}^{n}\right\rangle_F\qquad\text{subject to}\qquad k_1,\ldots,k_n\in\mathbb{Z}/k\mathbb{Z}. \tag*{(14)} k 1 , … , k n maximize m = 1 ∑ d ⟨ Z m , [ ω m k j − k i ] i , j = 1 n ⟩ F subject to k 1 , … , k n ∈ Z / k Z . (14)
Overall, the cyclic structure reduces our n d × n d nd\times nd n d × n d matrix problem to an equivalent n × n × d n\times n\times d n × n × d tensor problem. The corresponding spectral and semidefinite relaxations also take special forms.
Spectral Relaxation for Cyclic Actions
The form of (14) allows us to use multi-frequency phase synchronization [9 ] , where global alignment is obtained by first synchronizing slices Z m Z_m Z m of a common mode ω m \omega_m ω m , then combining the modes to estimate pairwise relative shifts, then finally synchronizing them globally:
For each mode ω ∈ { ω 1 , … , ω d } \omega\in\{\omega_1,\ldots,\omega_d\} ω ∈ { ω 1 , … , ω d } , let Ω ω \Omega_\omega Ω ω denote the best rank-1 approximation to the positive semidefinite matrix
∑ m ∈ { 1 , … , d } ω m = ω Z m \sum_{\substack{m\in\{1,\ldots,d\}\\ \omega_m=\omega}} Z_m m ∈ { 1 , … , d } ω m = ω ∑ Z m
i.e., Ω ω = λ ω u ω u ω ∗ \Omega_\omega= \lambda_\omega u_\omega u_\omega^* Ω ω = λ ω u ω u ω ∗ , where λ ω \lambda_\omega λ ω and u ω u_\omega u ω are the top eigenvalue and eigenvector.
For each i , j ∈ { 1 , … , n } i,j \in\{1,\ldots,n\} i , j ∈ { 1 , … , n } with i < j i<j i < j , find k i j ∈ { 0 , … , k − 1 } k_{ij} \in\{0,\ldots,k-1\} k ij ∈ { 0 , … , k − 1 } that maximizes
Re ( ∑ ω ∈ { ω 1 , … , ω d } ( Ω ω ) i j ω k i j ) \operatorname{Re}\left(\sum_{\omega\in\{\omega_1,\ldots,\omega_d\}}(\Omega_\omega)_{ij}\omega^{k_{ij}}\right) Re ω ∈ { ω 1 , … , ω d } ∑ ( Ω ω ) ij ω k ij
Estimate k 1 , … , k n k_1,\ldots,k_n k 1 , … , k n by angular synchronization: Define H ∈ C n × n H \in\mathbb{C}^{n\times n} H ∈ C n × n by H i i = 1 H_{ii}=1 H ii = 1 and by H i j : = e 2 π i k i j / k H_{ij}:=e^{2\pi i k_{ij}/k} H ij := e 2 π i k ij / k and H j i = H i j ‾ H_{ji}=\overline{H_{ij}} H j i = H ij for i < j i<j i < j , compute the top eigenvector v v v of H H H , and set
k i : = round ( k 2 π arg ( v i ) ) , i ∈ { 1 , … , n } . k_i:=\operatorname{round}\left(\frac{k}{2\pi}\arg(v_i)\right),\qquad i\in\{1,\ldots,n\}. k i := round ( 2 π k arg ( v i ) ) , i ∈ { 1 , … , n } .
While the first step approximately solves
Ω ω ≈ [ 1 ω k 2 − k 1 ⋯ ω k n − k 1 ω k 1 − k 2 1 ⋯ ω k n − k 2 ⋮ ⋮ ⋱ ⋮ ω k 1 − k n ω k 2 − k n ⋯ 1 ] , \Omega_\omega\approx
\begin{bmatrix}
1 & \omega^{k_2-k_1} & \cdots& \omega^{k_n-k_1}\\
\omega^{k_1-k_2} & 1 & \cdots& \omega^{k_n-k_2}\\
\vdots& \vdots& \ddots& \vdots\\
\omega^{k_1-k_n} & \omega^{k_2-k_n} & \cdots& 1
\end{bmatrix}, Ω ω ≈ 1 ω k 1 − k 2 ⋮ ω k 1 − k n ω k 2 − k 1 1 ⋮ ω k 2 − k n ⋯ ⋯ ⋱ ⋯ ω k n − k 1 ω k n − k 2 ⋮ 1 ,
we do not round the entries of Ω ω \Omega_\omega Ω ω to phases since this would discard magnitude information that benefits step 2. In the special case where p = 1 p=1 p = 1 and no mode is repeated (e.g., when k = d k=d k = d and G G G acts by cyclic permutations), we note that each Z m Z_m Z m already has rank at most 1, and so the first step is unnecessary.
Semidefinite Relaxation for Cyclic Actions
Our slices of data form a tensor Z ∈ C n × n × d Z\in\mathbb{C}^{n\times n\times d} Z ∈ C n × n × d defined by Z i , j , m = ( Z m ) i , j Z_{i,j,m}=(Z_m)_{i,j} Z i , j , m = ( Z m ) i , j , and the relevant modes are given by the vectors
χ t : = diag ( D t ) = ( ω 1 t , … , ω d t ) , t ∈ { 0 , … , k − 1 } . \chi_t:=\operatorname{diag}(D^t)=(\omega_1^t,\ldots,\omega_d^t),\qquad t\in\{0,\ldots,k-1\}. χ t := diag ( D t ) = ( ω 1 t , … , ω d t ) , t ∈ { 0 , … , k − 1 } .
This notation yields an equivalent form of the SDP (9) for cyclic actions:
Cyclic Action Fréchet Mean SDP:
maximize Re ⟨ Z , Ω ⟩ subject to Ω i , i , ℓ = 1 for all i , ℓ , Ω i , j , : ∈ Conv { χ t } t = 0 k − 1 for all i , j , Ω : , : , ℓ ⪰ 0 for all ℓ . (15) \begin{aligned}
\text{maximize}\quad& \operatorname{Re}\langle Z,\Omega\rangle\\
\text{subject to}\quad& \Omega_{i,i,\ell}=1 \text{ for all } i,\ell,\\
& \Omega_{i,j,:}\in\operatorname{Conv}\{\chi_t\}_{t=0}^{k-1} \text{ for all } i,j,\\
& \Omega_{:,:, \ell}\succeq0 \text{ for all } \ell. \tag*{(15)}
\end{aligned} maximize subject to Re ⟨ Z , Ω ⟩ Ω i , i , ℓ = 1 for all i , ℓ , Ω i , j , : ∈ Conv { χ t } t = 0 k − 1 for all i , j , Ω : , : , ℓ ⪰ 0 for all ℓ . (15)
This form replaces an n d × n d nd\times nd n d × n d semidefinite constraint with d d d constraints of size n × n n\times n n × n , potentially reducing some computational burden.
Tightness of the Sign-Invariant Fréchet Mean SDP
In this section, we compare alignment with Proposition 4.5 for datasets in R d / ± \mathbb{R}^{d}/\pm R d / ± . We call a dataset SDP aligned if it satisfies the condition in Proposition 4.5. Alignment implies SDP alignment, which in turn guarantees that the orbit of the Euclidean mean is a Fréchet mean. The following proposition compares these conditions under a random data model: the noise threshold for alignment decreases as the ambient dimension d d d grows, while the threshold for SDP alignment remains constant (up to a log factor). Thus, alignment exhibits a curse of dimensionality that the SDP avoids.
Proposition 5.1. There exist universal constants C , c > 0 C,c>0 C , c > 0 for which the following holds: For every ϵ ∈ ( 0 , 1 / 2 ) \epsilon\in(0,1/2) ϵ ∈ ( 0 , 1/2 ) and d , n ∈ N d,n\in\mathbb{N} d , n ∈ N satisfying
C log ( n 2 / ϵ ) ≤ d ≤ n , C\log(n^{2}/\epsilon)\le d\le n, C log ( n 2 / ϵ ) ≤ d ≤ n , if we fix x ∈ S d − 1 x\in S^{d-1} x ∈ S d − 1 and draw iid random vectors { x i } i = 1 n \{x_i\}_{i=1}^{n} { x i } i = 1 n from N ( x , σ 2 I d ) \mathcal{N}(x,\sigma^{2}I_d) N ( x , σ 2 I d ) , then
σ 2 ≤ c d log ( n 2 / ϵ ) ⟹ P ( { x i } i = 1 n aligned ) > 1 − ϵ , \sigma^{2}\le\frac{c}{\sqrt{d\log(n^{2}/\epsilon)}} \quad\Longrightarrow\quad\mathbb{P}\left(\{x_i\}_{i=1}^{n}\ \text{aligned}\right)>1-\epsilon, σ 2 ≤ d log ( n 2 / ϵ ) c ⟹ P ( { x i } i = 1 n aligned ) > 1 − ϵ , σ 2 ≥ C d ⟹ P ( { x i } i = 1 n not aligned ) > 1 − ϵ , \sigma^{2}\ge\frac{C}{\sqrt{d}} \quad\Longrightarrow\quad\mathbb{P}\left(\{x_i\}_{i=1}^{n}\ \text{not aligned}\right)>1-\epsilon, σ 2 ≥ d C ⟹ P ( { x i } i = 1 n not aligned ) > 1 − ϵ , σ 2 ≤ c log ( n 2 / ϵ ) ⟹ P ( { x i } i = 1 n SDP aligned ) > 1 − ϵ . \sigma^{2}\le\frac{c}{\log(n^{2}/\epsilon)} \quad\Longrightarrow\quad\mathbb{P}\left(\{x_i\}_{i=1}^{n}\ \text{SDP aligned}\right)>1-\epsilon. σ 2 ≤ log ( n 2 / ϵ ) c ⟹ P ( { x i } i = 1 n SDP aligned ) > 1 − ϵ . This reveals a sizable gap between alignment and SDP alignment. When
1 d ≲ σ 2 ≲ 1 log ( n 2 / ϵ ) , \frac{1}{\sqrt{d}}\lesssim\sigma^{2}\lesssim\frac{1}{\log(n^{2}/\epsilon)}, d 1 ≲ σ 2 ≲ log ( n 2 / ϵ ) 1 , it holds with high probability that Gaussian points are SDP aligned but not aligned; see Figure 5.1 for an illustration. Thus, for high-dimensional sign-invariant data, the SDP tolerates substantially more noise than alignment does. Experiments in § 6 show a similar gap for other groups.
Figure 5.1. Illustration of Proposition 5.1 in the usual setting where d ≫ log 2 ( n 2 / ϵ ) d \gg\log^{2}(n^{2}/\epsilon) d ≫ log 2 ( n 2 / ϵ ) . This establishes the strength of the sign-invariant Fréchet mean SDP (13) over the notion of alignment introduced in § 3.1 .
Proof of Proposition 5.1. We prove each claimed implication separately.
Claim I: Fix i , j ∈ { 1 , … , n } i,j\in\{1,\ldots,n\} i , j ∈ { 1 , … , n } with i ≠ j i\ne j i = j . We start by upper bounding the probability that x i x_i x i and x j x_j x j are not aligned, i.e., ⟨ x i , x j ⟩ < 0 \langle x_i,x_j\rangle<0 ⟨ x i , x j ⟩ < 0 . If we denote z i : = x i − x z_i:=x_i-x z i := x i − x , z j : = x j − x z_j:=x_j-x z j := x j − x , W : = ⟨ z i , x ⟩ + ⟨ x , z j ⟩ W:=\langle z_i,x\rangle+\langle x,z_j\rangle W := ⟨ z i , x ⟩ + ⟨ x , z j ⟩ and Z : = ⟨ z i , z j ⟩ Z:=\langle z_i,z_j\rangle Z := ⟨ z i , z j ⟩ , then
P ( ⟨ x i , x j ⟩ < 0 ) = P ( 1 + W + Z < 0 ) ≤ P ( W < − 1 2 ) + P ( Z < − 1 2 ) . \mathbb{P}(\langle x_i,x_j\rangle<0)=\mathbb{P}(1+W+Z<0)\le\mathbb{P}\left(W<-\frac{1}{2}\right)+\mathbb{P}\left(Z<-\frac{1}{2}\right). P (⟨ x i , x j ⟩ < 0 ) = P ( 1 + W + Z < 0 ) ≤ P ( W < − 2 1 ) + P ( Z < − 2 1 ) .
Since W ∼ N ( 0 , 2 σ 2 ) W \sim N(0,2\sigma^2) W ∼ N ( 0 , 2 σ 2 ) , the Chernoff bound gives P ( W < − 1 2 ) ≤ e − 1 / ( 16 σ 2 ) \mathbb{P}(W < -\frac{1}{2}) \le e^{-1/(16\sigma^2)} P ( W < − 2 1 ) ≤ e − 1/ ( 16 σ 2 ) . Meanwhile, an application of the Hanson–Wright inequality gives
P ( Z < − 1 2 ) ≤ 2 exp ( − c 1 min { 1 d σ 4 , 1 σ 2 } ) . \mathbb{P}(Z < -\tfrac{1}{2}) \le2\exp\left(-c_1\min\left\{\frac{1}{d\sigma^4},\frac{1}{\sigma^2}\right\}\right). P ( Z < − 2 1 ) ≤ 2 exp ( − c 1 min { d σ 4 1 , σ 2 1 } ) .
where c 1 > 0 c_1 > 0 c 1 > 0 is a universal constant. We combine these estimates to obtain
P ( ⟨ x i , x j ⟩ < 0 ) ≤ 3 exp ( − c 2 min { 1 d σ 4 , 1 σ 2 } ) , \mathbb{P}(\langle x_i,x_j\rangle< 0) \le3\exp\left(-c_2\min\left\{\frac{1}{d\sigma^4},\frac{1}{\sigma^2}\right\}\right), P (⟨ x i , x j ⟩ < 0 ) ≤ 3 exp ( − c 2 min { d σ 4 1 , σ 2 1 } ) ,
where c 2 > 0 c_2 > 0 c 2 > 0 is a universal constant. An application of the union bound then gives
P ( { x i } i = 1 n aligned ) ≥ 1 − ( n 2 ) ⋅ 3 exp ( − c 2 min { 1 d σ 4 , 1 σ 2 } ) . \mathbb{P}(\{x_i\}_{i=1}^n\text{ aligned}) \ge1-\binom{n}{2}\cdot3\exp\left(-c_2\min\left\{\frac{1}{d\sigma^4},\frac{1}{\sigma^2}\right\}\right). P ({ x i } i = 1 n aligned ) ≥ 1 − ( 2 n ) ⋅ 3 exp ( − c 2 min { d σ 4 1 , σ 2 1 } ) .
Squaring and rearranging our hypothesis on σ 2 \sigma^2 σ 2 gives 1 d σ 4 ≥ 1 c 2 log ( n 2 / ϵ ) \frac{1}{d\sigma^4} \ge\frac{1}{c^2}\log(n^2/\epsilon) d σ 4 1 ≥ c 2 1 log ( n 2 / ϵ ) . Meanwhile, combining our hypothesis on σ 2 \sigma^2 σ 2 with the assumption d ≥ C log ( n 2 / ϵ ) d \ge C\log(n^2/\epsilon) d ≥ C log ( n 2 / ϵ ) gives
1 σ 2 ≥ d log ( n 2 / ϵ ) c ≥ C c ⋅ log ( n 2 / ϵ ) . \frac{1}{\sigma^2} \ge\frac{\sqrt{d\log(n^2/\epsilon)}}{c} \ge\frac{\sqrt{C}}{c}\cdot\log(n^2/\epsilon). σ 2 1 ≥ c d log ( n 2 / ϵ ) ≥ c C ⋅ log ( n 2 / ϵ ) .
Taking C C C sufficiently large and c c c sufficiently small, it follows that our lower bound on the aligned probability is strictly greater than 1 − ϵ 1-\epsilon 1 − ϵ , as desired.
Claim II: Fix i , j ∈ { 1 , … , n } i,j\in\{1,\ldots,n\} i , j ∈ { 1 , … , n } with i ≠ j i\ne j i = j . We start by lower bounding the probability that x i x_i x i and x j x_j x j are not aligned. Recalling z i , z j , W z_i,z_j,W z i , z j , W , and Z Z Z from the previous argument, note that simultaneously negating z i z_i z i and z j z_j z j negates W W W and fixes Z Z Z . It follows that
P ( ⟨ x i , x j ⟩ < 0 ) ≥ P ( W < 0 , Z < − 1 ) = 1 2 P ( Z < − 1 ) = 1 4 P ( Z 2 > 1 ) , \mathbb{P}(\langle x_i,x_j\rangle< 0) \ge\mathbb{P}(W<0,Z<-1)=\frac{1}{2}\mathbb{P}(Z<-1)=\frac{1}{4}\mathbb{P}(Z^2>1), P (⟨ x i , x j ⟩ < 0 ) ≥ P ( W < 0 , Z < − 1 ) = 2 1 P ( Z < − 1 ) = 4 1 P ( Z 2 > 1 ) ,
where the last step uses the fact that the distribution of Z Z Z is symmetric about zero. We obtain a further lower bound using the Paley–Zygmund inequality. First, we compute the relevant moments:
E Z 2 = E [ ∑ k , l = 1 d ( z i ) k ( z j ) k ( z i ) l ( z j ) l ] = ∑ k = 1 d E [ ( z i ) k 2 ] E [ ( z j ) k 2 ] = d σ 4 , \mathbb{E}Z^2=\mathbb{E}\left[\sum_{k,l=1}^{d}(z_i)_k(z_j)_k(z_i)_l(z_j)_l\right]=\sum_{k=1}^{d}\mathbb{E}[(z_i)_k^2]\mathbb{E}[(z_j)_k^2]=d\sigma^4, E Z 2 = E k , l = 1 ∑ d ( z i ) k ( z j ) k ( z i ) l ( z j ) l = k = 1 ∑ d E [( z i ) k 2 ] E [( z j ) k 2 ] = d σ 4 ,
E Z 4 = E [ E [ Z 4 ∣ z i ] ] = E [ 3 σ 4 ∥ z i ∥ 4 ] = 3 σ 4 ⋅ E [ ∑ k , l = 1 d ( z i ) k 2 ( z i ) l 2 ] = 3 d ( d + 2 ) σ 8 . \mathbb{E}Z^4=\mathbb{E}[\mathbb{E}[Z^4\mid z_i]]=\mathbb{E}[3\sigma^4\|z_i\|^4]=3\sigma^4\cdot\mathbb{E}\left[\sum_{k,l=1}^{d}(z_i)_k^2(z_i)_l^2\right]=3d(d+2)\sigma^8. E Z 4 = E [ E [ Z 4 ∣ z i ]] = E [ 3 σ 4 ∥ z i ∥ 4 ] = 3 σ 4 ⋅ E k , l = 1 ∑ d ( z i ) k 2 ( z i ) l 2 = 3 d ( d + 2 ) σ 8 .
Then we combine the Paley–Zygmund inequality with the fact that d ≥ 1 d\ge1 d ≥ 1 to obtain
P ( Z 2 > 1 2 E Z 2 ) ≥ ( E Z 2 ) 2 4 E Z 4 = d 12 ( d + 2 ) ≥ 1 36 . \mathbb{P}(Z^2>\tfrac{1}{2}\mathbb{E}Z^2)\ge\frac{(\mathbb{E}Z^2)^2}{4\mathbb{E}Z^4}=\frac{d}{12(d+2)}\ge\frac{1}{36}. P ( Z 2 > 2 1 E Z 2 ) ≥ 4 E Z 4 ( E Z 2 ) 2 = 12 ( d + 2 ) d ≥ 36 1 .
Provided C ≥ 2 C\ge\sqrt{2} C ≥ 2 , our hypothesis on σ 2 \sigma^2 σ 2 gives 1 2 E Z 2 = 1 2 d σ 4 ≥ 1 \frac{1}{2}\mathbb{E}Z^2=\frac{1}{2}d\sigma^4\ge1 2 1 E Z 2 = 2 1 d σ 4 ≥ 1 , and so
P ( ⟨ x i , x j ⟩ < 0 ) ≥ 1 4 P ( Z 2 > 1 ) ≥ 1 4 P ( Z 2 > 1 2 E Z 2 ) ≥ 1 144 . \mathbb{P}(\langle x_i,x_j\rangle<0)\ge\frac{1}{4}\mathbb{P}(Z^2>1)\ge\frac{1}{4}\mathbb{P}(Z^2>\tfrac{1}{2}\mathbb{E}Z^2)\ge\frac{1}{144}. P (⟨ x i , x j ⟩ < 0 ) ≥ 4 1 P ( Z 2 > 1 ) ≥ 4 1 P ( Z 2 > 2 1 E Z 2 ) ≥ 144 1 .
Now note that { x i } i = 1 n \{x_i\}_{i=1}^n { x i } i = 1 n is aligned only if ⟨ x i , x i + 1 ⟩ ≥ 0 \langle x_i,x_{i+1}\rangle\ge0 ⟨ x i , x i + 1 ⟩ ≥ 0 for each odd i < n i<n i < n . These events are independent and have the same probability, and so
P ( { x i } i = 1 n aligned ) ≤ ( 1 − P ( ⟨ x 1 , x 2 ⟩ < 0 ) ) ⌊ n / 2 ⌋ ≤ ( 143 144 ) ⌊ n / 2 ⌋ . \mathbb{P}(\{x_i\}_{i=1}^n\text{ aligned})\le\left(1-\mathbb{P}(\langle x_1,x_2\rangle<0)\right)^{\lfloor n/2\rfloor}\le\left(\frac{143}{144}\right)^{\lfloor n/2\rfloor}. P ({ x i } i = 1 n aligned ) ≤ ( 1 − P (⟨ x 1 , x 2 ⟩ < 0 ) ) ⌊ n /2 ⌋ ≤ ( 144 143 ) ⌊ n /2 ⌋ .
Since n ≥ C log ( n 2 / ϵ ) ≥ C log ( 1 / ϵ ) n\ge C\log(n^2/\epsilon)\ge C\log(1/\epsilon) n ≥ C log ( n 2 / ϵ ) ≥ C log ( 1/ ϵ ) by assumption, taking C C C sufficiently large makes this upper bound strictly less than ϵ \epsilon ϵ , as desired.
Claim III: Following Proposition 4.5 , we put L : = diag ( X T X 1 n ) − X T X L:=\operatorname{diag}(X^{\mathsf{T}}X\mathbf{1}_n)-X^{\mathsf{T}}X L := diag ( X T X 1 n ) − X T X , where X X X has columns x 1 , … , x n x_1,\ldots,x_n x 1 , … , x n . It suffices to show L ⪰ 0 L \succeq0 L ⪰ 0 . Define
μ : = 1 n ∑ i = 1 n x i , r i : = x i − μ , R : = [ r 1 ⋯ r n ] . \mu:=\frac{1}{n}\sum_{i=1}^{n}x_i,\qquad r_i:=x_i-\mu,\qquad R:=\begin{bmatrix}r_1&\cdots&r_n\end{bmatrix}. μ := n 1 i = 1 ∑ n x i , r i := x i − μ , R := [ r 1 ⋯ r n ] . Since L 1 n = 0 L\mathbf{1}_n=0 L 1 n = 0 , we may focus on the unit vectors v v v orthogonal to 1 n \mathbf{1}_n 1 n . Since X 1 n = n μ X\mathbf{1}_n=n\mu X 1 n = n μ and X v = R v Xv=Rv X v = R v for every such vector, we have
v T L v = v T diag ( X T X 1 n ) v − v T X T X v = ∑ i = 1 n ⟨ x i , n μ ⟩ v i 2 − ∥ R v ∥ 2 2 v^{\mathsf{T}}Lv=v^{\mathsf{T}}\operatorname{diag}(X^{\mathsf{T}}X\mathbf{1}_n)v-v^{\mathsf{T}}X^{\mathsf{T}}Xv=\sum_{i=1}^{n}\langle x_i,n\mu\rangle v_i^2-\lVert Rv\rVert_2^2 v T Lv = v T diag ( X T X 1 n ) v − v T X T X v = i = 1 ∑ n ⟨ x i , n μ ⟩ v i 2 − ∥ R v ∥ 2 2 ≥ min i { ⟨ x i , n μ ⟩ } − ∥ R ∥ 2 2 \geq\min_i\{\langle x_i,n\mu\rangle\}-\lVert R\rVert_2^2 ≥ i min {⟨ x i , n μ ⟩} − ∥ R ∥ 2 2 = n ( ∥ μ ∥ 2 + min i ⟨ r i , μ ⟩ ) − ∥ R ∥ 2 2 . =n\left(\lVert\mu\rVert^2+\min_i\langle r_i,\mu\rangle\right)-\lVert R\rVert_2^2. = n ( ∥ μ ∥ 2 + i min ⟨ r i , μ ⟩ ) − ∥ R ∥ 2 2 . We will show that the right-hand side is positive with high probability.
First, ⟨ μ , x ⟩ ∼ N ( 1 , σ 2 / n ) \langle\mu,x\rangle\sim N(1,\sigma^2/n) ⟨ μ , x ⟩ ∼ N ( 1 , σ 2 / n ) , and so the Chernoff bound gives
P ( ∥ μ ∥ < 1 / 2 ) ≤ P ( ⟨ μ , x ⟩ < 1 / 2 ) ≤ e − n / ( 8 σ 2 ) . \mathbb{P}(\lVert\mu\rVert<1/2)\leq\mathbb{P}(\langle\mu,x\rangle<1/2)\leq e^{-n/(8\sigma^2)}. P (∥ μ ∥ < 1/2 ) ≤ P (⟨ μ , x ⟩ < 1/2 ) ≤ e − n / ( 8 σ 2 ) . Next, the sample mean μ \mu μ and residual matrix R R R are jointly Gaussian with zero covariance, and therefore independent. Since r i ∼ N ( 0 , ( 1 − 1 / n ) σ 2 I d ) r_i\sim N(0,(1-1/n)\sigma^2 I_d) r i ∼ N ( 0 , ( 1 − 1/ n ) σ 2 I d ) , it follows that, conditional on μ \mu μ , each ⟨ r i , μ ⟩ \langle r_i,\mu\rangle ⟨ r i , μ ⟩ has distribution N ( 0 , ( 1 − 1 / n ) σ 2 ∥ μ ∥ 2 ) N(0,(1-1/n)\sigma^2\lVert\mu\rVert^2) N ( 0 , ( 1 − 1/ n ) σ 2 ∥ μ ∥ 2 ) . We apply the union bound, the law of total probability, and the Chernoff bound to obtain
P ( min i ⟨ r i , μ ⟩ < − s ∥ μ ∥ ) ≤ n ⋅ E [ P ( ⟨ r 1 , μ ⟩ < − s ∥ μ ∥ ∣ μ ) ] ≤ n ⋅ e − s 2 / ( 2 σ 2 ) \mathbb{P}\left(\min_i\langle r_i,\mu\rangle<-s\lVert\mu\rVert\right)\leq n\cdot\mathbb{E}\left[\mathbb{P}\left(\langle r_1,\mu\rangle<-s\lVert\mu\rVert\mid\mu\right)\right]\leq n\cdot e^{-s^2/(2\sigma^2)} P ( i min ⟨ r i , μ ⟩ < − s ∥ μ ∥ ) ≤ n ⋅ E [ P ( ⟨ r 1 , μ ⟩ < − s ∥ μ ∥ ∣ μ ) ] ≤ n ⋅ e − s 2 / ( 2 σ 2 ) for every s ≥ 0 s\geq0 s ≥ 0 . Finally, write E : = [ z 1 ⋯ z n ] E:=\begin{bmatrix}z_1&\cdots&z_n\end{bmatrix} E := [ z 1 ⋯ z n ] , where again z i : = x i − x ˉ z_i:=x_i-\bar{x} z i := x i − x ˉ . Then
∥ R ∥ 2 = ∥ E ( I n − 1 n 1 n 1 n T ) ∥ 2 ≤ ∥ E ∥ 2 , \lVert R\rVert_2=\left\lVert E\left(I_n-\frac{1}{n}\mathbf{1}_n\mathbf{1}_n^{\mathsf{T}}\right)\right\rVert_2\leq\lVert E\rVert_2, ∥ R ∥ 2 = E ( I n − n 1 1 n 1 n T ) 2 ≤ ∥ E ∥ 2 , and so the standard Gaussian matrix norm bound gives
P ( ∥ R ∥ 2 > σ ( d + n + t ) ) ≤ 2 e − t 2 / 2 \mathbb{P}\left(\lVert R\rVert_2>\sigma(\sqrt{d}+\sqrt{n}+t)\right)\leq2e^{-t^2/2} P ( ∥ R ∥ 2 > σ ( d + n + t ) ) ≤ 2 e − t 2 /2 for every t ≥ 0 t\geq0 t ≥ 0 .
Now take s = 1 / 4 s=1/4 s = 1/4 and t = n t=\sqrt{n} t = n . Since d ≤ n d\leq n d ≤ n , the preceding estimates imply that
∥ μ ∥ ≥ 1 2 , min i ⟨ r i , μ ⟩ ≥ − 1 4 ∥ μ ∥ , ∥ R ∥ 2 ≤ 3 σ n \lVert\mu\rVert\geq\frac{1}{2},\qquad\min_i\langle r_i,\mu\rangle\geq-\frac{1}{4}\lVert\mu\rVert,\qquad\lVert R\rVert_2\leq3\sigma\sqrt{n} ∥ μ ∥ ≥ 2 1 , i min ⟨ r i , μ ⟩ ≥ − 4 1 ∥ μ ∥ , ∥ R ∥ 2 ≤ 3 σ n hold simultaneously except on an event of probability at most
e − n / ( 8 σ 2 ) + n e − 1 / ( 32 σ 2 ) + 2 e − n / 2 < ϵ , e^{-n/(8\sigma^2)}+ne^{-1/(32\sigma^2)}+2e^{-n/2}<\epsilon, e − n / ( 8 σ 2 ) + n e − 1/ ( 32 σ 2 ) + 2 e − n /2 < ϵ , where the last step applies our assumption n ≥ C log ( n 2 / ϵ ) n\geq C\log(n^2/\epsilon) n ≥ C log ( n 2 / ϵ ) with C C C sufficiently large and our hypothesis on σ 2 \sigma^2 σ 2 with c c c sufficiently small. Overall, with probability greater than 1 − ϵ 1-\epsilon 1 − ϵ , it holds that every unit vector v v v orthogonal to 1 n \mathbf{1}_n 1 n satisfies
v T L v ≥ n ( ∥ μ ∥ 2 + min i ⟨ r i , μ ⟩ ) − ∥ R ∥ 2 2 ≥ n ( 1 8 − 9 σ 2 ) > 0 , v^{\mathsf{T}}Lv\geq n\left(\lVert\mu\rVert^2+\min_i\langle r_i,\mu\rangle\right)-\lVert R\rVert_2^2\geq n\left(\frac{1}{8}-9\sigma^2\right)>0, v T Lv ≥ n ( ∥ μ ∥ 2 + i min ⟨ r i , μ ⟩ ) − ∥ R ∥ 2 2 ≥ n ( 8 1 − 9 σ 2 ) > 0 , where the last step holds provided c c c is sufficiently small. Thus, L L L is positive semidefinite, as desired.
Numerical Results and Applications
In this section, we perform numerical experiments with Fréchet means. Section 6.1 compares different ways to certify the correctness of a Fréchet mean, Section 6.2 compares the efficacy of the numerical methods from § 4 , and the remaining subsections apply these methods to various datasets.
Gap Between Alignment and Fréchet Optimality
As discussed in § 3 , aligned data points are optimal orbit representatives for the Fréchet mean. The Laplacian condition in Corollary 4.4 relaxes this notion of alignment, providing a sufficient condition that is more readily satisfied for some group actions. While Proposition 5.1 quantified the difference between these conditions in the special case where G = ± G = \pm G = ± , we now examine other cases by numerical means in Figure 6.1 .
Figure 6.1. Empirical probability of alignment (top) versus empirical probability that the Laplacian condition of Corollary 4.4 holds (bottom) for several group actions on Gaussian data. Color indicates probability from purple (near 0) to yellow (near 1). The representations are (a) ± I d \pm I_d ± I d , (b) rotations by multiples of 2 π / 3 2\pi/3 2 π /3 tensored with I d / 2 I_{d/2} I d /2 , (c) cyclic permutations, (d) cyclic permutations with reversal, (e) coordinate permutations, and (f) even sign flips.
We test the probability that random data satisfies either sufficient condition across various noise levels and ambient dimensions. For each combination of parameters, n = 100 n = 100 n = 100 vectors are drawn independently from a Gaussian distribution centered at a uniformly random point on S d − 1 S^{d-1} S d − 1 . The horizontal axis captures the variance, while the vertical axis captures the ambient dimension d d d . We record the proportion of the 1000 trials for which the generated data is aligned or satisfies the Laplacian condition. Figure 6.1 a illustrates behavior in the case of G = ± G = \pm G = ± described by Proposition 5.1.
Comparison of Methods
As the ambient dimension increases, smaller noise levels are required for alignment. In contrast, the probability that the data satisfies the Laplacian condition is relatively stable. Other groups show similar behavior. In settings where the ambient dimension is comparable to the size of the group, the Laplacian condition shows a clear improvement over alignment. These results demonstrate settings in which orbit representatives need not be pairwise aligned to be optimal for the Fréchet mean.
Figure 6.1 e shows that the two sufficient conditions are satisfied with equal probability across all tests. This is consistent with our discussion of alignment. In the case G = S d G = S_d G = S d , sorting all vectors in the same order simultaneously minimizes every pairwise distance (see Example 3.2 ). Consequently, every dataset is alignable, and Fréchet-optimal representatives must therefore be aligned by Theorem 2.1 . While visually similar, this is not the case in Figure 6.1 f. There is in fact a small difference in computed probabilities between the two conditions. That said, the size of the group in this case (2 d − 1 2^{d-1} 2 d − 1 ) makes it highly likely that a different set of orbit representatives is Fréchet optimal whenever alignment fails.
Comparison of Methods
Next, we compare the accuracy and runtime of different methods that compute approximate Fréchet means. In order to determine the ground-truth Fréchet mean, we choose a small group action acting on a small n n n -point dataset. In this setting, a brute-force O ( ∣ G ∣ n ) \mathcal{O}(|G|^n) O ( ∣ G ∣ n ) combinatorial approach is feasible to use as a baseline.
We measure error in the computed Fréchet mean using percent error in the Fréchet functional (2) . Figure 6.2 shows the log-distribution of errors for each method in the settings of R 5 / ± \mathbb{R}^5/\pm R 5 / ± and R 5 / C 5 \mathbb{R}^5/C_5 R 5 / C 5 acting by cyclic permutations. Each distribution is computed from 1000 independently sampled Gaussian datasets with unit variance and a center chosen uniformly at random from the sphere. For the same settings, Figure 6.3 displays the average runtime of each method over 100 trials for increasing dataset sizes. In the case of G = ± G=\pm G = ± , the synchronization approximation is equivalent to the spectral method and is therefore omitted.
Figure 6.2. Distribution of percent error in the Fréchet functional at the computed means across 1000 trials. Median errors are shown in red.
Figure 6.3. Runtime to compute an approximate Fréchet mean.
In both settings, the rounded SDP relaxation performs remarkably well in computing the Fréchet mean with median error at machine precision. The price of this accuracy is runtime, as both SDP methods take significantly longer than the others. Using the reduced-form SDPs in § 4.3.2 and § 4.4.2 reduces overall runtime, but they scale similarly with dataset size.
For gradient descent, we used the alternating method for finding Karcher means discussed in § 2.1 , as it is equivalent to gradient descent with a specific step size. We chose to initialize at a uniformly random data point for this comparison. The error distribution indicates that gradient descent frequently finds a local Karcher mean rather than the true Fréchet mean. In contrast to an SDP approach, gradient descent is computationally efficient and scales well with large datasets.
The specific spectral methods derived for these actions demonstrate a useful middle ground in both runtime and accuracy. The spectral methods provide an initialization-independent approximation, but often have nonzero errors since they do not necessarily produce even a Karcher mean. Using the spectral method to provide an initialization for gradient descent performs better than either the spectral method or gradient descent alone, and scales as well as the spectral method itself. This suggests that when n n n , d d d , or ∣ G ∣ |G| ∣ G ∣ is too large for an SDP, performing a spectral approximation followed by gradient steps provides a robust and tractable way to compute an approximate Fréchet mean.
MNIST Digits
In this section, we consider a modified version of the MNIST database of handwritten digits. Each image is processed to extract the digit boundaries, and 25 points are sampled uniformly along each boundary in a loop. The starting point of this loop is chosen arbitrarily, introducing a cyclic symmetry. As such, we think of this MNIST outline data as residing in R 25 × 2 / C 25 \mathbb{R}^{25\times2}/C_{25} R 25 × 2 / C 25 , where C 25 C_{25} C 25 acts by cyclically permuting the points along the loop.
We partition the digits according to their digit label and compute the Fréchet mean of each class using the spectral method detailed in § 4.4.1 . The resulting in-class Fréchet means are shown in Figure 6.4 , which also displays the naive Euclidean means for comparison. By working directly in the quotient space, we avoid an explicit alignment preprocessing step, which might fail to align the data uniformly. The computed Fréchet means reflect the true structure of the data, independent of the ambiguity in the starting point.
Figure 6.4. Euclidean and approximate Fréchet means of MNIST digit outlines.
Districting Plans
In this section, we compute an approximate Fréchet mean of congressional districting plans that exhibit an inherent permutation symmetry. We analyze 1000 plans generated using the cycle walk algorithm , an MCMC-based
MNIST Digits
scheme for sampling graph partitions that was specifically developed to create political districting plans [5 ] . Each plan is represented as a 14 × 2650 14 \times2650 14 × 2650 binary matrix, where entry ( i , j ) (i,j) ( i , j ) equals 1 when the j j j th voting precinct is assigned to the i i i th district. Accordingly, each column contains exactly one nonzero entry. Since district labels are not canonical, we view this data as residing in the orbit space R 14 × 2650 / S 14 \mathbb{R}^{14 \times2650}/S_{14} R 14 × 2650 / S 14 .
To compute an approximate Fréchet mean, we apply the spectral approach described in Algorithm 4.1, followed by gradient descent. Notably, this data does not require rounding to a corresponding synchronization problem. The resulting Fréchet mean can be interpreted as a “fuzzy assignment” of precincts to districts. See Figure 6.5 for a visualization. For clarity, we separately display each fuzzy district as well as the population. A similar experiment was performed in [21 Section 5.1] , using a different dataset and a different Fréchet mean approximation algorithm. In particular, the dataset in that paper used pre-2020 census data, for which North Carolina was assigned 13 districts (rather than the 14 district plans used here). Despite these differences, the majority of the fuzzy districts we obtain here have clear geographic counterparts in the result presented in the previous work.
Figure 6.5. (a) Individual districts; (b) Population density by precinct (2020 Census); (c) Approximate Fréchet mean of 1000 MCMC plans. Approximate Fréchet mean of districting plans in North Carolina.
Clustering with Symmetries
In the following sections, we implement k k k -means clustering in the context of orbit spaces. We define k k k -Fréchet mean clustering
Districting Plans
via the optimization problem
arg min C 1 , … , C k C 1 ⊔ ⋯ ⊔ C k = { 1 , … , n } ∑ i = 1 k ∑ j ∈ C i d ( [ μ i ] , [ x j ] ) 2 , (16) \underset{\substack{C_1,\ldots,C_k\\ C_1\sqcup\cdots\sqcup C_k=\{1,\ldots,n\}}}{\arg\min}\ \sum_{i=1}^{k}\sum_{j\in C_i}d([\mu_i],[x_j])^2, \tag*{(16)} C 1 , … , C k C 1 ⊔ ⋯ ⊔ C k = { 1 , … , n } arg min i = 1 ∑ k j ∈ C i ∑ d ([ μ i ] , [ x j ] ) 2 , (16)
where μ i \mu_i μ i denotes the Fréchet mean of the cluster { [ x j ] } j ∈ C i \{[x_j]\}_{j\in C_i} {[ x j ] } j ∈ C i with respect to the quotient metric.
This formulation seeks a partition that minimizes the total within-cluster variance, as measured by the Fréchet functional. This provides a natural way to perform unsupervised clustering of data in an orbit space. The standard iterative k k k -means algorithm can be readily adapted to this setting by alternating between assigning clusters and computing Fréchet means. Orbits are assigned to clusters according to the nearest cluster mean in the quotient metric, and then cluster means are updated using an appropriate method from § 4 .
Cylinder, Bell, Funnel
The Cylinder–Bell–Funnel dataset [26 ] was introduced to compare classification methods for time series data. It consists of realizations of three types of time series: cylinders, which resemble indicator functions over a central interval; bells, which exhibit a gradual increase followed by a step down; and funnels, which display a step up followed by a gradual decrease. Each realization is corrupted by noise in both its amplitude and its time domain, leading to perturbations in signal height and horizontal alignment. More details can be found in Example 4.7 of [24 ] . The data is split into a training set of only 30 time series of length 128 and 900 test samples. In this section, we cluster these time series.
We first apply k k k -means clustering to the training set with k = 3 k=3 k = 3 . The results of standard k k k -means are shown in the top-left panel of Figure 6.6 . Using the resulting cluster centers to classify the test set yields an accuracy of only 65%. Since the data exhibit variability in temporal alignment, the orbit space R 128 / C 128 \mathbb{R}^{128}/\mathbb{C}_{128} R 128 / C 128 provides a more natural setting for clustering. We therefore apply the k k k -Fréchet means algorithm to perform clustering in the quotient space, using the spectral method of § 4.4.1 followed by gradient descent to compute cluster means in each iteration. The resulting centroids (defined up to cyclic shift) are shown in the bottom-left panel of Figure 6.6 . Visually, this approach recovers the underlying shapes more accurately than standard k k k -means. In fact, classification using these centroids achieves a 90% accuracy on the test set.
Figure 6.6. k k k -means centroids from the CBF training set (left) and the sliding-window augmented CBF training set (right). The top and bottom rows show results obtained by working in Euclidean space R 128 \mathbb{R}^{128} R 128 and the quotient space R 128 / C 128 \mathbb{R}^{128}/C_{128} R 128 / C 128 , respectively.
We next focus our attention on the clustering behavior of sliding windows. We concatenate the Cylinder, Bell, Funnel training set into a single time series of length 3840 and extract all 3713 overlapping windows of length 128. This setup follows the experiments in § 4 of [18 ] and § 3 of [2 ] . In both works, applying k k k -means to the sliding window representation is found to be completely meaningless, as the resulting centroids resemble sinusoids (see the top-right panel of Figure 6.6 ). The authors of [2 ] attribute this ambiguity to an approximate cyclic symmetry in the sliding window construction: consecutive windows differ by a cyclic permutation and the replacement of one boundary sample. We instead perform clustering in the orbit space and report the resulting centroids in the bottom-right panel of Figure 6.6 . By accounting for this symmetry, the resulting clusters become meaningful. Using these centroids to classify the test set yields an accuracy of 81%, despite the substantial noise introduced by the sliding window representation.
Electrocardiography
The PTB-XL dataset [28 ] consists of 21,799 clinical 12-lead ECGs from 18,869 patients, each of length 10 seconds sampled at 100Hz. Each ECG is annotated by up to two cardiologists, with potentially multiple labels per recording. We restrict attention to recordings labeled either as myocardial infarction (heart attack) or as healthy ECGs.
We apply several preprocessing steps to the ECG recordings. First, each recording is truncated to a one-second segment. We then use a simple peak-detection procedure to ensure that each segment contains a single cardiac peak, padding the remainder with the mean waveform value. Finally, we normalize each channel to a common scale and center each waveform. For computational tractability, we subsample 500 ECGs per class. The one-second ECG segments each contain a single heartbeat, but are not naturally aligned in time. To account for this misalignment, we model the data in the orbit space induced by cyclic time shifts, namely, R 100 × 12 / C 100 \mathbb{R}^{100 \times12}/\mathbb{C}_{100} R 100 × 12 / C 100 .
Our first experiment is computing the mean ECG for both classes. Two leads of the resulting means are shown in the left panel of Figure 6.7 b. The averaged waveforms reveal clear visual differences between healthy subjects and those with myocardial infarction. In particular, healthy ECGs exhibit a more defined positive bump in lead 1 following the main spike and lead 6 shows a distinct downward deflection at the main spike in the infarction class. We further use these class means to construct a highly interpretable distance-based classifier, labeling a new ECG according to its relative distance to the two Fréchet means in the orbit space. The corresponding ROC curve is shown in Figure 6.7 a. Despite its simplicity, this classifier achieves an AUC of 0.82 when evaluated on the held-out test data.
Figure 6.7. (a) ROC curve for classifying myocardial infarction based on distance from the Fréchet mean of each class. (b) Fréchet mean of 500 randomly sampled heart attack and normal ECG signals alongside the k k k -Fréchet-means centroids on the sampled data. The top and bottom panels show two different ECG lead readings.
We next perform a separate k k k -Fréchet means clustering on the data with k = 2 k = 2 k = 2 . The resulting centroids are shown on the right of Figure 6.7 b. Interestingly, these cluster means appear to capture meaningful patterns associated with the underlying classes. For example, the post-spike bump in lead 1 is clearly present in the orange centroid, while the large negative spike in lead 6 is reflected in the blue centroid. In contrast, applying classical k k k -means clustering directly to the ECG data results in a singleton cluster and therefore meaningless centroids.
Discussion
Fréchet means in orbit spaces provide a natural notion of averaging in settings with underlying symmetries. While computing these means exactly is generally intractable, we introduced a suite of global relaxations that make the problem computationally feasible. These relaxations yield practical and robust approaches to approximating Fréchet means. Moreover, we have established conditions under which a computed solution can be certified as a true Fréchet mean using the geometry of the orbit space and semidefinite programming.
This work leaves several directions for future research. First, a more principled analysis of the gradient-based approach could give further conditions under which the Fréchet functional can be globally minimized quickly. Second, many of the numerical methods developed here extend naturally to settings with continuous group actions, such as orthogonal actions on point clouds. It would be interesting to investigate alignment in these contexts, along with certification via semidefinite programming. Finally, more work is needed to better understand how orbit space geometry influences the complexity of finding the Fréchet mean.
Acknowledgments. We would like to thank Thomas Weighill for providing the districting data and the code for the visualization used in § 6.5 . DGM was supported in part by NSF grant DMS 2220304 and AFOSR grant FA9550-26-1-B224.
TN was partially supported by NSF grant CIF 2526630. DGM thanks OpenAI for complimentary access to ChatGPT-6 Pro. The authors used ChatGPT to find relevant literature, to help generate the figures, and to give feedback on preliminary versions of this manuscript. All mathematical claims, citations, and computations were checked by the authors, who take full responsibility for the content of this paper.
Appendix A. Fréchet SDP Dual Program
This section is dedicated to the dual problem of the Fréchet SDP (9) . We first detail the derivation of the form used in Lemma 4.2 , then explicitly demonstrate weak and strong duality.
Deriving the Dual
For convenience, we restate the primal problem:
max Y ∈ R n d × n d ⟨ x x T , Y ⟩ s.t. Y ⪰ 0 , Y [ i j ] ∈ Conv ( G ) , 1 ≤ i < j ≤ n , Y [ i i ] = I d , i = 1 , … , n . \begin{aligned}
\max_{Y \in\mathbb{R}^{nd \times nd}}\quad& \langle xx^{\mathsf{T}},Y\rangle\\
\text{s.t.}\quad& Y \succeq0, \\
& Y_{[ij]} \in\operatorname{Conv}(G), \qquad1 \le i < j \le n, \\
& Y_{[ii]} = I_d, \qquad i=1,\ldots,n.
\end{aligned} Y ∈ R n d × n d max s.t. ⟨ x x T , Y ⟩ Y ⪰ 0 , Y [ ij ] ∈ Conv ( G ) , 1 ≤ i < j ≤ n , Y [ ii ] = I d , i = 1 , … , n .
Let λ ℓ i j \lambda_{\ell}^{ij} λ ℓ ij be weights indexed by $1 \le i < j \le na n d $ 1 ≤ ℓ ≤ ∣ G ∣ and \$1 \le\ell\le|G| an d $1 ≤ ℓ ≤ ∣ G ∣ , let E i j E^{ij} E ij be the n × n n \times n n × n elementary matrix with a one in the ( i , j ) (i,j) ( i , j ) th entry, and enumerate G = { g 1 , … , g ∣ G ∣ } G = \{g_1,\ldots,g_{|G|}\} G = { g 1 , … , g ∣ G ∣ } . Define
g ℓ i j : = E i j ⊗ g ℓ + E j i ⊗ g ℓ T . g_{\ell}^{ij} := E^{ij} \otimes g_{\ell} + E^{ji} \otimes g_{\ell}^{\mathsf{T}}. g ℓ ij := E ij ⊗ g ℓ + E j i ⊗ g ℓ T .
Then we can enforce the convex hull constraint explicitly by letting
Y [ i j ] = ∑ ℓ = 1 ∣ G ∣ λ ℓ i j g ℓ Y_{[ij]}=\sum_{\ell=1}^{|G|}\lambda_{\ell}^{ij}g_{\ell} Y [ ij ] = ℓ = 1 ∑ ∣ G ∣ λ ℓ ij g ℓ
for each $1 \le i < j \le n$. Our SDP obtained by these relaxations is then
max Y ∈ R n d × n d ⟨ x x T , Y ⟩ s.t. Y = I n d + ∑ 1 ≤ i < j ≤ n ∑ ℓ = 1 ∣ G ∣ λ ℓ i j g ℓ i j , Y ⪰ 0 , λ ℓ i j ≥ 0 , 1 ≤ i < j ≤ n , 1 ≤ ℓ ≤ ∣ G ∣ , ∑ ℓ = 1 ∣ G ∣ λ ℓ i j = 1 , 1 ≤ i < j ≤ n . \begin{aligned}
\max_{Y\in\mathbb{R}^{nd\times nd}}\quad&\langle xx^{\mathsf T},Y\rangle\\
\text{s.t.}\quad&Y=I_{nd}+\sum_{1\le i<j\le n}\sum_{\ell=1}^{|G|}\lambda_{\ell}^{ij}g_{\ell}^{ij},\\
&Y\succeq0,\\
&\lambda_{\ell}^{ij}\ge0,\qquad1\le i<j\le n,\quad1\le\ell\le|G|,\\
&\sum_{\ell=1}^{|G|}\lambda_{\ell}^{ij}=1,\qquad1\le i<j\le n.
\end{aligned} Y ∈ R n d × n d max s.t. ⟨ x x T , Y ⟩ Y = I n d + 1 ≤ i < j ≤ n ∑ ℓ = 1 ∑ ∣ G ∣ λ ℓ ij g ℓ ij , Y ⪰ 0 , λ ℓ ij ≥ 0 , 1 ≤ i < j ≤ n , 1 ≤ ℓ ≤ ∣ G ∣ , ℓ = 1 ∑ ∣ G ∣ λ ℓ ij = 1 , 1 ≤ i < j ≤ n .
We can now rewrite the objective in terms of the λ ℓ i j \lambda_{\ell}^{ij} λ ℓ ij :
⟨ x x T , Y ⟩ = ⟨ x x T , I n d + ∑ 1 ≤ i < j ≤ n ∑ ℓ = 1 ∣ G ∣ λ ℓ i j g ℓ i j ⟩ = ∑ i = 1 n ∥ x i ∥ 2 + ∑ 1 ≤ i < j ≤ n ∑ ℓ = 1 ∣ G ∣ λ ℓ i j ⟨ x x T , g ℓ i j ⟩ = ∑ i = 1 n ∥ x i ∥ 2 + 2 ∑ 1 ≤ i < j ≤ n ∑ ℓ = 1 ∣ G ∣ λ ℓ i j ⟨ x i , g ℓ x j ⟩ . \begin{aligned}
\langle xx^{\mathsf T},Y\rangle
&=\left\langle xx^{\mathsf T},I_{nd}+\sum_{1\le i<j\le n}\sum_{\ell=1}^{|G|}\lambda_{\ell}^{ij}g_{\ell}^{ij}\right\rangle\\
&=\sum_{i=1}^{n}\lVert x_i\rVert^2+\sum_{1\le i<j\le n}\sum_{\ell=1}^{|G|}\lambda_{\ell}^{ij}\left\langle xx^{\mathsf T},g_{\ell}^{ij}\right\rangle\\
&=\sum_{i=1}^{n}\lVert x_i\rVert^2+2\sum_{1\le i<j\le n}\sum_{\ell=1}^{|G|}\lambda_{\ell}^{ij}\langle x_i,g_{\ell}x_j\rangle.
\end{aligned} ⟨ x x T , Y ⟩ = ⟨ x x T , I n d + 1 ≤ i < j ≤ n ∑ ℓ = 1 ∑ ∣ G ∣ λ ℓ ij g ℓ ij ⟩ = i = 1 ∑ n ∥ x i ∥ 2 + 1 ≤ i < j ≤ n ∑ ℓ = 1 ∑ ∣ G ∣ λ ℓ ij ⟨ x x T , g ℓ ij ⟩ = i = 1 ∑ n ∥ x i ∥ 2 + 2 1 ≤ i < j ≤ n ∑ ℓ = 1 ∑ ∣ G ∣ λ ℓ ij ⟨ x i , g ℓ x j ⟩ .
If we define
c ℓ i j : = ⟨ x i , g ℓ x j ⟩ c_{\ell}^{ij}:=\langle x_i,g_{\ell}x_j\rangle c ℓ ij := ⟨ x i , g ℓ x j ⟩
and let c , λ ∈ R ∣ G ∣ ( n 2 ) c,\lambda\in\mathbb{R}^{|G|\binom{n}{2}} c , λ ∈ R ∣ G ∣ ( 2 n ) be indexed by i , j , ℓ i,j,\ell i , j , ℓ as above, then our primal SDP, after dropping the additive constant ∑ i = 1 n ∥ x i ∥ 2 \sum_{i=1}^{n}\lVert x_i\rVert^2 ∑ i = 1 n ∥ x i ∥ 2 and the constant factor 2, becomes
max λ ≥ 0 ⟨ c , λ ⟩ s.t. ∑ ℓ = 1 ∣ G ∣ λ ℓ i j = 1 , 1 ≤ i < j ≤ n , I n d + ∑ 1 ≤ i < j ≤ n ∑ ℓ = 1 ∣ G ∣ λ ℓ i j g ℓ i j ⪰ 0. (17) \begin{aligned}
\max_{\lambda\ge0}\quad&\langle c,\lambda\rangle\\
\text{s.t.}\quad&\sum_{\ell=1}^{|G|}\lambda_{\ell}^{ij}=1,\qquad1\le i<j\le n,\\
&I_{nd}+\sum_{1\le i<j\le n}\sum_{\ell=1}^{|G|}\lambda_{\ell}^{ij}g_{\ell}^{ij}\succeq0. \tag*{(17)}
\end{aligned} λ ≥ 0 max s.t. ⟨ c , λ ⟩ ℓ = 1 ∑ ∣ G ∣ λ ℓ ij = 1 , 1 ≤ i < j ≤ n , I n d + 1 ≤ i < j ≤ n ∑ ℓ = 1 ∑ ∣ G ∣ λ ℓ ij g ℓ ij ⪰ 0. (17)
From this rewritten primal, we can now write down the dual program. Letting β ∈ R ( n 2 ) \beta\in\mathbb{R}^{\binom{n}{2}} β ∈ R ( 2 n ) and V ∈ R n d × n d V\in\mathbb{R}^{nd\times nd} V ∈ R n d × n d , our dual is
min β , V β T 1 + Tr ( V ) s.t. β i j ≥ c ℓ i j + ⟨ g ℓ i j , V ⟩ , 1 ≤ i < j ≤ n , 1 ≤ ℓ ≤ ∣ G ∣ , V ⪰ 0. (18) \begin{aligned}
\min_{\beta,V}\quad&\beta^{\mathsf T}1+\operatorname{Tr}(V)\\
\text{s.t.}\quad&\beta^{ij}\ge c_{\ell}^{ij}+\langle g_{\ell}^{ij},V\rangle,\qquad1\le i<j\le n,\quad1\le\ell\le|G|,\\
&V\succeq0. \tag*{(18)}
\end{aligned} β , V min s.t. β T 1 + Tr ( V ) β ij ≥ c ℓ ij + ⟨ g ℓ ij , V ⟩ , 1 ≤ i < j ≤ n , 1 ≤ ℓ ≤ ∣ G ∣ , V ⪰ 0. (18)
We next rewrite the dual in a more helpful form. By the sparse structure of g ℓ i j g_{\ell}^{ij} g ℓ ij , we can write
c ℓ i j + ⟨ g ℓ i j , V ⟩ = 1 2 ⟨ x x T + 2 V , g ℓ i j ⟩ . c_{\ell}^{ij}+\langle g_{\ell}^{ij},V\rangle=\frac{1}{2}\langle xx^{\mathsf{T}}+2V,g_{\ell}^{ij}\rangle. c ℓ ij + ⟨ g ℓ ij , V ⟩ = 2 1 ⟨ x x T + 2 V , g ℓ ij ⟩ .
Also notice that the minimal feasible values of β i j \beta^{ij} β ij are attained by
β i j = 1 2 max ℓ ∈ { 1 , … , ∣ G ∣ } ⟨ x x T + 2 V , g ℓ i j ⟩ . \beta^{ij}=\frac{1}{2}\max_{\ell\in\{1,\ldots,|G|\}}\langle xx^{\mathsf{T}}+2V,g_{\ell}^{ij}\rangle. β ij = 2 1 ℓ ∈ { 1 , … , ∣ G ∣ } max ⟨ x x T + 2 V , g ℓ ij ⟩ .
We can therefore rewrite the objective as
β T 1 + Tr ( V ) = Tr ( V ) + 1 2 ∑ 1 ≤ i < j ≤ n max ℓ ∈ { 1 , … , ∣ G ∣ } ⟨ x x T + 2 V , g ℓ i j ⟩ = 1 2 ( Tr ( S ) + ∑ 1 ≤ i < j ≤ n max ℓ ∈ { 1 , … , ∣ G ∣ } ⟨ x x T + S , g ℓ i j ⟩ ) , \begin{aligned}
\beta^{\mathsf{T}}\mathbf{1}+\operatorname{Tr}(V)
&=\operatorname{Tr}(V)+\frac{1}{2}\sum_{1\leq i<j\leq n}\max_{\ell\in\{1,\ldots,|G|\}}\langle xx^{\mathsf{T}}+2V,g_{\ell}^{ij}\rangle\\
&=\frac{1}{2}\left(\operatorname{Tr}(S)+\sum_{1\leq i<j\leq n}\max_{\ell\in\{1,\ldots,|G|\}}\langle xx^{\mathsf{T}}+S,g_{\ell}^{ij}\rangle\right),
\end{aligned} β T 1 + Tr ( V ) = Tr ( V ) + 2 1 1 ≤ i < j ≤ n ∑ ℓ ∈ { 1 , … , ∣ G ∣ } max ⟨ x x T + 2 V , g ℓ ij ⟩ = 2 1 ( Tr ( S ) + 1 ≤ i < j ≤ n ∑ ℓ ∈ { 1 , … , ∣ G ∣ } max ⟨ x x T + S , g ℓ ij ⟩ ) ,
where S : = 2 V ⪰ 0 S:=2V\succeq0 S := 2 V ⪰ 0 . Define W : = x x T + S W:=xx^{\mathsf{T}}+S W := x x T + S , and let
H : = { H ∈ S n d : H [ i i ] = I d , i = 1 , … , n , H [ i j ] ∈ G , 1 ≤ i < j ≤ n } . \mathcal{H}:=\left\{H\in\mathbb{S}^{nd}: \begin{array}{l}
H_{[ii]}=I_d,\quad i=1,\ldots,n,\\
H_{[ij]}\in G,\quad1\leq i<j\leq n
\end{array}\right\}. H := { H ∈ S n d : H [ ii ] = I d , i = 1 , … , n , H [ ij ] ∈ G , 1 ≤ i < j ≤ n } .
For a fixed W W W , the maximum over H ∈ H H\in\mathcal{H} H ∈ H is attained by choosing
H [ i j ] ∈ arg max g ∈ G ⟨ g , W [ i j ] ⟩ H_{[ij]}\in\underset{g\in G}{\operatorname{arg\,max}}\ \langle g,W_{[ij]}\rangle H [ ij ] ∈ g ∈ G arg max ⟨ g , W [ ij ] ⟩
for each 1 ≤ i < j ≤ n 1\leq i<j\leq n 1 ≤ i < j ≤ n , and setting H [ j i ] = H [ i j ] T H_{[ji]}=H_{[ij]}^{\mathsf{T}} H [ j i ] = H [ ij ] T . It follows that
max H ∈ H ⟨ H , W ⟩ = Tr ( W ) + ∑ 1 ≤ i < j ≤ n max ℓ ∈ { 1 , … , ∣ G ∣ } ⟨ W , g ℓ i j ⟩ = ∑ i = 1 n ∥ x i ∥ 2 + Tr ( S ) + ∑ 1 ≤ i < j ≤ n max ℓ ∈ { 1 , … , ∣ G ∣ } ⟨ x x T + S , g ℓ i j ⟩ . \begin{aligned}
\max_{H\in\mathcal{H}}\langle H,W\rangle
&=\operatorname{Tr}(W)+\sum_{1\leq i<j\leq n}\max_{\ell\in\{1,\ldots,|G|\}}\langle W,g_{\ell}^{ij}\rangle\\
&=\sum_{i=1}^{n}\|x_i\|^2+\operatorname{Tr}(S)+\sum_{1\leq i<j\leq n}\max_{\ell\in\{1,\ldots,|G|\}}\langle xx^{\mathsf{T}}+S,g_{\ell}^{ij}\rangle.
\end{aligned} H ∈ H max ⟨ H , W ⟩ = Tr ( W ) + 1 ≤ i < j ≤ n ∑ ℓ ∈ { 1 , … , ∣ G ∣ } max ⟨ W , g ℓ ij ⟩ = i = 1 ∑ n ∥ x i ∥ 2 + Tr ( S ) + 1 ≤ i < j ≤ n ∑ ℓ ∈ { 1 , … , ∣ G ∣ } max ⟨ x x T + S , g ℓ ij ⟩ .
Hence,
β T 1 + Tr ( V ) = 1 2 ( max H ∈ H ⟨ H , W ⟩ − ∑ i = 1 n ∥ x i ∥ 2 ) . \beta^{\mathsf{T}}\mathbf{1}+\operatorname{Tr}(V)=\frac{1}{2}\left(\max_{H\in\mathcal{H}}\langle H,W\rangle-\sum_{i=1}^{n}\|x_i\|^2\right). β T 1 + Tr ( V ) = 2 1 ( H ∈ H max ⟨ H , W ⟩ − i = 1 ∑ n ∥ x i ∥ 2 ) .
Restoring the additive constant and factor 2 that were removed in passing from the original primal objective to (A.1), we obtain the equivalent dual formulation
min W ⪰ x x T max H ∈ H ⟨ H , W ⟩ . \min_{W\succeq xx^{\mathsf{T}}}\ \max_{H\in\mathcal{H}}\langle H,W\rangle. W ⪰ x x T min H ∈ H max ⟨ H , W ⟩ .
Weak and Strong Duality
Here we demonstrate weak duality between the Fréchet SDP and its dual explicitly. Let Y Y Y be primal feasible and let W ⪰ x x T W\succeq xx^{\mathsf{T}} W ⪰ x x T be dual feasible. Since Y ⪰ 0 Y\succeq0 Y ⪰ 0 and W − x x T ⪰ 0 W-xx^{\mathsf{T}}\succeq0 W − x x T ⪰ 0 , we have
⟨ Y , W − x x T ⟩ ≥ 0. \langle Y,W-xx^{\mathsf{T}}\rangle\geq0. ⟨ Y , W − x x T ⟩ ≥ 0.
It follows that
⟨ Y , x x T ⟩ ≤ ⟨ Y , W ⟩ = ∑ i = 1 n ⟨ I d , W [ i i ] ⟩ + 2 ∑ 1 ≤ i < j ≤ n ⟨ Y [ i j ] , W [ i j ] ⟩ ≤ ∑ i = 1 n ⟨ I d , W [ i i ] ⟩ + 2 ∑ 1 ≤ i < j ≤ n max g ∈ G ⟨ g , W [ i j ] ⟩ = max H ∈ H ⟨ H , W ⟩ . \begin{aligned}
\langle Y,xx^{\mathsf T}\rangle&\le\langle Y,W\rangle\\
&= \sum_{i=1}^{n}\langle I_d,W_{[ii]}\rangle+ 2\sum_{1\le i<j\le n}\langle Y_{[ij]},W_{[ij]}\rangle\\
&\le\sum_{i=1}^{n}\langle I_d,W_{[ii]}\rangle+ 2\sum_{1\le i<j\le n}\max_{g\in G}\langle g,W_{[ij]}\rangle\\
&= \max_{H\in\mathcal{H}}\langle H,W\rangle.
\end{aligned} ⟨ Y , x x T ⟩ ≤ ⟨ Y , W ⟩ = i = 1 ∑ n ⟨ I d , W [ ii ] ⟩ + 2 1 ≤ i < j ≤ n ∑ ⟨ Y [ ij ] , W [ ij ] ⟩ ≤ i = 1 ∑ n ⟨ I d , W [ ii ] ⟩ + 2 1 ≤ i < j ≤ n ∑ g ∈ G max ⟨ g , W [ ij ] ⟩ = H ∈ H max ⟨ H , W ⟩ .
The second inequality follows from Y [ i j ] ∈ Conv G Y_{[ij]}\in\operatorname{Conv}G Y [ ij ] ∈ Conv G , and the last line follows from the definition of H \mathcal{H} H .
The SDP exhibits strong duality, following from the dual form of Slater’s condition. Consider the form of the dual in (A.2). Taking V = I n d ≻ 0 V=I_{nd}\succ0 V = I n d ≻ 0 will give an interior feasible point. For i < j i<j i < j , the nonzero blocks of g ℓ i j g_{\ell}^{ij} g ℓ ij are off-diagonal, whereas the nonzero blocks of I n d I_{nd} I n d are diagonal. Therefore
⟨ g ℓ i j , I n d ⟩ = 0. \left\langle g_{\ell}^{ij},I_{nd}\right\rangle=0. ⟨ g ℓ ij , I n d ⟩ = 0.
We may now choose
β i j > max ℓ ∈ { 1 , … , ∣ G ∣ } c ℓ i j \beta^{ij}>\max_{\ell\in\{1,\ldots,|G|\}}c_{\ell}^{ij} β ij > ℓ ∈ { 1 , … , ∣ G ∣ } max c ℓ ij
for every 1 ≤ i < j ≤ n 1\le i<j\le n 1 ≤ i < j ≤ n . This gives a strictly feasible dual point. Since the primal is feasible and has a finite optimal value, strong duality holds for every finite G G G .