\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, Fall 2020
\ifdefined\sol\else
\newline
Due: October 16 (Friday) at 23:59 (Pacific Time)
\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{10}
The \emph{equilateral dimension} of a metric space is the maximum number of points in the space that are all at the same distance from each other.
In this problem, we will determine the equilateral dimension of the $d$-dimensional Euclidean space $\cE^d = (\bR^d, \ell_2)$, and also explore a relaxed version of the equilateral dimension where the pairwise distances are only required to be
\emph{approximately} the same.
\begin{enumerate}
\item \pts{2} Let $X$ be a set of $d+1$ points in $\cE^m$ for some arbitrary positive integer $m$. Show that $(X, \ell_2)$ can be isometrically embedded into $\cE^{d}$.\\
\hint{Suppose $X = \{x_0,\ldots,x_{d}\}$. Consider the linear subspace spanned by the vectors $x_i - x_0$ for $i = 1,\ldots,d$.
How large can the dimension of the subspace be?}
\item \pts{2} For all positive integers $d$, use Part (a) to show that there exist $d+1$ points in $\cE^d$ that are all at distance 1 from each other. This shows that the equilateral dimension of $\cE^d$ is at least $d+1$.
\item \pts{3} Show that there exists a constant $c > 0$ such that for all positive integers $d$,
one can find at least $2^{cd}$ points in $\cE^d$ that are all at distances between $1$ and $1.1$ from each other.\\
\hint{Try applying the Johnsonâ€“Lindenstrauss lemma.}
\item \pts{0} \textbf{[Optional: this won't be graded.]}
For all positive integers $d$, show that one cannot find $d+2$ points in $\cE^d$
that are all at distance 1 from each other.
Together with Part (b), this shows that the equilateral dimension of $\cE^d$ is exactly $d+1$.\\
\hint{Prove by contradiction. Suppose there are $d+2$ such points $x_0,x_1,\ldots,x_{d+1}$. Consider the vectors $v_i = x_i - x_0$ and the matrix $A = [v_1,\cdots,v_{d+1}]$ (with the $v_i$ as columns) of size $d\times (d+1)$.
Explicitly compute the inner products $v_i^{\mathsf{T}}v_j$ and the matrix $A^{\mathsf{T}}A$. Use the fact that $\rank(A^{\mathsf{T}}A) = \rank(A)$ to derive a contradiction.\footnote{This proof strategy can be used to show that the Johnson-Lindenstrauss lemma is ``nearly tight''. See Problem 4.}
}
\item \pts{3} Show that there exists a constant $C > 0$ such that for all positive integers $d$,
one cannot find more than $2^{Cd}$ points in $\cE^d$ that are all at distances between $1$ and $1.1$ from each other.\\
\hint{Try using a similar strategy to problem 1. You can use the fact that the volume of a $d$-dimensional ball of radius $r$ scales as $\gamma r^d$ for some constant $\gamma$ that depends on $d$ but not $r$. It may be helpful if you understand the proof of Lemma 3 in lecture notes \#9, but that is not required for working on this problem.}
\end{enumerate}
\ifdefined\template
\begin{shaded}
\textbf{SOLUTION:}
\ifdefined\sol
\input{solution/equilateral.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{0} \textbf{[Optional: this won't be graded.]}
Prove that the Johnson-Lindenstrauss lemma is ``nearly tight''.\footnote{For improved results, see paper by Larsen and Nelson: Optimality of the Johnson-Lindenstrauss Lemma. (Link to the FOCS 2017 version: \url{https://ieeexplore.ieee.org/abstract/document/8104096}).} Specifically, for a sufficiently small positive constant $c$, show that for every positive integer $n>100$ and any $\eps\in[1/\sqrt n, 1/10)$, one can find a positive integer $d$ together with a set $X$ of $n$ points in $\bR^d$ such that for any positive integer $m < \frac{c\ln n}{\eps^2\ln(1/\eps)}$, there is no way to embed $(X, \ell_2)$ into $(\bR^m, \ell_2)$ with distortion $1+\eps$.
You can use the following theorem in linear algebra without proof:
\begin{theorem}[Alon '03]
There is a small positive constant $c$ with the following property.
Let $A = (a_{ij})$ be an $n$ by $n$ real matrix with $a_{ii} = 1$ for all i and $|a_{ij}| \leq \eps$ for all $i\neq j$. If $n > 4$ and $\eps\in[1/\sqrt n, 1/2)$, then
\begin{equation*}
\rank(A) \geq \frac{c\ln n}{\eps^2\ln(1/\eps)}.
\end{equation*}
\end{theorem}
\hint{Try using a similar proof strategy as Problem 2(d).}
\ifdefined\template
\begin{shaded}
\textbf{SOLUTION:}
\ifdefined\sol
\input{solution/tightJL.tex}
\fi
\end{shaded}
\fi
\end{enumerate}
\end{document}