  We propose a novel quadratic programming formulation for estimating the
corruption levels in group synchronization, and use these estimates to solve
this problem. Our objective function exploits the cycle consistency of the
group and we thus refer to our method as detection and estimation of structural
consistency (DESC). This general framework can be extended to other algebraic
and geometric structures. Our formulation has the following advantages: it can
tolerate corruption as high as the information-theoretic bound, it does not
require a good initialization for the estimates of group elements, it has a
simple interpretation, and under some mild conditions the global minimum of our
objective function exactly recovers the corruption levels. We demonstrate the
competitive accuracy of our approach on both synthetic and real data
experiments of rotation averaging.
