A Cheeger Inequality for the Graph Connection Laplacian

DOI10.1137/120875338zbMATH Open1287.05081OpenAlexW2008590575MaRDI QIDQ5413664FDOQ5413664

Authors Afonso S. Bandeira, A. Singer, Daniel A. Spielman 

Publication date 30 April 2014

Published in SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

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

zbMATH Keywords

graph connection LaplacianCheeger inequalityvector diffusion maps\(O(d)\) synchronization

Mathematics Subject Classification ID

Quadratic programming (90C20) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Programming involving graphs or networks (90C35) Numerical methods of relaxation type (49M20)

Abstract: The O(d) Synchronization problem consists of estimating a set of unknown orthogonal transformations O_i from noisy measurements of a subset of the pairwise ratios O_iO_j^{-1}. We formulate and prove a Cheeger-type inequality that relates a measure of how well it is possible to solve the O(d) synchronization problem with the spectra of an operator, the graph Connection Laplacian. We also show how this inequality provides a worst case performance guarantee for a spectral method to solve this problem.

Recommendations

• scientific article; zbMATH DE number 878889
• Cheeger inequalities for unbounded graph Laplacians
• Laplacians and the Cheeger inequality for directed graphs
• General Cheeger inequalities for \(p\)-Laplacians on graphs
• On Cheeger inequalities of a graph
• A Cheeger inequality for graphs based on a reflection principle
• Cheeger‐like inequalities for the largest eigenvalue of the graph Laplace operator
• On Cheeger-type inequalities for weighted graphs
• An inequality on Laplacian eigenvalues of connected graphs.
• Cheeger inequalities for general edge-weighted directed graphs

Cited In (44)

• Expansion in matrix-weighted graphs
• Title not available (Why is no real title available?)
• Phase retrieval from local measurements: improved robustness via eigenvector-based angular synchronization
• Optimization via low-rank approximation for community detection in networks
• Spectral convergence of the connection Laplacian from random samples
• A local clustering algorithm for connection graphs
• On recovery guarantees for angular synchronization
• Distributed methods for synchronization of orthogonal matrices over graphs
• Ranking and sparsifying a connection graph
• The geometry of synchronization problems and learning group actions
• Lagrangian duality in complex pose graph optimization
• Partitions of networks that are robust to vertex permutation dynamics
• Random Laplacian matrices and convex relaxations
• Random walks, conductance, and resistance for the connection graph Laplacian
• From intrinsic optimization to iterated extended Kalman filtering on Lie groups
• Toward a spectral theory of cellular sheaves
• Graph connection Laplacian and random matrices with random blocks
• Curvature and higher order Buser inequalities for the graph connection Laplacian
• Stable optimizationless recovery from phaseless linear measurements
• The diffusion geometry of fibre bundles: horizontal diffusion maps
• Near-optimal performance bounds for orthogonal and permutation group synchronization via spectral methods
• Deformed Laplacians and spectral ranking in directed networks
• Alternating projection, ptychographic imaging and phase synchronization
• The noise-sensitivity phase transition in spectral group synchronization over compact groups
• Nonconvex phase synchronization
• A Schur complement Cheeger inequality
• Approximating the little Grothendieck problem over the orthogonal and unitary groups
• Kazdan-Warner equation on infinite graphs
• Benign landscapes of low-dimensional relaxations for orthogonal synchronization on general graphs
• Group synchronization on grids
• On Cheeger-type inequalities for weighted graphs
• A unified approach to synchronization problems over subgroups of the orthogonal group
• Robust Phase Retrieval Algorithm for Time-Frequency Structured Measurements
• Frustration and isoperimetric inequalities for signed graphs
• Frustration index and Cheeger inequalities for discrete and continuous magnetic Laplacians
• Hermitian Laplacians and a Cheeger Inequality for the Max-2-Lin Problem
• Magnetic-sparseness and Schrödinger operators on graphs
• An isoperimetric constant for signed graphs
• Magnetic eigenmaps for the visualization of directed networks
• Title not available (Why is no real title available?)
• Global registration of multiple point clouds using semidefinite programming
• Non-unique games over compact groups and orientation estimation in cryo-EM
• Solving jigsaw puzzles by the graph connection Laplacian
• Tightness of the maximum likelihood semidefinite relaxation for angular synchronization

This page was built for publication: A Cheeger Inequality for the Graph Connection Laplacian

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