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