📖 AI 总结

本文研究置换同步问题中投影幂方法（PPM）的恢复理论，考虑n个未知置换对m个对象进行同步，测量模型允许稀疏且均匀的随机损坏：每对观测以概率p出现，观测值以概率π₀保持正确，否则为独立均匀置换。作者在log m = o(npπ₀²)条件下证明了单步精确恢复，即对具有固定正多数正确块的独立估计，每个指定块可高概率精确恢复；在np ≥ C₀ log n且m = o(npπ₀²)时，证明存在一个高概率事件使所有最优对齐误差不超过0.5−ε的估计同时发生块误差收缩，收缩因子为O(m/(npπ₀²))，误差下界为O(e^{−cnpπ₀}+e^{−cnpπ₀²}+log n/n)。由此，一次更新即可将该盆地内任意估计的块误差降至消失，后续迭代保持几乎精确。结果可推广至独立非同分布的置换值损坏，并给出参考块谱初始化器的端到端保证；在更强信号条件下PPM可有限步达到精确恢复。理论还可迁移至具有公共支撑的部分置换情形，并为变化支撑建立了共可见性边界。

🔑 关键词速览