Source-linked AI summary
Angular Synchronization by Eigenvectors and Semidefinite Programming
Amit Singer
TL;DR
The paper addresses recovering unknown angles from noisy pairwise offsets when many measurements are uniform outliers and their identities are unknown. It proposes eigenvector and semidefinite-programming estimators, emphasizing the faster spectral method. The eigenvector approach is reported to remain accurate with many outliers and to be asymptotically nearly optimal.
Problem
The problem is to recover angles up to a global phase from noisy offsets, including settings with many unidentified uniform outlier measurements.
Method
The paper constructs a Hermitian measurement matrix and estimates angles from its normalized top eigenvector, alongside a semidefinite relaxation with analogous rounding.
Results
The eigenvector and SDP methods have comparable accuracy, while the eigenvector method is much faster; complete-graph analysis shows successful recovery as np^2 grows, and the method is nearly Shannon-optimal asymptotically.
Takeaways & Limitations
The eigenvector method is preferred for large-scale problems because its speed and numerical stability support recovery under substantial outlier contamination.
Takeaways & Limitations
The main model ignores small discretization errors in good offsets, although the paper states their effect is negligible relative to outliers.
Abstract
from arXiv · showhide
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={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.
1. Introduction.
Angular synchronization seeks globally consistent angle estimates from noisy offsets, especially when many measurements are uninformative outliers. The paper contrasts robust spectral and semidefinite estimators with maximum-likelihood and least-squares approaches that become difficult or unreliable at scale.
- Problem setting: Connected measurement graphs permit exact angle recovery up to one additive phase, whereas disconnected components leave their relative offsets undetermined.A spanning tree allows sequential recovery when all offsets are exact.
- Measurement model: The model separates good edges, whose offsets equal θ_i−θ_j, from bad edges drawn uniformly on [0, 2π), without revealing which measurements are reliable.Small discretization error in good offsets is acknowledged but omitted from the main model.
- Existing objectives: Least squares is efficient for small Gaussian errors but can be dominated by outlier equations, motivating methods more robust to a large bad-measurement proportion.Tree-based integration is also sensitive because measurement errors accumulate along the selected spanning tree.
- Existing objectives: Maximum likelihood minimizes self-consistency violations or a smooth penalty, but its non-convex optimization is impractical for large n.The penalized formulation is equivalent to maximizing likelihood under a different probabilistic error model.
- Proposed estimators: The paper introduces an eigenvector estimator that constructs a Hermitian matrix, computes its top eigenvector, and normalizes its components into angle estimates.Hermitian structure ensures real eigenvalues; the top eigenvector is obtained by maximal eigenvalue.
- Proposed estimators: A second estimator uses a complex Hermitian semidefinite relaxation, with angles rounded from its normalized top eigenvector similarly to the spectral method.Its formulation is compared with the Goemans–Williamson relaxation for weighted maximum cut.
- Performance and analysis: The eigenvector and SDP methods have comparable numerical accuracy, while the eigenvector method is faster and numerically stable when the spectral gap is large.The paper analyzes the eigenvector method on complete and small-world graphs using random matrix theory.
- Performance and analysis: For complete graphs, non-trivial correlation appears when the good-measurement proportion exceeds 1/n, and correlation approaches 1 as np^2 grows.The paper also claims asymptotic near-optimality relative to the information-theoretic Shannon bound, up to a discretization-dependent factor.
2. The Eigenvector Method.
The eigenvector method encodes offset consistency in a Hermitian matrix and estimates angles from its normalized top eigenvector. Power iteration efficiently integrates consistency information across graph cycles, while random outlier contributions largely cancel.
- Matrix construction: The method begins by forming an n × n Hermitian matrix H from the measured offsets.The relation Hij = ¯Hji ensures H∗ = H.
- Outlier robustness: For the correct angles, good edges contribute coherently, whereas uniformly random outliers contribute only O(√mbad) through cancellation.Thus, outlier influence grows by a square-root scale rather than linearly with the number of bad edges.
- Spectral relaxation: The non-convex unit-magnitude constraints are relaxed to the single constraint ∥z∥2 = n.This produces a quadratic-form maximization problem.
- Angle estimation: The relaxed maximizer is the normalized top eigenvector v1 satisfying Hv1 = λ1v1, after which its components are normalized to estimate the angles.The components of v1 need not themselves have unit magnitude.
- Computation: Power iteration computes the top eigenvector through repeated matrix-vector multiplication, costing O(n^2) for dense matrices and O(m) for sparse matrices per iteration.The required iteration count decreases with the spectral gap.
- Cycle consistency: Matrix powers integrate consistency relations from triangles and longer cycles, so the top eigenvector incorporates cycle information globally.Triplet consistency appears in H^2, while higher powers exploit longer cycles.
3. The semidefinite program approach.
The semidefinite-program approach relaxes the rank-one formulation while retaining convex constraints and unit diagonal entries. Although it explicitly enforces unit magnitudes, it performs similarly to the eigenvector method, which is preferred for large-scale problems because it is faster.
- SDP formulation: The objective can be reformulated using a Hermitian semidefinite matrix Θ with unit diagonal entries Θii = 1.The unit-diagonal constraints encode unit magnitudes for the angle variables.
- Convex relaxation: Dropping the non-convex rank-one constraint yields a natural semidefinite relaxation over complex-valued Hermitian matrices.The remaining constraints are convex.
- Relation to maximum cut: The SDP is almost identical to the Goemans-Williamson maximum-cut relaxation, differing in its use of complex-valued Hermitian rather than real symmetric matrices.The corresponding estimator is obtained from a best rank-one approximation.
- Comparison: The eigenvector and SDP methods give similar numerical results, but the eigenvector method is much faster and is preferred for large-scale problems.The SDP’s explicit unit-magnitude constraint does not yield a practical advantage in the reported experiments.
4. Connections with random matrix theory and spectral graph theory.
The analysis models the measurement matrix as a low-rank signal plus random noise, connecting eigenvalue behavior to angle-recovery accuracy. It derives spectral thresholds and validates them numerically for complete and small-world graphs.
- The Hermitian matrix H is decomposed into its expected rank-one signal and a zero-mean random matrix R.This decomposition enables random-matrix analysis of the synchronization estimator.
- In the complete-graph model, R follows Wigner’s semicircle behavior, with its largest eigenvalue concentrated near the spectrum’s right edge.The perturbation H = npzz* + R determines whether the signal eigenvalue separates from the noise spectrum.
- The top eigenvector becomes informative when the spectral gap between H’s leading eigenvalue and R’s leading eigenvalue is sufficiently large.Under this condition, the top eigenvector correlates strongly with the true angle vector z.
- For sufficiently many measurements, recovery remains successful even at small good-edge probability, provided np^2 is large enough.As np^2 grows, the angle between the estimated and true vectors approaches zero and their correlation approaches 1.
- For n = 400, the observed correlation was ρ1 = 0.97 when 85% of offset measurements were outliers.The experiments also report agreement between predicted and observed leading eigenvalues.
- In small-world graphs, multiple large eigenvalues reflect spherical-harmonic structure, while experimental correlation jumps occur near predicted threshold values.The eigenvector method is slightly less accurate than SDP but runs faster in the reported comparison.
5. Information Theoretic Analysis.
The section compares polynomial-time eigenvector recovery with information-theoretic limits for discretized angular synchronization. It shows near-optimality up to a discretization-dependent factor while distinguishing correlation from exact angle recovery.
- The eigenvector threshold is asymptotically within a multiplicative factor of the optimal recovery threshold, depending on discretization resolution but not n or m.The method becomes less optimal as angular resolution improves.
- The information-theoretic lower bound uses conditional entropy and converse theorems to constrain the probability of recovering all angles.The measurement graph must typically have at least n log n edges for connectivity with high probability.
- Information theory rules out accurate recovery below a threshold probability for every decoding algorithm, including maximum likelihood.The converse bounds apply beyond the eigenvector method.
- Non-trivial correlation of the top eigenvector with the true angles can occur below the information-theoretic exact-recovery bound without implying that all angles are recovered correctly.The paper distinguishes approximate correlation from exact decoding.
- For small modulo values, specifically L ≤6, the eigenvector method is regarded as highly successful for recovering offset equations.The paper notes that larger L creates a wider gap between eigenvector and exhaustive maximum-likelihood thresholds.
6. Connection with Max-2-Lin mod L and Unique Games.
The angular synchronization problem is a Max-2-Lin mod L instance when offsets are discretized, linking the recovery task to unique games and SDP-based approximation. The paper places its formulation among related approximation algorithms and complexity results.
- Discretized equations θ_i−θ_j = δ_ij mod L are exactly Max-2-Lin mod L constraints with two variables per equation.Max-2-Lin mod L seeks to maximize the number of satisfied modular linear equations.
- The paper relates its SDP formulation to prior SDP algorithms for Max-2-Lin mod L and unique games, whose guarantees depend on the domain size L.Related formulations use an nL × nL inner-products matrix and distinct rounding procedures.
- Each offset constraint is a bijection between the values of its two variables, making the problem an instance of unique games.For every value of θ_i, exactly one θ_j satisfies the offset constraint.
- Unique Games Conjecture results imply hardness of satisfying more than a small fraction of constraints when only a 1−ε fraction is satisfiable.The cited algorithms are described as near optimal if the conjecture holds.
- The paper presents eigenvector synchronization as a method that extends beyond angular recovery to synchronization over other group structures.This broader perspective connects the angular problem to the general group-synchronization framework.
7. Summary and Further Applications.
The paper concludes that eigenvector and SDP approaches support synchronization beyond SO(2), including partial-information and non-compact-group settings. It illustrates these extensions for SO(3) structure recovery and real-valued clock synchronization.
- In the general group setting, triplet consistency is expressed through products of measured ratios equaling the identity element.The identity element is denoted by e.
- For compact groups with matrix representations, a block Hermitian measurement matrix supports estimation from its top eigenvectors or an SDP solution.The block entries encode measured group ratios or zero when no direct measurement exists.
- The methods can operate with partial group-ratio information, including SO(3) recovery from common lines in cryo-electron microscopy.The paper also identifies applications in molecular structure, NMR distance geometry, and sensor-network localization.
- The eigenvector method can be applied to non-compact groups after compactification, illustrated by mapping real-valued time differences to the unit circle.The frequency parameter must balance sensitivity to small errors against suppression of large outliers.
- Under the compactified clock model, good measurements contribute approximately 1 to the synchronization matrix while bad measurements are uniformly distributed on the unit circle.This preserves the eigenvector method’s separation between informative measurements and outliers.