| Angular Synchronization by Eigenvectors and Semidefinite Programming. | |
| | |
MedLine Citation:
|
PMID: 21179593 Owner: NLM Status: Publisher |
Abstract/OtherAbstract:
|
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. |
| | |
Authors:
|
A Singer |
Related Documents
:
|
16629403 - The relation between dimensions of attachment and internalizing or externalizing proble... 3389703 - Port-wine stain--a surgical and psychological problem. 8481743 - The adult adjustment of offspring of parents with drinking problems. |
Publication Detail:
|
Type: JOURNAL ARTICLE |
Journal Detail:
|
Title: Applied and computational harmonic analysis Volume: 30 ISSN: 1096-603X ISO Abbreviation: - Publication Date: 2011 Jan |
Date Detail:
|
Created Date: 2010-12-23 Completed Date: - Revised Date: - |
Medline Journal Info:
|
Nlm Unique ID: 101525593 Medline TA: Appl Comput Harmon Anal Country: - |
Other Details:
|
Languages: ENG Pagination: 20-36 Citation Subset: - |
Affiliation:
|
Department of Mathematics and PACM, Princeton University, Fine Hall, Washington Road, Princeton NJ 08544-1000 USA, amits@math.princeton.edu. |
Export Citation:
|
APA/MLA Format Download EndNote Download BibTex |
| MeSH Terms | |
Descriptor/Qualifier:
|
|
| Grant Support | |
ID/Acronym/Agency:
|
R01 GM090200-01//NIGMS NIH HHS |
From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine
Previous Document: Variable Selection for Qualitative Interactions.
Next Document: The role of pramipexole in a severe Parkinson's disease model in mice.