高级算法 (Fall 2019)/Dimension Reduction

Metric Embedding

A metric space is a pair [math]\displaystyle{ (X,d) }[/math], where [math]\displaystyle{ X }[/math] is a set and [math]\displaystyle{ d }[/math] is a metric (or distance) on [math]\displaystyle{ X }[/math], i.e., a function

[math]\displaystyle{ d:X^2\to\mathbb{R}_{\ge 0} }[/math]

such that for any [math]\displaystyle{ x,y,z\in X }[/math], the following axioms hold:

1. (identity of indiscernibles) [math]\displaystyle{ d(x,y)=0\Leftrightarrow x=y }[/math]
2. (symmetry) [math]\displaystyle{ d(x,y)=d(y,x) }[/math]
3. (triangle inequality) [math]\displaystyle{ d(x,z)\le d(x,y)+d(y,z) }[/math]

Let [math]\displaystyle{ (X,d_X) }[/math] and [math]\displaystyle{ (Y,d_Y) }[/math] be two metric spaces. A mapping

[math]\displaystyle{ \phi:X\to Y }[/math]

is called an embedding of metric space [math]\displaystyle{ X }[/math] into [math]\displaystyle{ Y }[/math]. The embedding is said to be with distortion [math]\displaystyle{ \alpha\ge1 }[/math] if for any [math]\displaystyle{ x,y\in X }[/math] it holds that

[math]\displaystyle{ \frac{1}{\alpha}\cdot d(x,y)\le d(\phi(x),\phi(y))\le \alpha\cdot d(x,y) }[/math].

In Computer Science, a typical scenario for the metric embedding is as follows. We want to solve some difficult computation problem on a metric space [math]\displaystyle{ (X,d) }[/math]. Instead of solving this problem directly on the original metric space, we embed the metric into a new metric space [math]\displaystyle{ (Y,d_Y) }[/math] (with low distortion) where the computation problem is much easier to solve.

One particular important case for the metric embedding is to embed a high-dimensional metric space to a new metric space whose dimension is much lower. This is called dimension reduction. This can be very helpful because various very common computation tasks can be very hard to solve on high-dimensional space due to the curse of dimensionality.

The Johnson-Lindenstrauss Theorem

The Johnson-Lindenstrauss Theorem or Johnson-Lindenstrauss Transformation (both shorten as JLT) is a fundamental result for dimension reduction in Euclidian space.

Recall that in Euclidian space [math]\displaystyle{ \mathbf{R}^d }[/math], for any two points [math]\displaystyle{ x,y\in\mathbf{R}^d }[/math], the Euclidian distance between them is given by [math]\displaystyle{ \|x-y\|=\sqrt{(x_1-y_1)^2+(x_2-y_2)^2+\cdots +(x_d-y_d)^2} }[/math], where [math]\displaystyle{ \|\cdot\|=\|\cdot\|_2 }[/math] denotes the Euclidian norm (a.k.a. the [math]\displaystyle{ \ell_2 }[/math]-norm).

The JLT says that in Euclidian space, it is always possible to embed a set of [math]\displaystyle{ n }[/math] points in arbitrary dimension to [math]\displaystyle{ O(\log n) }[/math] dimension with constant distortion. The theorem itself is stated formally as follows.

Johnson-Lindenstrauss Theorem, 1984

For any [math]\displaystyle{ 0\lt \epsilon\lt 1 }[/math] and any positive integer [math]\displaystyle{ n }[/math], there is a positive integer [math]\displaystyle{ k=O(\epsilon^{-2}\log n) }[/math] such that the following holds: For any set [math]\displaystyle{ S\subset\mathbf{R}^d }[/math] with [math]\displaystyle{ |S|=n }[/math], where [math]\displaystyle{ d }[/math] is arbitrary, there is an embedding [math]\displaystyle{ \phi:\mathbf{R}^d\rightarrow\mathbf{R}^k }[/math] such that [math]\displaystyle{ \forall x,y\in S,\quad (1-\epsilon)\|x-y\|^2\le\|\phi(x)-\phi(y)\|^2\le(1+\epsilon)\|x-y\|^2 }[/math].

The Johnson-Lindenstrauss Theorem is usually stated for the [math]\displaystyle{ \ell_2^2 }[/math]-norm [math]\displaystyle{ \|\cdot\|^2 }[/math] instead of the Euclidian norm [math]\displaystyle{ \|\cdot\| }[/math] itself. Note that this does not change anything other than the constant faction in [math]\displaystyle{ k=O(\epsilon^{-2}\log n) }[/math] because [math]\displaystyle{ (1\pm\epsilon)^{\frac{1}{2}}\approx 1\pm\frac{\epsilon}{2} }[/math]. The reason for stating the theorem in [math]\displaystyle{ \ell_2^2 }[/math]-norm is because [math]\displaystyle{ \|\cdot\|^2 }[/math] is a sum (rather than a square root) which is easier to analyze.

