The celebrated Cheeger's Inequality \cite{am85,a86} establishes a bound on
the expansion of a graph via its spectrum. This inequality is central to a rich
spectral theory of graphs, based on studying the eigenvalues and eigenvectors
of the adjacency matrix (and other related matrices) of graphs. It has remained
open to define a suitable spectral model for hypergraphs whose spectra can be
used to estimate various combinatorial properties of the hypergraph.
In this paper we introduce a new hypergraph Laplacian operator (generalizing
the Laplacian matrix of graphs)and study its spectra. We prove a Cheeger-type
inequality for hypergraphs, relating the second smallest eigenvalue of this
operator to the expansion of the hypergraph. We bound other hypergraph
expansion parameters via higher eigenvalues of this operator. We give bounds on
the diameter of the hypergraph as a function of the second smallest eigenvalue
of the Laplacian operator. The Markov process underlying the Laplacian operator
can be viewed as a dispersion process on the vertices of the hypergraph that
might be of independent interest. We bound the {\em Mixing-time} of this
process as a function of the second smallest eigenvalue of the Laplacian
operator. All these results are generalizations of the corresponding results
for graphs.
We show that there can be no linear operator for hypergraphs whose spectra
captures hypergraph expansion in a Cheeger-like manner. For any $k$, we give a
polynomial time algorithm to compute an approximation to the $k^{th}$ smallest
eigenvalue of the operator. We show that this approximation factor is optimal
under the SSE hypothesis (introduced by \cite{rs10}) for constant values of
$k$.
Finally, using the factor preserving reduction from vertex expansion in
graphs to hypergraph expansion, we show that all our results for hypergraphs
extend to vertex expansion in graphs.

本文引入了一种新的超图拉普拉斯算子，并研究了其光谱。通过该算子的第二小本征值，证明了超图的扩展性和混合时间，并进一步将这些结果推广到了图的节点扩展。

超图马尔可夫算子、特征值和近似算法

Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms

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.

本篇论文通过提出 Cheeger 不等式，利用操作符与图连接拉普拉斯的特征值关系来解决 O (d) 同步问题，并为其频谱方法提供最坏情况下的性能保证。