Remarks on Lecture 4

You can see notes for this lecture here. In the next lecture, we will cover a different approach based on these notes.

Advertisements

Remarks on Lecture 3

Today we saw the connection between mixing times of random walks and the second eigenvalue of the normalized Laplacian. Recall that {G=(V,E,w)} is an {n} -vertex, weighted graph.

First, we introduced the lazy walk matrix,

\displaystyle  W_G = \frac{1}{2} (I + A_G D_G^{-1})\,,

which is related to the normalized Laplacian via,

\displaystyle  W_G = I - \frac{1}{2} D_G^{1/2} \mathcal{L}_G D_G^{-1/2}\,.

In particular, if we arrange the eigenvalues of {W_G} as {1=\beta_1 \geq \beta_2 \geq \cdots \geq \beta_n} , then

\displaystyle  \beta_i = 1 - \frac{\lambda_i}{2}\,,

where {\lambda_i} is the {i} th smallest eigenvalue of {\mathcal{L}_G} . Furthermore, the eigenfunctions of {W_G} are given by {g = D_G^{1/2} f} , where {f} is an eigenfunction of {\mathcal L_G} .

The eigenfunctions of {W_G} are orthogonal with respect to the inner product

\displaystyle  (f,g) = \sum_{u \in V} \frac{1}{w(u)} f(u) g(u)\,.

We will refer to this Hilbert space as {\ell^2(1/w)} . Recall that {\|f\|_{\ell^2(1/w)} = \sqrt{(f,f)} = \sqrt{\sum_{v \in V} \frac{1}{w(v)} f(v)^2}} .

If we define the stationary distribution {\pi : V \rightarrow [0,1]} by

\displaystyle  \pi(u) = \frac{w(u)}{w(V)} = \frac{w(u)}{2 w(E)},

then {W_G \pi = \pi} .

Let {f_1, f_2, \ldots, f_n} be an {\ell^2(1/w)} -orthornormal system of eigenvectors for {W_G} . Now fix an initial distribution {p_0 : V \rightarrow [0,1]} and write,

\displaystyle  p_0 = \sum_{i=1}^n \alpha_i f_i\,.

Then we have,

\displaystyle  p_t = W^t p_0 = \pi + \sum_{i > 1} \alpha_i \left(1-\frac{\lambda_i}{2}\right)^t f_i\,.

In particular,

\displaystyle  \|p_t - \pi\|_{\ell^2(1/w)}^2 = \sum_{i > 1} \alpha_i^2 \left(1-\frac{\lambda_i}{2}\right)^{2t} \leq \left(1-\frac{\lambda_2}{2}\right)^{2t} \sum_{i > 1} \alpha_i^2 \leq \left(1-\frac{\lambda_2}{2}\right)^{2t} \|p_0\|_{\ell^2(1/w)}^2\,.

Let {\pi_* = \min_{u \in V} \pi(u)} be the minimum stationary measure. A particularly strongly notion of mixing time is given by the following definition.

\displaystyle  \tau_{\infty} = \sup_{p_0} \min \left\{ t : \|p_t - \pi\|_{\infty} < \frac{\pi_*}{4} \right\}\,

where the supremum is taken over all initial distributions {p_0} . By time {\tau_{\infty}} , the distribution {p_t} is pointwise very close to the stationary distribution {\pi} .

Let {w^* = \max_{u \in V} w(u)} and {w_* = \min_{u \in V} w(u)} . Using our preceding calculation, we have

\displaystyle  \|p_t - \pi\|_{\infty} \leq \sqrt{w^*} \|p_t - \pi\|_{\ell^2(1/w)} \leq \sqrt{w^*} \left(1-\frac{\lambda_2}{2}\right)^{t} \|p_0\|_{\ell^2(V,w)} \leq \left(1-\frac{\lambda_2}{2}\right)^{t} \sqrt{\frac{w^*}{w_*}}\,.

Observe that {\frac{w^*}{w_*} \leq \frac{1}{\pi_*}} , so if we now choose {t \asymp \frac{1}{\lambda_2} \log \frac{1}{\pi_*}} appropriately, then

\displaystyle  \|p_t - \pi\|_{\infty} < \frac{\pi_*}{4},

yielding our main result:

\displaystyle  \tau_{\infty} \lesssim \frac{1}{\lambda_2} \log \frac{1}{\pi_*}\,.

