Near-optimal performance bounds for orthogonal and permutation group synchronization via spectral methods

• Published in: Applied and computational harmonic analysis 2022-09, Vol.60, p.20-52
• Main Author: Ling, Shuyang
• Format: Article
• Language: English
• Subjects: Eigenvector perturbation; Object matching; Orthogonal/permutation group synchronization; Signal processing; Spectral methods
• ISSN: 1063-5203; 1096-603X
• DOI: 10.1016/j.acha.2022.02.003

Group synchronization asks to recover group elements from their pairwise measurements. It has found numerous applications across various scientific disciplines. In this work, we focus on orthogonal and permutation group synchronization which are widely used in computer vision such as object matching and structure from motion. Among many available approaches, the spectral methods have enjoyed great popularity due to their efficiency and convenience. We will study the performance guarantees of the spectral methods in solving these two synchronization problems by investigating how well the computed eigenvectors approximate each group element individually. We establish our theory by applying the recent popular leave-one-out technique and derive a block-wise performance bound for the recovery of each group element via eigenvectors. In particular, for orthogonal group synchronization, we obtain a near-optimal performance bound for the group recovery in presence of additive Gaussian noise. For permutation group synchronization under random corruption, we show that the widely-used two-step procedure (spectral method plus rounding) can recover all the group elements exactly if the SNR (signal-to-noise ratio) is close to the information theoretical limit. Our numerical experiments confirm our theory and indicate a sharp phase transition for the exact group recovery.