Probability bounds.
Random projections.
From controlling uncertainty to preserving distances in fewer dimensions.
Start with the toolkit, then follow the nine lessons in order. Each topic uses short points, separate equations, worked examples, graphs, and self-check questions. Read the optional proof extension after the main lessons.
Study sections
Follow the order or choose a sectionPrerequisite toolkit
Review these foundations before starting the main lessons. Each idea includes an explanation and a small example.
02Algorithms at scale
You already know how to classify, cluster and reduce data (PCA, nearest neighbour, SVM…). This course asks what happens when the data i…
03Markov’s inequality
Markov’s inequality requires a non-negative random variable and a positive threshold.
04Chebyshev’s inequality
The variance must be finite.
05Hoeffding’s inequality
The displayed Hoeffding bound is one-sided.
06Union bound and event relationships
Several events: add their probabilities to bound the chance that at least one happens. Related events: if A can happen only when B happ…
07Johnson–Lindenstrauss lemma
Big-O describes growth and does not determine a numerical target dimension without an explicit constant.
08Linear maps and the limits of exact preservation
Shine a torch on a stick and look at its shadow on the floor. The shadow is a 2D version of a 3D object. Tilt the stick so it points st…
09Gaussian random projections and scaling
Unbiasedness means that the expected squared projected length is correct.
10Measuring projection accuracy
Normalization requires a fixed nonzero input vector.