Project 59: Random Matrix Theory for High-Dimensional ML

A self-contained deep-dive from the canonical Math from Foundations to Machine Learning curriculum.

  • Difficulty: Level 5: Master
  • Time: 2-3 weeks
  • Language: Python
  • Prerequisites: Projects 12, 24-25, 30, and 54
  • Source: ML-Math P31

What You Will Build

Build a simulation lab that separates covariance signal from high-dimensional noise. Generate Gaussian noise and spiked-covariance datasets across sample/feature aspect ratios, compute correctly normalized sample covariance spectra, and overlay empirical eigenvalue histograms with Marchenko-Pastur bulk support. Detect eigenvalues beyond the theoretical edge, measure false positives on pure-noise trials, and test how signal strength and finite sample size affect detection. Use spectrum-informed component retention or shrinkage in a downstream prediction/reconstruction task and compare it with naive explained-variance PCA.

Real World Outcome

A configured run reports n, p, aspect ratio, predicted bulk edges, observed extreme eigenvalues, detected spikes, and bootstrap-calibrated false-positive evidence. Plots show bulk/outliers across regimes, and a decision table demonstrates whether theory-guided truncation improves held-out performance or covariance estimation.

Core Question

When the number of dimensions is comparable to the number of observations, how can you distinguish genuine low-rank structure from noise eigenvalues?

Concepts You Must Understand First

  • Sample covariance, eigenvalue spectra, PCA, and aspect ratio.
  • Concentration in high dimensions — Roman Vershynin, High-Dimensional Probability.
  • Marchenko-Pastur bulk law and its asymptotic support.
  • Spiked covariance models, spectral outliers, and detectability thresholds.
  • Shrinkage, finite-sample calibration, and train/test evaluation.

Build Milestones

  1. Simulate pure-noise matrices over several p/n regimes and validate covariance normalization.
  2. Overlay empirical spectra with Marchenko-Pastur density/support and track extreme eigenvalues.
  3. Add controllable low-rank spikes and measure detection rate versus strength/sample size.
  4. Estimate false-positive rates and add bootstrap or repeated-simulation edge calibration.
  5. Compare spectrum-guided truncation/shrinkage with naive PCA on a downstream task.

Hints in Layers

  1. State whether data matrix entries and covariance use 1/n or 1/(n-1); formulas must match.
  2. Keep variance scaling consistent before comparing with the theoretical bulk edges.
  3. A finite-sample eigenvalue just beyond the asymptotic edge is not automatically signal—measure null fluctuations.

Common Pitfalls and Debugging

  • Pure noise produces many “signals”: covariance scaling or bulk formula is mismatched. Validate on large synthetic Gaussian cases first.
  • Results disagree after transposing data: sample and feature axes were confused. Assert shapes and define covariance orientation explicitly.
  • All outliers are retained without validation: finite-sample edge variation is ignored. Calibrate false-positive rate through null simulations.

Definition of Done

  • Pure-noise spectra match theoretical bulk behavior across multiple aspect ratios.
  • Covariance normalization and axis conventions are explicit and tested.
  • Spiked experiments report detection and false-positive rates over repeated trials.
  • Finite-sample edge uncertainty is measured rather than dismissed.
  • Theory-guided retention/shrinkage is compared with naive PCA on held-out data.
  • The final report distinguishes asymptotic prediction, simulation evidence, and practical recommendation.

Previous: Project 58 · Complete learning path · Next: Project 60