A cheeger inequality for the graph connection laplacian

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

doi:10.1137/120875338

A cheeger inequality for the graph connection laplacian

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

Research output: Contribution to journal › Article › peer-review

62 Scopus citations

Abstract

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 O_iO^-1_j . 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 language	English (US)
Pages (from-to)	1611-1630
Number of pages	20
Journal	SIAM Journal on Matrix Analysis and Applications
Volume	34
Issue number	4
DOIs	https://doi.org/10.1137/120875338
State	Published - 2013

All Science Journal Classification (ASJC) codes

Analysis

Keywords

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

Access to Document

10.1137/120875338

Cite this

@article{de20852c77bb470b9bad7101eae3f277,

title = "A cheeger inequality for the graph connection laplacian",

abstract = "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.",

keywords = "Cheeger inequality, Graph connection Laplacian, O(d) synchronization, Vector diffusion maps",

author = "Bandeira, {Afonso S.} and Amit Singer and Spielman, {Daniel A.}",

year = "2013",

doi = "10.1137/120875338",

language = "English (US)",

volume = "34",

pages = "1611--1630",

journal = "SIAM Journal on Matrix Analysis and Applications",

issn = "0895-4798",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "4",

}

TY - JOUR

T1 - A cheeger inequality for the graph connection laplacian

AU - Bandeira, Afonso S.

AU - Singer, Amit

AU - Spielman, Daniel A.

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

KW - Cheeger inequality

KW - Graph connection Laplacian

KW - O(d) synchronization

KW - Vector diffusion maps

UR - http://www.scopus.com/inward/record.url?scp=84892418594&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84892418594&partnerID=8YFLogxK

U2 - 10.1137/120875338

DO - 10.1137/120875338

M3 - Article

AN - SCOPUS:84892418594

SN - 0895-4798

VL - 34

SP - 1611

EP - 1630

JO - SIAM Journal on Matrix Analysis and Applications

JF - SIAM Journal on Matrix Analysis and Applications

IS - 4

ER -

A cheeger inequality for the graph connection laplacian

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this