\documentclass[11pt]{article}
\usepackage{latexsym}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{epsfig}
\usepackage[right=0.8in, top=1in, bottom=1.2in, left=0.8in]{geometry}
\usepackage{setspace}
\usepackage{enumerate}
\spacing{1.06}

\usepackage[english]{babel}

\newcommand{\handout}[5]{
  \noindent
  \begin{center}
  \framebox{
    \vbox{\vspace{0.25cm}
      \hbox to 5.78in { {COMS 4995-8:\hspace{0.12cm}Advanced
          Algorithms (Spring'21)} \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{13: Max Flow, Spectral Graph Theory}{Feb 23,
  2021}{Instructor:\hspace{0.08cm}\emph{Alex Andoni }}{\emph{Yuanchu Dang, Yunfeng Guan}}

%%% DELETE this.
% A few reminders:
% \begin{itemize}
%   \item
%   Please make sure to coordinate with your partner(s) to scribe the
%   lecture. You are to produce one set of scribes amongst yourselves.
% \item
%   Please submit by midnight the next day after the lecture, by sending
%   Alex an email.
% \item Send {\em both the source tex and pdf} file (and
%   auxiliary files, if you have any), titled \texttt{scribeX.tex},
%   \texttt{scribeX.pdf}, where X is the lecture number.
% \end{itemize}
%%% END DELETE

% \section{Introduction}

% Today's lecture is about 1) overview of the class, and 2) approx counting...

% \section{Course Info}

% \section{Course Topics}
% \textbullet{} Flying Algorithms  \\
% ....


% \section{Problem: Counting}

% In this problem, the goal is to count like toddlers do...



% \begin{claim}
% $\E_{fixed\ variables}[something]=n$.
% \end{claim}
% \begin{proof}
%   The proof is by induction...
% \end{proof}

\section{Introduction}

In the last lecture, we explored 3 algorithms that improve on the run time of the original Ford-Fulkerson algorithm. Today we will continue on Ford-Fulkerson, and also get started on the foundational concepts of Spectral Graph Theory as well.

\section{Max Flow Continuation}

In this section, we will continue from the last lecture and finish the last bit of the Ford-Fulkerson shortest path algorithm and obtain a few extensions from it. 

Denote $d_f(s, v)$ as the distance from $s$ to $v$ in $G_f$ (the residual graph). 

\begin{claim}
Fix $f$. Let $P$ be the shortest augmenting path in $G_f$, and $f'$ be the flow after augmenting $P$, we would have 

$$d_{f'}(s, v) \ge d_f(s, v)$$

\end{claim}

\begin{proof}
Let $A = \{v: d_{f'}(s, v) < d_f(s, v)\}$
and $v = \min_{v\in A} d_{f'}(s, v)$.
From the premise, $A \ne \varnothing$.

Let $w$ be the preceding node of $v$ in $P$, then
$$d_{f'}(s, v) = d_{f'}(s, w) + 1$$

Since $d_{f'}(s, v) < d_{f}(s, v)$ and $d_{f'}(s, w) \ge d_f(s, w)$, we have 
$$d_f(s, v) \ge d_f(s, w) + 2$$

However, if there exists $w \rightarrow v$ in $G_f$, it must be
$$d_f(s, v) \le d_f(s, w) + 1$$

This implies in $G_f$, path $P$ goes from $v$ to $w$, and in turn that 
$$d_f(s, w) = d_f(s, v) + 1$$

which results in a contradiction with $d_f(s, v) \ge d_f(s, w) + 2$ that we obtained previously. 

\end{proof}

\begin{claim}
For $\forall v \in V$, $d_f(s, v) \le n$.
\end{claim}

\begin{claim}
For every edge $v \rightarrow w$, it can be saturated at most $\frac{n}{2}$ times. 
\end{claim}

\begin{proof}
During a saturating event, if $v\rightarrow w$ is on the (shortest) augmenting path $P$, then we have 
$$d_f(s, w) = d_f(s, v) + 1$$

At the same time, as $v\rightarrow w$ is saturated, in the next residual graph $G_{f'}$, $v \rightarrow w$ does not exist.

Before edge $v \rightarrow w$ is saturated again, it must be created first, which means that a shortest path $P'$ must go from $w \rightarrow v$ in some $G_{f''}$ for $f''$.

This implies that 
\begin{align*}
d_{f''}(s, v) &= d_{f''}(s, w) + 1  \\
&\ge d_f(s, w) + 1  \tag{Claim 1}\\
&= d_f(s, v) + 1 + 1 \\
&= d_f(s, v) + 2
\end{align*}
i.e. there are at most $\frac{n}{2}$ saturations of $v \rightarrow w$. 

\end{proof}

\begin{claim}
In every step of the FF algorithm, at least $1$ edge is saturated. 
\end{claim}

In conclusion, for run time analysis, we have:

\begin{itemize}
    \item Number of iterations in FF: $m \cdot \frac{n}{2}$.
    
    \item Total time: $O(\frac{mn}{2} \cdot m) = O(m^2n)$.
\end{itemize}

There are also improved run time results from a few other references:

\begin{itemize}
    \item $O(m^{1.5}\log n \log U)$ (up to the 90s). 
    
    \item $O(m \sqrt{n} \log U)$ (Lee and Sidford \cite{lee2015path}).
    
    \item $O(m^{4/3}\cdot (\log n)^{O(1)})$ for $U = O(1)$ (Kathuria, Liu and Sidford \cite{KathuriaLS20}). 
\end{itemize}




\section{Spectral Graph Theory}
In this section, we mainly focus on undirected graph $G = (V, E)$.
\begin{definition}
Adjacency matrix $A_G$ of graph $G$ is an $n\times n$ matrix with elements
\[(A_G)_{ij} = \left\{\begin{array}{cc}
     1 & \mathrm{if } (i, j)\in E  \\
     0 & \mathrm{otherwise}
\end{array}\right.\]
\end{definition}

\begin{observation}
For undirected graph $G$, $A_G$ is symmetric.
\end{observation}

\begin{definition}
Degree matrix $D_G$ of graph $G$ is an $n\times n$ diagonal matrix with elements
\[(D_G)_{ii} = degree(i)\]
\end{definition}

\section{Random Walks / Diffusion}
\subsection{Diffusion equation}
Think of a walker walking randomly in $G$, who at every time step, takes a step to a (uniformly) random neighbor.
\begin{definition}
$x^t \in \mathbb R^+$ is the probability distribution of the walker's position after $t$ steps.
\end{definition}
Starting from the initial position $x^0 = (1, 0, \cdots, 0)$,
the evolution of $x^t$ is dictated by diffusion operator $W$, in the form $x^{t+1} = Wx^t$.

From the statement of random walk process, we have
\[x^{t+1}_j = \sum_{(i, j)\in E} \frac{x_i^t}{degree(i)}\]
in which $x^{t}_i$ is the probability that the walker is in position $i$ at time step $t$.

Therefore, we can see $W$ is in fact an $n\times n$ matrix with elements
\[W_{ji} = \frac{1}{degree(i)}(A_G)_{ji}\]
Further it can be written as
\[W = A_GD_G^{-1}\]

Here we have some remarks:
\begin{enumerate}[1)]
    \item $x^t = Wx^{t-1} =\cdots = W^tx^0$
    \item In the evolution process $x^{t+1} = A_GD_G^{-1}x^t$, $D_G^{-1} x^t$ can be seen as a special vector indicating how much fraction node $i$ gives to each of its neighbor.
    \item $W$ is not necessarily symmetric even if $A_G$ is symmetric.
\end{enumerate}

\subsection{Stationary distribution}
\begin{definition}
The stationary distribution for a random walk process is the vector $x^*\in \mathbb R_+^n$ s.t. $Wx^* = x^*$.
\end{definition}
Two questions centering on stationary distribution are:
\begin{enumerate}[1)]
    \item What is $x^*$? Does it exist? Is it unique if existence is guaranteed?
    \item When $t\rightarrow \infty$, does $x^t$ converge? If so, is $x^*$ the limit point?
\end{enumerate}

\section{Spectral Decomposition/Theory of symmetric matrices}
\subsection{Eigenvector and eigenvalue}
\begin{definition}
Let $M$ be an $n\times n$ matrix. A non-zero vector $v\in \mathbb R^n$ is called an eigenvector of $M$ if $Mv = \lambda v$. $\lambda$ is the corresponding eigenvalue of $v$.
\end{definition}
From the definition we have the observation that for any eigenvector/eigenvalue pair $(v, \lambda)$, $Mv = \lambda v \Rightarrow (M-\lambda I) v = 0$.

It further implies that the determinant $\det(M-\lambda I) = 0$. Since the determinant is a polynomial of $\lambda$ of degree $n$ (in fact a summation of products of $n$ items from $M-\lambda I$), this equation has precisely $n$ roots (counting multiplicities).

In addition we have the following fact:
\begin{fact}
If $M$ is a real symmetric matrix, then all $n$ roots of $\det(M-\lambda I) = 0$.
\end{fact}

\subsection{Spectral Theorem}
\begin{theorem}
For any $n\times n$ matrix $M$, there exist $n$ eigenvalue/eigenvector pairs $(\lambda_i, v_i)$ such that
\begin{enumerate}[1)]
    \item $\|v_i\| = 1$
    \item $v_i \cdot v_j  = 0$ for $i\neq j$
    \item $Mv_i = \lambda_iv_i$
\end{enumerate}
\end{theorem}
Here are some remarks on spectral theorem.
\begin{enumerate}[1)]
    \item The eigenvalues $\lambda_1, \cdots, \lambda_n$ are unique. (By convention, eigenvalues are named in the order $\lambda_1 \ge \cdots \ge \lambda_n$)
    \item The eigenvectors are not necessarily unique.
    
    If $\lambda_i$ are distinct, then the corresponding eigenvectors $v_1, \cdots, v_n$ must be unique (up to negativity, i.e. $v_i$ and $-v_i$ are the only two eigenvectors corresponding to $\lambda_i$).
    
    Otherwise, it is not the case. For example, given $\lambda_i = \lambda_{i+1}$, apart from $v_i, v_{i+1}$, $\frac1{\sqrt 2}(v_i + v_{i+1}), \frac1{\sqrt 2}(v_i-v_{i+1})$ can also be two valid eigenvectors.
    \item $M$ can be expressed as the sum of outer products of eigenvectors.
    \[M = \sum_{i=1}^n \lambda_iv_i^Tv_i\]
\end{enumerate}

Some examples of spectral decomposition:
\begin{enumerate}[1)]
    \item $M= 0$, then $\lambda_i=0, i = 1, \cdots, n$. Any basis in $\mathbb R^n$ is a valid set of eigenvectors.
    \item $M= I$, then $\lambda_i=1, i = 1, \cdots, n$. Any basis in $\mathbb R^n$ is a valid set of eigenvectors.
\end{enumerate}

Further, since we proved that $n$ eigenvectors form a basis of $\mathbb R^n$, any vector $x\in \mathbb R^n$ can be expressed as a linear combination of them.
\[x = \sum_{i=1}^n \alpha_i v_i\]
Then the result of $M$ being applied to $x$ is just the summation of scaled eigenvectors.
\[Mx = M\sum_{i=1}^n \alpha_i v_i = \sum_{i=1}^n \alpha_i (Mv_i) 
= \sum_{i=1}^n \lambda_i \alpha_i v_i\]

\subsection{Rayleigh Quotient}

\begin{definition}
$\forall x \ne 0$, Rayleigh Quotient $R(x)$ is a function mapping from $\mathbb R^n$ to $\mathbb R$: 

$$R(x) = \frac{x^T M x}{||x||^2} = \frac{x^T M x}{x^T x}$$
\end{definition}

\begin{observation}
For $\forall$ eigenvector $v_i$,
\[R(v_i) = \frac{v_i^T M v_i}{||v_i||^2} = 
\frac{v_i^T \lambda_i v_i}{|| v_i ||^2} = \lambda_i\]
\end{observation}

From the observation, we can easily derive the following theorems.

\begin{theorem}

\[
  \max_{\substack{x \ne 0 }} R(x) = \lambda_1 \quad \text{(maximum eigenvalue)}
\]


\[
  \min_{\substack{x \ne 0 }} R(x) = \lambda_n \quad \text{(minimum eigenvalue)}
\]
\end{theorem}
\begin{theorem}
\[
  \lambda_i = \max_{\substack{x \ne 0 \\ x \perp v_1, v_2, ..., v_{i - 1}}} R(x)
\]

e.g. 

\[
  \lambda_2 = \max_{\substack{x \ne 0 \\ x \perp v_1}} R(x)
\]

\end{theorem}

This observation in fact shows a different way to compute eigenvalue without finding the roots of determinant.

But it is worth noting that only eigenvalues are obtained. The corresponding eigenvectors still need to be computed by solving $(M-\lambda I)v = 0$.

%\printbibliography

\bibliographystyle{alpha}
\bibliography{ref} 

\end{document}
 
