A Computational Theory of Robust Localization Verifiability in the Presence of Pure Outlier Measurements
A Computational Theory of Robust Localization Verifiability in the Presence of Pure Outlier Measurements
复制标题
DOI：
10.1109/cdc40024.2019.9029819
复制
发表时间：
2019-10
期刊：
影响因子：
--
通讯作者：
Mahroo Bahreinian;Roberto Tron
中科院分区：
文献类型：
--
作者：
Mahroo Bahreinian;Roberto Tron
来自相对成对测量的一组节点的问题是许多应用程序的核心，例如运动（SFM），传感器网络和同时定位和映射（SLAM）。由于噪声和离群值，我们有一个量化的问题，我们应该相信一些给定的本地化解决方案的解决方案。关注ℓ1-核心强大的优化公式是否可以恢复与地面真理相同的解决方案，在仅翻译的测量方面，仅由异常值损坏，而我们称之为噪声一方，我们证明问题的可验证性仅取决于测量图的拓扑，离群值的边缘支撑及其符号，而它独立于节点的地面真相位置和在计算方面的任何积极缩放率。作为我们理论的应用，我们提供了一个程序，以恢复与地面真相相等的解决方案的先验概率包含异常值。
The problem of localizing a set of nodes from relative pairwise measurements is at the core of many applications such as Structure from Motion (SfM), sensor networks, and Simultaneous Localization And Mapping (SLAM). In practical situations, the accuracy of the relative measurements is marred by noise and outliers; hence, we have the problem of quantifying how much we should trust the solution returned by some given localization solver. In this work, we focus on the question of whether an ℓ1-norm robust optimization formulation can recover a solution that is identical to the ground truth, under the scenario of translation-only measurements corrupted exclusively by outliers and no noise; we call this concept verifiability. On the theoretical side, we prove that the verifiability of a problem depends only on the topology of the graph of measurements, the edge support of the outliers, and their signs, while it is independent of ground truth locations of the nodes, and of any positive scaling of the outliers. On the computational side, we present a novel approach based on the dual simplex algorithm that can check the verifiability of a problem, completely characterize the space of equivalent solutions if they exist, and identify subgraphs that are verifiable. As an application of our theory, we provide a procedure to compute a priori probability of recovering a solution congruent or equivalent to the ground truth given a measurement graph and the probabilities of each edge containing an outlier.