In fact, the embedding [math]\displaystyle{ \phi:\mathbf{R}^d\rightarrow\mathbf{R}^k }[/math] can be as simple as a linear transformation [math]\displaystyle{ A\in\mathbf{R}^{k\times d} }[/math] so that [math]\displaystyle{ \phi(x)=Ax }[/math] for any [math]\displaystyle{ x\in\mathbf{R}^{d} }[/math]. Therefore, the above theorem can be stated more precisely as follows.

Johnson-Lindenstrauss Theorem (linear embedding)

For any [math]\displaystyle{ 0\lt \epsilon\lt 1 }[/math] and any positive integer [math]\displaystyle{ n }[/math], there is a positive integer [math]\displaystyle{ k=O(\epsilon^{-2}\log n) }[/math] such that the following holds: For any set [math]\displaystyle{ S\subset\mathbf{R}^d }[/math] with [math]\displaystyle{ |S|=n }[/math], where [math]\displaystyle{ d }[/math] is arbitrary, there is a linear transformation [math]\displaystyle{ A\in\mathbf{R}^{k\times d} }[/math] such that [math]\displaystyle{ \forall x,y\in S,\quad (1-\epsilon)\|x-y\|^2\le\|Ax-Ay\|^2\le(1+\epsilon)\|x-y\|^2 }[/math].

The theorem is proved by the probabilistic method. Specifically, we construct a random matrix [math]\displaystyle{ A\in\mathbf{R}^{k\times d} }[/math] and show that with high probability ([math]\displaystyle{ 1-O(1/n) }[/math]) it is a good embedding satisfying:

[math]\displaystyle{ \forall x,y\in S,\quad (1-\epsilon)\|x-y\|\le\|Ax-Ay\|\le(1+\epsilon)\|x-y\| }[/math].

Therefore, if such random matrix [math]\displaystyle{ A }[/math] is efficient to construct, it immediately gives us an efficient randomized algorithm for dimension reduction in the Euclidian space.

There are several such constructions of the random matrix [math]\displaystyle{ A\in\mathbf{R}^{k\times d} }[/math], including:

• projection onto uniform random [math]\displaystyle{ k }[/math]-dimensional subspace of [math]\displaystyle{ \mathbf{R}^{d} }[/math]; (The original construction of Johnson and Lindenstrauss in 1984; a simplified analysis due to Dasgupta and Gupta in 1999)
• random matrix with i.i.d. Gaussian entries; (due to Indyk and Motwani in 1998)
• random matrix with i.i.d. -1/+1 entries; (due to Achlioptas in 2003)

JLT via Gaussian matrix

Here we prove the Johnson-Lindenstrauss theorem with the second construction, by the random matrix [math]\displaystyle{ A\in\mathbf{R}^{k\times d} }[/math] with i.i.d. Gaussian entries. The construction of [math]\displaystyle{ A }[/math] is very simple:

Each entry of [math]\displaystyle{ A\in\mathbf{R}^{k\times d} }[/math] is drawn independently from the Gaussian distribution [math]\displaystyle{ N(0,1/k) }[/math].

Recall that a Gaussian distribution [math]\displaystyle{ N(\mu,\sigma^2) }[/math] is specified by its mean [math]\displaystyle{ \mu }[/math] and standard deviation [math]\displaystyle{ \sigma }[/math] such that for a random variable [math]\displaystyle{ X }[/math] distributed as [math]\displaystyle{ N(\mu,\sigma^2) }[/math], we have

[math]\displaystyle{ \mathbf{E}[X]=\mu }[/math] and [math]\displaystyle{ \mathbf{Var}[X]=\sigma^2 }[/math],

and the probability density function is given by [math]\displaystyle{ p(x)=\frac{1}{\sqrt{2\pi\sigma^2}}\mathrm{e}^{-\frac{(x-\mu)^2}{2\sigma^2}} }[/math], therefore

[math]\displaystyle{ \Pr[X\le t]=\int_{-\infty}^t\frac{1}{\sqrt{2\pi\sigma^2}}\mathrm{e}^{-\frac{(x-\mu)^2}{2\sigma^2}}\,\mathrm{d}x }[/math].