A CHEEGER INEQUALITY FOR THE GRAPH CONNECTION LAPLACIAN
Author(s): Bandeira, Afonso S; Singer, Amit; Spielman, Daniel A
DownloadTo refer to this page use:
http://arks.princeton.edu/ark:/88435/pr14q7z| Abstract: | The O(d) synchronization problem consists of estimating a set of n unknown orthogonal d x d matrices O-1,..., O-n from noisy measurements of a subset of the pairwise ratios OiOj-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. |
| Publication Date: | 2013 |
| Electronic Publication Date: | 5-Dec-2013 |
| Citation: | Bandeira, Afonso S, Singer, Amit, Spielman, Daniel A. (2013). A CHEEGER INEQUALITY FOR THE GRAPH CONNECTION LAPLACIAN. SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 34 (1611 - 1630. doi:10.1137/120875338 |
| DOI: | doi:10.1137/120875338 |
| ISSN: | 0895-4798 |
| EISSN: | 1095-7162 |
| Pages: | 1611 - 1630 |
| Type of Material: | Journal Article |
| Journal/Proceeding Title: | SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS |
| Version: | Final published version. Article is made available in OAR by the publisher's permission or policy. |
Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.