\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{8 -- Dimension Reduction}{Oct 1, 2015}{Instructor:\hspace{0.08cm}\emph{Alex Andoni}}{\emph{Kevin Shi}}

\section{Dimension Reduction}

Exact algorithms typically have linear or worse complexity in the dimension. As an example, consider the nearest neighbor search problem. The naive solution of computing the distance from the query point to every training point takes time $O(n\cdot d)$ and space $O(n\cdot d)$. The query time can be improved up to $O(\log n \cdot d)$ by constructing a Voronoi diagram around each point. 

Approximate distance preserving dimension reduction cannot be for all points. To see this, suppose $f: \R^n \rightarrow \R^m$ is a function which preserves distance approximately, that is, $(1-\alpha)\|x-y\| \le \|f(x)-f(y)\| \le (1+\alpha)\|x-y\|$. Then $f$ must be a continuous function; given any $\epsilon > 0$, just choose $\delta = \frac{\epsilon}{1+\alpha}$. 
But from standard results in point-set topology, there does not exist a continuous mapping from $\R^n$ to any lower dimensional Euclidean space.

\section{Johnson-Lindenstrauss}

If a subset of points from $\R^n$ is fixed, then dimension reduction can be done while preserving the $l_2$ norm of each point with high probability. 

\begin{claim}

There exists a randomized linear map $F: l_2^d \longrightarrow l_2^k$, with $k << d$, such that for all $x,y \in l_2^d$,

\[\|x-y\| \le \|F(x)-F(y) \| \le (1+\epsilon)\|x-y\|\]

with probability at least $1-\exp(-C\epsilon^2 k)$. 

\end{claim}

Note that in the statement of the theorem, the query points are fixed first, and then the random linear map is drawn. Johnson-Lindenstrauss does not hold if the query points are allowed to be chosen adaptively. To prove this statement, we need the following stability property of the Gaussian distribution. 

\begin{lemma}
Fix $x \in \R^d$. Given $d$ draws $g_i \stackrel{iid}{\sim} \mathcal{N}(0,1)$, then $\sum_i g_ix_i$ is distributed as $\|x\|_2 g$ where $g \sim \mathcal{N}(0,1)$. 
\end{lemma}

In other words, the weighted sum of Gaussian random variables is itself distributed as a Gaussian. The Gaussian distribution is the only 2-parameter distribution which is stable.

\begin{proof}[Proof of Lemma]

The claim is immediate if $x = e_i$ for some coordinate vector $e_i.$. Note that $(g_1,\cdots,g_d)$ is a spherical Gaussian and thus the projection onto any vector $x$ only depends on the $l_2$-norm of $x$. Thus the projection is just $\|x\| \langle \frac{x}{\|x\|}, g\rangle$. Now we can change the basis so that $\frac{x}{\|x\|}$ is a coordinate vector without changing the norm $\|x\|$, so it is sufficient to just consider $x = e_i$. 
\end{proof}


%\begin{proof}
%The claim is immediate if $x = e_i$ for some coordinate vector $e_i$. Now we prove the equality for a unit vector $x = \alpha e_1 + \beta e_2$ where $\alpha^2+\beta^2=1$ by computing the moment generating function. 

%\begin{align*}
%\E[\exp(t(\alpha g_1 + \beta g_2))] &= \E[\exp(t\alpha g_1) \exp(t\beta g_2)]\\
%&= \E[\exp((\alpha t)g_1)] \E[\exp((\beta t)g_2)]\\
%&= \exp\left(\mu \alpha t + \frac{1}{2}\sigma^2 \alpha^2 t^2\right) \exp\left(\mu \beta t + \frac{1}{2}\sigma^2 \beta^2 t^2\right)\\
%&= \exp\left( \mu (\alpha+\beta) t + \frac{1}{2}\sigma^2(\alpha^2+\beta^2)t^2\right)\\&
%\end{align*}

%This is a Gaussian distribution with mean $\mu(\alpha+\beta)$ and variance $\sigam^2(\alpha^2+\beta^2)=\sigma^2$. Note that $\|x\|

%\end{proof}


\begin{proof}[Proof of Claim] 
It is sufficient to prove that the Johnson Lindenstrauss transform preserves the norm of a vector $z$ with high probability (let $z = x-y$). 
First we consider the case of a random linear function $f: l_2^d \longrightarrow l_2$. The expectation for this is
\begin{align*}
\E[\|f(z)\|^2] &= \E[\|z\|^2 g^2]\\
&= \|z\|^2 \E[g^2]\\
&= \|z\|^2
\end{align*}

