Optimal Orthogonal Group Synchronization and Rotation Group Synchronization
This provides an optimal solution for synchronization problems in fields like robotics and computer vision, though it is incremental as it builds on existing spectral methods.
The paper tackles the problem of estimating orthogonal and rotation matrices from noisy pairwise observations, showing that their iterative polar decomposition algorithm achieves an error of (1+o(1))σ²d(d-1)/(2np) when initialized spectrally, with a matching minimax lower bound proving optimality.
We study the statistical estimation problem of orthogonal group synchronization and rotation group synchronization. The model is $Y_{ij} = Z_i^* Z_j^{*T} + σW_{ij}\in\mathbb{R}^{d\times d}$ where $W_{ij}$ is a Gaussian random matrix and $Z_i^*$ is either an orthogonal matrix or a rotation matrix, and each $Y_{ij}$ is observed independently with probability $p$. We analyze an iterative polar decomposition algorithm for the estimation of $Z^*$ and show it has an error of $(1+o(1))\frac{σ^2 d(d-1)}{2np}$ when initialized by spectral methods. A matching minimax lower bound is further established which leads to the optimality of the proposed algorithm as it achieves the exact minimax risk.