Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2011 Jan 30;30(1):20-36.
doi: 10.1016/j.acha.2010.02.001.

Angular Synchronization by Eigenvectors and Semidefinite Programming

A Singer  1
Affiliations

Angular Synchronization by Eigenvectors and Semidefinite Programming

A Singer. Appl Comput Harmon Anal. .

Abstract

The angular synchronization problem is to obtain an accurate estimation (up to a constant additive phase) for a set of unknown angles θ(1), …, θ(n) from m noisy measurements of their offsets θ(i) - θ(j) mod 2π. Of particular interest is angle recovery in the presence of many outlier measurements that are uniformly distributed in [0, 2π) 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=(4002) 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 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.

PubMed Disclaimer

Figures

Figure 1
Figure 1
Histogram of the eigenvalues of the matrix H in the complete graph model for n = 400 and different values of p.
Figure 2
Figure 2
Histogram of the eigenvalues of the matrix H in the small-world model for n = 400, ε = 0.2, m ≈ 8000, and different values of p.
Figure 3
Figure 3
Bar plot of the 25 largest eigenvalues of the matrix H in the small-world model for n = 4000, ε = 0.2, m ≈ 8 · 105, and different values of p. The multiplicities 1, 3, 5, 7, 9 corresponding to the spherical harmonics are evident as long as p is not too small. As p decreases, the high-oscillatory spherical harmonics are getting “swallowed” by the semi-circle.
See this image and copyright information in PMC

References

    1. Agrawal AK, Raskar R, Chellappa R. What is the range of surface reconstructions from a gradient field?. Computer Vision – ECCV 2006: 9th European Conference on Computer Vision; Graz, Austria. May 7–13, 2006.2006.
    2. Proceedings, Part IV (Lecture Notes in Computer Science); pp. 578–591.
    1. Alon N, Krivelevich M, Vu VH. On the concentration of eigenvalues of random symmetric matrices. Israel Journal of Mathematics. 2002;131(1):259–267.
    1. Andersson G, Engebretsen L, Håstad J. A new way to use semidefinite programming with applications to linear equations mod. Proceedings 10th annual ACM-SIAM symposium on Discrete algorithms; 1999. pp. 41–50.
    1. Biswas P, Liang TC, Toh KC, Wang TC, Ye Y. Semidefinite programming approaches for sensor network localization with noisy distance measurements. IEEE Transactions on Automation Science and Engineering. 2006;3(4):360–371.
    1. Burer S, Monteiro RDC. A Nonlinear Programming Algorithm for Solving Semidefinite Programs Via Low-Rank Factorization. Mathematical Programming (series B) 2003;95 (2):329–357.

LinkOut - more resources