TY - JOUR
T1 - Eigenvector synchronization, graph rigidity and the molecule problem
AU - Cucuringu, Mihai
AU - Singer, Amit
AU - Cowburn, David
N1 - Funding Information:
This work was supported by the National Institute of General Medical Sciences (grant number R01GM090200 to M. C. and A. S.), the Air Force Office of Scientific Research (grant number FA9550-09-1-0551 to M. C. and A. S.), and by the Alfred P. Sloan Foundation (to A.S). The authors would like to thank Yinyu Ye for useful discussions on rigidity theory and for sharing the FULL-SDP and SNL-SDP code, and the anonymous reviewers for their valuable comments and suggestions to improve this manuscript.
Funding Information:
This work was supported by the National Institute of General Medical Sciences (grant number R01GM090200 to M. C. and A. S.), the Air Force Office of Scientific Research (grant number FA9550-09-1-0551 to M. C. and A. S.), and by the Alfred P. Sloan Foundation (to A.S).
Publisher Copyright:
© The authors 2012.
PY - 2012/12/1
Y1 - 2012/12/1
N2 - The graph realization problem has received a great deal of attention in recent years, due to its importance in applications such as wireless sensor networks and structural biology. In this paper, we extend the previous work and propose the 3D-As-Synchronized-As-Possible (3D-ASAP) algorithm, for the graph realization problem in R3, given a sparse and noisy set of distance measurements. 3D-ASAP is a divide and conquer, non-incremental and non-iterative algorithm, which integrates local distance information into a global structure determination. Our approach starts with identifying, for every node, a subgraph of its 1-hop neighborhood graph, which can be accurately embedded in its own coordinate system. In the noise-free case, the computed coordinates of the sensors in each patch must agree with their global positioning up to some unknown rigid motion, that is, up to translation, rotation and possibly reflection. In other words, to every patch, there corresponds an element of the Euclidean group, Euc(3), of rigid transformations in R3, and the goal was to estimate the group elements that will properly align all the patches in a globally consistent way. Furthermore, 3D-ASAP successfully incorporates information specific to the molecule problem in structural biology, in particular information on known substructures and their orientation. In addition, we also propose 3D-spectral-partitioning (SP)-ASAP, a faster version of 3D-ASAP, which uses a spectral partitioning algorithm as a pre-processing step for dividing the initial graph into smaller subgraphs. Our extensive numerical simulations show that 3D-ASAP and 3D-SP-ASAP are very robust to high levels of noise in the measured distances and to sparse connectivity in the measurement graph, and compare favorably with similar state-of-the-art localization algorithms.
AB - The graph realization problem has received a great deal of attention in recent years, due to its importance in applications such as wireless sensor networks and structural biology. In this paper, we extend the previous work and propose the 3D-As-Synchronized-As-Possible (3D-ASAP) algorithm, for the graph realization problem in R3, given a sparse and noisy set of distance measurements. 3D-ASAP is a divide and conquer, non-incremental and non-iterative algorithm, which integrates local distance information into a global structure determination. Our approach starts with identifying, for every node, a subgraph of its 1-hop neighborhood graph, which can be accurately embedded in its own coordinate system. In the noise-free case, the computed coordinates of the sensors in each patch must agree with their global positioning up to some unknown rigid motion, that is, up to translation, rotation and possibly reflection. In other words, to every patch, there corresponds an element of the Euclidean group, Euc(3), of rigid transformations in R3, and the goal was to estimate the group elements that will properly align all the patches in a globally consistent way. Furthermore, 3D-ASAP successfully incorporates information specific to the molecule problem in structural biology, in particular information on known substructures and their orientation. In addition, we also propose 3D-spectral-partitioning (SP)-ASAP, a faster version of 3D-ASAP, which uses a spectral partitioning algorithm as a pre-processing step for dividing the initial graph into smaller subgraphs. Our extensive numerical simulations show that 3D-ASAP and 3D-SP-ASAP are very robust to high levels of noise in the measured distances and to sparse connectivity in the measurement graph, and compare favorably with similar state-of-the-art localization algorithms.
KW - Conquer
KW - Distance geometry
KW - Divide
KW - Eigenvectors
KW - Graph realization
KW - Rigidity theory
KW - SDP
KW - Spectral graph theory
KW - Synchronization
KW - The molecule problem
UR - http://www.scopus.com/inward/record.url?scp=84892391966&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84892391966&partnerID=8YFLogxK
U2 - 10.1093/imaiai/ias002
DO - 10.1093/imaiai/ias002
M3 - Article
C2 - 24432187
AN - SCOPUS:84892391966
SN - 2049-8772
VL - 1
SP - 21
EP - 67
JO - Information and Inference
JF - Information and Inference
IS - 1
ER -