Implement random projection and measure the distortion

CodingIntermediate⏱ 1 hourHigh-Dim Probabilityjlimplementationdistortionempirical

Problem

Implement Gaussian random projection and measure, for a cloud of $N$ points in $\R^D$ :

The maximum and mean pairwise distortion as a function of $k$ .
Verify that the maximum distortion decays like $1/\sqrt k$ and that the mean decays likewise but with a much smaller constant.
Verify that varying $D$ at fixed $k$ barely changes the distortion.
Compare Gaussian entries with Rademacher entries.

Implement it, then check the implementation against something you can verify independently.

Solve it here4 tests · Python runs in your browser

⌘/Ctrl + ↵ to run · limit 40s · draft saved in this browser

4 tests will run against your code. The first run downloads the Python runtime — several megabytes, once per browser.

Hints — 0 of 3 revealed

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
Johnson–Lindenstrauss dimension arithmetic	High-Dim Probability	Numerical	Beginner	15 min
From distance preservation to inner-product preservation	High-Dim Probability	Proof	Intermediate	30 min
Implement backpropagation from scratch run	Deep Learning	Coding	Intermediate	3 hours
Implement kernel ridge regression run	Classical ML	Coding	Intermediate	1 hour
Implement multi-head attention from scratch run	Deep Learning	Coding	Intermediate	3 hours