#### DMCA

## ShapeFit: Exact location recovery from corrupted pairwise directions

### Citations

382 |
YALMIP : A toolbox for modeling and optimization in MATLAB.
- Lofberg
- 2004
(Show Context)
Citation Context ...blocks represent an average recovery error of 100%. The left panel corresponds to the noiseless case σ = 0, and the right panel corresponds to the noisy case σ = 0.05. let vij = zij with probability q t (0) i −t (0) j ‖t(0)i −t (0) j ‖2 + σzij with probability 1− q where zij are independent and uniform over S 2. Let vij = vij/‖vij‖2. That is, each observation is corrupted with probability q, and each corruption is in a random direction. In the noiseless case, with σ = 0, each observation is exact with probability 1− q. We solved ShapeFit using the SDPT3 solver [23, 26] and YALMIP [16]. For output T = {ti}i∈[n], define its relative error with respect to T (0) = {t(0)i }i∈[n] as ∥ ∥ ∥ ∥ ∥ T ‖T‖F − T (0) ‖T (0)‖F ∥ ∥ ∥ ∥ ∥ F where ‖T‖F is the Frobenius norm of the matrix whose column are {ti}. This error metric amounts to an ℓ2 norm after rescaling. Figure 1 shows the average residual of the output of ShapeFit over 10 independent trials for locations in R3 generated by p = 1/2, σ ∈ {0, 0.05}, and a range of values 10 ≤ n ≤ 80 and 0 ≤ q ≤ 0.5. White blocks represent zero average residual, and black blocks represent an average residual of 1 or higher. Average residuals between ... |

359 | Sdpt3 - a matlab software package for semidefinite programming,
- Toh, Todd, et al.
- 1999
(Show Context)
Citation Context ...ted problems. Black blocks represent an average recovery error of 100%. The left panel corresponds to the noiseless case σ = 0, and the right panel corresponds to the noisy case σ = 0.05. let vij = zij with probability q t (0) i −t (0) j ‖t(0)i −t (0) j ‖2 + σzij with probability 1− q where zij are independent and uniform over S 2. Let vij = vij/‖vij‖2. That is, each observation is corrupted with probability q, and each corruption is in a random direction. In the noiseless case, with σ = 0, each observation is exact with probability 1− q. We solved ShapeFit using the SDPT3 solver [23, 26] and YALMIP [16]. For output T = {ti}i∈[n], define its relative error with respect to T (0) = {t(0)i }i∈[n] as ∥ ∥ ∥ ∥ ∥ T ‖T‖F − T (0) ‖T (0)‖F ∥ ∥ ∥ ∥ ∥ F where ‖T‖F is the Frobenius norm of the matrix whose column are {ti}. This error metric amounts to an ℓ2 norm after rescaling. Figure 1 shows the average residual of the output of ShapeFit over 10 independent trials for locations in R3 generated by p = 1/2, σ ∈ {0, 0.05}, and a range of values 10 ≤ n ≤ 80 and 0 ≤ q ≤ 0.5. White blocks represent zero average residual, and black blocks represent an average residual of 1 or higher. Average re... |

349 | Introduction to the non-asymptotic analysis of random matrices
- Vershynin
- 2011
(Show Context)
Citation Context ...2|δij |‖t(0)ij ‖2 ≥ R(T (0)). This condition on ε is satisfied under the assumption ε ≤ βc0c 2 1p 4 3·256·64·32 . 2.5 Properties of Gaussians in high dimensions In this section, we prove that i.i.d. Gaussians satisfy properties needed to establish Conditions 2, 3, and 5 in Theorem 3. We begin by recording some useful facts regarding concentration of random Gaussian vectors: Lemma 7. Let x, y be i.i.d. N (0, Id×d), and ǫ ≤ 1, then P ( d(1− ǫ) ≤ ‖x‖22 ≤ d(1 + ǫ) ) ≥ 1− e−cǫ2d and P (|〈x, y〉 |≥ dǫ) ≤ e−cǫ2d where c > 0 is an absolute constant. Proof. Both statements follow from Corollary 5.17 in [27], concerning concentration of sub-exponential random variables. Lemma 8 ([27] Corollary 5.35). Let A be an n × d matrix with i.i.d. N (0, 1) entries. Then for any t ≥ 0, P ( σmax(A) ≥ √ n+ √ d+ t ) ≤ 2e− t 2 2 where σmax(A) is the largest singular value of A. Lemma 9. Let t (0) i , i ∈ [n] be i.i.d. N (0, Id×d). Then, there exists an event E, such that on E, we have for all i, j, k, l ∈ [n], i 6= j, k 6= l, ‖t(0)ij ‖2 ‖t(0)kl ‖2 ≥ 9 10 and for all distinct i, j, k ∈ [n], 〈t(0)ij , t (0) ik 〉2 ≤ 1/3 and P(Ec) ≤ 3n2e−cd, where c > 0 is an absolute constant. Proof. This follows from repeated ap... |

