nucleation

LIT-1655: Angular synchronization by eigenvectors and semidefinite programming

1 min read

Properties5
StatusActive — read in full 2026-10-27 (NOTE-1224), from arXiv v2; worth reading as the paper that posed angular synchronization with outliers and sketched its extension to other groups, and as a clean case that separates what pairwise evidence determines from what a cheap method can recover: an information bound that binds every algorithm, and a spectral relaxation whose threshold sits within an L-dependent factor of it. The spectral threshold is a careful heuristic confirmed by simulation, not a theorem.
Version2
Tagsmathematics, information-theory, network-science
Cited as “paper” byNOTE-1224 — Singer — Angular synchronization
Cited as “source” byTHEORY-1056 — In angular synchronization with outlier offsets, a polynomial-time spectral relaxation, the top eigenvector of the Hermitian matrix of measured phase offsets, recovers the angles once the share of good offsets exceeds about 1/√n on the complete graph, within a factor √((L − 1)/(2 log₂ L)) of the information bound that limits every algorithm, while exact maximum likelihood is a non-convex search costing O(mLⁿ) exhaustively; in this model the price of recovering the global configuration cheaply instead of optimally is a constant factor in evidence, which vanishes for L ≤ 6, THEORY-1067 — In angular synchronization from m pairwise offsets, each exact with probability p and otherwise uniform over L values, no estimator of any computational cost can recover all n angles with small error when p is below about √((n/m)·2 log₂ L/(L − 1)), nor an angle of average degree below about √((n/m)·log₂ L/(L − 1)), because each offset carries at most I(L, p) ≈ ½(L − 1)p² bits; below these thresholds a global configuration that exists is not determined by the pairwise evidence, whatever the resources spent on finding it

Graph View

Singer, A. (2011). Angular synchronization by eigenvectors and semidefinite programming. Applied and Computational Harmonic Analysis, 30(1), 20–36. doi:10.1016/j.acha.2010.02.001.

Read in full on 2026-10-27 (NOTE-1224).

Why this is here

A21 §8 cited it for the gap between a compatible global configuration existing and an apparatus recovering it from pairwise evidence at a cost: “Interaction produces relational evidence, but recovering a larger structure from that evidence is itself a resource-bounded process.” It bears on CLAIM-471 and CLAIM-475.

Backlinks