We propose fast and communication-efficient distributed algorithms for rotation averaging and translation recovery problems that arise from multi-robot simultaneous localization and mapping (SLAM) and distributed camera network localization applications. Our methods are based on theoretical relations between the Hessians of the underlying Riemannian optimization problems and the Laplacians of suitably weighted graphs. We leverage these results to design a distributed solver that performs approximate second-order optimization by solving a Laplacian system at each iteration. Crucially, our algorithms permit robots to employ spectral sparsification to sparsify intermediate dense matrices before communication, and hence provide a mechanism to trade off accuracy with communication efficiency with provable guarantees. We perform rigorous theoretical analysis of our methods and prove that they enjoy (local) linear rate of convergence on the problems of interest. Numerical experiments show that the proposed methods converge to high-precision solutions in a few iterations and that they are significantly more communication-efficient compared to baseline second-order solvers.
翻译:我们建议采用快速和通信高效分布式算法来进行平均轮换和翻译的回收问题,这些问题产生于多机器人同时进行本地化和绘图(SLAM)以及分布式摄影机网络本地化应用。我们的方法基于赖曼尼亚优化问题背后的赫西人与适当加权图表的拉普拉西人之间的理论关系。我们利用这些算法设计一个分布式求解器,通过在每次迭代中解决一个拉普拉西人系统来进行大约二级优化。关键的是,我们的算法允许机器人在通信前使用光谱透析法来对中间稠密的基质进行加固,从而提供一个机制,用可变保证的保证来交换通信效率的准确性与通信效率。我们对方法进行严格的理论分析,并证明他们享有(当地)在利息问题上的线性趋同率。数字实验表明,拟议的方法在几个迭代中与高精度解决方案相融合,而且它们与基线二阶解器相比具有显著的通信效率。