Having (non-rigorously) defined the Laplacian operator in manifolds in the previous post, we turn to the proof of the Cheeger inequality in manifolds, which we restate below.
Theorem 1 (Cheeger’s inequality) Let
be an
-dimensional smooth, compact, Riemann manifold without boundary with metric
, let
be the Laplace-Beltrami operator on
, let
be the eigenvalues of
, and define the Cheeger constant of
to be
where the
is the boundary of
,
is the
-dimensional measure, and
is
-th dimensional measure defined using
. Then
We begin by recalling the proof of the analogous result in graphs, and then we will repeat the same steps in the context of manifolds.
Theorem 2 (Cheeger’s inequality in graphs) Let
be a
-regular graph,
be its adjacency matrix,
be its normalized Laplacian matrix,
be the eigenvalues of
, and define
for every subset of vertices
. Define the conductance of
as
where
is the number of edges with one endpoint in
and one endpoint in
. Then
1. Proof the Cheeger inequality in graphs
We will use the variational characterization of the eigenvalues of the Laplacian of a graph
.
and if is a minimizer in the above expression then
Following the definition of we see that
and so the minimum in (3) is 0, and it is achieved for . This means that
The expression in the right-hand-side of (4) is an important one, and it is called the Rayleigh quotient of , which we will denote by
:
It is also useful to consider the variant of the Rayleigh quotient where there are no squares; this does not have a standard name, so let us call it the Rayleigh quotient and denote it by
:
The proof of the graph Cheeger inequality now continues with the proof of the following three facts.
Lemma 3 (Rounding of
embeddings) For every non-negative vector
there is a value
such that
Lemma 4 (Embedding of
into
) For every non-negative vector
, we have
Lemma 5 (From an eigenvector to a non-negative vector) For every
such that
there is a non-negative
such that
and such that
Now let us start from a function that optimizes (4), so that
and
, then apply Lemma 5 to find a function
such that the volume of the vertices having positive coordinates in
is at most
and such that
. Then consider the vector
such that
; by Lemma 4, we have
, and by Lemma 3 there is a threshold
such that the set
has conductance
. Since
is a subset of the vertices having positive coordinates in
, we have
, and so
which is the Cheeger inequality for graphs. It remains to prove the three lemmas.
Proof: of Lemma 3. For each threshold , define the set
The idea of the proof is that if we pick at random then the probability that an edge belongs to
is proportional to
and the probability that
is proportional to
, so that the expected number of edges in
is proportional to the numerator of
and the expected number of vertices in
is proportional to the denominator of
; if
is small, it is not possible for
to always be large for every
.
To avoid having to normalize the range of to be between
and
, instead of taking averages over a random choice of
, we will consider the integral over all values of
. We have
because we can write , where
if
and
otherwise, and we see that only the values of
between
and
make
, so
.
We also have
and if we denote by the threshold such that
is smallest among all the
, then
so that
Proof: of Lemma 3. Let us consider the numerator of ; it is:
(we used Cauchy-Swarz)
(we used the definition of and Cauchy-Swarz again)
And so
Proof: of Lemma 5. Let be the median of
, and consider
defined as
. We have
because the numerators of and
are the same (the additive term
cancels). The denominators are such that
because and the vector
are orthogonal, and so by Pythagoras’s theorem the length-squared of
equals the length-squared of
plus the length-squared of
.
Let us define and
so that
. We use the following fact:
Fact 6 Let
be disjointly supported non-negative vectors (“disjointly supported” means that they are non-zero on disjoint subsets of coordinates), then
Proof: The numerator of is
and, using orthogonality and Pythagoras’s theorem, the denominator of is
The fact now follows from the inequality
The lemma now follows by observing that and
are non-negative and disjointly supported, so
and that both and
have at most
non-zero coordinate.
2. Proof of the Cheeger inequality in manifolds
We will now translate the proof of the graph Cheeger inequality to the setting of manifolds.
As you may remember, we started off by saying that is symmetric and so all its eigenvalues are real and they are given by the variational characterization. Now we are already in trouble because the operator
on manifolds cannot be thought of as a matrix, so what does it mean for it to be symmetric? The consequence of symmetry that is exploited in the analysis of the spectrum of symmetric matrices is the fact that if
is symmetric, then for every
we have
and the property makes no references to coordinates, and it is well defined even for linear operators over infinite-dimensional spaces, provided that there is a notion of inner product. If we the define the inner product
on functions , and more generally
for functions , where
is a vector space with inner product
, then we can say that an operator
is self-adjoint if
for all (appropriately restricted) functions . If
is compact, this property is true for the Laplacian, and, in particular,
and
are adjoints of each others, that is,
(The discrete analog would be that is the transpose of
.)
Self-adjointness (and appropriate conditions on ) imply a version of the spectral theorem and of the variational characterization. In particular, all eigenvalues of
are real, and if there is a minimum one then it is
and if is a minimizer of the above, then
(The minimization is quantified over all functions that are square-integrable, and the minimum is achieved because if is compact then the space of such functions is also compact and the cost function that we are minimizing is continuous. In this post, whenever we talk about “all functions,” it should be understood that we are restricting to whatever space of functions makes sense in the context.)
From the property that and
are adjoint, we have
so
where the Rayleigh quotient
is always non-negative, and it is zero for constant , so we see that
and
By analogy with the graph case, we define the “ Rayleigh quotient”
And we can prove the analogs of the lemmas that we proved for graphs.
Lemma 7 (Rounding of
embeddings) For every non-negative function
there is a value
such that
where the Cheeger constant of a subset
of the manifold is
Lemma 8 (Embedding of
into
) For every non-negative function
, we have
Lemma 9 (From an eigenfunction to a non-negative function) For every function
such that
there is a non-negative
such that
and such that
Let us see the proof of these lemmas.
Proof: of Lemma 7. For each threshold , define the set
Let be a threshold for which
is minimized
We will integrate the numerator and denominator of over all
. The coarea formula for nonnegative functions is
and we also have
which combine to
so that
Proof: of Lemma 8. Let us consider the numerator of ; it is:
We can apply the chain rule, and see that
which implies
and, after applying Caucy-Swarz,
And so
Proof: of Lemma 9. Let be a median of
, and consider
defined as
. We have
because the numerators of and
are the same (the derivatives of functions that differ by a constant are identical) and the denominators are such that
where we used the fact the integral of is zero.
Let us define and
so that
. We use the following fact:
Fact 10 Let
be disjointly supported non-negative functions (“disjointly supported” means that they are non-zero on disjoint subsets of inputs), then
Proof: We begin with the following observation: if is a non-negative function, and
, then
, because
has to be a local minimum.
Consider the expression occurring in the numerator of
. We have
But
because for every at least one of
or
is zero, and so at least one of
or
is zero.
Using this fact, we have that the numerator of is equal to the sum of the numerators of
and
:
and the denominator of is also the sum of the denominators of
and
:
because for every
. The fact now follows from the inequality
The lemma now follows by observing that and
are non-negative and disjointly supported, so
and that both and
have a support of volume at most
.
If anybody is still reading, it is worth observing a couple of differences between the discrete proof and the continuous proof.
The Rayleigh quotient is defined slightly differently in the continuous case. It would correspond to defining it as
in the discrete case.
If are disjointly supported and nonnegative, the sum of the numerators of the Rayleigh quotients
and
can be strictly smaller than the numerator of
, while we always have equality in the continuous case. In the discrete case, the sum of the numerators of
and
can be up to twice the numerator of
(this fact is useful, but it did not come up in this proof), while again we have exact equality in the continuous case.
The chain rule calculation
corresponds to the step
In the continuous case, and
are “infinitesimally close”, so we can approximate
by
.