\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb}
\usepackage{algorithm,algpseudocode}
\usepackage{bm}
\usepackage{hyperref}
\usepackage{float}
\usepackage{subcaption}
\usepackage{enumitem}
\usepackage{xcolor}
\definecolor{darkgreen}{rgb}{0.0, 0.5, 0.0}
\definecolor{aaltoBlue}{RGB}{0, 51, 102}
\definecolor{pinegreen}{cmyk}{0.92,0,0.59,0.25}
\definecolor{royalblue}{cmyk}{1,0.50,0,0}
\definecolor{lavander}{cmyk}{0,0.48,0,0}
\definecolor{violet}{cmyk}{0.79,0.88,0,0}
\definecolor{lightblue}{RGB}{173, 216, 230}
\usepackage{tikz}
\usepackage{pgfplots}
\usetikzlibrary{calc,arrows.meta,positioning,fit,shapes.geometric,shapes.misc,intersections,patterns,decorations.pathreplacing,backgrounds,matrix}
\usepgfplotslibrary{fillbetween,groupplots}
\setcounter{secnumdepth}{-\maxdimen}
% Long unbreakable tokens (the ISO/IEC author names in citations, term names
% in the title) otherwise overflow the margin by a few points; a modest
% emergency stretch lets TeX loosen the paragraph instead.
\emergencystretch=2em
\usepackage{mleftright}
% Project macros used by this entry (auto-extracted).
\newcommand{\dataset}{\mathcal{D}}
\newcommand{\expect}{\mathbb{E} }
\newcommand{\featuredim}{d}
\newcommand{\featuretrafovec}{{\bf \Phi}}
\newcommand{\featurevec}{\vx}
\newcommand{\mA}[0]{{\bf A}}
\newcommand{\normgeneric}[2]{\mleft\lVert #1 \mright\rVert_{#2}}
\newcommand{\reals}{\mathbb{R}}
\newcommand{\sampleidx}{r}
\newcommand{\samplesize}{m}
\newcommand{\vu}[0]{{\bf u}}
\newcommand{\vx}[0]{{\bf x}}

\begin{document}

\section{random projection}

\subsection*{Author and editors}
Alexander Jung\textsuperscript{*}, Department of Computer Science, Aalto University, Espoo, Finland (ORCID \mbox{\href{https://orcid.org/0000-0001-7538-0990}{0000-0001-7538-0990}}) \\
Editors: Konstantina Olioumtsevits (ORCID \mbox{\href{https://orcid.org/0000-0003-2697-8659}{0000-0003-2697-8659}}), Ekkehard Schnoor (ORCID \mbox{\href{https://orcid.org/0000-0001-8252-1499}{0000-0001-8252-1499}}), Aalto University, Espoo, Finland \\
\textsuperscript{*}Corresponding author: \href{mailto:alex.jung@aalto.fi}{alex.jung@aalto.fi}



\subsection{Abstract}
A random projection replaces the feature vector
		$\featurevec \in \reals^{\featuredim}$ of a data point by
		$\mA \featurevec \in \reals^{\featuredim'}$, with $\featuredim' <
		\featuredim$ and a wide matrix $\mA$ whose entries are
		realizations of independent and identically distributed (i.i.d.) random variables (RVs). No data enter
		$\mA$, which separates a random projection from principal component analysis (PCA) and from
		an autoencoder, whose maps for dimensionality reduction are learned from
		a training set. When the entries have mean zero and
		variance $1/\featuredim'$, the expectation of the
		squared length of $\mA \featurevec$ equals the squared length of
		$\featurevec$, so squared Euclidean distances between
		data points survive on average. The Johnson--Lindenstrauss lemma (JL lemma) turns this into a
		guarantee for a whole finite dataset: a target dimension of
		at least $4 \ln \samplesize / (\varepsilon^{2}/2 -
		\varepsilon^{3}/3)$ keeps every pairwise squared Euclidean distance
		within the factor $1 \pm \varepsilon$. That requirement involves
		the sample size $\samplesize$ and the tolerance $\varepsilon$
		and not the ambient dimension $\featuredim$, so the saving grows
		with the length of the original feature vector. The entries may
		be normal RVs or take the values $\pm 1/\sqrt{\featuredim'}$
		with probability one half each. A random projection costs
		one matrix multiplication per data point and no pass
		over the data.

\subsection{Definition}
A weather archive at Krems an
		der Donau (Austria) keeps, for each day, the daily maximum air
		temperature of the preceding ten years. Such a day is a
		data point whose feature vector $\featurevec \in
		\reals^{\featuredim}$ holds $\featuredim = 3650$ numbers, and a
		search for the days most similar to a given one compares these
		feature vectors by their Euclidean distance. A random projection
		shortens every record before the search: it replaces $\featurevec$
		by $\mA \featurevec \in \reals^{\featuredim'}$, where $\featuredim'
		< \featuredim$ and $\mA \in \reals^{\featuredim' \times
		\featuredim}$ is a wide matrix whose entries are
		realizations of independent and identically distributed (i.i.d.) random variables (RVs). No data enter
		$\mA$, and that is what separates a random projection from
		principal component analysis (PCA) and from an autoencoder, whose maps for
		dimensionality reduction are learned from a training set. The word
		\emph{projection} is traditional here: the matrix $\mA$ maps
		into $\reals^{\featuredim'}$, so it is not a projection of
		$\reals^{\featuredim}$ onto one of its subsets.
\par
		The probability distribution of these RVs has mean zero and
		variance $1/\featuredim'$. Consider a fixed $\vu \in
		\reals^{\featuredim}$. Each entry of $\mA \vu$ is
		then an RV with mean zero and variance
		$\normgeneric{\vu}{2}^{2}/\featuredim'$. Adding the
		variances of the $\featuredim'$ entries gives the
		expectation of the squared length of $\mA \vu$,
		\begin{equation}
			\label{equ_randomprojection_isometry_dict}
			\expect \big\{ \normgeneric{\mA \vu}{2}^{2} \big\}
			= \normgeneric{\vu}{2}^{2} \text{.}
		\end{equation}
		Read with $\vu = \featurevec^{(\sampleidx)} -
		\featurevec^{(\sampleidx')}$, the identity
		\eqref{equ_randomprojection_isometry_dict} says that the squared
		Euclidean distance between two data points survives the
		projection on average. One draw of $\mA$ is another matter. For two
		of the Krems days and $\featuredim' = 16$, the squared
		Euclidean distance after the projection ranged from $0.22$ to $2.68$
		times the one before it over $4000$ draws.
\par
		That spread narrows as $\featuredim'$ grows, and the
		Johnson--Lindenstrauss lemma (JL lemma), proved by
		Johnson and Lindenstrauss (1984), turns the narrowing into a
		guarantee that covers every pair of a finite dataset at
		once.
		Consider a dataset $\dataset = \{\featurevec^{(1)}, \ldots,
		\featurevec^{(\samplesize)}\}$ of sample size $\samplesize$
		and a tolerance $\varepsilon$ with $0 < \varepsilon < 1$. Whenever
		the target dimension satisfies
		\begin{equation}
			\label{equ_randomprojection_jldim_dict}
			\featuredim' \ge \frac{4 \ln \samplesize}
			{\varepsilon^{2}/2 - \varepsilon^{3}/3} \text{,}
		\end{equation}
		there is a map $\featuretrafovec \colon \reals^{\featuredim} \to
		\reals^{\featuredim'}$ with
		\begin{equation}
			\label{equ_randomprojection_jldist_dict}
			(1 - \varepsilon) \normgeneric{\featurevec^{(\sampleidx)} -
			\featurevec^{(\sampleidx')}}{2}^{2}
			\le \normgeneric{\featuretrafovec \big(
			\featurevec^{(\sampleidx)} \big) - \featuretrafovec \big(
			\featurevec^{(\sampleidx')} \big)}{2}^{2}
			\le (1 + \varepsilon) \normgeneric{\featurevec^{(\sampleidx)} -
			\featurevec^{(\sampleidx')}}{2}^{2} \text{,}
		\end{equation}
		for every $\sampleidx, \sampleidx' \in \{1, \ldots,
		\samplesize\}$, and a random projection delivers such a map with
		positive probability, which repeated draws raise as high as
		wanted (Dasgupta and Gupta, 2003, Thm.~2.1). The requirement
		\eqref{equ_randomprojection_jldim_dict} involves the
		sample size $\samplesize$ and the tolerance $\varepsilon$, and
		not the ambient dimension $\featuredim$. Its denominator is largest
		at $\varepsilon = 1$, where it equals $1/6$, so no tolerance below
		one is granted before $\featuredim' \ge 24 \ln \samplesize$, which
		is $134$ for $\samplesize = 256$ days. The sample size enters
		through its logarithm: at $\varepsilon = 1/2$, a hundredfold larger
		dataset raises the requirement from $266$ to $487$.
		Fig.~\ref{fig_randomprojection_dict} holds the two-sided bound
		\eqref{equ_randomprojection_jldist_dict} against what one draw of
		$\mA$ does to the $32640$ pairwise squared Euclidean distances of
		$256$ such days.
		\begin{figure}[H]
		\centering
		\begin{tikzpicture}
		\begin{groupplot}[
			group style={group size=2 by 1, horizontal sep=1.7cm},
			width=0.5\linewidth, height=0.44\linewidth,
			axis lines=left,
			tick label style={font=\scriptsize},
			label style={font=\scriptsize, align=center},
			legend style={draw=none, fill=none, font=\scriptsize,
				at={(0.5,-0.40)}, anchor=north},
			legend cell align=left,
			xmin=130, xmax=334, xtick={144,192,256,320}, ymin=0,
		]
			\nextgroupplot[
				xlabel={target dimension $\featuredim'$\\(a) ten-year records, $\featuredim = 3650$},
				ylabel={relative change of a squared distance},
				ymax=0.95]
			\addplot[black, dashdotted, thick]
				table[col sep=comma, x=dprime, y=eps]{randomprojection_distortion.csv};
			\addlegendentry{tolerance (dash-dotted curve)}
			\addplot[black, dotted, thick, mark=triangle, mark size=2.6pt]
				table[col sep=comma, x=dprime, y=max_long]{randomprojection_distortion.csv};
			\addlegendentry{largest change (dotted curve)}
			\addplot[black, dashed, mark=square, mark size=1.8pt]
				table[col sep=comma, x=dprime, y=p95_long]{randomprojection_distortion.csv};
			\addlegendentry{95th percentile (dashed curve)}
			\addplot[black, mark=*, mark size=1.5pt]
				table[col sep=comma, x=dprime, y=med_long]{randomprojection_distortion.csv};
			\addlegendentry{median (solid curve)}
			\nextgroupplot[
				xlabel={target dimension $\featuredim'$\\(b) ambient $\featuredim = 365$ and $\featuredim = 3650$},
				ylabel={largest relative change},
				ymax=0.6]
			\addplot[black, mark=*, mark size=1.5pt]
				table[col sep=comma, x=dprime, y=max_short]{randomprojection_distortion.csv};
			\addlegendentry{one-year records (solid curve)}
			\addplot[black, dashed, mark=square, mark size=1.8pt]
				table[col sep=comma, x=dprime, y=max_long]{randomprojection_distortion.csv};
			\addlegendentry{ten-year records (dashed curve)}
		\end{groupplot}
		\end{tikzpicture}
		\caption{The relative change of the $32640$ pairwise squared
			Euclidean distances of $256$ days at Krems under a random
			projection, against the target dimension $\featuredim'$, each
			value the median over $40$ draws of $\mA$. (a) For the
			ten-year records, $\featuredim = 3650$: the median over the
			pairs (solid curve, filled circles), their 95th percentile
			(dashed curve, open squares), the largest change (dotted
			curve, open triangles), and the tolerance $\varepsilon$ that
			the requirement \eqref{equ_randomprojection_jldim_dict} grants
			(dash-dotted curve). (b) The largest change for the one-year
			records, $\featuredim = 365$ (solid curve, filled circles),
			and for the ten-year ones, $\featuredim = 3650$ (dashed curve,
			open squares), a tenfold difference in $\featuredim$ that
			leaves the curve where it was. Data
			generated by \texttt{pythondemos/randomprojection.py}
			\label{fig_randomprojection_dict}}
		\end{figure}
		Two probability distributions for the entries of $\mA$ are in common use.
		Normal RVs with mean zero and variance
		$1/\featuredim'$ give the guarantee in the form stated above
		(Shalev-Shwartz and Ben-David, 2014, Lemma~23.4). Entries equal to
		$1/\sqrt{\featuredim'}$ or $-1/\sqrt{\featuredim'}$, each with
		probability one half, meet the same requirement
		\eqref{equ_randomprojection_jldim_dict}
		(Achlioptas, 2001;
		Dasgupta and Gupta, 2003, Sect.~3), and the products in $\mA
		\featurevec$ then reduce to additions and subtractions of the
		features. Either way the cost is $\featuredim \featuredim'$
		multiplications per data point, paid once: there is no
		iteration and no training.
\par
		For the Krems archive and $\featuredim' = 256$, the ten-year
		record of a day shrinks from $3650$ numbers to $256$, a factor of
		$14.3$. In a typical draw of $\mA$, no pair of the $32640$
		squared Euclidean distances changes by more than $36$ percent and
		half of them change by less than $6$ percent, against the $51$
		percent the requirement \eqref{equ_randomprojection_jldim_dict}
		grants at that target dimension. A method that reads the
		data points only through their pairwise Euclidean distances,
		such as $k$-nearest neighbors ($k$-NN), therefore works on nearly the dataset it
		would have worked on before. When both the map and the
		reconstruction are linear, PCA is the choice with the
		smallest average squared error over the training set, and a
		random projection is not. When the step back to
		$\reals^{\featuredim}$ may be nonlinear, the ranking can turn
		around: feature vectors with few nonzero features are
		recovered better from a random projection than from PCA
		(Shalev-Shwartz and Ben-David, 2014, Sect.~23.5).

\subsection{Cross References}
dimensionality reduction, feature learning, JL lemma, PCA, autoencoder, random matrix, wide matrix, Euclidean distance, feature vector, $k$-NN

\subsection{References}
\begin{enumerate}
  \item Achlioptas (2001). Database-friendly random projections. In: PODS '01: Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pp.~274--281. ACM.
  \item Dasgupta and Gupta (2003). An elementary proof of a theorem of Johnson and Lindenstrauss. Random Struct. Algorithms, 22(1), pp.~60--65.
  \item Shalev-Shwartz and Ben-David (2014). Understanding Machine Learning: From Theory to Algorithms. Cambridge Univ. Press, New York, NY, USA.
  \item Johnson and Lindenstrauss (1984). Extensions of Lipschitz mappings into a Hilbert space. Contemporary Math., 26, pp.~189--206.
\end{enumerate}

\end{document}
