# Recovery Theory for Projected Power Iterations in Permutation Synchronization

arXiv: https://arxiv.org/abs/2609.09502 · HTML: https://mlsanity.com/paper/2609.09502/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 31 references that are in the map.
- First posted on arXiv 8 Sep 2026.

## Builds on (most cited first, 17 of 17)

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Consistency of spectral clustering in stochastic block models](https://mlsanity.com/paper/1312.2050/) (2013)
- [Multi-Image Matching via Fast Alternating Minimization](https://mlsanity.com/paper/1505.04845/) (2015)
- [Near-optimal bounds for phase synchronization](https://mlsanity.com/paper/1703.06605/) (2017)
- [Nonconvex phase synchronization](https://mlsanity.com/paper/1601.06114/) (2016)
- [Higher-order Projected Power Iterations for Scalable Multi-Matching](https://mlsanity.com/paper/1811.10541/) (2018)
- [Iterative Algorithm for Discrete Structure Recovery](https://mlsanity.com/paper/1911.01018/) (2019)
- [Robust Group Synchronization via Cycle-Edge Message Passing](https://mlsanity.com/paper/1912.11347/) (2019)
- [Near-Optimal Performance Bounds for Orthogonal and Permutation Group Synchronization via Spectral Methods](https://mlsanity.com/paper/2008.05341/) (2020)
- [Near-Optimal Joint Object Matching via Convex Relaxation](https://mlsanity.com/paper/1402.1473/) (2014)
- [Synchronisation of Partial Multi-Matchings via Non-negative Factorisations](https://mlsanity.com/paper/1803.06320/) (2018)
- [A Unified Approach to Synchronization Problems over Subgroups of the Orthogonal Group](https://mlsanity.com/paper/2009.07514/) (2020)
- [Robust Multi-object Matching via Iterative Reweighting of the Graph Connection Laplacian](https://mlsanity.com/paper/2006.06658/) (2020)
- [Fast, Accurate and Memory-Efficient Partial Permutation Synchronization](https://mlsanity.com/paper/2203.16505/) (2022)
- [Scalable Cluster-Consistency Statistics for Robust Multi-Object Matching](https://mlsanity.com/paper/2201.04797/) (2022)
- [Initialization and Coordinate Optimization for Multi-way Matching](https://mlsanity.com/paper/1611.00838/) (2016)
- [A Novel and Optimal Spectral Method for Permutation Synchronization](https://mlsanity.com/paper/2303.12051/) (2023)

## Abstract (arXiv)

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.