\documentclass[11pt]{article}
% Problem set: do not define TEMPLATE or SOL
% LaTeX template: define TEMPLATE but not SOL
% Solution: define both TEMPLATE and SOL
%\def\sol{1}
\def\template{1}
\usepackage{fullpage,graphicx}
\usepackage{amsmath,amsfonts,amsthm,amssymb,multirow}
\usepackage{algorithmic,comment,url,enumerate}
\usepackage{tikz}
\usepackage{framed}
\usetikzlibrary{decorations.pathreplacing, shapes}
\usepackage[ruled,vlined,commentsnumbered,titlenotnumbered]{algorithm2e}
\newcommand{\expecting}[1]{\noindent{[\textbf{We are expecting:} \em #1\em]}}
\newcommand{\hint}[1]{\noindent{[\textbf{HINT:} \em #1\em]}}
\newcommand{\pts}[1]{\textbf{(#1 pt.)}}
\newcommand{\sgn}{\mathrm{sgn}}
\definecolor{shadecolor}{gray}{0.95}
\newcommand{\clarification}[1]{\noindent{[\textbf{Clarification:} \em #1 \em]}}

\usepackage{mathtools}
\newcommand{\bE}{\ensuremath{\mathbb{E}}}
\newcommand{\bR}{\ensuremath{\mathbb{R}}}
\newcommand{\cE}{\ensuremath{\mathcal{E}}}
\newcommand{\eps}{\ensuremath{\epsilon}}
\newcommand{\rank}{\ensuremath{\mathrm{rank}}}
\newtheorem{theorem}{Theorem}

\begin{document}
\noindent
\textbf{Problem Set 4 \ifdefined\sol Solution \fi} \hfill CS265, Autumn 2022
\ifdefined\sol\else
\newline
Due: Friday 10/28 at 11:59pm on Gradescope
\ifdefined\template
\newline 
%Group members: INSERT NAMES HERE
\fi

\vspace{.4cm}\noindent
Please follow the homework policies on the course website.
\fi

\noindent
\rule{\linewidth}{0.4pt}


\begin{enumerate}


\item \pts{4} Prove that $(\bR^3, \ell_2)$ cannot be embedded into $(\bR^2, \ell_2)$
with bounded distortion.
In other words, there are no functions $f:\bR^3\rightarrow \bR^2$ and constants $\alpha,\beta > 0$
such that the following inequality holds for all $x,y\in \bR^3$:
\begin{equation*}
\beta \|x-y\|_2 \leq \|f(x) - f(y)\|_2 \leq \alpha\beta\|x - y\|_2.
\end{equation*}
\hint{Try a proof by contradiction.
How should the grid $G_n \coloneqq \{(i,j,k):i,j,k\in \{0,1,\ldots,n\}\}$ be embedded?}\\
\hint{A disc of radius $r$ has area $\pi r^2$.}

\ifdefined\template
\begin{shaded}
\textbf{SOLUTION:}
\ifdefined\sol
\input{solution/R3-to-R2-embedding.tex}
\fi
\end{shaded}
\fi


\item \pts{4} We showed that Bourgain's embedding allows us to embed an arbitrary metric space $(X, d)$ with $|X| = n$ into $(\bR^k, \ell_1)$ with target dimension $k$ being $O((\log n)^2)$ and distortion being $O(\log n)$. Moreover, the embedding can be computed efficiently using a randomized algorithm. Prove that the exact same embedding computed by the randomized algorithm also achieves $O(\log n)$ distortion with high probability when the target metric is $\ell_p$ for $p > 1$.
We encourage you to emphasize only the differences from the proof in the lecture notes rather than copying the entire proof.\\
\hint{Let $f:X\rightarrow \bR^k$ denote the relevant embedding. For any two points $x,y\in X$, we showed that $\|f(x) - f(y)\|_1 \leq k\cdot d(x,y)$. Can we say something similar about $\|f(x) - f(y)\|_p$?}\\
\hint{For any two points $a,b\in\bR^k$ and $p>1$, it holds that $\|a - b\|_p \geq k^{(1/p) - 1}\|a - b\|_1$. This is a special case of H\"older's inequality.}

\ifdefined\template
\begin{shaded}
\textbf{SOLUTION:}
\ifdefined\sol
\input{solution/Bourgain.tex}
\fi
\end{shaded}
\fi

\item
\pts{11} \textbf{Johnson-Lindenstrauss with $\pm 1$ entries:} 
In the lecture notes and videos we showed that a matrix of standard Gaussians can be used to get a dimension reducing map with very little distortion. However, a matrix of arbitrary real numbers can be cumbersome to store and compute with. In this problem you’ll show that you can get essentially the same guarantees using random matrices with $\pm 1$ entries. Throughout this problem, let $A$ be an $m \times d$ matrix who's entries are independently set to $+1$ with probability $1/2$ and otherwise to $-1$, and $z \in \mathrm{R}^d$ be an arbitrary unit vector.\footnote{You may wonder why the proof from the lecture notes doesn't directly apply to $\pm 1$ entries. This is because, when the entries are drawn from a normal distribution, we can use the rotational invariance of Gaussians to rotate $z$ until it is a standard unit vector. That trick no longer applies if the entries are $\pm 1$.}

In this problem, you can use the statements from previous subparts even if you do not successfully prove them.

\begin{enumerate}
    \item \pts{2} Show that $\bE[\| Az\|_2^2] = m$.
    \item \pts{2} For $Y \sim N(0, 1)$, show that for any even $k \geq 0$, $\bE[Y^k] \geq 1$, and for odd $k \geq 0$, $\bE[Y^k] = 0$.\\
    \hint{There are many solutions to this. Try to find a short one!}
    \item \pts{2} Prove that for any independent $X_1, \ldots, X_n$ and independent $Y_1, \ldots, Y_n$, if, for all integers $k \geq 0$ and $i = 1,\ldots, n$,
    \begin{equation*}
        0 \leq \bE[(X_i)^k] \leq \bE[(Y_i)^k]
    \end{equation*}
    then for all integers $p \geq 0$,
    \begin{equation*}
        \bE\left[\left(\sum_{i=1}^nX_i\right)^p\right] \leq \bE\left[\left(\sum_{i=1}^nY_i\right)^p\right]
    \end{equation*}
    \item \pts{4} Let $B$ be an $m \times d$ matrix who entries are independently drawn from $N(0,1)$. Prove that, for any $t \geq 0$ and unit vector $z$, if $\bE[e^{t \|Bz\|_2^2}]$ is finite\footnote{For the purpose of your solutions, feel free to ignore this ``is finite."}, then
    \begin{equation*}
        \bE[e^{t \|Az\|_2^2}] \leq \bE[e^{t \|Bz\|_2^2}]
    \end{equation*}
    \hint{For any random variable $X$, $\bE[e^{tX}] = \sum_{k = 0}^\infty \frac{t^k}{k!}\bE[X^k]$}
    \item \pts{1} Show that, for any $\eps \in (0, 1]$,
    \begin{equation*}
        \Pr[\|Az\|_2^2 \geq m(1+\eps)] \leq e^{-\Omega(m\eps^2)}.
    \end{equation*}
    If your proof is similar to that of Theorem 1 in lecture notes 8, we encourage you to emphasize only the differences from the proof in the lecture notes rather than copying the entire proof.
    \item \pts{0} \textbf{[Optional: this won't be graded.]} Show that, for any $\eps \in (0, 1]$,
    \begin{equation*}
        \Pr[\|Az\|_2^2 \leq m(1-\eps)] \leq e^{-\Omega(m\eps^2)}.
    \end{equation*}
    \hint{We recommend you first show that for any \emph{independent} and \emph{nonnegative} random variables $X_1, \ldots, X_m$, defining $S = \sum_{i =1}^m X_i$, the probability $S \leq \bE[S] - \Delta$ is at most $\exp(-\Omega(\Delta^2 / \sum_{i =1}^m \bE[X_i^2]))$. To do so, use the inequality $e^{-v} \leq 1 - v + v^2/2$ which holds for any $v \geq 0$. Feel free to use the fact that for $Y \sim N(0,1)$, $\bE[Y^4] = 3$.}
\end{enumerate}

\ifdefined\template
\begin{shaded}
\textbf{SOLUTION:}
\ifdefined\sol
\input{solution/binaryJL.tex}
\fi
\end{shaded}
\fi


\end{enumerate}
\end{document}
