Recovery Theory for Projected Power Iterations in Permutation Synchronization
Vahan Huroyan, Gilad Lerman
原文摘要
We study the projected power method for permutation synchronization: recovering $n$ unknown permutations of $m$ objects from pairwise relative permutations, observed independently with probability $p$ and independently corrupted by uniform permutations with probability $1-π_0$. Our main theorem establishes uniform one-step contraction for all estimates with optimally aligned block-error fraction at most $1/2-ε$, for fixed $ε>0$, including measurement-dependent estimates. When $np\ge C_0\log(n)$ and $m=o(npπ_0^2)$, one update contracts the error by a factor $O(m/(npπ_0^2))$, up to a floor of $O(e^{-c\min\{m\,npπ_0^2,\,npπ_0\}} + \log(n) / n)$. Thus, every initialization in this majority basin achieves $o(1)$ error after one update and maintains it uniformly over subsequent iterations. A reference-block spectral initializer enters the basin with probability $1-o(1)$, yielding end-to-end almost-exact recovery. If additionally $\min\{m\,npπ_0^2,\,npπ_0\} \ge C\log(n)$ for sufficiently large $C$, the method achieves exact recovery in finitely many iterations. We also establish prescribed-block recovery under weaker conditions for measurement-independent estimates and extend the guarantees to independent permutation-valued corruptions with uniform mean and to partial permutations with common visible support.
stat.ML · cs.IT · math.OC