Angular synchronization by eigenvectors and semidefinite programming

被引：253

作者：

Singer, A. ^{[1
,2
]}

机构：

[1] Princeton Univ, Dept Math, Princeton, NJ 08544 USA

[2] Princeton Univ, PACM, Princeton, NJ 08544 USA

来源：

APPLIED AND COMPUTATIONAL HARMONIC ANALYSIS | 2011年 / 30卷 / 01期

基金：

美国国家科学基金会;

关键词：

IMPROVED APPROXIMATION ALGORITHMS; LARGEST EIGENVALUE; CUT; MATRICES; EDGE;

D O I：

10.1016/j.acha.2010.02.001

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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

引用

页码：20 / 36

页数：17

共 42 条

[11]

Feige U., 1992, Proceedings of the Twenty-Fourth Annual ACM Symposium on the Theory of Computing, P733, DOI 10.1145/129712.129783

[12] The largest eigenvalue of rank one deformation of large Wigner matrices [J].

Feral, Delphine ;

Peche, Sandrine .

COMMUNICATIONS IN MATHEMATICAL PHYSICS, 2007, 272 (01) :185-228

[13]

Frank J., 2006, Three-dimensional electron microscopy of macromolecular assemblies: visualization of biological molecules in their native state

[14] A METHOD FOR ENFORCING INTEGRABILITY IN SHAPE FROM SHADING ALGORITHMS [J].

FRANKOT, RT ;

CHELLAPPA, R .

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 1988, 10 (04) :439-451

[15] Improved approximation algorithms for MAX k-CUT and MAX BISECTION [J].

Frieze, A ;

Jerrum, M .

ALGORITHMICA, 1997, 18 (01) :67-81

[16] THE EIGENVALUES OF RANDOM SYMMETRIC-MATRICES [J].

FUREDI, Z ;

KOMLOS, J .

COMBINATORICA, 1981, 1 (03) :233-241

[17]

Gallager R. G., 1968, Information Theory and Reliable Communication, V2

[18] Distributed clock synchronization over wireless networks: Algorithms and analysis [J].

Giridhar, Arvind ;

Kumar, P. R. .

PROCEEDINGS OF THE 45TH IEEE CONFERENCE ON DECISION AND CONTROL, VOLS 1-14, 2006, :4915-4915

[19] Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming [J].

Goemans, MX ;

Williamson, DP .

JOURNAL OF THE ACM, 1995, 42 (06) :1115-1145

[20]

Goemans MX, 2001, P 33 ANN ACM S THEOR, P443, DOI [10.1016/j.jcss.2003.07.012, DOI 10.1016/J.JCSS.2003.07.012]

← 1 2 3 4 5 →