In this work we present the first initialization methods equipped with explicit performance guarantees adapted to the pose-graph simultaneous localization and mapping (SLAM) and rotation averaging (RA) problems. SLAM and rotation averaging are typically formalized as large-scale nonconvex point estimation problems, with many bad local minima that can entrap the smooth optimization methods typically applied to solve them; the performance of standard SLAM and RA algorithms thus crucially depends upon the quality of the estimates used to initialize this local search. While many initialization methods for SLAM and RA have appeared in the literature, these are typically obtained as purely heuristic approximations, making it difficult to determine whether (or under what circumstances) these techniques can be reliably deployed. In contrast, in this work we study the problem of initialization through the lens of spectral relaxation. Specifically, we derive a simple spectral relaxation of SLAM and RA, the form of which enables us to exploit classical linear-algebraic techniques (eigenvector perturbation bounds) to control the distance from our spectral estimate to both the (unknown) ground-truth and the global minimizer of the estimation problem as a function of measurement noise. Our results reveal the critical role that spectral graph-theoretic properties of the measurement network play in controlling estimation accuracy; moreover, as a by-product of our analysis we obtain new bounds on the estimation error for the maximum likelihood estimators in SLAM and RA, which are likely to be of independent interest. Finally, we show experimentally that our spectral estimator is very effective in practice, producing initializations of comparable or superior quality at lower computational cost compared to existing state-of-the-art techniques.
翻译:在这项工作中,我们展示了第一批初始化方法,这些方法配备了适应表面同步本地化和绘图(SLAM)和平均轮换(RA)问题的明确性保证。 SLAM和平均轮换平均率通常被正式确定为大规模非康维克斯点估算问题,而许多糟糕的本地迷你,可以套用平坦优化方法来解决这些问题;因此,标准的SLAM和RA算法的性能,关键地取决于启动本地搜索所使用的估算的质量。虽然文献中出现了许多用于SLAM和RA的初始性能保障,但这些方法通常都是纯粹超常性近似法,因此难以确定这些技术是否(或者在什么情况下)可靠地部署。相比之下,我们通过光谱放松的镜头研究初始化问题;具体地平线性SLAM和RA算法的性能,使我们能够利用经典的线性肿瘤计算技术(低基因指数)来控制我们光谱估计的距离,而我们最初(已知的)地平流率近似近似,因此很难确定这些技术是否可靠。