We establish exact recovery for the Least Unsquared Deviations (LUD) algorithm of Ozye sil and Singer. More precisely, we show that for sufficiently many cameras with given corrupted pairwise directions, where both camera locations and pairwise directions are generated by a special probabilistic model, the LUD algorithm exactly recovers the camera locations with high probability. A similar exact recovery guarantee for camera locations was established for the ShapeFit algorithm by Hand, Lee, and Voroninski, but with typically less corruption.
Bibliographical notePublisher Copyright:
© 2018 Society for Industrial and Applied Mathematics.
- Camera location estimation
- Convex recovery
- Least unsquared deviations
- Random graph theory
- Robust estimation
- Structure from motion