= Lecture Notes =
# [[随机算法 (Fall 2011)/Introduction|Introduction]]
#*[[随机算法 (Fall 2011)/Complexity Classes|Complexity Classes]]
# Probability Basics
#* [[随机算法 (Fall 2011)/Probability Space|Probability Space]]
#* [[随机算法 (Fall 2011)/Verifying Matrix Multiplication|Verifying Matrix Multiplication]]
#* [[随机算法 (Fall 2011)/Conditional Probability|Conditional Probability]]
#* [[随机算法 (Fall 2011)/Randomized Min-Cut|Randomized Min-Cut]]
#* [[随机算法 (Fall 2011)/Random Variables and Expectations|Random Variables and Expectations]]
#* [[随机算法 (Fall 2011)/Randomized Quicksort|Randomized Quicksort]]
# Balls and Bins
#* [[随机算法 (Fall 2011)/Distributions of Coin Flipping|Distributions of Coin Flipping]]
#* [[随机算法 (Fall 2011)/Birthday Problem|Birthday Problem]]
#* [[随机算法 (Fall 2011)/Coupon Collector|Coupon Collector]]
#* [[随机算法 (Fall 2011)/Balls-into-balls Occupancy Problem|Balls-into-balls Occupancy Problem]]
#* [[随机算法 (Fall 2011)/Bloom Filter|Bloom Filter]]
#* [[随机算法 (Fall 2011)/Stable Marriage|Stable Marriage]]
# Moment and Deviation
#* [[随机算法 (Fall 2011)/Markov's Inequality|Markov's Inequality]]
#* [[随机算法 (Fall 2011)/Chebyshev's Inequality|Chebyshev's Inequality]]
#* [[随机算法 (Fall 2011)/Median Selection|Median Selection]]
#* [[随机算法 (Fall 2011)/Random Graphs|Random Graphs]]
# Hashing and Fingerprinting
#* [[随机算法 (Fall 2011)/Pair-wise Independence|Pair-wise Independence]]
#* [[随机算法 (Fall 2011)/Derandomization: Two-Point Sampling|Derandomization: Two-Point Sampling]]
# Chernoff Bound
#* [[随机算法 (Fall 2011)/Chernoff Bound|Chernoff Bound]]
#* [[随机算法 (Fall 2011)/Set Balancing|Set Balancing]]
#* [[随机算法 (Fall 2011)/DNF Counting|DNF Counting]]
#* [[随机算法 (Fall 2011)/Routing in a Parallel Network|Routing in a Parallel Network]]
# Concentration of Measure
#* [[随机算法 (Fall 2011)/Martingales|Martingales]]
#* [[随机算法 (Fall 2011)/Azuma's Inequality|Azuma's Inequality]]
#* [[随机算法 (Fall 2011)/The Method of Bounded Differences|The Method of Bounded Differences]]
# Dimension Reduction
#* [[随机算法 (Fall 2011)/Johnson-Lindenstrauss Theorem|Johnson-Lindenstrauss Theorem]]
#* [[随机算法 (Fall 2011)/Locality Sensitive Hashing|Locality Sensitive Hashing]]
# The Probabilistic Method
#* [[随机算法 (Fall 2011)/The Probabilistic Method|The Probabilistic Method]]
#* [[随机算法 (Fall 2011)/Lovász Local Lemma|Lovász Local Lemma]]
#* [[随机算法 (Fall 2011)/Derandomization: Conditional Expectation|Derandomization: Conditional Expectation]]
#* [[随机算法 (Fall 2011)/Derandomization: Color Coding|Derandomization: Color Coding]]
# Approximation Algorithms, On-line Algorithms
#* [[随机算法 (Fall 2011)/Max-SAT|Max-SAT]]
#* [[随机算法 (Fall 2011)/Linear Programming|Linear Programming]]
#* [[随机算法 (Fall 2011)/Randomized Rounding|Randomized Rounding]]
#* [[随机算法 (Fall 2011)/On-line Algorithms|On-line Algorithms]]
# Markov Chain and Random Walk
#* [[随机算法 (Fall 2011)/Markov Chains|Markov Chains]]
#* [[随机算法 (Fall 2011)/Random Walks on Undirected Graphs|Random Walks on Undirected Graphs]]
#* [[随机算法 (Fall 2011)/Electrical Network|Electrical Network]]
#* [[随机算法 (Fall 2011)/Cover Time|Cover Time]]
#* [[随机算法 (Fall 2011)/Graph Connectivity|Graph Connectivity]]
# Random Walk Algorithms
#* [[随机算法 (Fall 2011)/Randomized 2SAT|Randomized 2SAT]]
#* [[随机算法 (Fall 2011)/Randomized 3SAT|Randomized 3SAT]]
#* [[随机算法 (Fall 2011)/Perfect Matching in Regular Bipartite Graph|Perfect Matching in Regular Bipartite Graph]]
#* [[随机算法 (Fall 2011)/The Metropolis Algorithm|The Metropolis Algorithm]]
#* [[随机算法 (Fall 2011)/Dynamics on Spins|Dynamics on Spins]]
# Coupling and Mixing Time
#* [[随机算法 (Fall 2011)/Mixing Time|Mixing Time]]
#* [[随机算法 (Fall 2011)/Coupling|Coupling]]
#* [[随机算法 (Fall 2011)/Card Shuffling|Card Shuffling]]
#* [[随机算法 (Fall 2011)/Path Coupling|Path Coupling]]
#* [[随机算法 (Fall 2011)/Graph Coloring|Graph Coloring]]
# Expander Graphs I
#* [[随机算法 (Fall 2011)/Expander Graphs|Expander Graphs]]
#* [[随机算法 (Fall 2011)/Graph Spectrum|Graph Spectrum]]
#* [[随机算法 (Fall 2011)/The Spectral Gap|The Spectral Gap]]
#* [[随机算法 (Fall 2011)/Random Walk on Expander Graph|Random Walk on Expander Graph]]
# Expander Graphs II
#* [[随机算法 (Fall 2011)/Expander Mixing Lemma|Expander Mixing Lemma]]
#* [[随机算法 (Fall 2011)/Chernoff Bound for Expander Walks|Chernoff Bound for Expander Walks]]
#* [[随机算法 (Fall 2011)/The Zig-Zag Product|The Zig-Zag Product]]
#* [[随机算法 (Fall 2011)/USTCON in LOGSPACE|USTCON in LOGSPACE]]
# Sampling and Counting
#* [[随机算法 (Fall 2011)/The #P Class and Approximation|The #P Class and Approximation]]
#* [[随机算法 (Fall 2011)/DNF Counting|DNF Counting]]
#* [[随机算法 (Fall 2011)/Canonical Paths|Canonical Paths]]
#* [[随机算法 (Fall 2011)/Count Matchings|Count Matchings]]
#* [[随机算法 (Fall 2011)/Sampling and Counting|Sampling and Counting]]
# MCMC
#* [[随机算法 (Fall 2011)/Spin Systems|Spin Systems]]
#* [[随机算法 (Fall 2011)/Simulated Annealing|Simulated Annealing]]
#* [[随机算法 (Fall 2011)/Volume Estimation|Volume Estimation]]
# Complexity

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