One can also proof that {\tau_{\infty} \gtrsim \frac{1}{\lambda_2}} (see the exercises). In general, we will be concerned with weaker notions of mixing. We’ll discuss those when they arise.

Excersies

Prove that {\tau_{\infty} \gtrsim \frac{1}{\lambda_2}} for any graph G.

Remarks on Lecture 2

In this lecture, we generalized our setting to weighted graphs {G=(V,E,w)} where {w : E \to \mathbb R^+} is a positive weight function on edges. We also looked at the basic spectral theory of the normalized Laplacian, defined by

{\mathcal L_G = I - D_G^{-1/2} A_G D_G^{-1/2}} ,

which operates on functions {f : V \to \mathbb R} via

{\displaystyle \mathcal L_G f(u) = f(u) - \sum_{v \sim u} \frac{w(u,v)}{\sqrt{w(u) w(v)}} f(v)} .

In particular, we associated with {\mathcal L_G} the normalized Rayleigh quotient,

{\displaystyle \mathcal R_G(f) = \frac{\sum_{u \sim v} w(u,v) (f(u)-f(v))^2}{\sum_{u \in V} w(u) f(u)^2}} ,

and we showed that we can express the second-smallest eigenvalue as

{\lambda_2(\mathcal L_G) = \min \{ \mathcal R_G(f) : \sum_{v \in V} w(v) f(v) = 0 \}} .

We defined the expansion of a subset {S \subseteq V} by

{\phi_G(S) = \mathcal R_G(\mathbf{1}_S)} ,

where {\mathbf{1}_S} is the characteristic function for {S} .

Finally, we defined the expansion of a graph by

{\Phi_G = \min \left\{ \phi_G(S) : 0 < w(S) < w(V)/2\right\}}

We then stated and (almost) proved the following discrete Cheeger inequality.

Theorem 1. For any weighted graph {G=(V,E,w)} , we have

{\displaystyle \frac{\lambda_2}{2} \leq \Phi_G \leq 2 \sqrt{\lambda_2}} ,

where {\lambda_2 = \lambda_2(\mathcal L_G)} .

Exercises (optional)

  1. Prove that for the normalized Laplacian, just as for the combinatorial Laplacian, the number of connected components in a graph G is precisely the multiplicity of the smallest eigenvalue.
  2. We saw the the right-hand inequality in Theorem 1 is asymptotically tight. Prove that the left-hand side is asymptotically tight for the complete graph on n nodes.

Remarks on Lecture 1

Today we started studying the spectrum of the combinatorial Laplacian on a graph G=(V,E) . This is the operator L_G : \mathbb R^V \to \mathbb R^V given by

{\displaystyle L_G f(x) = \mathrm{deg}(x) f(x) - \sum_{y \sim x} f(y)\,.}

We saw that L_G has a spectrum of the form 0 = \lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_n , and that the number of connected components in G is precisely the multiplicity of \lambda_1 .

I encourage you to look at the first four lectures of Spielman’s course for a refresher.

Exercises

The best way to learn a subject is to get your hands dirty. Here are some optional exercises to help build your intuition.

Recall that for a function f : V \to \mathbb R , we define its Rayleigh quotient by

\displaystyle \mathcal R_G(f) = \frac{\sum_{x \sim y} (f(x)-f(y))^2}{\sum_{x \in V} f(x)^2}.

If P_n is the path graph on n vertices, then as we argued today, we have \lambda_k \asymp \left(\frac{k}{n}\right)^2  .

  1. Prove that \lambda_2 \asymp \frac{1}{n^2}  by showing that (a) there exists a map f : V \to \mathbb R  with f \perp \mathbf{1} and \mathcal R_G(f) \lesssim \frac{1}{n^2} and (b) for any such map with f \perp \mathbf{1} , we have \mathcal R_G(f) \gtrsim \frac{1}{n^2} . We did this in class, but it will help to reconstruct the proof on your own.

  2. Try to prove that \lambda_k \lesssim \left(\frac{k}{n}\right)^2 by exhibiting an explicit subspace of test functions
    that achieves this bound. It may help to use the Courant-Fischer min-max principle
    which says that

    \displaystyle \lambda_k = \min_{S \subseteq \mathbb R^V} \max_{0 \neq f \in S} \mathcal R_G(f),

    where the minimum is over all k-dimensional subspaces S .

    [Hint: Have your subspace be the span of k functions with disjoint supports, where the support of a function f : V \to \mathbb R  is \mathrm{supp}(f) = \{ x \in V : f(x) \neq 0 \} .]