2 - High-Dimensional Space

1. Introduction:
   • Summary of how high-dimensional space is different from low-dimensional space.
2. Law of Large numbers:
   • Markov's inequality and proof.
   • Chebyshev's inequality and proof.
   • Upper-bound on volume of unit ball using law of large numbers.
   • Expected square distance between high-dim gaussians.
   • Master tail bounds theorem (proof in appendix).
   • Chernoff bound.
3. The Geometry of High Dimensions:
   • Most of the volume of the unit ball lies in an annulus of width O(1/d) near the boundary.
4. Properties of the Unit Ball:
   • Proof of V(d) = A(d)/d.
   • Computing exact value of A(d).
   • Proof that volume is concentrated near the equator.
   • Proof that two random vectors from the unit ball are nearly orthogonal.
5. Generating Points Uniformly at Random from a Ball:
6. Gaussians in High Dimension:
   • Gaussian Annulus Theorem and its proof.
7. Random Projection and Johnson-Lindenstrauss Lemma:
   • Random projection theorem and its proof.
   • Johnson-Lindenstrauss lemma and its proof.
   • Using JL lemma for nearest neighbor search.
8. Separating Gaussians:
   • Distance (or norm) between vectors from the same spherical gaussian.
   • Distance (or norm) between vectors from separated spherical gaussians.
9. Fitting a Spherical Gaussian to Data:
   • Estimating mean.
   • Estimating variance.