Eigenvector synchronization, graph rigidity and the molecule problem

DOI10.1093/IMAIAI/IAS002MaRDI QIDQ2869799zbMATH OpenOpenAlexWikidataFDO

Authors Mihai Cucuringu, A. Singer, David Cowburn

Publication date 6 January 2014

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

Full work available at URL https://arxiv.org/abs/1111.3304, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.387.6835

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)

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.

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

Cited in

(28)

• Spectral conditions for graph rigidity in the Euclidean plane
• Global registration of multiple point clouds using semidefinite programming
• Dynamic angular synchronization under smoothness constraints
• scientific article; zbMATH DE number 7370536 (Why is no real title available?)
• Rigid graph compression: motif-based rigidity analysis for disordered fiber networks
• Sparsification of the regularized magnetic Laplacian with multi-type spanning forests
• Diagonally dominant programming in distance geometry
• Lagrangian duality in complex pose graph optimization
• Orthogonal Trace-Sum Maximization: Tightness of the Semidefinite Relaxation and Guarantee of Locally Optimal Solutions
• Rigidity percolation in disordered 3D rod systems
• Barvinok's naive algorithm in distance geometry
• Spectral radius conditions for the rigidity of graphs
• A remark on global positioning from local distances
• Graph connection Laplacian and random matrices with random blocks
• Multi-dimensional scaling from \(K\)-nearest neighbourhood distances
• Near-optimal bounds for phase synchronization
• An extension of the angular synchronization problem to the heterogeneous setting
• ASAP: an eigenvector synchronization algorithm for the graph realization problem
• Non-degenerate rigid alignment in a patch framework
• Embedding Riemannian manifolds by the heat kernel of the connection Laplacian
• Graph connection Laplacian methods can be made robust to noise
• A survey and evaluation of graph realization algorithms
• Concentration of the Kirchhoff index for Erdős-Rényi graphs
• Group synchronization on grids
• Local2global: a distributed approach for scaling representation learning on graphs
• Nonconvex landscapes for \(\mathbf{Z}_2\) synchronization and graph clustering are benign near exact recovery thresholds
• A unified approach to synchronization problems over subgroups of the orthogonal group
• A survey of structure from motion

Describes a project that uses

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)