Exact simultaneous recovery of locations and structure from known orientations and corrupted point correspondences

Abstract

Let t_1,,t_n_l R^d and p_1,,p_n_s R^d and consider the bipartite location recovery problem: given a subset of pairwise direction observations \(t_i - p_j) / \|t_i - p_j\|_2\_i,j [n_l] [n_s], where a constant fraction of these observations are arbitrarily corrupted, find _i\_i [n_ll] and _j\_j [n_s] up to a global translation and scale. We study the recently introduced ShapeFit algorithm as a method for solving this bipartite location recovery problem. In this case, ShapeFit consists of a simple convex program over d(n_l + n_s) real variables. We prove that this program recovers a set of n_l+n_s i.i.d. Gaussian locations exactly and with high probability if the observations are given by a bipartite Erdos-R\'enyi graph, d is large enough, and provided that at most a constant fraction of observations involving any particular location are adversarially corrupted. This recovery theorem is based on a set of deterministic conditions that we prove are sufficient for exact recovery. Finally, we propose a modified pipeline for the Structure for Motion problem, based on this bipartite location recovery problem.

Tasks

Reproductions