Random Projections

\(\newcommand{\abs}[1]{\left\lvert#1\right\rvert}\) \(\newcommand{\norm}[1]{\left\lVert#1\right\rVert}\) \(\newcommand{\inner}[1]{\left\langle#1\right\rangle}\) \(\DeclareMathOperator*{\argmin}{arg\,min}\) \(\DeclareMathOperator*{\argmax}{arg\,max}\) \(\DeclareMathOperator*{\E}{\mathbb{E}}\) \(\DeclareMathOperator*{\V}{\mathbb{V}}\)

R

andom projections from the geometric side: what a random linear map preserves, and how few dimensions it needs.

Setup

Given a set $Q$ of $q$ points in $\mathbb{R}^N$ with $N$ large, we would like to embed them in a lower-dimensional space $\mathbb{R}^n$ while approximately preserving the distance between every pair. The question is how small $n$ can be relative to $q$, and which embeddings work.

Random Linear Maps

Let $R \in \mathbb{R}^{n\times N}$ be a random matrix and define the linear map

Common choices for $R$ include:

• i.i.d. Gaussian entries $R_{ij}\sim \mathcal N(0,1)$,
• i.i.d. Rademacher entries $R_{ij}\in{\pm1}$ with equal probability,
• sparse or structured random matrices.

The normalization ensures that $\mathbb E\norm{f(x)}_2^2=\norm{x}_2^2$.

Johnson-Lindenstrauss Lemma

The answer is logarithmic in $q$ (Johnson and Lindenstrauss, 1984):

Let $Q={x_1,\ldots,x_q}\subset\mathbb{R}^N$ and let $\epsilon\in(0,1)$. There exists a linear map $f:\mathbb{R}^N\to\mathbb{R}^n$ with \(n = O\!\left(\frac{\log q}{\epsilon^2}\right)\) such that, for all $u,v\in Q$, \((1-\epsilon)\|u-v\|_2^2 \le \|f(u)-f(v)\|_2^2 \le (1+\epsilon)\|u-v\|_2^2.\)

Moreover, a random projection with i.i.d. Gaussian or Rademacher entries satisfies this property with high probability.

Interpretation

• The target dimension $n$ depends on the number of points only through $\log q$, and not at all on the ambient dimension $N$.
• The map is oblivious: it is drawn without looking at $Q$, and a single draw works for all pairs at once.

Underneath is concentration of measure: for fixed $x$, $\norm{f(x)}_2^2$ is an average of $n$ independent terms, so it concentrates around $\norm{x}_2^2$, and a union bound over the $\binom{q}{2}$ pairs costs only $\log q$ in $n$.

Distance and Inner Product Preservation

Distance preservation gives approximate inner product preservation through polarization,

If $0\in Q$, the norms $\norm{u}_2$ are themselves pairwise distances, so a JL embedding also preserves norms up to $1\pm\epsilon$ and inner products up to an additive error of order $\epsilon(\norm{u}_2^2+\norm{v}_2^2)$. Angles and cosine similarity follow.

Subspace Embeddings

The JL lemma extends beyond finite point sets.

Let $S\subset\mathbb{R}^N$ be a fixed $k$-dimensional subspace. A random projection $f:\mathbb{R}^N\to\mathbb{R}^n$ with

satisfies

with high probability.

Such maps are called oblivious subspace embeddings.

Because the map ignores the data, it preserves geometry but cannot find structure. In practice it is used as a compression step before SVD or PCA.