Lecture 3: Courant-Fischer and Rayleigh Quotients, Graph Cutting, Cheerger’s Inequality

18.409 An Algorithmist’s Toolkit September 17, 2009 Lecture 3 Lecturer: Jonathan Kelner 1 Scribe: Andre Wibisono Outline Today’s lecture covers three main parts: • Courant-Fischer formula and Rayleigh quotients • The connection of λ2 to graph cutting • Cheeger’s Inequality 2 Courant-Fischer and Rayleigh Quotients The Courant-Fischer theorem gives a variational formulation of the eigenvalues of a symmetric matrix, which can be useful for obtaining bounds on the eigevalues. Theorem 1 (Courant-Fischer Formula) Let A be an n × n symmetric matrix with eigenvalues λ1 ≤ λ2 ≤ . . . ≤ λn and corresponding eigenvectors v1 , . . . , vn . Then λ1 = min xT Ax = min xT Ax , xT x λ2 = min xT Ax = min xT Ax , xT x x=0 x=1 x=0 x⊥v1 x=1 x⊥v1 λn = λmax = max xT Ax = max x=0 x=1 xT Ax . xT x In general, for 1 ≤ k ≤ n, let Sk denote the span of v1 , . . . , vk (with S0 = {0}), and let Sk⊥ denote the orthogonal complement of Sk . Then λk = min xT Ax = min x=0 x∈Sk⊥−1 x=1 x∈Sk⊥−1 xT Ax . xT x Proof Let A = QT ΛQ be the eigendecomposition of A. We observe that xT Ax = xT QT ΛQx = T (Qx) Λ(Qx), and since Q is orthogonal, Qx = x. Thus it suffices to consider the case when A = Λ is a diagonal matrix with the eigenvalues λ1 , . . . , λn in the diagonal. Then we can write ⎞⎛ ⎞ ⎛ λ1 x1 n ⎜  ⎟ ⎜ . ⎟ T . .. x Ax = x1 · · · xn ⎝ λi x2i . ⎠ ⎝ .. ⎠ = λn xn i=1 We note that when A is diagonal, the eigenvectors of A are vk = ek , the standard basis vector in Rn , i.e. (ek )i = 1 if i = k, and (ek )i = 0 otherwise. Then the condition x ∈ Sk⊥−1 implies x ⊥ ei for i = 1, . . . , k − 1, so xi = x, ei  = 0. Therefore, for x ∈ Sk⊥−1 with x = 1, we have xT Ax = n i=1 λi x2i = n λi x2i ≥ λk i=k n i=k 3-1 x2i = λk x2 = λk . On the other hand, plugging in x = ek ∈ Sk⊥−1 yields xT Ax = (ek )T Aek = λk . This shows that λk = min xT Ax. x=1 x∈Sk⊥−1 Similarly, for x = 1, xT Ax = n λi x2i ≤ λmax i=1 n x2i = λmax x2 = λmax . i=1 On the other hand, taking x = en yields xT Ax = (en )T Aen = λmax . Hence we conclude that λmax = max xT Ax. x=1 The Rayleigh quotient is the application of the Courant-Fischer Formula to the Laplacian of a graph. Corollary 2 (Rayleigh Quotient) Let G = (V, E) be a graph and L be the Laplacian of G. We already know that the smallest eigenvalue is λ1 = 0 with eigenvector v1 = 1. By the Courant-Fischer Formula, λ2 = min x=0 x⊥v1 xT Ax = min x=0  xT x λmax = max x=0 (i,j)∈E (xi i∈V x⊥1 xT Ax = max x=0  xT x − xj )2 x2i (i,j)∈E (xi i∈V , − xj )2 x2i . We can interpret the formula for λ2 as putting springs on each edge (with slightly weird boundary conditions corresponding to normalization) and minimizing the potential energy of the configuration. Some big matrices are hard or annoying to diagonalize, so in some cases, we may not want to calculate the exact value of λ2 . However, we can still get an approximation by just constructing a vector x that has a small Rayleigh quotient. Similarly, we can find a lower bound on λmax by constructing a vector that has a large Rayleigh quotient. We will look at two examples in which we bound λ2 . 2.1 Example 1: The Path Graph Let Pn+1 be the path graph of n + 1 vertices. Label the vertices as 0, 1, . . . , n from one end of the path to the n other. Consider the vector x ∈ Rn+1 given by xi = 2i − n for vertices i = 0, 1, . . . , n. Note that i=0 xi = 0, so x ⊥ 1. Calculating the Rayleigh quotient for x gives us (i,j)∈E (xi − xj )2 2 i∈V xi = 4n n i=0 (2i − n)2 = 4n =O Ω(n3 ) 1 n2 . Thus we can bound λ2 ≤ O(1/n2 ). We knew this was true from the explicit formula of λ2 in terms of sines and cosines from Lecture 2, but this is much cleaner and more general of a result. 2.2 Example 2: A Complete Binary Tree Let G be a complete binary tree on n = 2h − 1 nodes. Define the vector x ∈ Rn to have the value 0 on the root node, −1 on all nodes in the left subtree of the root, and 1 on all nodes in the right subtree of the root. 3-2 It is easy to see that i∈V xi = 0, since there are equal numbers of nodes on the left and right subtrees of the root, so x ⊥ 1. Calculating the Rayleigh quotient of x gives us (i,j)∈E (xi i∈V − xj )2 x2i = 2 =O n−1 1 n . Thus we get λ2 ≤ O(1/n), again with little effort. It turns out in this case that our approximation is correct within a constant factor, and we did not even need to diagonalize a big matrix. 3 Graph Cutting The basic problem of graph cutting is to cut a given graph G into two pieces such that both are “pretty big”. Graph cutting has many applications in computer science and computing, e.g. for parallel processing, divide-and-conquer algorithms, or clustering. In each application, we want to divide the problem into smaller pieces so as to optimize some measure of efficiency, depending on the specific problems. 3.1 How Do We Cut Graphs? The first question to ask about graph cutting is what we want to optimize when we are cutting a graph. Before attempting to answer this question, we introduce several notations. Let G = (V, E) be a graph. Given a set S ⊆ V of vertices of G, let S¯ = V \ S be the complement of S in V . Let |S| and |S̄| denote the number of vertices in S and S̄, respectively. Finally, let e(S) denote the number of edges between S and S̄. Note that e(S) = e(S̄). Now we consider some possible answers to our earlier question. Attempt 1: Min-cut. Divide the vertex set V into two parts S and S¯ to minimize e(S). This approach is motivated by the intuition that to get a good cut, we do not want to break too many edges. However, this approach alone is not sufficient, as Figure 1(a) demonstrates. In this example, we ideally want to cut the graph across the two edges in the middle, but the min-cut criterion would result in a cut across the one edge on the right. Attempt 2: Approximate bisection. Divide the vertex set V into two parts S and S̄, such that |S| and |S̄| are approximately n/2 (or at least n/3). This criterion would take care of the problem mentioned in Figure 1(a), but it is also not free of problems, as Figure 1(b) shows. In this example, we ideally want to cut the graph across the one edge in the middle that separates the two clusters. However, the approximate bisection criterion would force us to make a cut across the dense graph on the left. (a) Problem with min-cut (b) Problem with approximate bisection Figure 1: Illustration for problems with the proposed graph cutting criteria. Now we propose a criterion for graph cutting that balances the two approaches above. Definition 3 (Cut Ratio) The cut ratio φ of a cut S − S¯ is given by φ(S) = e(S) . min(|S|, |S̄|) 3-3 The cut of minimum ratio is the cut that minimizes φ(S). The isoperimetric number of a graph G is the value of the minimum cut, φ(G) = min φ(S). S⊆V As we can see from the definition above, the cut ratio is trying to minimize the number of edges across the cut, while penalizing cuts with small number of vertices. This criterion turns out to be a good one, and is widely used for graph cutting in practice. 3.2 An Integer Program for the Cut Ratio Now that we have a good definition of graph cutting, the question is how to find the optimal cut in a reasonable time. It turns out that we can cast the problem of finding cut of minimum ratio as an integer program as follows. Associate every cut S − S¯ with a vector x ∈ {−1, 1}n , where  1, if i ∈ S, and xi = ¯ −1, if i ∈ S. Then it is easy to see that we can write e(S) = 1 4 (xi − xj )2 . (i,j)∈E For a boolean statement A, let [A] denote the characteristic function on A, so [A] = 1 if A is true, and [A] = 0 if A is false. Then we also have ⎞  ⎛ 1 ¯⎠= ¯ =1 [i ∈ S] ⎝ [j ∈ S] [i ∈ S, j ∈ S] [xi = xj ] = (xi − xj )2 . |S| · |S̄| = 2 4 i 0, a b a+b ≥ min , , c+d c d so it is enough to bound  (yi − (i,j)∈E− m 2 i=1 yi yj )2 and  (yi − (i,j)∈E+ n 2 i=m yi yj )2 . Since the two values are essentially the same, we will focus only on the first one. 4.2.4 The Main Lemma Let Ci be the number of edges crossing the point xi , i.e. the number of edges in the cut if we were to take S = {1, . . . , i}. Recall that e(S) φ = φ(G) = min , S⊆V min(|S|, |S̄|) so by taking S = {1, . . . , i}, we get Ci ≥ φi for i ≤ n/2 and Ci ≥ φ(n − i) for i ≥ n/2. The main lemma we use to prove Cheeger’s Inequality is as follows. Lemma 8 (Summation by Parts) For any z1 ≤ . . . ≤ zm = 0, m |zi − zj | ≥ φ Proof |zi |. i=1  (i,j)∈E−  with i < j, write For each (i, j) ∈ E− j−1 |zi − zj | = zj − zi = (zi+1 − zi ) + (zi+2 − zi+1 ) + · · · + (zj − zj−1 ) = (zk+1 − zk ). k=i  , we observe that each term zk+1 − zk appears exactly Ck times. Therefore, Summing over (i, j) ∈ E− m−1 |zi − zj | =  (i,j)∈E− m−1 Ck (zk+1 − zk ) ≥ φ k=1 k(zk+1 − zk ). k=1 Note that zi ≤ zm = 0, so |zi | = −zi for 1 ≤ i ≤ m. Then we can evaluate the last summation above as m−1 |zi − zj | ≥ φ  (i,j)∈E− k(zk+1 − zk ) k=1   = φ (z2 − z1 ) + 2(z3 − z2 ) + 3(z4 − z3 ) + · · · + (m − 1)(zm − zm−1 ) = φ(−z1 − z2 − · · · − zm−1 + (m − 1)zm ) m |zi |. =φ i=1 3-8 4.2.5 Using the Main Lemma to Prove Cheeger’s Inequality Now we can finally prove Cheeger’s inequality. Proof of Cheeger’s Inequality: This proof has five main steps. m i=1 1. First, we normalize y such that yi2 = 1. 2. Next, this is perhaps a somewhat nonintuitive step, but we want to get squares into our expression, so we apply the main lemma (Lemma 8) to a new vector z with zi = −yi2 . We now have m |yi2 − yj2 | ≥ φ |yi2 | = φ. i=1  (i,j)∈E− 3. Next, we want something that looks like (yi − yj )2 instead of yi2 − yj2 , so we are going to use the Cauchy-Schwarz inequality. ⎞1/2 ⎛ ⎛  (i,j)∈E− (yi − yj )2 ⎠ |yi − yj | · |yi + yj | ≤ ⎝ |yi2 − yj2 | =  (i,j)∈E− ⎞1/2 ⎝  (i,j)∈E− (yi + yj )2 ⎠ .  (i,j)∈E− 4. We want to get rid of the (yi + yj )2 part, so we bound it and observe that the maximum number of times any yi2 can show up in the summation over the edges is the the maximum degree of any vertex. (yi + yj )2 ≤ 2  (i,j)∈E− (yi2 + yj2 ) ≤ 2 m dmax · yi2 ≤ 2dmax . i=1  (i,j)∈E− 5. Putting it all together, we get  (i,j)∈E− (yi − yj )2 m i=1 yi2   (i,j)∈E− ≥ 2 |yi2 − yj2 |  (yi (i,j)∈E− + yj )2 ≥ φ2 . 2dmax Similarly, we can also show that  (yi − (i,j)∈E+ n 2 i=m yi yj )2 ≥ φ2 . 2dmax Therefore, y T Ly xT Lx ≥ T ≥ min T x x y y 4.2.6   (yi − (i,j)∈E− m 2 i=1 yi yj )2 ,  (yi − (i,j)∈E+ n 2 i=m yi yj )2  ≥ φ2 . 2dmax So who is Cheeger anyway? Jeff Cheeger is a differential geometer. His inequality makes a lot more sense in the continuous world, and his motivation was in differential geometry. This was part of his PhD thesis, and he was actually investigating heat kernels on smooth manifolds. A heat kernel can also be thought of as a point of heat in space, and the question is the speed at which the heat spreads. It can also be thought of as the mixing time of a random walk, which will be discussed in future lectures. 3-9