On Paul Erdos and Kim Kardashian

This year is the centennial of Paul Erdős’s birth. Erdős lived most of his adult life as a traveling mathematician, “couchsurfing,” as we would say now, from place to place and from mathematical conference to mathematical conference. He wrote more than 1,500 papers with more than 500 different coauthors, introduced the probabilistic method and was the defining figure of the “Hungarian approach” to combinatorics. He died at age 83 while attending a mathematical conference.

Last year, we celebrated the centennial of Alan Turing’s birth. Turing and Erdős have become such iconic figures both for the impact of their work and for the fascinating facts of their lives. I would like to argue that the cultural archetype through which we interpret their lives is that of the saint. It is clearly that of the martyr saint in the case of Turing, while Erdős gave up material possessions and devoted his life to others, traveling everywhere and “preaching” to everybody, much in the mold of Saint Francis.

(A comparison of the Turing centennial celebration and Erdős’s, and a look at the frescoes of Medieval Catholic churches will show which kind of saint people are more interested in.)

The first step to become a saint of the Catholic church is to establish that the person exhibited “heroic virtues,” which is a great expression. This is an archetype that is not restricted to religion: you see it occurring in communist propaganda (Stakhanov, Lei Feng) and in every civil rights movement.

Saints were the “celebrities” of the Middle Ages, those whose life people liked to talk about. But contemporary celebrities come from a totally different archetype, that of the Greek God. Greek (and Roman) gods were petty and jealous, they cheated on their spouses, they were terrible parents, but there were good stories to be told about them. We don’t want (at least, I don’t) to live the life of a saint, but thinking about them is certainly inspirational and it makes us think that if someone can be so much better than us, maybe we can be a little better ourself in the practice of “virtues”, whatever this may mean to us. And we don’t admire gods, but, well, it’s probably fun to be one.

As usual, I have lost track of what I was trying to say, but I think that it speaks well of the academic community that we are more interested in saints than in gods, I will close by saying that my favorite saint of complexity theory is Avi Wigderson, I will keep to myself who my favorite god of complexity theory is, and I will leave it to the readers to contribute their picks.

The Power Method

This week, the topic of my online course on graph partitioning and expanders is the computation of approximate eigenvalues and eigenvectors with the power method.

If is a positive semidefinite matrix (a symmetric matrix all whose eigenvalues are nonnegative), then the power method is simply to pick a random vector , and compute . If is of the order of , then one has a constant probability that

where is the largest eigenvalue of . If we are interested in the Laplacian matrix of a -regular graph, where is the adjacency matrix of the graph, this gives a way to compute an approximation of the largest eigenvalue, and a vector of approximately maximum Rayleigh quotient, which is useful to approximate Max Cut, but not to apply spectral partitioning algorithms. For those, we need a vector that approximates the eigenvector of the second smallest eigenvalue.

Equivalently, we want to approximate the second largest eigenvalue of the adjacency matrix . The power method is easy to adjust to compute the second largest eigenvalue instead of the largest (if we know an eigenvector of the largest eigenvalue): after you pick the random vector, subtract the component of the vector that is parallel to the eigenvector of the largest eigenvalue. In the case of the adjacency matrix of a regular graph, subtract from every coordinate of the random vector the average of the coordinates.

