\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}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{mleftright, xspace,hyperref, todonotes}
% Probability
\newcommand{\proba}{\Pr}
\newcommand{\probaOf}[1]{\proba\!\left[\, #1\, \right]}
\newcommand{\probaCond}[2]{\proba\!\left[\, #1 \;\middle\vert\; #2\, \right]}
\newcommand{\probaDistrOf}[2]{\proba_{#1}\left[\, #2\, \right]}

% Support of a distribution/function
\newcommand{\supp}[1]{\operatorname{supp}\!\left(#1\right)}
% Expectation & variance
\newcommand{\expect}[1]{\mathbb{E}\!\left[#1\right]}
\newcommand{\expectCond}[2]{\mathbb{E}\!\left[\, #1 \;\middle\vert\; #2\, \right]}
\newcommand{\shortexpect}{\mathbb{E}}
\newcommand{\var}{\operatorname{Var}}

% Distributions
\newcommand{\uniform}{\ensuremath{\mathcal{U}}}
\newcommand{\uniformOn}[1]{\ensuremath{\uniform\!\left( #1 \right) }}
\newcommand{\geom}[1]{\ensuremath{\operatorname{Geom}\!\left( #1 \right)}}
\newcommand{\bernoulli}[1]{\ensuremath{\operatorname{Bern}\!\left( #1 \right)}}
\newcommand{\bern}[2]{\ensuremath{\operatorname{Bern}^{#1}\!\left( #2 \right)}}
\newcommand{\binomial}[2]{\ensuremath{\operatorname{Bin}\!\left( #1, #2 \right)}}
\newcommand{\poisson}[1]{\ensuremath{\operatorname{Poisson}\!\left( #1 \right) }}
\newcommand{\gaussian}[2]{\ensuremath{ \mathcal{N}\!\left(#1,#2\right) }}
\newcommand{\gaussianpdf}[2]{\ensuremath{ g_{#1,#2}}}
\newcommand{\betadistr}[2]{\ensuremath{ \operatorname{Beta}\!\left( #1, #2 \right) }}

% Norms
\newcommand{\norm}[1]{\lVert#1{\rVert}}
\newcommand{\normone}[1]{{\norm{#1}}_1}
\newcommand{\normtwo}[1]{{\norm{#1}}_2}
\newcommand{\norminf}[1]{{\norm{#1}}_\infty}
\newcommand{\abs}[1]{\left\lvert #1 \right\rvert}
\newcommand{\dabs}[1]{\lvert #1 \rvert}

\newcommand{\vect}[1]{\mathbf{#1}} 			% shortcut

% Sets and indicators
\newcommand{\setOfSuchThat}[2]{ \left\{\; #1 \;\colon\; #2\; \right\} } 			% sets such as "{ elems | condition }"
\newcommand{\indicSet}[1]{\mathbf{1}_{#1}}                                              % indicator function
\newcommand{\indic}[1]{\indicSet{\left\{#1\right\}}}                                             % indicator function
\newcommand{\disjunion}{\amalg}%\coprod, \dotcup...

\newcommand{\eps}{\ensuremath{\varepsilon}\xspace}
\newcommand{\eqdef}{\stackrel{\rm def}{=}}

% Complexity
\newcommand{\littleO}[1]{{o\mleft( #1 \mright)}}
\newcommand{\bigO}[1]{{O\mleft( #1 \mright)}}
\newcommand{\bigTheta}[1]{{\Theta\mleft( #1 \mright)}}
\newcommand{\bigOmega}[1]{{\Omega\mleft( #1 \mright)}}
\newcommand{\tildeO}[1]{\tilde{O}\mleft( #1 \mright)}
\newcommand{\tildeTheta}[1]{\operatorname{\tilde{\Theta}}\mleft( #1 \mright)}
\newcommand{\tildeOmega}[1]{\operatorname{\tilde{\Omega}}\mleft( #1 \mright)}
\providecommand{\poly}{\operatorname*{poly}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%




\newcommand{\handout}[5]{
  \noindent
  \begin{center}
  \framebox{
    \vbox{\vspace{0.25cm}
      \hbox to 5.78in { {COMS E6998-9:\hspace{0.12cm}Algorithmic
          Techniques for Massive Data} \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}{Scribe:\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{\R}{\mathbb{R}}
\newcommand{\E}{\mathbb{E}}
\usepackage{parskip}

\begin{document}

\lecture{9 -- Fast Dimension Reduction}{Oct 6, 2015}{Instructor:\hspace{0.08cm}\emph{Alex Andoni}}{\emph{Negev Shekel Nosatzki}}

\section{Johnson-Lindenstrauss Summary}

\begin{itemize}

	\item $F(x) = \frac{1}{\sqrt{k}}G_{k*d}x$
	\item $\norm{F(x)} = (1 \pm \epsilon)\norm{x}$ with probability $\geq 1-\delta$
	\item $k = O(\frac{1}{\epsilon^2} \log \frac{1}{\delta})$
	\item Takes time $O(k\cdot d)$ as we need to calculate k*d dense matrix
\end{itemize}

\section{Fast Johnson-Lindenstrauss Transformation Idea and Issues}
\subsection{Running Time Goal}
\begin{itemize}
	\item $O(d+k)$ is optimal goal
	\item We'll show $O(d \log d + k^3)$
\end{itemize}
\subsection{Sampling}
To improve the algorithm speed, we can sample s entries from each row.
We can define:
\begin{itemize}
	\item $h: [d]\rightarrow\{0,1\}$
	\item $\Pr[h(i) = 1] = \frac{s}{d}$
\end{itemize}
And compute:
\begin{itemize}
	\item $z = \sqrt{\frac{d}{s}}\sum_{i=1}^d h(i) \cdot g_i x_i$
	\item $\E[\norm{z}^2] = \frac{d}{s}\E[\sum_{i=1}^k h(i) \cdot g_i^2 x_i^2] = \norm{x}^2$
\end{itemize}

While this tactic works when x is dense, x can be sparse which can create large variance.
\subsection{Example of sparse x}
Consider the case where $x = e_1 - e_2 \Longrightarrow$ even choosing relatively large sample size $s=\frac{d}{k}$ has high chance to fail since $\Pr[h(1)=1 \wedge h(2)=1] = (\frac{s}{d})^2 = \frac{1}{k^2}$.\newline
And since we have k rows the overall chance is $\frac{1}{k}$ which is too high.
\subsection{Spreading x}
To solve the above issue we will "spread-around" x and use sparse G.

\section{FJLT construction}
\includegraphics[width=\textwidth]{zPHD}
\subsection{Spreading x into y - Overview}
The idea is to spread x into y, by defining $y=HDx$. y is in dimension d (like x) and $\norm{y} = \norm{x}$. However, unlike x, we will be able to provide certain guarantees as to the maximum coordinate values, and therefore we can project y into lower-dimensional z using a sparse matrix P with high probability.
\subsection{Definitions}
\begin{itemize}
	\item D = diagonal matrix with random $\pm 1$ on diagonal
	\item H = Hadamard Matrix = Fourier Transform
	\item P = Projection Matrix - similar to previous G but sparse and dimension $k'*d$, with $k' \approx k^2$ 
\end{itemize}
\subsection{Why Fourier Transform?}
Fourier Transform is non-trivial rotation. A trivial rotation (i.e. random) takes $O(d^2)$ to compute, while FT takes $O(d \log d)$.
$$H_1 = 1$$
$$H_{2^l} = \frac{1}{\sqrt{2}}\left( \begin{array}{cc}
H_{2^{l-1}} & H_{2^{l-1}} \\
H_{2^{l-1}} & -H_{2^{l-1}}\end{array} \right)$$
$$H_{d*d} = \left( \begin{array}{c}
H_1 \\ H_2 \\ ... \\ H_i \\ ... \\ H_d\end{array} \right)$$
Where $H_{ij} = \pm \frac{1}{\sqrt{d}}$.\newline
Therefore, $y_i = H_iDx = rx$, where $rx$ is a random vector of $\pm \frac{1}{\sqrt{d}}$\newline

\begin{lemma}
	$r\cdot x$ behaves like $g \cdot x$
\end{lemma}
This needs to be proved (wasn't proved in class). Also, we need to bound $y_i$.\newline
\begin{lemma}
	$\Pr[y_i^2 \leq \frac{1}{d}\cdot O(\log\frac{1}{\delta})] \geq 1-\delta$
\end{lemma}
\begin{proof}
	We will approximate $y_i \approx g \cdot x \sim l$ where l is Gaussian $\Longrightarrow \frac{1}{\sqrt{2\pi}}\cdot e^\frac{-l^2}{2} < \delta$ when $l \approx \sqrt{\log\frac{1}{\delta}}$	
\end{proof}
\subsection{Why do we need D?}
If x is sparse, then $Hx$ is dense. However $\exists$ dense $x$ s.t. $Hx$ is sparse. $D$ fixes it by randomizing $H$ ($HD$ is randomization of $H$) and since there are very few such dense $x$, randomization fixes that issue.
\subsection{$y_i$ Dependence - issue?}
Clearly, $y_i$ are not independent:
\begin{itemize}
	\item $y_1 = H_1Dx$
	\item $y_2 = H_2Dx$
	\item and so on.
\end{itemize}
However, since we are only rotating, the norm doesn't change: $\norm{y} = \norm{x}$!
\section{P Projection}
	\subsection{Density of y}
	As we saw: $y_i^2 \leq \frac{1}{d} \cdot O(\log\frac{1}{\delta})$ with prob. $1-\delta$; and since y has d coordinates, we get:
	\begin{align}
	m &= \max y_i^2 \leq \frac{1}{d} \cdot O(\log\frac{1}{\delta}) \text{ with prob. } 1-d\delta \Longrightarrow \\
	m &\leq \frac{1}{d} \cdot O(\log\frac{d}{\delta}) \text{ with prob. } 1-\delta
	\end{align}
	\subsection{Projecting to z}
	Define:
	\begin{itemize}
		\item $j \in [k']$
		\item $z_j = y_i$ for random $i \in [d] \rightarrow \forall i,j; \Pr[z_j=y_i] = \frac{1}{d}$
		\item Assume w.l.o.g $\norm{x} = 1$
	\end{itemize}
	\paragraph{}
	\begin{claim}
		$\norm{z}^2 = (1\pm\epsilon)\norm{x}^2$ with prob. $1-2\delta$	
	\end{claim}
	We want to show $\sum_j z_j^2$ concentrates.\newline\newline
	Define:
	\begin{itemize}
		\item $t_j = \frac{z_j^2}{m} \in [0,1]$
		\item $\mu = \E[\sum_{j=1}^{k'} t_j]$
	\end{itemize}
	\begin{proof}
	\begin{align}
		&\mu = \E[\sum_j \frac{z_j^2}{m}] = \frac{1}{m}\sum_j[\frac{1}{d}y_1^2 + \frac{1}{d}y_1^2 + ...] = \frac{1}{md}\sum_j\norm{y} = \frac{k'}{md} \Longrightarrow \\
		\text{Chernoff:} &\Pr[\sum_j t_j \notin (1 \pm \epsilon)\mu] \leq 2e^\frac{-\epsilon^2\mu}{3} = 2e^\frac{\epsilon^2k'}{3md} < \delta \Longrightarrow \\
		&k' = m \cdot d \cdot \frac{3}{\epsilon^2} \cdot \ln\frac{2}{\delta} = O(\log\frac{d}{\delta} \cdot \frac{1}{e^2} \cdot \log \frac{1}{\delta})
	\end{align}
	Since each of Chernoff and m can deviate from bound with prob. $\delta$, the overall success rate is $1-2\delta$.
	\end{proof}
	\section{Time analysis and further reduction}
	So far we reduced dimension d to k' with time $O(d\log d + k')$:
	\begin{itemize}
		\item $d \log d \rightarrow HDx$ multiplication
		\item $k' \rightarrow$ Projection 
	\end{itemize}
	To further reduce dimension from $k'$ to $k=O(\frac{1}{\epsilon^2}\log \frac{1}{\delta})$, we can apply regular (dense) JL on z:
	\begin{itemize}
		\item $Gz$ projection takes $k' \cdot k$ time.
		\item Final time for $d \rightarrow k$ dimension reduction: $O(d \log d + k \cdot k') = O(d \log d + k^3)$
	\end{itemize}
	\subsection{Example}
	Assume:
	\begin{itemize}
		\item $d=\log^3 n$
		\item $\delta = \frac{1}{n^2}$
	\end{itemize}
	We get:
	\begin{align}
		k &= O(\frac{1}{\epsilon^2} \log n) \\
		k' &= O(\frac{1}{\epsilon^2}\log^2 n) \\
		\text{FJL Time} &: O(\log^3 n \log \log n + \frac{1}{\epsilon^4}\log^3 n) \\
		\text{JL Time} &: O(dk) = O(\frac{1}{\epsilon^2}\log^4 n) 
	\end{align}
	Since we assume $\epsilon$ is constant $\Rightarrow$ FJL Time $\ll$ JL Time. 
	\subsection{Optimal time}
	What can we hope for?
	\begin{itemize}
		\item $O(d + k)$ or $O(d \log d +k)$
		\item Assume $d=\log n$
		\item JL Time: $O(dk) \approx \log^2 n$
		\item Optimal Time: $O(d+k) \approx \log n$
	\end{itemize}
\end{document}