2011-07-19T15:55:34Z

114.212.208.2: Created page with 'It turns out that the second largest eigenvalue of a graph contains important information about the graph's expansion parameter. The following theorem is the so-called Cheeger's …'

It turns out that the second largest eigenvalue of a graph contains important information about the graph's expansion parameter. The following theorem is the so-called Cheeger's inequality.
{{Theorem
|Theorem (Cheeger's inequality)|
:Let <math>G</math> be a <math>d</math>-regular graph with spectrum <math>\lambda_1\ge\lambda_2\ge\cdots\ge\lambda_n</math>. Then
::<math>
\frac{d-\lambda_2}{2}\le \phi(G) \le \sqrt{2d(d-\lambda_2)}
</math>
}}
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 <math>d</math>-regular graph, the value <math>(d-\lambda_2)</math> is known as the '''spectral gap'''. The name is due to the fact that it is the gap between the first and the second eigenvalue in the spectrum of a graph. The spectral gap provides an estimate on the expansion ratio of a graph. More precisely, a <math>d</math>-regular graph has large expansion ratio (thus being an expander) if the spectral gap is large.

If we write <math>\alpha=1-\frac{\lambda_2}{d}</math> (sometimes it is called the normalized spectral gap), the Cheeger's inequality is turned into a nicer form:
:<math>
\frac{\alpha}{2}\le \frac{\phi}{d}\le\sqrt{2\alpha} </math> or equivalently <math>
\frac{1}{2}\left(\frac{\phi}{d}\right)^2\le \alpha\le 2\left(\frac{\phi}{d}\right)
</math>.

----
We will not prove the theorem, but we will explain briefly why it works.

For the spectra of graphs, the Cheeger's inequality is proved by the [http://en.wikipedia.org/wiki/Min-max_theorem Courant-Fischer theorem] in linear algebra. The Courant-Fischer theorem is a fundamental theorem in linear algebra which characterizes the eigenvalues by a series of optimizations:
{{Theorem
|Theorem (Courant-Fischer theorem)|
:Let <math>A</math> be a symmetric matrix with eigenvalues <math>\lambda_1\ge\lambda_2\ge\cdots\ge\lambda_n</math>. Then
::<math>
\begin{align}
\lambda_k
&=\max_{v_1,v_2,\ldots,v_{n-k}\in \mathbb{R}^n}\min_{\overset{x\in\mathbb{R}^n, x\neq \mathbf{0}}{x\bot v_1,v_2,\ldots,v_{n-k}}}\frac{x^TAx}{x^Tx}\\
&=
\min_{v_1,v_2,\ldots,v_{k-1}\in \mathbb{R}^n}\max_{\overset{x\in\mathbb{R}^n, x\neq \mathbf{0}}{x\bot v_1,v_2,\ldots,v_{k-1}}}\frac{x^TAx}{x^Tx}.
\end{align}
</math>
}}
For a <math>d</math>-regular graph with adjacency matrix <math>A</math> and spectrum <math>\lambda_1\ge\lambda_2\ge\cdots\ge\lambda_n</math>, its largest eigenvalue <math>\lambda_1=d</math> with eigenvector <math>A\cdot\mathbf{1}=d\mathbf{1}</math>. According to the Courant-Fischer theorem, the second largest eigenvalue can be computed as
:<math>
\lambda_2=\max_{x\bot \mathbf{1}}\frac{x^TAx}{x^Tx},
</math>
and
:<math>
d-\lambda_2=\min_{x\bot \mathbf{1}}\frac{x^T(dI-A)x}{x^Tx}.
</math>
The later is an optimization, which shares some resemblance of the expansion ratio <math>\phi(G)=\min_{\overset{S\subset V}{|S|\le\frac{n}{2}}}\frac{|\partial S|}{|S|}=\min_{\chi_S}\frac{\chi_S^T(dI-A)\chi_S}{\chi_S^T\chi_S}</math>, where <math>\chi_S</math> is the '''characteristic vector''' of the set <math>S</math>, defined as <math>\chi_S(i)=1</math> if <math>i\in S</math> and <math>\chi_S(i)=0</math> if <math>i\not\in S</math>. It is not hard to verify that <math>\chi_S^T\chi_S=\sum_{i}\chi_S(i)=|S|</math> and <math>\chi_S^T(dI-A)\chi_S=\sum_{i\sim j}(\chi_S(i)-\chi_S(j))^2=|\partial S|</math>.

Therefore, the spectral gap <math>d-\lambda_2</math> and the expansion ratio <math>\phi(G)</math> both involve some optimizations with the similar forms. It explains why they can be used to approximate each other.

随机算法 (Fall 2011)

2011-07-18T13:02:28Z

114.212.208.2: /* Future plan */

= Lecture Notes =
# [[随机算法 (Fall 2011)/Introduction|Introduction]]
# [[随机算法 (Fall 2011)/Complexity classes and lower bounds|Complexity classes, lower bounds]]
# [[随机算法 (Fall 2011)/Balls and bins|Balls and bins]]
# [[随机算法 (Fall 2011)/Tail inequalities|Tail inequalities]]
# [[随机算法 (Fall 2011)/Chernoff bounds| Chernoff bounds]]
# [[随机算法 (Fall 2011)/Martingales | Martingales]]
# [[随机算法 (Fall 2011)/Hashing, limited independence | Hashing, limited independence]]
# [[随机算法 (Fall 2011)/Fingerprinting|Fingerprinting]]
# [[随机算法 (Fall 2011)/The probabilistic method | The probabilistic method]]
# [[随机算法 (Fall 2011)/Markov chains and random walks | Markov chains and random walks]]
# [[随机算法 (Fall 2011)/Expander graphs | Expander graphs]]
# [[随机算法 (Fall 2011)/Rapid mixing random walks | Rapid mixing random walks]]
# [[随机算法 (Fall 2011)/Random sampling | Random sampling, MCMC]]
# [[随机算法 (Fall 2011)/Approximate counting|Approximate counting]]
# [[随机算法 (Fall 2011)/Randomized approximation algorithms|Randomized approximation algorithms]]
# [[随机算法 (Fall 2011)/Distributed algorithms, data streams|Distributed algorithms, data streams]]