ASAP: An Eigenvector Synchronization Algorithm for the Graph Realization Problem

Mihai Cucuringu ()
Additional contact information
Mihai Cucuringu: Princeton University, PACM

Chapter Chapter 10 in Distance Geometry, 2013, pp 177-195 from Springer

Abstract: Abstract We review a recent algorithm for localization of points in Euclidean space from a sparse and noisy subset of their pairwise distances. Our approach starts by extracting and embedding uniquely realizable subsets of neighboring sensors called patches. In the noise-free case, each patch agrees with its global positioning up to an unknown rigid motion of translation, rotation, and possibly reflection. The reflections and rotations are estimated using the recently developed eigenvector synchronization algorithm, while the translations are estimated by solving an overdetermined linear system. In other words, to every patch, there corresponds an element of the Euclidean group Euc(3) of rigid transformations in $${\mathbb{R}}^{3}$$ , and the goal is to estimate the group elements that will properly align all the patches in a globally consistent way. The algorithm is scalable as the number of nodes increases, and can be implemented in a distributed fashion. Extensive numerical experiments show that it compares favorably to other existing algorithms in terms of robustness to noise, sparse connectivity and running time.

Keywords: Graph realization problem; Sensor networks; Molecule problem; Distance geometry; Eigenvectors; Synchronization; Rigidity theory; Spectral graph theory (search for similar items in EconPapers)
Date: 2013
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4614-5128-0_10

Ordering information: This item can be ordered from
http://www.springer.com/9781461451280

DOI: 10.1007/978-1-4614-5128-0_10

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().