Projected power method achieves near exact permutation synchronization recovery
Recovery Theory for Projected Power Iterations in Permutation Synchronization
Information Theory
Summary
This paper studies how to accurately match multiple scrambled sets of items despite errors, using a mathematical approach called the projected power method (PPM). The authors show that, with enough observations and some initial accuracy, PPM can quickly improve guesses and recover the correct item arrangements nearly perfectly. Their results apply even when the data has random noise and when some items are missing or partially matched. They also provide guarantees on how fast and reliably the method converges to the right solution.
What this means in practice
- •For computer vision engineers: Improve multi-object matching algorithms in 3D reconstruction by applying near-exact synchronization of partial object correspondences despite noisy data.
- •For robotics developers: Enhance robot mapping and localization systems by reliably aligning multiple sensor views through robust permutation synchronization methods.
A theory result. No direct application yet.
Authors
Vahan Huroyan, Gilad Lerman
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π_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π_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} \mathbf{1}\mathbf{1}^{\top}\). Under the uniform model, a reference-block spectral initializer has aligned block error \(O_{\mathbb P}(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.