  The angular synchronization problem is to obtain an accurate estimation (up
to a constant additive phase) for a set of unknown angles
$\theta_1,...,\theta_n$ from $m$ noisy measurements of their offsets
$\theta_i-\theta_j \mod 2\pi$. Of particular interest is angle recovery in the
presence of many outlier measurements that are uniformly distributed in
$[0,2\pi)$ and carry no information on the true offsets. We introduce an
efficient recovery algorithm for the unknown angles from the top eigenvector of
a specially designed Hermitian matrix. The eigenvector method is extremely
stable and succeeds even when the number of outliers is exceedingly large. For
example, we successfully estimate $n=400$ angles from a full set of $m={400
\choose 2}$ offset measurements of which 90% are outliers in less than a second
on a commercial laptop. The performance of the method is analyzed using random
matrix theory and information theory. We discuss the relation of the
synchronization problem to the combinatorial optimization problem
\textsc{Max-2-Lin mod} $L$ and present a semidefinite relaxation for angle
recovery, drawing similarities with the Goemans-Williamson algorithm for
finding the maximum cut in a weighted graph. We present extensions of the
eigenvector method to other synchronization problems that involve different
group structures and their applications, such as the time synchronization
problem in distributed networks and the surface reconstruction problems in
computer vision and optics.