The general embedding is obtained by repeat this one-dimensional embedding $k$ times, so that

\[F(z) = \frac{1}{\sqrt{k}} (G_1z, G_2 z,\cdots, G_k z) = \frac{1}{\sqrt{k}} Gz\]

where $G$ is a $k\times n$ Gaussian random matrix where each entry is drawn from $\mathcal{N}(0,1)$. By the stability property,

\[F(z) \stackrel{d}{=} \frac{1}{\sqrt{k}} (\|z\| a_1,\cdots, \|z\|a_k)\]

where each $a_i \sim \mathcal{N}(0,1)$. The squared norm of this embedding is distributed as

\begin{align*}
\left\|\frac{1}{\sqrt{k}} Gz\right\|^2&= \sum_i \frac{1}{k} (G_iz)^2\\
&= \frac{1}{k}\|z\|^2 \sum_{i=1}^k G_i^2\\
\end{align*}

Recall that each $G_i$ is a Gaussian drawn from $\mathcal{N}(0,1)$, so this is an unbiased estimator. The random variable $\displaystyle\sum_{i=1}^k G_i^2$ is a chi-squared distribution with $k$ degrees of freedom. For this distribution we have the following two concentration results:

\begin{align*}
\Pr[\mathcal{X}_k^2 \ge (1+\epsilon)k] \le \exp\left(-\frac{k}{4}(\epsilon^2-\epsilon^3)\right)\\
\Pr[\mathcal{X}_k^2 \le (1-\epsilon)k] \le \exp\left(-\frac{k}{4}(\epsilon^2-\epsilon^3)\right)
\end{align*}

which show that $F(z)$ is within $(1\pm \epsilon)$ of $\|z\|$. 

\end{proof}

The Johnson Lindenstrauss transform can be thought of as projecting $x$ into an almost-orthogonal coordinate system. Given two independent Gaussian vectors $g_1,g_2$, their inner product $\frac{g_1}{\|g_1\|} \cdot \frac{g_2}{\|g_2\|}$ has the same distribution as if $g_1 = e_1$ since $g_2$ is a spherical Gaussian. Thus this distribution is approximately equal to $\frac{g_2}{\sqrt{d}}$ since $\E[\|g\|] = \sqrt{d}$. Note that the variance of this normalized dot product decreases with the dimension $d$, so for large $d$ if we take $k << d$ independent unit Gaussian random vectors, then with high probability they are nearly all orthogonal. 

%More specifically, let $g_1,g_2$ be independent normalized Gaussian vectors (note the different coordinates are not independent). Then we have

%\begin{align}
%\E\left[\sum_i (g_1)_i (g_2)_i \right] &= 0\\
%\E\left[(\sum_i (g_1)_i (g_2)_i )^2\right] &= \E\left[ \sum_i (g_1)_i^2(g_2)_i^2 + 2\sum_{i\neq j} (g_1)_i (g_2)_i (g_1)_j (g_2)_j\right]\\
%&= \E\left[ \sum_i (g_1)_i^2(g_2)_i^2 \right] + 0\\
%&\le \E\left[ \sqrt{\sum_i (g_1)_i^4} \sqrt{\sum_i (g_2)_i^4}\right]\\
%&= \E\left[ \sqrt{\sum_i g_i^4}\right] \E\left[ \sqrt{\sum_i g_i^4}\right]\\
%&\le \sqrt{\E\left[ \sum_i g_i^4\right]}^2\\
%&= \E\left[ \sum_i g_i^4\right]
%\end{align}

%where $(4)$ is from Holder's inequality, $(5)$ from independence of $g_1,g_2$, and $(6)$ from the fact that the square root function is concave. 

%where $d$ is the dimension of the original space. Note that 

\section{Dimension reduction for the $l_1$ norm}

There is an analogous distribution which has the stability property for the $l_1$ norm. The Cauchy distribution is defined as

\[p(s) = \frac{1}{\pi(s^2+1)}\]

and has the property

\[\sum c_iz_i \sim c\cdot \|z\|_1\]

However this distribution is heavy tailed - $\E[s] = \infty$. Thus by a similar argument to a homework problem from last time, taking the mean here over several independent copies of the estimate does not give a good estimator. However, we can still obtain a good estimator with high probability by taking the median. An estimator can be arbitrarily bad (e.g. infinite expectation) but still give the correct answer with high probability. More details next time...

\end{document}