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 (π0) and is otherwise an independent uniform permutation. Under (log m=o(npπ02)), 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≥ C0log n) and (m=o(npπ02)), 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-ε). The contraction factor is (O(m/(npπ02))) and the error floor is (O(e-cnpπ0+e-cnpπ02+log n/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 11top). Under the uniform model, a reference-block spectral initializer has aligned block error (Omathbb P(m/(npπ02))), 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.