Recovery Theory for Projected Power Iterations in Permutation Synchronization
Abstract
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 11⊤. Under the uniform model, a reference-block spectral initializer has aligned block error Oℙ(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.
Related
- Palm Disintegration and Height-Profile Recovery for Projected Hardy--Szegő Zeros
- Singleton-Optimal Rank-Metric CSS Codes : Equality Structure and Exact Projected-Recovery Radii
- Projected Yang-Mills Theory and the MacDowell-Mansouri Analogy
- Visitation measures for non-linear iterations with random perturbations
- Component-wise accurate fixed point iterations for computing the square root of a singular M-matrix
BibTeX
@misc{huroyan2026recovery,
title = {{Recovery Theory for Projected Power Iterations in Permutation Synchronization}},
author = {Vahan Huroyan and Gilad Lerman},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.09502},
eprint = {2609.09502},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.09502},
}
RIS
TY - UNPB
TI - Recovery Theory for Projected Power Iterations in Permutation Synchronization
AU - Vahan Huroyan
AU - Gilad Lerman
PY - 2026
DA - 2026/09/08
PB - arXiv
DO - 10.48550/arxiv.2609.09502
UR - https://arxiv.org/abs/2609.09502
AB - 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π_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≥ C_0log n and m=o(npπ_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−ε. The contraction factor is O(m/(npπ_0^2)) and the error floor is O(e^−cnpπ_0+e^−cnpπ_0^2+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 11^⊤. Under the uniform model, a reference-block spectral initializer has aligned block error O_ℙ(m/(npπ_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.
ER -