随机算法 (Fall 2011)/The Spectral Gap

From EtoneWiki
Jump to: navigation, search

Cheeger's Inequality

One of the most exciting results in spectral graph theory is the following theorem which relate the graph expansion to the spectral gap.

Theorem (Cheeger's inequality)
Let be a -regular graph with spectrum . Then

The theorem was first stated for Riemannian manifolds, and was proved by Cheeger and Buser (for different directions of the inequalities). The discrete case is proved independently by Dodziuk and Alon-Milman.

For a -regular graph, the quantity is called the spectral gap. The name is due to the fact that it is the gap between the first and the second largest eigenvalues of a graph.

If we write (sometimes it is called the normalized spectral gap), the Cheeger's inequality is turned into a nicer form:

or equivalently .

Optimization Characterization of Eigenvalues

Theorem (Rayleigh-Ritz theorem)
Let be a symmetric matrix. Let be the eigen values of and be the corresponding eigenvectors. Then
and
Proof.

Without loss of generality, we may assume that are orthonormal eigen-basis. Then it holds that

,

thus we have .

Let be an arbitrary vector and let be its normalization. Since are orthonormal basis, can be expressed as . Then

Therefore, . Altogether we have

It is similar to prove . In the first part take to show that ; and in the second part take an arbitrary and . Notice that , thus with .

The Rayleigh-Ritz Theorem is a special case of a fundamental theorem in linear algebra, called the Courant-Fischer theorem, which characterizes the eigenvalues of a symmetric matrix by a series of optimizations:

Theorem (Courant-Fischer theorem)
Let be a symmetric matrix with eigenvalues . Then

Graph Laplacian

Let be a -regular graph of vertices and let be its adjacency matrix. We define to be the Laplacian of the graph . Take as a distribution over vertices, its Laplacian quadratic form measures the "smoothness" of over the graph topology, just as what the Laplacian operator does to the differentiable functions.

Laplacian Property
For any vector , it holds that
.
Proof.

On the other hand,

Applying the Rayleigh-Ritz theorem to the Laplacian matrix of the graph, we have the following "variational characterization" of the spectral gap .

Theorem (Variational Characterization)
Let be a -regular graph of vertices. Suppose that its adjacency matrix is , whose eigenvalues are . Let be the Laplacian matrix. Then
Proof.

For -regular graph, we know that and , thus is the eigenvector of . Due to Rayleigh-Ritz Theorem, it holds that . Then

We know it holds for the graph Laplacian that . So the variational characterization of the second eigenvalue of graph is proved.

Proof of Cheeger's Inequality

We will first give an informal explanation why Cheeger's inequality holds.

Recall that the expansion is defined as

Let be the characteristic vector of the set such that

It is easy to see that

Thus, the expansion can be expressed algebraically as

On the other hand, due to the variational characterization of the spectral gap, we have

We can easily observe the similarity between the two formulas. Both the expansion ration and the spectral gap can be characterized by optimizations of the same objective function over different domains (for the spectral gap, the optimization is over all ; and for the expansion ratio, it is over all such vectors with at most many 1-entries).


Notations

Throughout the proof, we assume that is the -regular graph of vertices, is the adjacency matrix, whose eigenvalues are , and is the graph Laplacian.

Large spectral gap implies high expansion

Cheeger's inequality (lower bound)
Proof.

Let , , be the vertex set achieving the optimal expansion ratio , and be a vector defined as

Clearly, , thus .

Due to the variational characterization of the second eigenvalue,

High expansion implies large spectral gap

We next prove the upper bound direction of the Cheeger's inequality:

Cheeger's inequality (upper bound)

This direction is harder than the lower bound direction. But it is mathematically more interesting and also more useful to us for analyzing the mixing time of random walks.

We prove the following equivalent inequality:

Let satisfy that

  • , i.e., it is a eigenvector for ;
  • , i.e., has at most positive entries. (We can always choose to be if this is not satisfied.)

And let nonnegative vector be defined as

We then prove the following inequalities:

  1. ;
  2. .

The theorem is then a simple consequence by combining these two inequalities.

We prove the first inequality:

Lemma
.
Proof.

If , then

Then

which proves the lemma.

We then prove the second inequality:

Lemma
.
Proof.

To prove this, we introduce a new quantity and shows that

.

This will give us the desired inequality .

Lemma
.
Proof.

By the Cauchy-Schwarz Inequality,

By the Laplacian property, the first term . By the Inequality of Arithmetic and Geometric Means, the second term

Combining them together, we have

.
Lemma
.
Proof.

Suppose that has nonzero entries. We know that due to the definition of . We enumerate the vertices such that

.

Then

We have the following universal equation for sums:

Notice that , which is at most since . Therefore, combining these together, we have