\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{amsmath}
\usepackage{amssymb}
\usepackage[ruled,vlined]{algorithm2e}
\usepackage{mathtools}
\newcommand{\defeq}{\vcentcolon=}
\newcommand{\R}{\mathbb{R}}
\newcommand{\norm}[1]{\left\lVert#1\right\rVert}

\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{7: Dimension Reduction}{Feb 02,
  2021}{Instructor:\hspace{0.08cm}\emph{Alex Andoni }}{\emph{Zixuan Zhang, Linxiao Wu}}

\section{Introduction:}
This lecture mainly focuses on dimension reduction: Johnson-Linderstrauss Lemma and especially its
distributional version. Chi-squared distribution is introduced when there is a sum of Gaussian distributed
variables.

\section{Last time Recap}
\subsection*{Tug-of-War+ Algorithm}
\begin{enumerate}
    \item Frequency vector $f \in \R_+^{n}$
    \item Goal: estimate $F_2 = \norm{f}_2^2$
    \item 
\end{enumerate}

\begin{algorithm}[H]
\SetAlgoLined
% \KwResult{a data structure using $O(n)$ space, $O(1)$ query time, $O(n)$ construction time}
%  Pick some random $h : U \to [m]$ where $m=n$ \\
 \For{$i = 1,2, \dots, k$, where $k = O(\frac{\lg n}{\epsilon^2})$}{
  pick $r_{ij} \in \{\pm 1\}$, $j \in [n]$
  
  % \[ \sum_{n=1}^{\infty} 2^{-n} = 1 \]
  sketch: $Z_i = \sum_{j=1}^{n}{r_{ij}f_j}$
  }
  


\textbf{return} Estimator: $Z \defeq \frac{1}{k}\sum_{i=1}^{k}Z_i^2$
 \caption{Tug-of-War+ Algorithm: repeat ToW k times, and take the average of the estimators.}
\end{algorithm}

\subsection*{Better complexity}

If probability fails $\leq$ $\delta$ where $\delta$ is some parameter.

\begin{equation}
    Pr[Z^2 = (1 \pm \epsilon) F_2] \geq 1 - \delta
\end{equation}

as long as $k \geq \Omega(\frac{1}{\delta} \cdot \frac{1}{\epsilon^2})$

Question to today's lecture: Can we get better dependence on $\delta$?

\begin{claim}
Yes, and in fact we can get $k = O(\frac{\lg (1/\delta)}{\epsilon^2})$
\end{claim}

\section{Dimension Reduction}
\noindent\textbf{Definition 1}:(Sketch function). \emph{For $x \in \mathbb{R}^n$, a sketching function $ \varphi: \mathbb{R}^n -> \mathbb{R}^k$ is defined as:
\begin{align*}
    \varphi(x) = \sigma \cdot x = \frac{1}{\sqrt{k}}(\sum\sigma_{1i}x_i, \sum\sigma_{2i}x_i, ..., \sum\sigma_{ki}x_i)
\end{align*}}
Note that $\sigma \in \mathbb{R}^{k \times n}$ . We can use $\varphi$ as an estimator of the L2 norm of its argument:
\begin{align*}
    \Vert \varphi(f) \Vert_2^2=(1 \pm \epsilon) F_2
\end{align*}


\noindent\textbf{Definition 2}:(Linearity). \emph{If sketching function $\varphi$ is linear, the following properties hold true:
\begin{align*}
    \varphi(x \pm y) = \varphi(x) \pm \varphi(y)
\end{align*}
}

\subsection{Johnson-Lindenstrauss Lemma}
\noindent\textbf{Lemma}:\emph{
$\forall \epsilon >0$, there exists a linear, randomized function $\varphi$ such that: $\forall x, y \in \mathbb{R}^n$:
\begin{align*}
    Pr[\Vert \varphi(x) - \varphi(x) \Vert \in (1 \pm \epsilon)\Vert x - y\Vert] \geq 1 - e^{\frac{-\epsilon^2 k}{9}}
\end{align*}
}

\begin{proof} 
Because $\varphi$ is linear, we have $\varphi(x) - \varphi(x) = \varphi(x-y)$. If we define $z=x-y$, the original lemma is equivalent to:
\begin{align*}
    Pr[\Vert \varphi(z) \Vert \in (1 \pm \epsilon)\Vert z\Vert] \geq 1 - e^{\frac{-\epsilon^2 k}{9}}
\end{align*}
Note that there could be various implementation of $\varphi$:
\begin{itemize}
    \item we could use Tug-of-war algorithm where $\sigma_{ij} = {\pm1}$
    \item $\varphi$ maps $\mathbb{R}^n$ to a random k-dim linear subspace 
    \item Similar to Tug-of-war but $\sigma_{ij} \sim N(0, 1)$
\end{itemize}

Recall: We proved the correctness of Tug-of-War by showing: 
\begin{itemize}
    \item $\mathbb{E}[\sigma_i] = 0$
    \item $\mathbb{E}[\sigma_i^2] = 1$
    \item $\mathbb{E}[\sigma_i^4] = 1$
\end{itemize}
Here we adopt the third implementation, which also satisfies the above conditions. Before moving onto the rest of the proof, we must understand the following properties: \\

\noindent\textbf{Definition}(Stability Property):
\begin{align*}
    \sum_{i=1}^ng_ix_i \sim \Vert x \Vert_2 \cdot a = \sum x_i^2 \cdot a;\ where\ a \sim N(0, 1) 
\end{align*}

\noindent\textbf{Property}(Spherically Symmetric):
For a vector $b = (b_1, b_2, ..., b_n)$ where $b_i \sim N(0,1)$ are i.i.d

\begin{align*}
    pdf(b) = \Pi \frac{1}{\sqrt{2\pi }} e^{\frac{-b_i^2}{2}} 
    = \frac{1}{(2 \pi )^{\frac{n}{2}}} e ^ {\frac{- \Vert g \Vert_2^2}{2}}
\end{align*}

Now, let's rewrite the definition of $\varphi$:
\begin{align*}
    \varphi(z) ={}& \frac{1}{\sqrt{k}}(\sum_jg_{1j}z_j, \sum_jg_{2j}z_j, ..., \sum_jg_{kj}z_j) \\
    ={}& \frac{1}{\sqrt{k}}(\Vert z \Vert g^{(1)}, \Vert z \Vert g^{(2)}, ..., \Vert z \Vert g^{(k)}) \\
    ={}& \frac{\Vert z \Vert }{\sqrt{k}} (g^{(1)}, g^{(2)}, ..., g^{(k)}) \xrightarrow[]{} k-dim\ Gaussian  \\
    \Vert \varphi(z) \Vert^2 ={}& \frac{1}{k} \sum_{j=1}^k (g^{(j)})^2 \cdot \Vert z \Vert^2 \\
    ={}& \Vert z \Vert^2 \frac{1}{k}\sum_j (g^{(j)})^2 \\
    ={}& \Vert z \Vert^2 \boldsymbol{\chi_k^2}, where\ \chi\ is\ the\ Chi\ square\ distribution
\end{align*}

\noindent\textbf{Fact}: 
\begin{align*}
    P[\chi_k^2 \notin (1 \pm \epsilon)] \leq e^{\frac{-\epsilon^2 k}{9}}
\end{align*}
Therefore, we have: 
\begin{align*}
    Pr[\Vert \varphi(z) \Vert \in (1 \pm \epsilon)\Vert z\Vert] ={}& 1 - Pr[\Vert \varphi(z) \Vert \notin (1 \pm \epsilon)\Vert z\Vert]\\
    \geq{}&  1 - e^{\frac{-\epsilon^2 k}{9}}
\end{align*}
Q.E.D
\end{proof}

\begin{corollary} (of Johnson-Linderstrauss '84)

\begin{itemize}
    \item fix N vectors $x_1, x_2, \dots, x_N \in \R^n$, pick $\Phi$ as in Johnson-Linderstrauss, with $k = \Theta(\frac{\lg N}{\epsilon^2})$
    
    \item $Pr_{\Phi}[\forall i,j \in [N], \norm{\Phi{x_i} - \Phi{x_j}} = (1 \pm \epsilon)\norm{x_i - x_j}] \geq 1 - \frac{1}{N}$
\end{itemize}

\end{corollary}

\begin{proof} fix $k = \frac{3 \cdot 9 \cdot \ln N}{\epsilon^2}$

Then, by Johnson-Linderstrauss, $\forall i,j \in [N]$

$$
Pr[\norm{\Phi{x_i} - \Phi{x_j}} \notin (1 \pm \epsilon)\norm{x_i - x_j}] \leq e^{\frac{-\epsilon^2k}{9}} = \frac{1}{N^3}
$$

Recall the union bound theorem

$$
{\displaystyle \mathbb {P} \left(\bigcup _{i}A_{i}\right)\leq \sum _{i}{\mathbb {P} }(A_{i}).}
$$

By Union bound over all pairs for $i, j \in [N]$

\begin{align*}
    Pr_{\Phi}[\exists i,j\ pair\in [N], \norm{\Phi{x_i} - \Phi{x_j}} \notin (1 \pm \epsilon)\norm{x_i - x_j}] &\leq \sum_{i,j\ pairs}Pr[\norm{\Phi{x_i} - \Phi{x_j}} \notin (1 \pm \epsilon)\norm{x_i - x_j}] \\
    & \leq N^2 \times \frac{1}{N^3} \\
    & = \frac{1}{N}
\end{align*}

\end{proof}

Rephrase: For $\forall$ N vectors in $\R^n$, can map them in to $\R^k$, where k = $O(\frac{\lg N}{\epsilon^2})$ while preserving distance $1 \pm \epsilon$

\subsection*{Dimension Reduction in Other space}
\textbf{Remark:} Can we do the same for $l_1$? 

Recall that

$$
l_1^d: \R^d\ where\ \norm{x - y}_1 = \sum_{i=1}^n\norm{x_i - y_i}
$$

For $l_1$: $N$ vectors into lower dimension $l_1$:
$$
k = N^{\Omega(\frac{1}{\alpha})}
$$

for $\alpha$-approximation. 

\end{document}
