pipette
ESEspañol

Certifiably Correct Fr\'echet Means in Orbit Spaaces

Dustin G. Mixon, Tom Needham, Nathan Willey

Preprint

In the authors' words

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

Main resultThe abstract does not state a limitation.

Appeared: Tuesday, October 20. arXiv. Preprint, not yet peer-reviewed.