arXiv preprint ·
Recovery Theory for Projected Power Iterations in Permutation Synchronization
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Machine Learning (Statistics)
Non-Coherent Over-the-Air Federated Learning: Protocol, Convergence, and Device Scheduling
Frame-Coded Legged Locomotion over Noisy Terrain
Non-Adaptive 1-Bit Mean Estimation: Minimax Rates and the Sample-Interval Tradeoff
Optimal Low-Rank Quantum State Tomography with Bounded-Sample Joint Measurements
A Note on Scaling in Randomly Rotated Quantization and Its Connection to the CDEF +1 Pythagorean Relation
Get the few papers worth your time in Machine Learning (Statistics) every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.