0.6 Dimensionality reduction  (Page 3/3)

The johnson-lindenstrauss lemma

Fundamentals

As with the above techniques in manifold learning, the Johnson-Lindenstrauss (JL)lemma  [link] , [link] , [link] , [link] provides a method for dimensionality reduction of a set of data in ${\mathbb{R}}^N$ . Unlike manifold-based methods, however, the JL lemma can be used for any arbitrary set $Q$ of points in ${\mathbb{R}}^N$ ; the data set is not assumed to have any a priori structure.

Despite the apparent lack of structure in an arbitrary point cloud data set, the JL lemma suggests that there does exist a method for dimensionality reduction of that data set that can preserve key information while mapping the data to a lower-dimensional space ${\mathbb{R}}^M$ . In particular, the original formulation of the JL lemma  [link] states that there exists a Lipschitz mapping $\Phi :{\mathbb{R}}^N\mapsto {\mathbb{R}}^M$ with $M=O(log(\#Q\left)\right)$ such that all pairwise distances between points in $Q$ are approximately preserved. This fact is useful for solving problemssuch as Approximate Nearest Neighbor   [link] , in which one desires the nearest point in $Q$ to some query point $y\in {\mathbb{R}}^N$ (but a solution not much further than the optimal point is also acceptable). Such problems can be solvedsignificantly more quickly in ${\mathbb{R}}^M$ than in ${\mathbb{R}}^N$ .

Recent reformulations of the JL lemma propose random linear operators that, with high probability, will ensure a nearisometric embedding. These typically build on concentration of measure results such as the following.

[link] , [link] Let $x\in {\mathbb{R}}^N$ , fix $0<ϵ<1$ , and let $\Phi$ be a matrix constructed in one of the following two manners:

1. $\Phi$ is a random $M\times N$ matrix with i.i.d. $\mathcal{N}(0,{\sigma }^2)$ entries, where ${\sigma }^2=1/N$ , or
2. $\Phi$ is random orthoprojector from ${\mathbb{R}}^N$ to ${\mathbb{R}}^M$ .

Then with probability exceeding

the following holds:

The random orthoprojector referred to above is clearly related to the first case (simple matrix multiplication by a Gaussian $\Phi$ ) but subtly different; one could think of constructing a randomGaussian $\Phi$ , then using Gram-Schmidt to orthonormalize the rows before multiplying $x$ . We note also that simple rescaling of $\Phi$ can be used to eliminate the $\sqrt{\frac{M}{N}}$ in [link] ; however we prefer this formulation for later reference.

By using the union bound over all $\left(\genfrac{}{}{0pt}{}{\#Q}{2}\right)$ pairs of distinct points in $Q$ , Lemma  "The Johnson-Lindenstrauss lemma" can be used to prove a randomized version of the Johnson-Lindenstrauss lemma.

Johnson-lindenstrauss

Let $Q$ be a finite collection of points in ${\mathbb{R}}^N$ . Fix $0<ϵ<1$ and $\beta >0$ . Set

Let $\Phi$ be a matrix constructed in one of the following two manners:

1. $\Phi$ is a random $M\times N$ matrix with i.i.d. $\mathcal{N}(0,{\sigma }^2)$ entries, where ${\sigma }^2=1/N$ , or
2. $\Phi$ is random orthoprojector from ${\mathbb{R}}^N$ to ${\mathbb{R}}^M$ .

Then with probability exceeding $1-{(\#Q)}^{-\beta }$ , the following statement holds: for every $x,y\in Q$ ,

Indeed, [link] establishes that both [link] and [link] also hold when the elements of $\Phi$ are chosen i.i.d. from a random Rademacher distribution ( $\pm \sigma$ with equal probability $1/2$ ) or from a similar ternary distribution ( $\pm \sqrt{3}\sigma$ with equal probability $1/6$ ; 0 with probability $2/3$ ). These can further improve the computational benefits of the JL lemma.

Connections with compressed sensing

In the following module on Compressed Sensing we will discuss further topics in dimensionality reduction that relate to the JL lemma. In particular, as discussed in Connections with dimensionality reduction , the core mechanics of Compressed Sensing can be interpreted in terms of a stable embedding that arises for the family of $K$ -sparse signals when observed with random measurements, and this stable embedding can be proved using the JL lemma. Furthermore, as discussed in Stable embeddings of manifolds , one can ensure a stable embedding of families of signals obeying manifold models under a sufficient number of random projections, with the theory again following from the JL lemma.