Johnson–Lindenstrauss dimension arithmetic

NumericalBeginner⏱ 15 minHigh-Dim Probabilityjldimensionarithmeticpractice

Problem

Using $k \ge 24\eps^{-2}\log N$ :

Compute the required $k$ for $N=10^3, 10^6, 10^9$ at $\eps = 0.1$ .
Compute the required $k$ for $N = 10^6$ at $\eps = 0.5, 0.1, 0.01$ .
A team wants to compress $10^6$ vectors from $D = 4096$ to $k = 256$ . What distortion does the lemma guarantee? Is the guarantee useful?

Compute the requested quantities and say what they mean. A number without an interpretation is not an answer.

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Problem	Field	Type	Difficulty	Time
Simulate distance contrast run	Classical ML	Coding	Beginner	30 min
A sufficient condition for correct retrieval	RAG	Proof	Intermediate	30 min
From distance preservation to inner-product preservation	High-Dim Probability	Proof	Intermediate	30 min
Implement random projection and measure the distortion run	High-Dim Probability	Coding	Intermediate	1 hour
The chi-squared moment generating function and its Chernoff bound	High-Dim Probability	Proof	Intermediate	30 min