Optimal orthogonal group synchronization and rotation group synchronization
Authors:
- 6 August 2022
- journal article
- research article
- Published by Oxford University Press (OUP) in Information and Inference: A Journal of the IMA
- Vol. 12 (2) , 591-632
Abstract
We study the statistical estimation problem of orthogonal group synchronization and rotation group synchronization. The model is $Y_{ij} = Z_i^* Z_j^{*T} + \sigma 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{\sigma ^2 d(d-1)}{2np}$ when initialized by spectral methods. A matching minimax lower bound is further established that leads to the optimality of the proposed algorithm as it achieves the exact minimax risk.
Keywords
All Related Versions
Funding Information
- National Science Foundation (DMS-1847590, CCF-1934931, DMS-2112988)
This publication has 25 references indexed in Scilit:
- Exact and stable recovery of rotations for robust synchronizationInformation and Inference: A Journal of the IMA, 2013
- Cramer-Rao bounds for synchronization of rotationsInformation and Inference: A Journal of the IMA, 2013
- Sensor network localization by eigenvector synchronization over the euclidean groupACM Transactions on Sensor Networks, 2012
- Viewing Direction Estimation in Cryo-EM Using SynchronizationSIAM Journal on Imaging Sciences, 2012
- Three-Dimensional Structure Determination from Common Lines in Cryo-EM by Eigenvectors and Semidefinite ProgrammingSIAM Journal on Imaging Sciences, 2011
- Angular synchronization by eigenvectors and semidefinite programmingApplied and Computational Harmonic Analysis, 2011
- Perturbation Bounds for Determinants and Characteristic PolynomialsSIAM Journal on Matrix Analysis and Applications, 2008
- Applications of the van Trees Inequality: A Bayesian Cramér-Rao BoundBernoulli, 1995
- New Perturbation Bounds for the Unitary Polar FactorSIAM Journal on Matrix Analysis and Applications, 1995
- A discussion of the solution for the best rotation to relate two sets of vectorsActa Crystallographica Section A, 1978