Angular synchronization by eigenvectors and semidefinite programming
Open accessAbstract
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.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Collective dynamics of ‘small-world’ networks
Watts, D. J., & Strogatz, S. H. (1998) · Nature · doi:10.1038/30918 · Cited by 43,060 · see citing works
Elements of Information Theory
Cover, T. M., & Thomas, J. A. (2001) · Wiley eBooks · doi:10.1002/0471200611 · Cited by 37,139 · see citing works
Horn, R. A., & Johnson, C. R. (1985) · Cited by 22,203 · see citing works
Information Theory and Reliable Communication.
Lee, P. M., & Gallager, R. T. (1970) · Journal of the Royal Statistical Society Series A (General) · doi:10.2307/2344305 · Cited by 5,559 · see citing works
Vandenberghe, L., & Boyd, S. (1996) · SIAM Review · doi:10.1137/1038003 · Cited by 4,079 · see citing works
Information Theory and Reliable Communication
Bell, D. A. (1969) · Electronics and Power · doi:10.1049/ep.1969.0319 · Cited by 4,023 · see citing works
Goemans, M. X., & Williamson, D. P. (1995) · Journal of the ACM · doi:10.1145/227683.227684 · Cited by 3,587 · see citing works
Elements of Information Theory
Jacobs, K. (1992) · Birkhäuser Basel eBooks · doi:10.1007/978-3-0348-8645-1_7 · Cited by 2,957 · see citing works
The Mathematics of Computerized Tomography
Natterer, F., & Wang, G. (2002) · Medical Physics · doi:10.1118/1.1429631 · Cited by 2,594 · see citing works
Coifman, R. R., & Lafon, S. (2006) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2006.04.006 · Cited by 2,380 · see citing works
Introduction to Quantum Mechanics
Grimes, R. A. (2019) · doi:10.1002/9781119618232.ch1 · Cited by 2,227 · see citing works
SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
Toh, K.-C., Todd, M. J., & Tütüncü, R. H. (1999) · Optimization methods & software · doi:10.1080/10556789908805762 · Cited by 1,939 · see citing works
Level-spacing distributions and the Airy kernel
Tracy, C. A., & Widom, H. (1994) · Communications in Mathematical Physics · doi:10.1007/bf02100489 · Cited by 1,905 · see citing works
Characteristic Vectors of Bordered Matrices With Infinite Dimensions
Wigner, E. P. (1955) · Annals of Mathematics · doi:10.2307/1970079 · Cited by 1,581 · see citing works
On the Distribution of the Roots of Certain Symmetric Matrices
Wigner, E. P. (1958) · Annals of Mathematics · doi:10.2307/1970008 · Cited by 1,523 · see citing works
Solving semidefinite-quadratic-linear programs using SDPT3
T�t�nc�, R. H., Toh, K.-C., & Todd, M. J. (2003) · Mathematical Programming · doi:10.1007/s10107-002-0347-5 · Cited by 1,167 · see citing works
The Mathematics of Computerized Tomography
Natterer, F. (2001) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9780898719284 · Cited by 1,057 · see citing works
A method for enforcing integrability in shape from shading algorithms
Frankot, R. T., & Chellappa, R. (1988) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.3909 · Cited by 1,043 · see citing works
Diffusion maps, spectral clustering and reaction coordinates of dynamical systems
Nadler, B., Lafon, S., Coifman, R. R., & Kevrekidis, I. G. (2006) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2005.07.004 · Cited by 989 · see citing works
On the power of unique 2-prover 1-round games
Khot, S. (2002) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/509907.510017 · Cited by 825 · see citing works
A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
Burer, S., & Monteiro, R. D. C. (2003) · Mathematical Programming · doi:10.1007/s10107-002-0352-8 · Cited by 774 · see citing works
Characteristic Vectors of Bordered Matrices with Infinite Dimensions II
Wigner, E. P. (1993) · Springer eBooks · doi:10.1007/978-3-662-02781-3_36 · Cited by 693 · see citing works
The eigenvalues of random symmetric matrices
Füredi, Z., & Komlós, J. (1981) · COMBINATORICA · doi:10.1007/bf02579329 · Cited by 674 · see citing works
SDPT3 -- A Matlab Software Package for Semidefinite Programming
Toh, K.-C., Todd, M. J., & Tütüncü, R. H. (1996) · eCommons (Cornell University) · Cited by 654 · see citing works
Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
Khot, S., Kindler, G., Mossel, E., & O’Donnell, R. (2007) · SIAM Journal on Computing · doi:10.1137/s0097539705447372 · Cited by 592 · see citing works
Semidefinite Programming Approaches for Sensor Network Localization With Noisy Distance Measurements
Biswas, P., Liang, T.-C., Toh, K.-C., et al. (2006) · IEEE Transactions on Automation Science and Engineering · doi:10.1109/tase.2006.877401 · Cited by 466 · see citing works
Discrete Mathematics and Theoretical Computer Science
Calude, C. S., Vajnovszki, V., & Dinneen, M. J. (2003) · Lecture notes in computer science · doi:10.1007/3-540-45066-1 · Cited by 447 · see citing works
Improved approximation algorithms for MAXk-CUT and MAX BISECTION
FRIEZE, A. M., & Jerrum, M. (1997) · Algorithmica · doi:10.1007/bf02523688 · Cited by 405 · see citing works
Havel, T. F., & Wüthrich, K. (1985) · Journal of Molecular Biology · doi:10.1016/0022-2836(85)90346-8 · Cited by 379 · see citing works
What Is the Range of Surface Reconstructions from a Gradient Field?
Agrawal, A., Raskar, R., & Chellappa, R. (2006) · Lecture notes in computer science · doi:10.1007/11744023_45 · Cited by 317 · see citing works
Universality at the edge of the spectrum in Wigner random matricesPreprint
Soshnikov, A. B. (1999) · Cited by 297 · see citing works
Universality at the Edge of the Spectrum¶in Wigner Random Matrices
Soshnikov, A. (1999) · Communications in Mathematical Physics · doi:10.1007/s002200050743 · Cited by 268 · see citing works
The largest eigenvalue of small rank perturbations of Hermitian random matrices
Péché, S. (2005) · Probability Theory and Related Fields · doi:10.1007/s00440-005-0466-z · Cited by 220 · see citing works
The Largest Eigenvalue of Rank One Deformation of Large Wigner Matrices
Féral, D., & Péché, S. (2007) · Communications in Mathematical Physics · doi:10.1007/s00220-007-0209-3 · Cited by 207 · see citing works
Distributed Clock Synchronization over Wireless Networks: Algorithms and Analysis
Giridhar, A., & Kumar, P. (2006) · Proceedings of the IEEE Conference on Decision & Control, including the Symposium on Adaptive Processes · doi:10.1109/cdc.2006.377325 · Cited by 207 · see citing works
Two-prover one-round proof systems: Their power and their problems
Feige, U., & Lovász, L. (1992) · Symposium on the Theory of Computing · Cited by 181 · see citing works
Singer, A., & Shkolnisky, Y. (2011) · SIAM Journal on Imaging Sciences · doi:10.1137/090767777 · Cited by 173 · see citing works
Self-citationTwo-prover one-round proof systems
Feige, U., & Lovász, L. (1992) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/129712.129783 · Cited by 159 · see citing works
Introduction to Quantum Mechanics
Warren, W. S. (1994) · Elsevier eBooks · doi:10.1016/b978-0-12-735850-5.50009-8 · Cited by 159 · see citing works
On the concentration of eigenvalues of random symmetric matrices
Alon, N., Krivelevich, M., & Vu, V. H. (2002) · Israel Journal of Mathematics · doi:10.1007/bf02785860 · Cited by 141 · see citing works
Near-optimal algorithms for unique games
Charikar, M., Makarychev, K., & Makarychev, Y. (2006) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1132516.1132547 · Cited by 124 · see citing works
Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming
Goemans, M. X., & Williamson, D. P. (2001) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/380752.380838 · Cited by 118 · see citing works
On the power of unique 2-prover 1-round games
Khot, S. (2003) · Proceedings - IEEE Conference on Computational Complexity/Proceedings · doi:10.1109/ccc.2002.1004334 · Cited by 113 · see citing works
A remark on global positioning from local distances
Singer, A. (2008) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0709842104 · Cited by 112 · see citing works
Self-citationNMR studies of structure and function of biological macromolecules (Nobel Lecture)*
Wüthrich, K. (2003) · Journal of Biomolecular NMR · doi:10.1023/a:1024733922459 · Cited by 109 · see citing works
Optimal and Global Time Synchronization in Sensornets
Karp, R. M., Elson, J., Estrin, D. L., et al. (2003) · eScholarship (California Digital Library) · Cited by 82 · see citing works
Viewing Angle Classification of Cryo-Electron Microscopy Images Using Eigenvectors
Singer, A., Zhao, Z., Shkolnisky, Y., & Hadani, R. (2011) · SIAM Journal on Imaging Sciences · doi:10.1137/090778390 · Cited by 69 · see citing works
Self-citationThe Mathematics of Computerized Tomography (Classics in Applied Mathematics, Vol. 32)
Censor, Y. (2002) · Inverse Problems · doi:10.1088/0266-5611/18/1/601 · Cited by 64 · see citing works
Global Synchronization in Sensornets
Elson, J., Karp, R. M., Papadimitriou, C. H., et al. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-24698-5_63 · Cited by 59 · see citing works
Sparse random matrices: spectral edge and statistics of rooted trees
Khorunzhy, A. (2001) · Advances in Applied Probability · doi:10.1239/aap/999187900 · Cited by 38 · see citing works
Reconstruction of Optical Surfaces from Ray Data
Rubinstein, J., & Wolansky, G. (2001) · Optical Review · doi:10.1007/s10043-001-0281-4 · Cited by 29 · see citing works
A new way to use semidefinite programming with applications to linear equations mod p
Andersson, G., Engebretsen, L. F., & Håstad, J. (1999) · Cited by 16 · see citing works
Rooted trees and moments of large sparse random matrices
Khorunzhiy, O. (2003) · Discrete Mathematics & Theoretical Computer Science · doi:10.46298/dmtcs.3346 · Cited by 8 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
Past, Present, and Future of Simultaneous Localization and Mapping: Toward the Robust-Perception Age
Cadena, C., Carlone, L., Carrillo, H., Latif, Y., Scaramuzza, D., Neira, J., Reid, I., & Leonard, J. J. (2016) · IEEE Transactions on Robotics · doi:10.1109/tro.2016.2624754 · Cited by 3,596 · see citing works
SyncSpecCNN: Synchronized Spectral CNN for 3D Shape Segmentation
Yi, L., Su, H., Guo, X., & Guibas, L. (2017) · 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2017.697 · Cited by 461 · see citing works
Exact and stable recovery of rotations for robust synchronization
Wang, L., & Singer, A. (2013) · Information and Inference · doi:10.1093/imaiai/iat005 · Cited by 178 · see citing works
Self-citationSubspace Estimation from Unbalanced and Incomplete Data Matrices: 𝓁2, ∞ Statistical Guarantees
Cai, C., Li, G., Chi, Y., Poor, H. V., & Chen, Y. (2021) · The Annals of Statistics · doi:10.1214/20-aos1986 · Cited by 37 · see citing works
Magnetic Eigenmaps for the visualization of directed networks
Fanuel, M., Alaíz, C. M., Fernández, Á., & Suykens, J. A. K. (2018) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2017.01.004 · Cited by 35 · see citing works
- Authors
- Singer, A.
- Affiliations
- Princeton University (US)
- Corresponding author
- Singer, A.
- ORCID
- Singer, A.
- Venue
- Applied and Computational Harmonic Analysis
- Publisher
- Elsevier BV
- Published
- 2011-01
- Volume
- 30
- Issue
- 1
- Pages
- 20-36
- ISSN
- 1063-5203 (ISSN-L)
- PMC
- PMC3003935
- OpenAlex
- W2143703915
- Cited by
- 329
- References
- 54
- Citations by year
- 2026: 12 · 2025: 15 · 2024: 19 · 2023: 36 · 2022: 28 · 2021: 27 · 2020: 31 · 2019: 29 · 2018: 20 · 2017: 28 · 2016: 22 · 2015: 18 · 2014: 13 · 2013: 16 · 2012: 11
- FWCI
- 9.76
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Licence
- Locations
- Applied and Computational Harmonic Analysis (publishedVersion)
- PubMed (publishedVersion)
- Europe PMC (PubMed Central) (acceptedVersion)
- PubMed Central (acceptedVersion)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Funders
- National Science Foundation (0914892)
- University of Pennsylvania
- Strong
- National Institutes of Health
- National Institute of General Medical Sciences (R01GM090200)
- Air Force Office of Scientific Research (FA9550-, R01GM090200, FA9550-09-1-0551)
- Topics
- Physical Sciences › Engineering › Computational Mechanics › Sparse and Compressive Sensing Techniques
- Physical Sciences › Mathematics › Applied Mathematics › Statistical and numerical algorithms
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Matrix Theory and Algorithms
- Keywords
- Hermitian matrices, semidefinite relaxation, random matrix theory, information theory, Goemans-Williamson algorithm, MaxCut, clock synchronization, distributed networks, surface reconstruction, collective synchronization
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
