\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}
\spacing{1.06}

\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{16: Cheeger Inequality}{Mar 11,
  2021}{Instructor:\hspace{0.08cm}\emph{Alex Andoni }}{\emph{Shaoyu Liu, Chengrui Zhou}}



\section{Spectral Partitioning}
\subsection{Recap}
Recall from last lecture we have:\\
1) $\mu_{2} = 0 $ if and only if graph G is disconnected.\\
2) We define the Laplacian and its normalized form for a graph G = (V,E):
$$L = D - A$$
$$\hat{L}=D^{-1 / 2} L D^{-1 / 2}$$
$$ = D^{-1 / 2} (D-A) D^{-1 / 2} = I - \hat{A}$$
where L is the Laplacian matrix, $
\hat{L}$ is the normalized Laplacian matrix, D is the degree matrix, A is the adjacency matrix and $\hat{A}$ is the normalzied adjacency matrix.\\

\subsection{Conductance}
\textbf{Definition 1}: A cut is defined as a separation of a graph G into two subsections S and $\bar{S}$.\\
\textbf{Definition 2}: for cut $S$, 
$$\partial S=\{(i, j) \in E, i \in S, j \in \bar{S}\}$$
In words, $\partial S$ is the number of edges crossing $S$ and $\bar{S}$.

We want to develop a quantitative statement to show how close to disconnected a graph is. This motivates the idea of conductance.\\
\textbf{Definition 3: Conductance}:
We define the conductance of a cut S to be:\\
$$\phi(S) = \frac{|\partial S|}{\operatorname{vol} S} \quad \text { where } \quad \operatorname{vol}(S) = \sum_{i \in S} d_{i}$$

We define the conductance of a graph $G$ to be:\\
$$\phi(G)=\min _{S \subset V} \phi(S) \text { s.t. } 0<\operatorname{vol}(S) \leq \frac{\operatorname{vol}(V)}{2}$$
Alternatively, it can be written as:
$$\phi(G)=\min _{S: v o l(S) \neq 0} \frac{|\partial S|}{\min \{\operatorname{vol}(S), \operatorname{vol}(\bar{S})\}}$$


\section{Cheeger's Inequality}
\textbf{Definition 4: Cheeger's Inequality}
$$\frac{\mu_{2}}{2} \leq \phi(G) \leq \sqrt{2 \mu_{2}}$$
Cheeger’s inequality allows us to bound the connectivity of a graph, and get an idea of how “connected” a graph is just from its Laplacian. The left-hand inequality is somewhat easier and more “intuitive” to prove, while the right-hand inequality involves a much more involved proof.
\subsection{Proof of $\frac{\mu_{2}}{2} \leq \phi(G)$}
Remember from last lecture,\\
$$\mu_{2}=\min _{x \neq 0, x \perp v_{1}} \frac{x^{T} \hat{L} x}{x^{T} x}$$
where $\frac{x^{T} \hat{L} x}{x^{T} x}$ is R($\hat{L}$, $x$), the Rayleigh quotient for $\hat{L}$ and nonzero vector $x$.\\
Therefore, we need to construct some $x$, such that it satisfies the two conditions:\\
1) $\mathbf{e}^T D^{\frac{1}{2}} x = 0$;\\
2) $R(\hat{L}, x) \leq 2 \phi(G)$\\
Remember the definition for $\phi(G)$: $\phi(G)=\min _{S \subset V} \phi(S) \text { s.t. } 0<\operatorname{vol}(S) \leq \frac{\operatorname{vol}(V)}{2}$.
Let $S^{*}=\arg \min _{S} \phi(S)$ where $S \subset V$ and $0<\operatorname{vol}(S) \leq \frac{\operatorname{vol}(V)}{2}$, so $\phi(G ) = \phi(S^{*}) = \frac{\partial S^{*}}{Vol(S^{*})}$.\\

Note:
$R(\hat{L}, x) = \frac{x^{T} \hat{L} x}{x^{T} x} = \frac{x^{T} D^{-\frac{1}{2}} L D^{-\frac{1}{2}} x}{x^{T} x}$.\\
Change notation, let $D^{-\frac{1}{2}} x = y$, then $x = D^{\frac{1}{2}} y$. As a result, we can write: 
\begin{equation}
    R(\hat{L}, x) = \frac{y^{T} L y}{y^{T} D y}
\end{equation}

