SECTION 08 / 10

Linear maps and the limits of exact preservation

On this page 7 headings

Learning goal: See why reducing dimension requires approximate preservation.

The ideaShine a torch on a stick and look at its shadow on the floor.
The shadow is a 2D version of a 3D object.
Tilt the stick so it points straight at the torch and its shadow becomes a dot: its length is lost completely.
Any squeeze from more dimensions to fewer must crush some direction like this.
So keeping every length exactly is impossible.
JL asks for less: keep lengths approximately, and only for your n points.

Key statementThe picture of JL: n points in $R^{d}$ (red blob) mapped by f to $R^{k}$ (blue blob).
The distance $∥ x - y ∥^{2}$ is compared with $∥ f (x) - f (y) ∥^{2}$ , with the 1 − ε and 1 + ε bounds and $k \in O (lo g n / ε^{2})$ .

Step 1: try the simplest kind of map, a matrix

linear transformations $u \in R^{d} R R u \in R^{k}$ , so $R \in R^{k \times d}$ .
Greedy wish: $∥ u ∥^{2} = ∥ R u ∥^{2}$ for every u.
Then

u^{⊤} u = (R u)^{⊤} (R u) = u^{⊤} (R^{⊤} R) u, R^{⊤} R is (d \times k) (k \times d) = d \times d .

Wish: $R^{⊤} R = I$ ?

Why can we focus on single vectors u when JL is about pairs?
Because a distance is a length: $∥ x - y ∥$ is the length of the vector $u = x - y$ .
For a matrix, $R x - R y = R (x - y)$ , so preserving the lengths of difference vectors is the same as preserving distances.
"Linear transformation" just means "multiply by a matrix".
For the wish to hold for every u, we need $R^{⊤} R$ to be the identity matrix.

Key statementWrite the rows of $R^{⊤}$ (= columns of R) as $a_{1}, \dots, a_{d}$ , each in $R^{k}$ .
Then entry (i, j) of $R^{⊤} R$ is $a_{i}^{⊤} a_{j}$ .
For $R^{⊤} R = I$ we need $a_{i}^{⊤} a_{i} = 1$ and $a_{i}^{⊤} a_{j} = 0$ for i ≠ j, i.e.
${a_{1}, \dots, a_{d}}$ orthonormal in $R^{k}$ .
Exact preservation is impossible when k < d. → aim for an approximate "isometry".

Linear algebra fact: in k dimensions you can have at most k mutually perpendicular unit vectors.
In 2D you can't draw 3 arrows that are all at right angles to each other.
We need d of them in $R^{k}$ with d > k.
Impossible.
Isometry = a map that keeps all distances exactly.
We have just shown no k × d matrix with k < d is an isometry.

A second proof: some vector always gets crushed to zero

A k × d matrix with k < d gives k equations in d unknowns for $R u = 0$ .
With more unknowns than equations, there is always a nonzero solution u.
That u has $∥ u ∥^{2} > 0$ but $∥ R u ∥^{2} = 0$ : its length is completely destroyed.
Example: $R = [23]$ (1 × 2) and $u = (3, - 2)$ give $R u = 6 - 6 = 0$ .

Approximate, not exact. We accept the 1 ± ε factor ("approximate isometry").
Only n points, not the whole space. We only need to preserve the $(2 n) \approx n^{2} /2$ pairwise distances of our data, not the length of every vector in $R^{d}$ .
The points can be anything, but there are only finitely many of them.

What size is

R^{⊤} R

if R is 3 × 10?

(10 × 3)(3 × 10) = 10 × 10.

Find a nonzero u that R = [1 1 1] sends to 0.

Any u with entries summing to 0, e.g. (1, −1, 0).

A k × d matrix maps d input coordinates to k output coordinates.
When $k < d$ , some nonzero vector must map to zero.
JL asks for approximate preservation of selected pairs, rather than exact preservation of every vector.

YOUR STUDY PROGRESS

Finished this section? Save your progress.