A cheeger inequality for the graph connection laplacian

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

Research output: Contribution to journalArticlepeer-review


The O(d) synchronization problem consists of estimating a set of n unknown orthogonal d × d matrices O1, ... , On from noisy measurements of a subset of the pairwise ratios OiO-1j . 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.

Original languageEnglish (US)
Pages (from-to)1611-1630
Number of pages20
JournalSIAM Journal on Matrix Analysis and Applications
Issue number4
StatePublished - 2013


  • Cheeger inequality
  • Graph connection Laplacian
  • O(d) synchronization
  • Vector diffusion maps

ASJC Scopus subject areas

  • Analysis


Dive into the research topics of 'A cheeger inequality for the graph connection laplacian'. Together they form a unique fingerprint.

Cite this