Remember we have shown that $y^{T} L y=\sum_{(i, j) \in E}\left(y_{i}-y_{j}\right)^{2}$ before, plug into equation (1), we have:
\begin{equation}
    R(\hat{L}, x) = \frac{\sum_{(i, j) \in E}\left(y_{i}-y_{j}\right)^{2}}{y^{T} D y}
\end{equation}
Now the problem is to find such a $y$ where 1) and 2) above hold.\\

So define $\mathbf{y}=\mathbb{1}_{S^{*}}$ where $y_{i}=\left\{\begin{array}{ll}
1 & \text { if } i \in S^{*} \\
0 & \text { otherwise }
\end{array}\right.$
Note by such definition, we immediately find that $y^{T} L y=\sum_{(i, j) \in E}\left(y_{i}-y_{j}\right)^{2}=\left|\partial S^{*}\right|$, where the second equality follows from the definition of $y_{i}$, where only an edge crossing from $S$ to $\bar{S}$ will contribute to the summation. However, such definition of $\mathbf{y}$ does not satisfy 1) because $\mathbf{e}^{T} D^{\frac{1}{2}} x = \mathbf{e}^{T} y \neq 0$.

To deal with this, we have to modify the definition of $\mathbf{y}$ slightly. Let $\mathbf{y}^{\prime} = \mathbf{y} - \sigma \times \mathbf{e}$ where $\sigma$ is a variable to be found to make $\mathbf{e}^{T} \mathbf{y}=0$.
Note that we still have $\left(y^{\prime}\right)^{T} L y^{\prime}=\left|\partial S^{*}\right|$. Now the goal is to solve for an appropriate $\sigma$.\\

