Fréchet means in orbit spaces arise when data are considered up to symmetry, such as summarizing ensembles of districting plans or clustering time series. Computing these means exactly is NP-hard in general, so tractable approximations are needed.

The authors draw on group synchronization to develop spectral and semidefinite relaxations. They show that pairwise alignment can certify global optimality, and they introduce a semidefinite certificate that extends beyond this condition, providing a stronger guarantee.

For Gaussian data modulo sign, they prove that the certificate succeeds in a high-noise regime where pairwise alignment fails. Numerical experiments evaluate the methods on summarizing districting plans and clustering time series, demonstrating practical applicability.