Random Projection

machine-learning dimensionality-reduction probability

Definition

Random Projection

Random projection is a computationally efficient dimensionality reduction technique that maps high-dimensional data points $x\in {\mathbb{R}}^p$ into a lower-dimensional subspace ${\mathbb{R}}^k$ using a random matrix $R$. Formally, the projection $f:{\mathbb{R}}^p\to {\mathbb{R}}^k$ is defined as:

$f(\mathbf{x})=\frac{1}{\sqrt{k}}R\mathbf{x}$

where the entries of $R$ are sampled independently from a zero-mean distribution (e.g., $R_{ij}\sim \mathcal{N}(0,1)$).

Distance Preservation

Johnson-Lindenstrauss Lemma

For any set of $n$ points in ${\mathbb{R}}^p$ and any $ϵ\in (0,1)$, there exists a projection into $k$ dimensions where $k\ge \mathcal{O}(\frac{\ln n}{{ϵ}^2})$ such that the pairwise squared Euclidean distances between all points are preserved within a factor of $1\pm ϵ$:

$(1-ϵ)\Vert \mathbf{u}-\mathbf{v}{\Vert }^2\le \Vert f(\mathbf{u})-f(\mathbf{v}){\Vert }^2\le (1+ϵ)\Vert \mathbf{u}-\mathbf{v}{\Vert }^2$

Computational Efficiency

Compared to PCA, which has a complexity of $\mathcal{O}(p^{2}n+p^3)$, random projection is significantly faster, requiring only $\mathcal{O}(pkn)$ time. It is particularly effective for extremely high-dimensional datasets where the covariance matrix calculation is computationally prohibitive.