Fréchet means generalize averages to metric spaces, but in orbit spaces—where points are identified under a group action—computing them is NP-hard. The authors tackle this by borrowing techniques from group synchronization, a framework for estimating group elements from noisy pairwise measurements. They introduce spectral and semidefinite relaxations that make the problem tractable while still offering guarantees.
Their key contribution is a certification mechanism. Pairwise alignment, a common heuristic, can certify global optimality in some cases, but it fails under high noise. The authors develop a semidefinite certificate that extends beyond this condition, and they prove it succeeds for Gaussian data modulo sign in a regime where alignment provably fails.
Numerical experiments demonstrate the method's practical value in summarizing ensembles of districting plans and clustering time series. These results suggest that the approach could be useful in applications where data naturally live in orbit spaces, such as shape analysis or synchronization problems.