  Rotation Averaging is a non-convex optimization problem that determines
orientations of a collection of cameras from their images of a 3D scene. The
problem has been studied using a variety of distances and robustifiers. The
intrinsic (or geodesic) distance on SO(3) is geometrically meaningful; but
while some extrinsic distance-based solvers admit (conditional) guarantees of
correctness, no comparable results have been found under the intrinsic metric.
  In this paper, we study the spatial distribution of local minima. First, we
do a novel empirical study to demonstrate sharp transitions in qualitative
behavior: as problems become noisier, they transition from a single
(easy-to-find) dominant minimum to a cost surface filled with minima. In the
second part of this paper we derive a theoretical bound for when this
transition occurs. This is an extension of the results of [24], which used
local convexity as a proxy to study the difficulty of problem. By recognizing
the underlying quotient manifold geometry of the problem we achieve an n-fold
improvement over prior work. Incidentally, our analysis also extends the prior
$l_2$ work to general $l_p$ costs. Our results suggest using algebraic
connectivity as an indicator of problem difficulty.
