Code supplement for "The Noise-Sensitivity Phase Transition in Spectral Group Synchronization Over Compact Groups"

<a href="https://embed.stanford.edu/iframe/?url=https%3A%2F%2Fpurl.stanford.edu%2Ffv335cr7803" class="su-underline">Show Content</a>

Abstract/Contents

Abstract: 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	software, multimedia
Date created	March 2018

Author	Romanov, Elad

Subject	group synchronization
Subject	random matrix theory

Related Publication	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
Related item	Title arxiv preprint
Location	https://purl.stanford.edu/fv335cr7803

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.
License: 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 Data

Loading usage metrics...