A Cheeger Inequality for the Graph Connection Laplacian
From MaRDI portal
Publication:5413664
DOI10.1137/120875338zbMATH Open1287.05081arXiv1204.3873OpenAlexW2008590575MaRDI 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)
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.
Full work available at URL: https://arxiv.org/abs/1204.3873
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
Quadratic programming (90C20) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Programming involving graphs or networks (90C35) Numerical methods of relaxation type (49M20)
Cited In (44)
- Expansion in matrix-weighted graphs
- Title not available (Why is that?)
- 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
- On recovery guarantees for angular synchronization
- Distributed methods for synchronization of orthogonal matrices over graphs
- Title not available (Why is that?)
- The geometry of synchronization problems and learning group actions
- 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
- A Local Clustering Algorithm for Connection Graphs
- Toward a spectral theory of cellular sheaves
- Graph connection Laplacian and random matrices with random blocks
- Stable optimizationless recovery from phaseless linear measurements
- The diffusion geometry of fibre bundles: horizontal diffusion maps
- Ranking and Sparsifying a Connection Graph
- Lagrangian Duality in Complex Pose Graph Optimization
- 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
- Solving Jigsaw Puzzles by the Graph Connection Laplacian
- 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
- Curvature and Higher Order Buser Inequalities for the Graph Connection Laplacian
- An isoperimetric constant for signed graphs
- Magnetic eigenmaps for the visualization of directed networks
- Title not available (Why is that?)
- Global registration of multiple point clouds using semidefinite programming
- Non-unique games over compact groups and orientation estimation in cryo-EM
- 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)