291 |
Fast probabilistic algorithms for hamiltonian circuits and matchings
- Angluin, Valiant
- 1979
(Show Context)
Citation Context ...s at most ⌊n/2⌋ ∑ k=1 ( n k ) (1− p)k(n−k) ≤ ⌊n/2⌋ ∑ k=1 (en k )k e−pk(n−k) < ⌊n/2⌋ ∑ k=1 ( ne1−p(n−k) )k . Since k ≤ ⌊n2 ⌋, we have ne1−p(n−k) ≤ ne1−pn/2 < 1 (since np ≥ 4 log n). Therefore the summand on the right-hand-side is at most (ne1−pn/2)k, which is maximized at k = 1. This shows that the probability that G(n, p) is not connected is at most n2e1−pn/2. In G(n, p), for a fixed vertex v, the expected value of deg(v)is (n−1)p, and for a pair of vertices v,w, the expected value of the codegree of v and w is (n− 2)p2. Therefore the lemma follows from Chernoff’s inequality — see Fact 4 from [1] — and a union bound. 2.7 Proof of Theorem 1 We can now prove the high dimensional recovery theorem, which we state here again for convenience: Theorem 1. Let G([n], E) be drawn from G(n, p) for some p = Ω(n−1/4). Take t(0)1 , . . . t (0) n ∼ N (0, Id×d) to be i.i.d., independent from G. There exists an absolute constant c > 0 and a γ = Ω(p4) not depending on n, such that if max(2 6 c6 , 43 c3 log 3 n) ≤ n ≤ e 16 cd and d = Ω(1), then there exists an event with probability at least 1− e−n1/6 − 13e− 12 cd, on which the following holds: For arbitrary subgraphs Eb satisfying maxi degb(i) ≤ γn and... |

236 | Solving semidefinite-quadratic-linear programs using sdpt3,
- Tutuncu, Toh, et al.
- 2003
(Show Context)
Citation Context ...ted problems. Black blocks represent an average recovery error of 100%. The left panel corresponds to the noiseless case σ = 0, and the right panel corresponds to the noisy case σ = 0.05. let vij = zij with probability q t (0) i −t (0) j ‖t(0)i −t (0) j ‖2 + σzij with probability 1− q where zij are independent and uniform over S 2. Let vij = vij/‖vij‖2. That is, each observation is corrupted with probability q, and each corruption is in a random direction. In the noiseless case, with σ = 0, each observation is exact with probability 1− q. We solved ShapeFit using the SDPT3 solver [23, 26] and YALMIP [16]. For output T = {ti}i∈[n], define its relative error with respect to T (0) = {t(0)i }i∈[n] as ∥ ∥ ∥ ∥ ∥ T ‖T‖F − T (0) ‖T (0)‖F ∥ ∥ ∥ ∥ ∥ F where ‖T‖F is the Frobenius norm of the matrix whose column are {ti}. This error metric amounts to an ℓ2 norm after rescaling. Figure 1 shows the average residual of the output of ShapeFit over 10 independent trials for locations in R3 generated by p = 1/2, σ ∈ {0, 0.05}, and a range of values 10 ≤ n ≤ 80 and 0 ≤ q ≤ 0.5. White blocks represent zero average residual, and black blocks represent an average residual of 1 or higher. Average re... |

