ShapeFit: Exact location recovery from corrupted pairwise directions

Vladislav Voroninski just sent me the following:

Hi Igor,


I'm writing to report on a new algorithm for location recovery from corrupted relative direction observations, a necessary subtask of the Structure from Motion pipeline in computer vision (recovering 3D structure from a collection of images). This is joint work with Paul Hand and Choongbum Lee.


We provide theoretical guarantees of exact location recovery from corrupted observations (the first such result in the literature), and provide empirical evidence of the effectiveness of this algorithm and its stability to noise.


The paper just became available on Arxiv: http://arxiv.org/abs/1506.01437


Best,

Vlad

 Thanks Vlad ! here is the paper:

ShapeFit: Exact location recovery from corrupted pairwise directions by Paul Hand, Choongbum Lee, Vladislav Voroninski

Let t1,…,tn∈Rd and consider the location recovery problem: given a subset of pairwise direction observations {(ti−tj)/∥ti−tj∥2}i<j∈[n]×[n], where a constant fraction of these observations are arbitrarily corrupted, find {ti}ni=1 up to a global translation and scale. We propose a novel algorithm for the location recovery problem, which consists of a simple convex program over dn real variables. We prove that this program recovers a set of n i.i.d. Gaussian locations exactly and with high probability if the observations are given by an Erd\"{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.

    Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.