A Cheeger Inequality for the Graph Connection Laplacian

2012/04/17 by Bandeira, Afonso S., Singer, Amit, Spielman, Daniel A. · 3 citations
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Spectral Theory (math.SP)

paper · doi:10.48550/arxiv.1204.3873

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.

Cited by

• Learning the Structure of Connection Graphs
• Global Synchronization in Matrix-Weighted Networks
• Powers of Magnetic Graph Matrix: Fourier Spectrum, Walk Compression, and Applications

Related

• A Class of Optimal Directed Graphs for Network Synchronization
• Cheeger inequalities for unbounded graph Laplacians
• Cheeger Inequalities for Submodular Transformations
• Improved Cheeger's Inequality: Analysis of Spectral Partitioning Algorithms through Higher Order Spectral Gap
• A Generalized Cheeger Inequality