204 |
Adaptive estimation of a quadratic functional by model selection
- Laurent, Massart
(Show Context)
Citation Context ... Lemma 17. For each distinct i, j ∈ [n], define Sij = {tk : ik, jk ∈ E(G)}. Consider the following events: (i) for all i ∈ [n], we have ‖ti‖2 ≤ 4 √ log n, (ii) ∑ ij∈E(G) ‖ti − tj‖2 ≥ 18n2p, (iii) for each distinct i, j ∈ [n], for all but at most εn integers k ∈ [n], we have 1−〈 tk−ti‖tk−ti‖2 , tj−ti ‖tj−ti‖2 〉 2 ≥ ε2 2(‖tk‖22+‖ti‖22) , (iv) for each distinct i, j ∈ [n], Sij is 8cmax{1,‖ti+tj‖2} -well-distributed with respect to (ti, tj). For a fixed i ∈ [n], since ‖ti‖22 follows a χ2 distribution with 3 degrees of freedom, standard estimates on Chi-squared random variables, such as Lemma 1 in [15], give P(‖ti‖22 ≥ 3 + 2 √ 3t+ 2t2) ≤ e−t2 . Let t = √ 7 log n. If n is sufficiently large, then 2t2 + 2 √ 3t + 3 < 16 log n. As a result, P(‖ti‖22 ≥ 16 log n) ≤ e−7 logn. Hence Property (i) holds with probability 1− n−6 by taking the union bound over all i ∈ [n]. Property (ii) holds with probability 1 − e−Ω(n) by Lemma 15. For a fixed pair i, j ∈ [n], Property (iii) holds with probability 1 − e−Ω(εn) by Lemma 16. Hence by taking the union bound, we see that Property (iii) holds with probability 1 − n2e−Ω(εn). For a fixed pair i, j ∈ [n], by Lemma 17 and the fact that each pair is contained in ... |

157 |
Bundle adjustment—a modern synthesis,” in Vision Algorithms: Theory and Practice
- Triggs, McLauchlan, et al.
(Show Context)
Citation Context ...al constraints yield estimates of the relative directions and orientations between pairs of cameras. Noise in these estimates is inherent to any real-world application, and worse yet, due to intrinsic challenges arising from the image formation process and properties of man-made scenes (illumination changes, specularities, occlusions, shadows, duplicate structures etc), severe outliers in estimated point correspondences and hence relative camera poses are unavoidable. Once camera locations and orientations are estimated, 3D structure can then be recovered by a process called bundle adjustment [24], which is a simultaneous nonlinear refinement of 3D structure, camera locations, and camera orientations. Bundle-adjustment is a local method, which generally works well when started close to an optimum. Thus, it is critical to obtain accurate camera location and rotation estimates for initialization. SfM therefore consists of three steps: 1) estimating relative camera pose from point correspondences, 2) recovering camera locations and orientations in a global coordinate framework, and 3) bundle adjustment. While the first and third steps have well-founded theories and algorithms, methods for... |