$\mathbf{e}^{T} \mathbf{y}=0 \Rightarrow \mathbf{e}^{T} D( 1_{S} - \sigma \mathbf{e}) = \sum_{i \in S^{*}} d_{i} (1-\sigma) + \sum_{i \notin S^{*}} d_{i} (-\sigma) = (1-\sigma) Vol(S) - \sigma (Vol(V) - Vol(S) \Rightarrow Vol(S) - \sigma Vol(V) \Rightarrow \sigma=\frac{\operatorname{vol}(S)}{\operatorname{vol}(V)}$. 

Thus, we have found that $\sigma=\frac{\operatorname{vol}(S)}{\operatorname{vol}(V)}$ will make $y^{\prime}$ s.t. $e^{T} y^{\prime} = 0$ and $\left(y^{\prime}\right)^{T} L y^{\prime}=\left|\partial S^{*}\right|$.

Next step, we will compute $\left(y^{\prime}\right)^{T} D y^{\prime}$. \\

$$\left(y^{\prime}\right)^{T} D y^{\prime}=\sum_{i \in[n]} y_{i}^{\prime} d_{i} y_{i}^{\prime}$$
$$=\sum_{i \in S^{*}}(1-\sigma)^{2} d_{i}+\sum_{i \notin S^{*}}(-\sigma)^{2} d_{i}$$
$$=(1-\sigma)^{2} \operatorname{vol}\left(S^{*}\right)+\sigma^{2}\left(\operatorname{vol}(V)-\operatorname{vol}\left(S^{*}\right)\right)$$
$$=(1-\frac{\operatorname{vol}(S^{*})}{\operatorname{vol}(V)}) \operatorname{vol}\left(S^{*}\right)$$
After that we check if such $y^{\prime}$ would make $R(\hat{L}, x)=\frac{y^{\prime T} L y^{\prime}}{y^{\prime T} D y^{\prime}} \leq 2 \phi\left(S^{*}\right)$\\

$$R(\hat{L}, x)=\frac{\left(y^{\prime}\right)^{T} L y^{\prime}}{\left(y^{\prime}\right)^{T} D y^{\prime}} = \frac{\left|\partial S^{*}\right|}{(1-\sigma) \operatorname{vol}\left(S^{*}\right)} =\frac{\phi\left(S^{*}\right)}{1-\sigma}\leq 2 \phi\left(S^{*}\right) = 2 \phi (G)$$
using the fact that $Vol(S) \leq \frac{1}{2} Vol(V)$ and $\phi(S^{*}) = \phi(G)$.






\subsection{Proof of $\phi(G) \leq \sqrt{2 \mu_{2}}$}
Introduction behind the proof:
$$\mu_{2}=\min _{x \in \mathbb{R}^{n},x \neq 0, x \perp v_{1}}{R(x)} $$
x need not look like $$x=D^{1 / 2}(\mathbb{1}s-\sigma \times \mathbf{e})$$
We now use Spectral Partitioning Algorithm: \\
Find a set S with $$ \phi(s) \leqslant \sqrt{2 \mu_{2}} \text { . }$$
Build $\mathrm{S}$ from $2^{\text {nd }}$ eigenvector $V_{2}=\underset{x \neq 0 \atop x \perp V_{1}}{\operatorname{arymin}} R(x) \quad \in \mathbb{R}^{n}$\\
\text {Sort all nodes }$$i \in[n]$$

$$\pi_{1}, \pi_{2}, \ldots \pi_{n} \in[n]: \quad V_{2} \pi_{i} \leqslant V_{2}, \pi_{i+1}$$
Iterate i=1,2,...,n-1, consider
$$ \quad S_{i}=\left\{\pi_{1}, \pi_{2}, \ldots \pi_{1}\right\}$$
and compute $$\phi\left(s_{i}\right)=\frac{\partial s}{\min \left\{vol(s), vol\left(s^{\prime}\right)\right\}}$$

\subsection{Example}
Now we give an example:\\
\includegraphics[width = 0.5\textwidth]{p1.png}
   $$\text {            Weight of edge }=\frac{1}{\text { difference in gray scale }}$$
Now what we want to do is to find a cut that minimizes weight of cut edges, and we can get $$\phi(s)=\frac{\partial S}{\operatorname{vol}(s)} .$$
Remark:Spectral Partitioning Algorithm runs in $\mathrm{O}(\mathrm{m}+\mathrm{nlgn})$ time after having computed $\mathrm{V}_{2}$.\\



\section{Optimization}
Now we are going to talk about:\\
——Linear Programming and the quality:\\
One of the main goals here will be to give a polynomial time algorithm following a program.\\
——Gradient Descent, Newton method $\left(2^{\text {nd }}\right.$ method)\\
\text{——IPM(Interior Point Method)}\\

\subsection{General Optimization Problem}
We usually want to maximize or minimize f(x), which is subject to $\mathrm{x} \in F \subset \mathbb{R}^{n}$, called feasible set.And linear programming is a instance.\\




\noindent \textbf{Problem 1:}
Computing $\phi(G)=\underset{\min \mathrm{s}}{\phi}(S) \quad$ var: $\quad \mathrm{x} \in \mathbb{R}^{\mathrm{h}}, x_{i} \in\{0,1\},$ whether $\mathrm{i} \in S$\\
\noindent \textbf{Solution 1:}\\
What we want is $$\min f(x)=\min \frac{\sum_{i j \in \ E}\left(x_{i}-x_{j}\right)^{2}}{\sum x_{i}^{2}}$$
We can take absolute values certain like this, level of generality. Usually having these little squares, not optimal values leads to nicer optimization problems. And this is what x transpose x rays, which is a summation of x ray squared.\\
There are more constrains that it is divided by the volume. Where volume was summation, over degree I. So we have $$\min f(x)=\min \frac{\sum_{i j \in \ E}\left(x_{i}-x_{j}\right)^{2}}{\sum_{i=1}^{n} d_{i} x_{i}}  \qquad (1)$$\\
The volume has to be positive, so $$\sum x_{i} \geqslant 1  \qquad(2)$$ \\
There should be at least one node there. And everyone is as volume has to be at most half volume of the entire reference summation of J. And we get $$\sum_{i=1}^{n} d_{i} x_{i} \leqslant \frac{1}{2} \sum_{i=1}^{n} d  \qquad (3)$$\\
$x_{i}$ is either 0 or 1, so we have $$x_{i}\left(x_{i}-1\right)=0   \qquad (4)$$\\
Combine (1),(2),(3),(4), we get $\phi(G)$.\\
And combine (2),(3),(4), we get set F.\\
This is so called NP-hard problem. These are the main barriers to being able to solve these and put them in real time. And the ratio in (1) is actually not an issue because we can always intimidate dissidents. Anyway, this is just an example connecting us to this chapter of an opposition problem. We don't expect to solve all of condition problems in a little time, but we hope to solve some of them. And there are different classes of of optimization problems that are solvable. The most classic example is linear program.

\subsection{Linear Programming}
Linear Programming is basically optimization set of transition problems where f is linear:$f(x)=c^{T} \cdot x$.\\
F is a linear as well.
F is defined as follows $A x \geqslant b$ $A_{i} x_{i} \geqslant b_{i}$.
We have the most general form of linear programming:
$$\min \left\{\mathbf{c}^{\mathrm{T}} \mathbf{x} \mid A x \geqslant b \wedge \mathbf{x} \geq 0\right\}$$

\end{document}
