Angular Synchronization by Eigenvectors and Semidefinite Programming

By Amit Singer. 2009

433 citations recorded by the source corpus.

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.

Subfields: Computational Mechanics, Computational Theory and Mathematics, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computational Theory and Mathematics

In Signal Processing

Citations in the corpus

SyncSpecCNN: Synchronized Spectral CNN for 3D Shape Segmentation (2016, methodology): “Inspired by the recent work on synchronization [23, 25, 26, 9], we propose to align these different spectral domains using functional map [21].”
Past, Present, and Future of Simultaneous Localization and Mapping: Toward the Robust-Perception Age (2016, neutral): “The most popular spatial-partitioning representation is the so called spatial-occupancy enumeration , which decomposes the 3D space into identical cubes ( voxels ), arranged in a regular 3D grid.”
Moment/Sum-of-Squares Hierarchy for Complex Polynomial Optimization (2015, background): “Multivariate polynomial optimization where variables and data are complex numbers is a non-deterministic polynomial-time hard problem that arises in various applications such as electric power systems (Section 4), imaging science [8, 13, 29, 66], signal processing [1, 6, 18, 45, 48, 49], automatic c”
Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview (2018, methodology): “Examples include low-rank matrix completion [1]–[3], phase retrieval [4], blind deconvolution and self-calibration [5], [6], robust principal component analysis [7], [8], synchronization and alignment [9]–[11], to name just a few.”
Spectral Method and Regularized MLE Are Both Optimal for Top-$K$ Ranking (2017, neutral): “…applied in numerous applications, e.g. matrix completion (Keshavan et al., 2010; Jain et al., 2013), phase retrieval (Candès et al., 2015; Chen and Candès, 2017), graph clustering (Rohe et al., 2011; Chaudhuri et al., 2012), synchronization and joint alignment (Singer, 2011; Chen and Candes, 2016).”
Singular vector and singular subspace distribution for the matrix denoising model (2018, background): “Such a problem arises in many scientific applications such as sparse PCA [68, 74], matrix denoising [25, 27], multiple signal classification (MUSIC) [36, 72], Z2 synchronization [64, 65] and multidimensional scaling [26, 30, 57].”
Distance geometry and data science (2019, neutral): “Circuit diagrams are a necessary design tool for any electrical and electronic circuit (Seshu and Reed 1961).”
Phase recovery, MaxCut and complex semidefinite programming (2012, background): “2 π , for ( i, j ) ∈ S [see Singer, 2011], the key difference between this last problem and the phase recovery problem in (1) is that the sign information is lost in the input to (1).”
Stochastic model-based minimization of weakly convex functions (2018, background): “Nonlinear least squares, phase retrieval [23,30,34], minimization of the Conditional Value-at-Risk [7, 8,60], graph synchronization [2,6,63], covariance estimation [17], and robust principal component analysis [11,14] naturally lead to weakly convex formulations.”
Global Motion Estimation from Point Matches (2012, methodology): “Our formulation is based on recent estimation methods shown in the context of 3D structure determination of macromolecules in cryo-electron microscopy (EM) images [16], [17].”
A Survey on Structure from Motion (2017, background): “The term was originally coined in [63], which studies the problem of estimating planar rotations from measurements of their pairwise ratios.”
Euclidean Distance Geometry and Applications (2012, methodology): “This is addressed using a 3D extension of a spectral technique introduced in [195].”
Bispectrum Inversion with Application to Multireference Alignment (2017, methodology): “Among them are the eigenvector method, SDP relaxation, projected power method, Riemannian optimization and approximate message passing [16], [20], [17], [18], [19].”