Abstract
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.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 2692-2721 |
| Number of pages | 30 |
| Journal | SIAM Journal on Imaging Sciences |
| Volume | 11 |
| Issue number | 4 |
| DOIs | |
| State | Published - 2018 |
Bibliographical note
Funding Information:\ast Received by the editors October 4, 2017; accepted for publication (in revised form) September 10, 2018; published electronically November 27, 2018. http://www.siam.org/journals/siims/11-4/M115061.html Funding: This work was supported by NSF awards DMS-14-18386 and DMS-18-21266. \dagger School of Mathematics, University of Minnesota, Twin Cities, Minneapolis, MN 55455 (lerman@umn.edu, shixx517@umn.edu). \ddagger Department of Mathematics, University of Central Florida, Oviedo, FL 32765 (Teng.Zhang@ucf.edu).
Publisher Copyright:
© 2018 Society for Industrial and Applied Mathematics.
Keywords
- Camera location estimation
- Convex recovery
- Least unsquared deviations
- Random graph theory
- Robust estimation
- Structure from motion