Eigenvector synchronization, graph rigidity and the molecule problem

DOI10.1093/IMAIAI/IAS002zbMATH Open1278.05231arXiv1111.3304OpenAlexW3100598149WikidataQ37467373 ScholiaQ37467373MaRDI QIDQ2869799FDOQ2869799

David Cowburn, Mihai Cucuringu, A. Singer

Publication date: 6 January 2014

Published in: Information and Inference (Search for Journal in Brave)

Abstract: 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 on previous work and propose the 3D-ASAP algorithm, for the graph realization problem in $mathbb{R}^3$, 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 $mathbb{R}^3$, and the goal is 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-SP-ASAP, a faster version of 3D-ASAP, which uses a spectral partitioning algorithm as a preprocessing 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 to similar state-of-the art localization algorithms.

Full work available at URL: https://arxiv.org/abs/1111.3304

Recommendations

• ASAP: an eigenvector synchronization algorithm for the graph realization problem
• A survey and evaluation of graph realization algorithms
• A Distributed SDP Approach for Large-Scale Noisy Anchor-Free Graph Realization with Applications to Molecular Conformation
• Localization from incomplete noisy distance measurements
• A remark on global positioning from local distances

zbMATH Keywords

spectral graph theoryeigenvectorssynchronizationdistance geometrydivide and conquergraph realizationrigidity theorySDPthe molecule problem

Mathematics Subject Classification ID

Applications of graph theory (05C90) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Semidefinite programming (90C22) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Molecular structure (graph-theoretic methods, methods of differential topology, etc.) (92E10)

Cited In (21)

• Title not available (Why is that?)
• Orthogonal Trace-Sum Maximization: Tightness of the Semidefinite Relaxation and Guarantee of Locally Optimal Solutions
• Spectral radius conditions for the rigidity of graphs
• Barvinok's naive algorithm in distance geometry
• Multi-dimensional scaling from \(K\)-nearest neighbourhood distances
• Graph connection Laplacian and random matrices with random blocks
• A survey of structure from motion.
• An extension of the angular synchronization problem to the heterogeneous setting
• Diagonally Dominant Programming in Distance Geometry
• Lagrangian Duality in Complex Pose Graph Optimization
• Embedding Riemannian manifolds by the heat kernel of the connection Laplacian
• Rigid Graph Compression: Motif-Based Rigidity Analysis for Disordered Fiber Networks
• Graph connection Laplacian methods can be made robust to noise
• Global Registration of Multiple Point Clouds Using Semidefinite Programming
• Local2global: a distributed approach for scaling representation learning on graphs
• Group synchronization on grids
• Concentration of the Kirchhoff index for Erdős-Rényi graphs
• A unified approach to synchronization problems over subgroups of the orthogonal group
• Rigidity Percolation in Disordered 3D Rod Systems
• Near-Optimal Bounds for Phase Synchronization
• Spectral conditions for graph rigidity in the Euclidean plane

Uses Software

• DISCO

This page was built for publication: Eigenvector synchronization, graph rigidity and the molecule problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2869799)