{"id":"arxiv/2609.09502","url":"https://arxiv.org/abs/2609.09502","tags":["stat.ML","cs.IT","math.OC"],"score":0,"title":"Recovery Theory for Projected Power Iterations in Permutation Synchronization","domain":"stat.ML","source":"arxiv","authors":["Vahan Huroyan","Gilad Lerman"],"reviews":0,"subject":"stat.ML","summary":"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…","category":"research","comments":0,"disputed":false,"division":"stat","mentions":0,"discussed":0,"published":"2026-09-08","reactions":{}}