\documentclass[11pt]{article}
\usepackage{latexsym}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{epsfig}
\DeclareMathOperator*{\argmax}{argmax} % thin space, limits underneath in displays
\usepackage{tikz}
\usepackage[right=0.8in, top=1in, bottom=1.2in, left=0.8in]{geometry}
\usepackage{setspace}
\spacing{1.06}
\newcommand{\handout}[5]{
  \noindent
  \begin{center}
  \framebox{
    \vbox{\vspace{0.25cm}
      \hbox to 5.78in { {COMS 4995-2:\hspace{0.12cm}Advanced
          Algorithms (Spring'20)} \hfill #2 }
      \vspace{0.48cm}
      \hbox to 5.78in { {\Large \hfill #5  \hfill} }
      \vspace{0.42cm}
      \hbox to 5.78in { {#3 \hfill #4} }\vspace{0.25cm}
    }
  }
  \end{center}
  \vspace*{4mm}
}

\newcommand{\lecture}[4]{\handout{#1}{#2}{#3}{Scribes:\hspace{0.08cm}#4}{Lecture #1}}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{example}[theorem]{Example}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{assumption}[theorem]{Assumption}

\newcommand{\E}{{\mathbb E}}
\DeclareMathOperator{\var}{Var}

\begin{document}

\lecture{7: Spectral Graph Theory}{Feb 13,
  2020}{Instructor:\hspace{0.08cm}\emph{Alex Andoni }}{\emph{Liushiya Chen, Yu Guo}}

\section{Diffusion Operator}
\begin{definition}
    Given graph $G$ with $n$ nodes, we define the diffusion operator $W$ as the following.
    $$ x\in \mathbb{R}^n_+, \ \ x_i=Pr(\text{at node $i$ in a random walk on G}) $$
    $$ W(x): \mathbb{R}^n \rightarrow \mathbb{R}^n, \ \ W(x)_i:=\sum_{j;(i,j)\in E} \frac{x_j}{degree_j} $$
\end{definition}

\begin{example} \end{example}
    \begin{center}
    G = 1|2|3|4|5, \ \
    $D =
    \begin{bmatrix}
    1 & 0 & 0 & 0 & 0\\
    0 & 2 & 0 & 0 & 0\\
    0 & 0 & 2 & 0 & 0\\
    0 & 0 & 0 & 2 & 0\\
    0 & 0 & 0 & 0 & 1\\
    \end{bmatrix}$, \ \
    A =
    $\begin{bmatrix}
    0 & 1 & 0 & 0 & 0\\
    1 & 0 & 1 & 0 & 0\\
    0 & 1 & 0 & 1 & 0\\
    0 & 0 & 1 & 0 & 1\\
    0 & 0 & 0 & 1 & 0\\
    \end{bmatrix}$ \bigbreak
    \end{center}
    Suppose we start at node 1, our initial state $x_0 = (0,\ 1,\ 0,\ 0,\ 0)^T$, then we should expect .5 probability of walking to node 0 and 2.
    $$W(x_0)=
    \begin{bmatrix}
    .5 \\
    0 \\
    .5 \\
    0 \\
    0 \\
    \end{bmatrix}
    $$
\\
\begin{definition}
A stationary distribution $x^*$ satisfies $ W(x^*)=x^*$.
\end{definition}
In our example above, $x^*= (1/8, \ 1/4, \ 1/4, \ 1/4, \ 1/8)^T$. The intuition is that node 1, 5 have degree 1 while nodes 2,3,4 have degree 2, and so $2x^*_1=2x^*_5=x^*_2=x^*_3=x^*_4$.
\\
\begin{definition}
Another way to define diffusion operator $W$:
\end{definition}
$$ W(x)=A\cdot \underbrace{D^{-1}\cdot x}_{\text{mass sent to each}\atop \text{neighbor of i}}, \ \ \
W(x)_j = \sum_{i\in[n]}A_{ij}(D^{-1}x)_i$$
Then the stationary distribution $x^*$ satisifies $AD^{-1}x^*=x^*$.

\section{Spectral Decomposition \& Theorem for Symmetric $M$}
\begin{definition}
$v$ is eigenvector with eigenvalue $\lambda\in \mathbb{R}$
if  $Mv=\lambda v$. 
\end{definition}

\begin{observation}
If $\lambda$ is an eigenvalue, then $Mv - \lambda v=0\Rightarrow (M-\lambda I)v=0\Rightarrow det(M-\lambda I)=0$, where $I$ is the identity matrix. So, solutions to $det(M-\lambda I)=0$ (where $\lambda$ is unknown) are the eigenvalues.
\end{observation}
\noindent $det(M-\lambda I)=0$ is degree-n polynomial in $\lambda$ $\Rightarrow$ There are $n$ solutions if counting multiplicities. 
\begin{fact}
If $M$ is \textbf{symmetric}, then all solutions are real (no complex numbers).
\end{fact}
\begin{theorem}
\textbf{Spectral theorem}
\end{theorem}
\noindent For symmetric matrix $M$, $\exists\ \text{vectors}\ v_1,\dots,v_n $ and eigenvalues $\lambda_1,\dots,\lambda_n\ $ s.t.\\
$1)\ ||v_i||_2=1\qquad2)\ v_i\ \cdot\ v_j=0$ if $i\neq j$ (orthonormal)$\qquad 3)\ Mv_i=\lambda_iv_i$\\

\noindent \textbf{Remarks:}\\
1) The sorted sequence of eigenvalues, i.e. $\lambda_1\ge \lambda_2\ge\dots\ge \lambda_n$, is unique.\\
2) The set of eigenvectors $v_1,\dots,v_n$ is not necessarily unique. E.g., if $\lambda_i=\lambda_{i+1}$, then can replace $v_i,\ v_{i+1}$ with $\frac{v_i+v_{i+1}}{\sqrt{2}},\ \frac{v_i-v_{i+1}}{\sqrt{2}}$.\\
3) $M=\sum_{i=1}^n \lambda_i\cdot v_i \cdot v_i^T$, where $v_i \cdot v_i^T$ is the outer product of vector $v_i$.\\
4) If $\lambda_1> \lambda_2>\dots> \lambda_n$, i.e., all eigenvalues
are strictly different, then the set of eigenvectors
$\{v_1,\dots,v_n\}$ is unique up to taking $\{-v_1,\dots,-v_n\}$.
\begin{example}
    $M=0\Rightarrow \lambda_1,\dots,\lambda_n=0$. Any set of $n$ orthonormal vectors is a set of eigenvectors.\\
    For example, we can take $e_1,e_2,\dots, e_n$, or alternatively we can take $\frac{e_1+e_2}{\sqrt{2}},\ \frac{e_1-e_2}{\sqrt{2}},e_3,\dots,e_n$ as a set of eigenvectors. 
\end{example}
\begin{example}
    $M=I\Rightarrow \lambda_1,\dots,\lambda_n=1$. Again, any set of $n$ orthonormal vectors is a set of eigenvectors. So, we can take any basis to be the set of orthogonal eigenvectors.
   
\end{example}
\noindent If $M=\sum_{i=1}^n \lambda_i\cdot v_i \cdot v_i^T$, where $\ v_i\ \cdot\ v_j=0$ for $i\neq j$, then the $\lambda$'s and $v$'s are the decomposition given by Spectral Theorem.
\begin{align*}
    M\cdot v_j&=\sum_{i=1}^n \lambda_i\cdot v_i \cdot v_i^T\cdot v_j\\
    &=\sum_{i=1}^n\lambda_i\cdot v_i \cdot\left\{
\begin{aligned}
1,\ i=j \\
0,\ i\ne j
\end{aligned}
\right.\\
&=\lambda_j\cdot v_j
\end{align*}

\section{Rayleigh Quotients}
\begin{definition}
For vector $x\ne0$, $R(x)=\frac{x^TMx}{||x||^2}$. 
\end{definition}
\begin{observation}
$R(v_i)=\lambda_i$
\end{observation}
\begin{proof}
\begin{align*}
R(v_i)&=\frac{v_i^T\cdot M\cdot v_i}{||v_i||^2}\\
&=\frac{v_i^T\cdot\lambda_i\cdot v_i}{||v_i||^2}\\
&=\lambda_i
\end{align*}
\end{proof}
\begin{theorem}
$$\max_{x\ne 0}R(x)=\lambda_1$$
$$\min_{x\ne 0}R(x)=\lambda_n$$
\end{theorem}
\noindent By the above theorem, $v_1=\argmax\limits_{x\ne 0}R(x)$.
\begin{proof}
Consider $x\ne 0$, 
$$R(x)=\frac{x^T\cdot[\sum_{i=1}^n \lambda_i\cdot v_i \cdot v_i^T]\cdot x}{||x||^2}$$
Since $v_1,\dots,v_n$ is basis $\Rightarrow\ \exists\ \underbrace{\alpha_1,\dots,\alpha_n}_\text{unique}\ $ s.t. 
$$1)\ x=\sum_{i=1}^n\alpha_i\cdot v_i\qquad 2)\  ||x||^2=x^T\cdot x=(\sum_{i=1}^n\alpha_i\cdot v_i)^T(\sum_{j=1}^n\alpha_j\cdot v_j)=\sum_{i=1}^n\alpha_i^2$$
\begin{align*}
R(x)&=\frac{x^T\cdot M\cdot x}{||x||^2}\\
&=\frac{x^T\cdot M\cdot\sum_{i=1}^n\alpha_i\cdot v_i}{||x||^2}\\
&=\frac{x^T\cdot \sum_{i=1}^n\alpha_i\cdot \lambda_i \cdot v_i}{||x||^2}\\
&=\frac{\sum_{i,j}(\alpha_j\cdot v_j)^T\cdot\alpha_i\cdot \lambda_i \cdot v_i}{||x||^2}\\
&=\sum_{i=1}^n \lambda_i\cdot\alpha_i^2\cdot\frac{1}{\sum_{i=1}^n\alpha_i^2}\\
&\le \max_i\lambda_i=\lambda_1
\end{align*}
The proof for lower bound is precisely the same, by just replacing the maximum with the minimum in the final inequality.
\end{proof}
\begin{theorem}
$$\lambda_i=\max_{x\ne0\atop x\perp v_1,\dots,v_{i-1}}R(x)$$
\end{theorem}
\noindent Proof for this extension theorem is similar to the previous one. 
\end{document}