75 | Robust rotation and translation estimation in multiview reconstruction
- Martinec, Pajdla
- 2007
(Show Context)
Citation Context ...d, which generally works well when started close to an optimum. Thus, it is critical to obtain accurate camera location and rotation estimates for initialization. SfM therefore consists of three steps: 1) estimating relative camera pose from point correspondences, 2) recovering camera locations and orientations in a global coordinate framework, and 3) bundle adjustment. While the first and third steps have well-founded theories and algorithms, methods for the second step are mostly heuristically motivated. Several efficient and stable algorithms exist for estimating global camera orientations [9, 6, 2, 18, 7, 22, 11, 4, 8, 4, 10, 17, 20]. Hence, it is standard to recover locations separately based on estimates of the orientations. There have been many different approaches to location recovery from relative directions, such as least squares [9, 2, 3, 17], second-order cone programs and l∞ methods [13, 17, 18, 14, 21], spectral methods [3], similarity transformations for pair alignment [22], Lie-algebraic averaging [10], markov random fields [5], and several others [22, 25, 20, 12]. Unfortunately, most location recovery algorithms either lack robustness to correspondence errors (which are unavoidable in large unordered datasets... |

67 | Lie-algebraic averaging for globally consistent motion estimation
- Govindu
- 2004
(Show Context)
Citation Context ...d, which generally works well when started close to an optimum. Thus, it is critical to obtain accurate camera location and rotation estimates for initialization. SfM therefore consists of three steps: 1) estimating relative camera pose from point correspondences, 2) recovering camera locations and orientations in a global coordinate framework, and 3) bundle adjustment. While the first and third steps have well-founded theories and algorithms, methods for the second step are mostly heuristically motivated. Several efficient and stable algorithms exist for estimating global camera orientations [9, 6, 2, 18, 7, 22, 11, 4, 8, 4, 10, 17, 20]. Hence, it is standard to recover locations separately based on estimates of the orientations. There have been many different approaches to location recovery from relative directions, such as least squares [9, 2, 3, 17], second-order cone programs and l∞ methods [13, 17, 18, 14, 21], spectral methods [3], similarity transformations for pair alignment [22], Lie-algebraic averaging [10], markov random fields [5], and several others [22, 25, 20, 12]. Unfortunately, most location recovery algorithms either lack robustness to correspondence errors (which are unavoidable in large unordered datasets... |

60 | Discrete-continuous optimization for largescale structure from motion
- Crandall, Owens, et al.
(Show Context)
Citation Context ...for the second step are mostly heuristically motivated. Several efficient and stable algorithms exist for estimating global camera orientations [9, 6, 2, 18, 7, 22, 11, 4, 8, 4, 10, 17, 20]. Hence, it is standard to recover locations separately based on estimates of the orientations. There have been many different approaches to location recovery from relative directions, such as least squares [9, 2, 3, 17], second-order cone programs and l∞ methods [13, 17, 18, 14, 21], spectral methods [3], similarity transformations for pair alignment [22], Lie-algebraic averaging [10], markov random fields [5], and several others [22, 25, 20, 12]. Unfortunately, most location recovery algorithms either lack robustness to correspondence errors (which are unavoidable in large unordered datasets), at times produce illegitimate collapsed solutions, or suffer from convergence to local minima, in sum causing large errors in or a complete degradation of, the recovered locations. There are some recent notable exceptions to the above limitations. An algorithm called 1dSfM [28] focuses on removing outliers by examining inconsistencies along one-dimensional projections, before attempting to recover camera loc... |

39 | A fast effective heuristic for the feedback arc set problem.
- Eades, Lin, et al.
- 1993
(Show Context)
Citation Context ...d, which generally works well when started close to an optimum. Thus, it is critical to obtain accurate camera location and rotation estimates for initialization. SfM therefore consists of three steps: 1) estimating relative camera pose from point correspondences, 2) recovering camera locations and orientations in a global coordinate framework, and 3) bundle adjustment. While the first and third steps have well-founded theories and algorithms, methods for the second step are mostly heuristically motivated. Several efficient and stable algorithms exist for estimating global camera orientations [9, 6, 2, 18, 7, 22, 11, 4, 8, 4, 10, 17, 20]. Hence, it is standard to recover locations separately based on estimates of the orientations. There have been many different approaches to location recovery from relative directions, such as least squares [9, 2, 3, 17], second-order cone programs and l∞ methods [13, 17, 18, 14, 21], spectral methods [3], similarity transformations for pair alignment [22], Lie-algebraic averaging [10], markov random fields [5], and several others [22, 25, 20, 12]. Unfortunately, most location recovery algorithms either lack robustness to correspondence errors (which are unavoidable in large unordered datasets... |

30 | Combining two-view constraints for motion estimation
- Govindu
- 2001
(Show Context)
Citation Context |

29 | Distributed image-based 3-d localization of camera sensor networks
- Tron, Vidal
(Show Context)
Citation Context ...mostly heuristically motivated. Several efficient and stable algorithms exist for estimating global camera orientations [9, 6, 2, 18, 7, 22, 11, 4, 8, 4, 10, 17, 20]. Hence, it is standard to recover locations separately based on estimates of the orientations. There have been many different approaches to location recovery from relative directions, such as least squares [9, 2, 3, 17], second-order cone programs and l∞ methods [13, 17, 18, 14, 21], spectral methods [3], similarity transformations for pair alignment [22], Lie-algebraic averaging [10], markov random fields [5], and several others [22, 25, 20, 12]. Unfortunately, most location recovery algorithms either lack robustness to correspondence errors (which are unavoidable in large unordered datasets), at times produce illegitimate collapsed solutions, or suffer from convergence to local minima, in sum causing large errors in or a complete degradation of, the recovered locations. There are some recent notable exceptions to the above limitations. An algorithm called 1dSfM [28] focuses on removing outliers by examining inconsistencies along one-dimensional projections, before attempting to recover camera locations. However, one drawback of this... |

20 | A multi-stage linear approach to structure from motion.
- Sinha, Steedly, et al.
- 2012
(Show Context)
Citation Context |

18 |
Spectral solution of large-scale extrinsic camera calibration as a graph embedding problem.
- Brand, Antone, et al.
- 2004
(Show Context)
Citation Context ...espondences, 2) recovering camera locations and orientations in a global coordinate framework, and 3) bundle adjustment. While the first and third steps have well-founded theories and algorithms, methods for the second step are mostly heuristically motivated. Several efficient and stable algorithms exist for estimating global camera orientations [9, 6, 2, 18, 7, 22, 11, 4, 8, 4, 10, 17, 20]. Hence, it is standard to recover locations separately based on estimates of the orientations. There have been many different approaches to location recovery from relative directions, such as least squares [9, 2, 3, 17], second-order cone programs and l∞ methods [13, 17, 18, 14, 21], spectral methods [3], similarity transformations for pair alignment [22], Lie-algebraic averaging [10], markov random fields [5], and several others [22, 25, 20, 12]. Unfortunately, most location recovery algorithms either lack robustness to correspondence errors (which are unavoidable in large unordered datasets), at times produce illegitimate collapsed solutions, or suffer from convergence to local minima, in sum causing large errors in or a complete degradation of, the recovered locations. There are some recent notable except... |

