论文标题
快速，准确和记忆有效的部分置换同步
Fast, Accurate and Memory-Efficient Partial Permutation Synchronization
论文作者
论文摘要
通常用于多对象匹配的先前部分置换同步（PPS）算法通常涉及计算密集型和存储器的矩阵操作。这些操作对于大型结构数据集变得棘手。对于纯置换同步，最近的循环边缘消息传递（CEMP）框架提出了一种记忆效率和快速解决方案。在这里，我们克服了CEMP对紧凑组的限制，并提出了改进的算法CEMP-Partial，以估计观察到的部分排列的损坏水平。它允许我们随后在不需要光谱初始化的情况下实现非凸的加权投影能力方法。由此产生的新PPS算法，MatchFame（快速，准确和存储效率的匹配）仅涉及稀疏的矩阵操作，因此与以前的PPS算法相比，时间和空间复杂性较低。我们证明，在对抗性腐败的情况下，尽管没有附加噪声，并且在某些假设的情况下，CEMP-Partial能够准确地对损坏和清洁的部分排列进行分类。我们证明了我们方法在合成和真实数据集上的最先进的准确性，速度和记忆效率。
Previous partial permutation synchronization (PPS) algorithms, which are commonly used for multi-object matching, often involve computation-intensive and memory-demanding matrix operations. These operations become intractable for large scale structure-from-motion datasets. For pure permutation synchronization, the recent Cycle-Edge Message Passing (CEMP) framework suggests a memory-efficient and fast solution. Here we overcome the restriction of CEMP to compact groups and propose an improved algorithm, CEMP-Partial, for estimating the corruption levels of the observed partial permutations. It allows us to subsequently implement a nonconvex weighted projected power method without the need of spectral initialization. The resulting new PPS algorithm, MatchFAME (Fast, Accurate and Memory-Efficient Matching), only involves sparse matrix operations, and thus enjoys lower time and space complexities in comparison to previous PPS algorithms. We prove that under adversarial corruption, though without additive noise and with certain assumptions, CEMP-Partial is able to exactly classify corrupted and clean partial permutations. We demonstrate the state-of-the-art accuracy, speed and memory efficiency of our method on both synthetic and real datasets.
