Code supplement for "The Noise-Sensitivity Phase Transition in Spectral Group Synchronization Over Compact Groups"
- In Group Synchronization, one attempts to find a collection of unknown group elements from noisy measurements of their pairwise differences. Several important problems in vision and data analysis reduce to group synchronization over various compact groups. Spectral Group Synchronization is a commonly used, robust algorithm for solving group synchronization problems, which relies on diagonalization of a block matrix whose blocks are matrix representations of the measured pairwise differences. Assuming uniformly distributed measurement errors, we present a rigorous analysis of the accuracy and noise sensitivity of spectral group synchronization algorithms over any compact group, up to the rounding error. We identify a Baik-Ben Arous-P\'ech\'e type phase transition in the noise level, beyond which spectral group synchronization necessarily fails. Below the phase transition, spectral group synchronization succeeds in recovering the unknown group elements, but its performance deteriorates with the noise level. We provide asymptotically exact formulas for the accuracy of spectral group synchronization below the phase transition, up to the rounding error. We also provide a consistent risk estimate, allowing practitioners to estimate the method's accuracy from available measurements.
|Type of resource
|random matrix theory
|Romanov, Elad, and Gavish, Matan. (2019). The Noise-Sensitivity Phase Transition in Spectral Group Synchronization Over Compact Groups. Applied and Computational Harmonic Analysis. https://doi.org/10.1016/j.acha.2019.05.002
- Use and reproduction
- User agrees that, where applicable, content will not be used to identify or to otherwise infringe the privacy or confidentiality rights of individuals. Content distributed via the Stanford Digital Repository may be subject to additional license and use restrictions applied by the depositor.
- This work is licensed under a Creative Commons Attribution 3.0 Unported license (CC BY).
- Preferred Citation
- Romanov, Elad. (2019). Code supplement for "The Noise-Sensitivity Phase Transition in Spectral Group Synchronization Over Compact Groups". Stanford Digital Repository. https://purl.stanford.edu/fv335cr7803
Stanford Research DataView other items in this collection in SearchWorks
Also listed in
Loading usage metrics...