SECTION 09 / 10

Gaussian random projections and scaling

On this page 8 headings

Learning goal: Derive why a Gaussian projection is divided by $\sqrt{k}$ .

Conditions to check

Unbiasedness means that the expected squared projected length is correct.
It does not guarantee that one random projection is accurate.
The input vector has dimension d; the projection has dimension k.

The ideaFill a matrix with random numbers from the bell curve and multiply your vector by it.
Each output number is a random "measurement" of your vector.
Individually they look like noise, but their spread is exactly the vector's squared length.
So by measuring how spread out the k outputs are, you can estimate the length.
More outputs give a better estimate.

Key statementGoal: approximate isometry for pairwise distances of any n points in $R^{d}$ .
Write R by rows:

R = r_{1}^{⊤} r_{2}^{⊤} ⋮ r_{k}^{⊤}, R u = r_{1}^{⊤} u ⋮ r_{k}^{⊤} u \in R^{k}, R = [r_{ij}], r_{ij} \sim N (0, 1) .

So we generate R by drawing all k × d entries independently from the standard normal.
Then we fix R and apply it to the data.
Because R is random, where u lands in $R^{k}$ is random too.

Step 1: the average of one output is 0

Look at the first output, $r_{1}^{⊤} u = \sum_{i = 1}^{d} r_{1 i} u_{i}$ .
Here u is fixed and the $r_{1 i}$ are random.

E [r_{1}^{⊤} u] = E [i = 1 \sum d r_{1 i} u_{i}] = i = 1 \sum d = 0 E [r_{1 i}] u_{i} = 0.

The tool is linearity of expectation, with $u_{i}$ pulled out as a fixed number.
Intuition: a random direction is equally likely to point "with" u as "against" it, so the dot products cancel on average.

Step 2: the variance of one output is $\|u\|^{2}$

Since the mean is 0, $Var (r_{1}^{⊤} u) = E [(r_{1}^{⊤} u)^{2}]$ .
Square the sum.
As in $(a + b)^{2} = a^{2} + b^{2} + 2 ab$ , you get squares plus cross terms:

(i \sum r_{1 i} u_{i})^{2} = i \sum r_{1 i}^{2} u_{i}^{2} + 2 j < ℓ \sum r_{1 j} r_{1 ℓ} u_{j} u_{ℓ} .

Take expectations term by term:

Cross terms vanish: $r_{1 j}$ and $r_{1 ℓ}$ are independent, so $E [r_{1 j} r_{1 ℓ}] = E [r_{1 j}] E [r_{1 ℓ}] = 0 \cdot 0 = 0$ .
Square terms: $E [r_{1 i}^{2}] = Var (r_{1 i}) + (E r_{1 i})^{2} = 1 + 0 = 1$ .

Var (r_{1}^{⊤} u) = i = 1 \sum d 1 \cdot u_{i}^{2} = ∥ u ∥^{2}

Since a weighted sum of independent normals is normal (Toolkit 0.5), we get more than mean and variance; we get the whole distribution:

r_{1}^{⊤} u \sim N (0, ∥ u ∥^{2}), and the same for r_{2}^{⊤} u, \dots, r_{k}^{⊤} u,

and these k numbers are independent of each other, since they use different rows of R.

Worked example: 2-D check

u = (3, 4), so ‖u‖² = 25.
Then $r^{⊤} u = 3 r_{1} + 4 r_{2}$ with $r_{1}, r_{2}$ independent N(0,1).
Variance = $3^{2} \cdot 1 + 4^{2} \cdot 1 = 25$ . ✓

Histogram of random dot products matching a normal curve with variance 25 — Simulation: u in 1,000 dimensions with ‖u‖² = 25, and 20,000 random rows r. The dot products have mean 0.05 and variance 25.09, matching N(0, 25).

Step 3: turn it into an estimation problem

Now forget it's a vector.
We have k independent observations $r_{1}^{⊤} u, \dots, r_{k}^{⊤} u$ from $N (0, σ^{2})$ , where the unknown variance is $σ^{2} = ∥ u ∥^{2}$ .
The best guess (MLE with known mean 0, Toolkit 0.9) is

∥ u ∥^{2} = \frac{1}{k} i = 1 \sum k (r_{i}^{⊤} u - 0)^{2} = i = 1 \sum k (\frac{r _{i}^{⊤} u}{k})^{2} .

The right-hand side is exactly the squared length of the vector whose entries are $r_{i}^{⊤} u / k$ .
So define the transformation

M = \frac{1}{k} R, u \in R^{d} \mapsto M u \in R^{k}, ∥ M u ∥^{2} = \frac{1}{k} i = 1 \sum k (r_{i}^{⊤} u)^{2} .

The squared length after projection estimates the original squared length. That is the whole trick: the √k scaling turns "estimate the variance" into "measure the length".

Worked example: a tiny projection by hand

d = 4, k = 2, u = (1, 2, 2, 4), so ‖u‖² = 25.
Suppose the random draws gave

R = [0.5 - 0.7 - 1.2 0.4 0.3 1.1 0.8 - 0.2] .

$r_{1}^{⊤} u = 0.5 - 2.4 + 0.6 + 3.2 = 1.9$
$r_{2}^{⊤} u = - 0.7 + 0.8 + 2.2 - 0.8 = 1.5$
$M u = \frac{1}{2} (1.9, 1.5)$ , so $∥ M u ∥^{2} = \frac{1. 9 ^{2} + 1. 5 ^{2}}{2} = \frac{3.61 + 2.25}{2} = 2.93$ .

That is far from 25.
This motivates the accuracy analysis: with only k = 2 observations the estimate is very noisy.
Repeating with fresh random R (one simulated run for each k) gave estimates of 1.3 (k = 2), 15.7 (k = 10), 33.5 (k = 100), 25.8 (k = 1,000) and 24.7 (k = 10,000).
Small k can be wildly off, even k = 100 missed by about a third in this run, and large k settles near 25.

Distribution of the length ratio for k = 10, 100, 1000 — Distribution of $∥ M u ∥^{2} /∥ u ∥^{2}$ . All three are centred at 1 (unbiased), but only large k keeps it inside the ±10 % band. Chance of landing in the band: 17 % (k = 10), 52 % (k = 100), 97.5 % (k = 1,000).

Check yourself

Why do we divide R by √k and not by k?

The estimate is $\frac{1}{k} \sum (r_{i}^{⊤} u)^{2}$ .
Putting $1/ k$ inside each term and squaring gives $1/ k$ .
So dividing the matrix by √k makes the squared length equal the average.

u = (1, 1, 1, 1). What distribution does

r^{⊤} u

have?

N(0, 4), since ‖u‖² = 4.

Key points to remember

Each Gaussian row output has mean zero and variance equal to the input’s squared length.
Dividing the matrix by $\sqrt{k}$ preserves squared length in expectation.
An unbiased estimate can still have a large error in one run.

YOUR STUDY PROGRESS

Finished this section? Save your progress.