2019/10/12 by Mahroo Bahreinian, Roberto Tron, Bahreinian, Mahroo +1
Computer Science · Decision Sciences · #Advanced Statistical Process Monitoring #Anomaly Detection Techniques and Applications #Computation (stat.CO) #FOS: Computer and information sciences #Target Tracking and Data Fusion in Sensor Networks
paper · pdf · doi:10.48550/arxiv.1910.05509
openalex publication_date 2019/10/12 · openalex created_date 2020/07/16 · openalex updated_date 2026/07/28
The problem of localizing a set of nodes from relative pairwise measurements\nis at the core of many applications such as Structure from Motion (SfM), sensor\nnetworks, and Simultaneous Localization And Mapping (SLAM). In practical\nsituations, the accuracy of the relative measurements is marred by noise and\noutliers; hence, we have the problem of quantifying how much we should trust\nthe solution returned by some given localization solver. In this work, we focus\non the question of whether an L1-norm robust optimization formulation can\nrecover a solution that is identical to the ground truth, under the scenario of\ntranslation-only measurements corrupted exclusively by outliers and no noise;\nwe call this concept verifiability. On the theoretical side, we prove that the\nverifiability of a problem depends only on the topology of the graph of\nmeasurements, the edge support of the outliers, and their signs, while it is\nindependent of ground truth locations of the nodes, and of any positive scaling\nof the outliers. On the computational side, we present a novel approach based\non the dual simplex algorithm that can check the verifiability of a problem,\ncompletely characterize the space of equivalent solutions if they exist, and\nidentify subgraphs that are verifiable. As an application of our theory, we\nprovide a procedure to compute a priori probability of recovering a solution\ncongruent or equivalent to the ground truth given a measurement graph and the\nprobabilities of each edge containing an outlier.\n