The adjacency matrix is not positive semidefinite, but we can adjust it to be by adding a multiple of the identity matrix. For example we can work with . Then the power method reduces to the following procedure: pick randomly , then subtract from every entry of , then repeat the following process times: for every entry , assign , that is, replace the value that the vector assigns to vertex with a convex combination of the current value and the current value of the neighbors. (Note that one iteration can be executed in time .

The problem is that if we started from a graph whose Laplacian matrix has a second smallest eigenvalue , the matrix has second largest eigenvalue , and if the power method finds a vector of Rayleigh quotient at least for , then that vector has Rayleigh quotient about for , and unless we choose of the same order as we get nothing. This means that the number of iterations has to be about , which can be quite large.

The video below (taken from this week’s lecture) shows how slowly the power method progresses on a small cycle with 31 vertices. It goes faster on the hypercube, which has a much larger .

A better way to apply the power method to find small eigenvalues of the Laplacian is to apply the power method to the pseudoinverse of the Laplacian. If the Laplacian of a connected graph has eigenvalues , then the pseudoinverse has eigenvalues with the same eigenvectors, so approximately finding the largest eigenvalue of is the same problem as approximately finding the second smallest eigenvalue of .

Although we do not have fast algorithms to compute , what we need to run the power method is, for a given , to find the such that , that is, to solve the linear system in given and .

For this problem, Spielman and Teng gave an algorithm nearly linear in the number of nonzero of , and new algorithms have been developed more recently (and with some promise of being practical) by Koutis, Miller and Peng and by Kelner, Orecchia, Sidford and Zhu.

Coincidentally, just this week, Nisheeth Vishnoi has completed his monograph Lx=b on algorithms to solve such linear systems and their applications. It’s going to be great summer reading for those long days at the beach.

Fun with expanders starts today

Long in the making, the online course on expanders starts today.

In the first week of class: what are the topics of the course, and how to prove that the eigenvalues of the adjacency matrix of a regular graph tell you how many connected components there are in the graph.

Introducing eXpandr

[I have been asked by the office of public affairs of the Institute for Advanced Study to publicize the following press release. L.T.]

April 1, 2013. For immediate release.

Cofounders Jean Bourgain and Peter Sarnak announce today the launch of eXpandr, a new venture that aims to become the world’s leading provider of expander graphs.

“We are excited about our mission to change the way the world uses expanders.” said CEO Guli Mars, who joined eXpandr after a distinguished career in several leading technology companies. “Expanders are vital to revenue-generating logarithms, and our technology will revolutionize a multi-billion dollar market.”

“Big data, disruption”, said Juan Raman, senior vice president for marketing. “Innovation, cloud computing”, Mr. Raman continued.

“Let p be a prime congruent to 1 modulo 4″ said Jean Bourgain, cofounder and senior vice-president for analytic number theory, “and consider the irreducible representations of PSL(2,p).”

About the Institute for Advanced Study. The Institute for Advanced Study is one of the world’s leading centers for theoretical research and intellectual inquiry. The Institute exists to encourage and support fundamental research in the sciences and humanities—the original, often speculative thinking that produces advances in knowledge that change the way we understand the world. Work at the Institute takes place in four Schools: Historical Studies, Mathematics, Natural Sciences and Social Science. It provides for the mentoring of scholars by a permanent Faculty of no more than 28, and it offers all who work there the freedom to undertake research that will make significant contributions in any of the broad range of fields in the sciences and humanities studied at the Institute.

The Institute, founded in 1930, is a private, independent academic institution located in Princeton, New Jersey. Its more than 6,000 former Members hold positions of intellectual and scientific leadership throughout the academic world. Some 33 Nobel Laureates and 38 out of 52 Fields Medalists, as well as many winners of the Wolf or MacArthur prizes, have been affiliated with the Institute.

About eXpandr. eXpandr aims to disrupt the way the world uses expander graphs, and to become the leading commercial provider of expanders. eXpandr received $2 million in angel investing and will launch its first product by Summer 2013.

Proof of the Cheeger inequality in manifolds

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 .

The Cheeger inequality in manifolds

Readers of in theory have heard about Cheeger’s inequality a lot. It is a relation between the edge expansion (or, in graphs that are not regular, the conductance) of a graph and the second smallest eigenvalue of its Laplacian (a normalized version of the adjacency matrix). The inequality gives a worst-case analysis of the “sweep” algorithm for finding sparse cuts, it shows a necessary and sufficient for a graph to be an expander, and it relates the mixing time of a graph to its conductance.

Readers who have heard this story before will recall that a version of this result for vertex expansion was first proved by Alon and Milman, and the result for edge expansion appeared in a paper of Dodzuik, all from the mid-1980s. The result, however, is not called Cheeger’s inequality just because of Stigler’s rule: Cheeger proved in the 1970s a very related result on manifolds, of which the result on graphs is the discrete analog.

So, what is the actual Cheeger’s inequality?

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

The purpose of this post is to describe to the reader who knows nothing about differential geometry and who does not remember much multivariate calculus (that is, the reader who is in the position I was in a few weeks ago) what the above statement means, to describe the proof, and to see that it is in fact the same proof as the proof of the statement about graphs.

In this post we will define the terms appearing in the above theorem, and see their relation with analogous notions in graphs. In the next post we will see the proof.

Hello, and Welcome to Fun with Expanders

Long in the planning, my online course on graph partitioning algorithms, expanders, and random walks, will start next month.

The course page is up for people to sign up. A friend of mine has compared my camera presence to Sheldon Cooper’s in “Fun with Flags,” which is sadly apt, but hopefully the material will speak for itself.

Meanwhile, I will be posting about some material that I have finally understood for the first time: the analysis of the Arora-Rao-Vazirani approximation algorithm, the Cheeger inequality in manifolds, and the use of the Selberg “3/16 theorem” to analyze expander constructions.

If you are not a fan of recorded performances, there will be a live show in Princeton at the end of June.

Let’s do it again in 2054

I would like to thank all those that contributed to the Turing Centennial series: all those who wrote posts, for sure; but also all those who spread the word about this, on blogs, twitter, facebook, and in real life; those who came to read them; and those who wrote lots of thoughtful comments. In a community where discussions over conference organizational issues or over the importance of matrix multiplication algorithms can become very acrimonious, I am impressed that we could have such a pleasant and troll-free conversation. This goes to show that in theory has not only the smartest and most handsome readers of the whole internet, as was well known, but also the nicest ones!

We will definitely do this again in 2054, to mark the centennial of Turing’s death.

A few days ago, I was very saddened to hear of the death of Sally Ride. A Stanford Alumna, Sally Ride became to first American woman to travel in space, she served on both the investigative committees after the two Shuttle disasters, and dedicated the past decade to the goal of getting young kids, and girls in particular, interested in science and technology. She cofounded, and directed, a non-profit foundation to further these goals, and wrote several books. After her death, it was revealed that she had been in a 25-year relationship with another woman, who was also the coauthor of her books and a partner in her foundation.

I think it is significant that a person that certainly had a lot of courage, determination, willingness to defy stereotypes, and to be an inspiration for people like her, felt that she could not be publicly out during her life. (In interviews about their books, Ride and her partner Tam O’Shaughnessy referred to each other as “friends”.)

Let’s hope that in 2054 it’s not just computer science professors in the West that are confortable being out, but also astronauts, movie stars, professional athletes, and so on.

Turing Centennial: Robert MacPherson

Two more posts are coming soon. Meanwhile, here is a wonderful interview with Robert MacPherson, which is part of an interview series by the Simons Foundation. Although the interview does not mention Turing, it does mention Kolmogorov.

(via Not Even Wrong)

The New York Times on False Positives and False Negatives

From this New York Times article:

Researchers found the home test accurate 99.98 percent of the time for people who do not have the virus. By comparison, they found it to be accurate 92 percent of the time in detecting people who do. [...]

So, while only about one person in 5,000 would get a false negative test, about one person in 12 could get a false positive.