SECTION 10 / 10

Measuring projection accuracy

On this page 8 headings

Learning goal: Rewrite a projection error using a standard Gaussian vector.

Normalization requires a fixed nonzero input vector.
The normalized vector is jointly Gaussian because it is a linear transformation of Gaussian entries.
Mean zero and identity covariance alone do not establish Gaussianity for an arbitrary random vector.

The ideaOn average our squeezed length is right, but we only squeeze once.
What is the chance that this one time the length comes out too big, more than (1 + ε) times the truth?
The key step is to rescale things so this question no longer mentions u or d at all.
It becomes a question about a standard random Gaussian vector in k dimensions, which is much easier to analyse.

v = \frac{1}{k} R u \in R^{k}, v_{i} = \frac{1}{k} j = 1 \sum d r_{ij} u_{j} .

Step 1: unbiased, the exercise solved

E ∥ v ∥^{2} = E [i = 1 \sum k v_{i}^{2}] = i = 1 \sum k \frac{1}{k} E [(r_{i}^{⊤} u)^{2}] = i = 1 \sum k \frac{1}{k} ∥ u ∥^{2} = ∥ u ∥^{2} .

The middle step uses Lesson 8: $E [(r_{i}^{⊤} u)^{2}] = ∥ u ∥^{2}$ for every row i.
So if we could repeat the random projection many times and average, we'd get the length exactly.
Compare this with Lesson 7: no fixed matrix can preserve lengths, but a random one does on average.
In practice we project only once, so we need the probability of a bad outcome.

BAD: ∥ v ∥^{2} \geq (1 + ε) ∥ u ∥^{2} (squeezed length too big) .

Here u is fixed and v is random, because R is random.
We want $P (BAD)$ to be tiny.
The "too small" side, $∥ v ∥^{2} \leq (1 - ε) ∥ u ∥^{2}$ , is handled the same way.

Define

x = \frac{k}{∥ u ∥} v = \frac{1}{∥ u ∥} R u = \frac{1}{∥ u ∥} r_{1}^{⊤} u ⋮ r_{k}^{⊤} u, ∥ x ∥^{2} = \frac{k ∥ v ∥ ^{2}}{∥ u ∥ ^{2}} (1) .

Why this choice?
It divides out the unknown length ‖u‖ and the √k scaling, leaving a vector with a "standard" shape.
Now compute its mean and covariance:

Mean: each entry is $\frac{1}{∥ u ∥} r_{i}^{⊤} u$ , and $E [r_{i}^{⊤} u] = 0$ , so $E [x] = 0$ .
Diagonal of covariance: $E [x_{i}^{2}] = \frac{E [( r _{i}^{⊤} u ) ^{2} ]}{∥ u ∥ ^{2}} = \frac{∥ u ∥ ^{2}}{∥ u ∥ ^{2}} = 1$ .
Off-diagonal (i ≠ j): $E [x_{i} x_{j}] = \frac{1}{∥ u ∥ ^{2}} E [(r_{i}^{⊤} u) (r_{j}^{⊤} u)] = \frac{1}{∥ u ∥ ^{2}} E [r_{i}^{⊤} u] E [r_{j}^{⊤} u] = 0$ .
The split is allowed because rows i and j of R are independent, so the two dot products are independent.

E [x] = 0, Cov (x) = I_{k \times k} ⟹ x \sim N (0, I_{k \times k})

So x is a standard multivariate normal vector: k independent N(0,1) numbers.
The facts that every $x_{i}$ is normal and that the coordinates are independent come from Lesson 8, so mean 0 and covariance I pin down the distribution completely.

P (∥ v ∥^{2} \geq (1 + ε) ∥ u ∥^{2}) = P (\frac{∥ v ∥ ^{2}}{∥ u ∥ ^{2}} \geq 1 + ε) = P (\frac{k ∥ v ∥ ^{2}}{∥ u ∥ ^{2}} \geq k (1 + ε)) = P (∥ x ∥^{2} \geq k (1 + ε))

Each step only divides or multiplies both sides by a positive number, so the events are identical (A ⇔ B from Lesson 5) and the probabilities are equal.
The last step uses (1).

k = 1,000, ε = 0.1.
Draw 1,000 independent N(0,1) numbers, square them and add them up.
The total averages 1,000 (each square averages 1).
The bad event is "the total is at least 1,100".
Computed exactly, this happens with probability about 1.5 %.
The "too small" event (total ≤ 900) has probability about 1.1 %.
So with k = 1,000, one fixed vector keeps its length within ±10 % about 97.5 % of the time.

Why is

E ∥ x ∥^{2} = k

$∥ x ∥^{2} = \sum_{i = 1}^{k} x_{i}^{2}$ and each $E [x_{i}^{2}] = 1$ .

Rewrite the "too small" event

∥ v ∥^{2} \leq (1 - ε) ∥ u ∥^{2}

in terms of x.

$P (∥ x ∥^{2} \leq k (1 - ε))$ .

Where does d appear in

P (∥ x ∥^{2} \geq k (1 + ε))

Fix a nonzero input vector before normalizing.
The normalized coordinates are independent standard normal variables.
The tail question depends on k and $\varepsilon$ ; the original dimension d disappears.

YOUR STUDY PROGRESS

Finished this section? Save your progress.