Recovery Theory for Projected Power Iterations in Permutation Synchronization

We study the projected power method (PPM) for synchronizing $n$ unknown permutations of $m$ objects under a possibly sparse uniform corruption model. Each pair is observed with probability $p$, and an observed measurement is uncorrupted with probability ${\pi }_0$ and is otherwise an independent uniform permutation. Under $\log m=o(np{\pi }_0^2)$, we prove exact one-step recovery (with high probability) of each prescribed block for an independent estimate with a fixed positive majority of correct blocks. When $np\ge C_0\log n$ and $m=o(np{\pi }_0^2)$, we prove that one high-probability event yields a block-error contraction simultaneously for every estimate whose optimally aligned error is at most $0.5-\epsilon$. The contraction factor is $O(m\mathrm{/}(np{\pi }_0^2))$ and the error floor is $O(e^{-cnp{\pi }_0}+e^{-cnp{\pi }_0^2}+\log n\mathrm{/}n)$. Consequently, one update maps every possibly data-dependent estimate in this basin to vanishing block error, and all subsequent iterates remain almost exact uniformly over the iteration index. The one-step and trajectory results extend to independent, non-identically distributed, permutation-valued corruptions with mean $m^{-1}{\mathbf{11}}^{\mathrm{\top }}$. Under the uniform model, a reference-block spectral initializer has aligned block error $O_{\mathbb{P}}(m\mathrm{/}(np{\pi }_0^2))$, yielding an end-to-end almost-exact recovery guarantee. Under a stronger all-block signal condition, PPM reaches exact recovery after finitely many iterations. The theory transfers exactly to partial permutations with common support; for varying supports, we establish deterministic and probabilistic co-visibility margins.