WEEK 02
Finish the proof.
Understand the geometry.
Chernoff bounds, preserving every pair, and the SVD view of random projection.
5 study sections10 illustrations2 resources
Begin with the recap →Begin with the Week 1 recap and toolkit. Then study three lessons: Chernoff bounds, preserving all pairs, and the SVD interpretation. Finish with the complete proof and formula summary. Explanations use short points, separate equations, worked examples and self-checks.
Study sections
Follow the order or choose a section01
Week 1 recap
The remaining goal is a high-probability guarantee.
02Prerequisite toolkit
For the upper-tail proof, choose 0 < λ < 1/2.
03Chernoff bounds for projection error
The normalized coordinates are independent standard normal variables.
04Preserving all pairs: the final JL guarantee
There are n(n−1)/2 distinct unordered pairs.
05The SVD interpretation of random projection
For the displayed k × d SVD, assume k ≤ d.