18 | Non-sequential structure from motion. In:
- Enqvist, Kahl, et al.
- 2011
(Show Context)
Citation Context |

17 |
Recovering camera motion using l∞ minimization.
- Sim, Hartley
- 2006
(Show Context)
Citation Context ...ons in a global coordinate framework, and 3) bundle adjustment. While the first and third steps have well-founded theories and algorithms, methods for the second step are mostly heuristically motivated. Several efficient and stable algorithms exist for estimating global camera orientations [9, 6, 2, 18, 7, 22, 11, 4, 8, 4, 10, 17, 20]. Hence, it is standard to recover locations separately based on estimates of the orientations. There have been many different approaches to location recovery from relative directions, such as least squares [9, 2, 3, 17], second-order cone programs and l∞ methods [13, 17, 18, 14, 21], spectral methods [3], similarity transformations for pair alignment [22], Lie-algebraic averaging [10], markov random fields [5], and several others [22, 25, 20, 12]. Unfortunately, most location recovery algorithms either lack robustness to correspondence errors (which are unavoidable in large unordered datasets), at times produce illegitimate collapsed solutions, or suffer from convergence to local minima, in sum causing large errors in or a complete degradation of, the recovered locations. There are some recent notable exceptions to the above limitations. An algorithm called 1dSfM [28] fo... |

15 | Global motion estimation from point matches
- Arie-Nachimson, Kovalsky, et al.
- 2012
(Show Context)
Citation Context |

14 | Multiple-view geometry under the l∞-norm. Pattern Analysis and Machine Intelligence,
- Kahl, Hartley
- 2008
(Show Context)
Citation Context ...ons in a global coordinate framework, and 3) bundle adjustment. While the first and third steps have well-founded theories and algorithms, methods for the second step are mostly heuristically motivated. Several efficient and stable algorithms exist for estimating global camera orientations [9, 6, 2, 18, 7, 22, 11, 4, 8, 4, 10, 17, 20]. Hence, it is standard to recover locations separately based on estimates of the orientations. There have been many different approaches to location recovery from relative directions, such as least squares [9, 2, 3, 17], second-order cone programs and l∞ methods [13, 17, 18, 14, 21], spectral methods [3], similarity transformations for pair alignment [22], Lie-algebraic averaging [10], markov random fields [5], and several others [22, 25, 20, 12]. Unfortunately, most location recovery algorithms either lack robustness to correspondence errors (which are unavoidable in large unordered datasets), at times produce illegitimate collapsed solutions, or suffer from convergence to local minima, in sum causing large errors in or a complete degradation of, the recovered locations. There are some recent notable exceptions to the above limitations. An algorithm called 1dSfM [28] fo... |

8 | Global fusion of relative motions for robust, accurate and scalable structure from motion.
- Moulon, Monasse, et al.
- 2013
(Show Context)
Citation Context |

7 | C.: Simultaneous multiple rotation averaging using lagrangian duality.
- Fredriksson, Olsson
- 2013
(Show Context)
Citation Context |

6 |
Efficient and robust large-scale rotation averaging.
- Chatterjee, Govindu
- 2013
(Show Context)
Citation Context |

