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

DOI10.1007/S00454-017-9892-9MaRDI QIDQ1704899zbMATH OpenOpenAlexFDO

Authors Choongbum Lee, Vladislav Voroninski, Paul E. Hand

Publication date 13 March 2018

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1509.05064

convex programming corruption robust recovery structure from motion

Combinatorial probability (60C05) Combinatorics in computer science (68R05) Convex programming (90C25) Theory of error-correcting codes and error-detecting codes (94B99)

Abstract: Let

t_{1}, l d o t s, t_{n_{l}} i n m a t h b b R^{d}

and

p_{1}, l d o t s, p_{n_{s}} i n m a t h b b 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 i n [n_{l}] i m e s [n_{s}]}

, where a constant fraction of these observations are arbitrarily corrupted, find

{t_{i}}_{i i n [n_{l} l]}

and

{p_{j}}_{j i n [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 ErdH{o}s-R'{e}nyi 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.

Recommendations

Cites work

Cited in

(3)

Describes a project that uses

Uses Software

This page was built for publication: Exact simultaneous recovery of locations and structure from known orientations and corrupted point correspondences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1704899)