6 |
A global linear method for camera pose registration.
- Jiang, Cui, et al.
- 2013
(Show Context)
Citation Context ...mostly heuristically motivated. Several efficient and stable algorithms exist for estimating global camera orientations [9, 6, 2, 18, 7, 22, 11, 4, 8, 4, 10, 17, 20]. Hence, it is standard to recover locations separately based on estimates of the orientations. There have been many different approaches to location recovery from relative directions, such as least squares [9, 2, 3, 17], second-order cone programs and l∞ methods [13, 17, 18, 14, 21], spectral methods [3], similarity transformations for pair alignment [22], Lie-algebraic averaging [10], markov random fields [5], and several others [22, 25, 20, 12]. Unfortunately, most location recovery algorithms either lack robustness to correspondence errors (which are unavoidable in large unordered datasets), at times produce illegitimate collapsed solutions, or suffer from convergence to local minima, in sum causing large errors in or a complete degradation of, the recovered locations. There are some recent notable exceptions to the above limitations. An algorithm called 1dSfM [28] focuses on removing outliers by examining inconsistencies along one-dimensional projections, before attempting to recover camera locations. However, one drawback of this... |

5 |
Camera motion estimation by convex programming.
- Ozyesil, Singer, et al.
- 2013
(Show Context)
Citation Context |

5 | Robust global translations with 1dsfm.
- Wilson, Snavely
- 2014
(Show Context)
Citation Context ...14, 21], spectral methods [3], similarity transformations for pair alignment [22], Lie-algebraic averaging [10], markov random fields [5], and several others [22, 25, 20, 12]. Unfortunately, most location recovery algorithms either lack robustness to correspondence errors (which are unavoidable in large unordered datasets), at times produce illegitimate collapsed solutions, or suffer from convergence to local minima, in sum causing large errors in or a complete degradation of, the recovered locations. There are some recent notable exceptions to the above limitations. An algorithm called 1dSfM [28] focuses on removing outliers by examining inconsistencies along one-dimensional projections, before attempting to recover camera locations. However, one drawback of this method is that it does not reason about self-consistent outliers, which occur due to repetitive structures, commonly found in man-made scenes. Also, Ozyesil and Singer propose a convex program over dn + |E| variables for location recovery and empirically demonstrate its robustness to outliers [19]. While both of these methods exhibit favorable empirical performance, they lack theoretical guarantees of robustness to outliers... |

2 |
Khurrum Aftab, and Jochen Trumpf. L1 rotation averaging using the weiszfeld algorithm.
- Hartley
- 2011
(Show Context)
Citation Context |

2 |
Robust camera location estimation by convex programming.
- Ozyesil, Singer
- 2014
(Show Context)
Citation Context ...dation of, the recovered locations. There are some recent notable exceptions to the above limitations. An algorithm called 1dSfM [28] focuses on removing outliers by examining inconsistencies along one-dimensional projections, before attempting to recover camera locations. However, one drawback of this method is that it does not reason about self-consistent outliers, which occur due to repetitive structures, commonly found in man-made scenes. Also, Ozyesil and Singer propose a convex program over dn + |E| variables for location recovery and empirically demonstrate its robustness to outliers [19]. While both of these methods exhibit favorable empirical performance, they lack theoretical guarantees of robustness to outliers. In this paper, we propose a novel convex program for location recovery from pairwise direction observations, and prove that this method recovers locations exactly, in the face of adversarial corruptions, and under rather broad technical assumptions. To the best of our knowledge, this is the first theoretical result guaranteeing location recovery in the challenging case of corrupted pairwise direction observations. We also demonstrate that this method performs well ... |

1 |
Multiple view geometry and the l∞-norm. In Computer Vision,
- Kahl
- 2005
(Show Context)
Citation Context ...ons in a global coordinate framework, and 3) bundle adjustment. While the first and third steps have well-founded theories and algorithms, methods for the second step are mostly heuristically motivated. Several efficient and stable algorithms exist for estimating global camera orientations [9, 6, 2, 18, 7, 22, 11, 4, 8, 4, 10, 17, 20]. Hence, it is standard to recover locations separately based on estimates of the orientations. There have been many different approaches to location recovery from relative directions, such as least squares [9, 2, 3, 17], second-order cone programs and l∞ methods [13, 17, 18, 14, 21], spectral methods [3], similarity transformations for pair alignment [22], Lie-algebraic averaging [10], markov random fields [5], and several others [22, 25, 20, 12]. Unfortunately, most location recovery algorithms either lack robustness to correspondence errors (which are unavoidable in large unordered datasets), at times produce illegitimate collapsed solutions, or suffer from convergence to local minima, in sum causing large errors in or a complete degradation of, the recovered locations. There are some recent notable exceptions to the above limitations. An algorithm called 1dSfM [28] fo... |