RandNLA Proof Wiki Home

Welcome to the Randomized Numerical Linear Algebra (RandNLA) Proof Wiki. The goal of this site is to catalogue the most clean and essential proofs used in the RandNLA literature. This website is a work-in-progress, and if you see something you would like to change, then reach out to Raphael Meyer at ram900@nyu.edu, or submit an issue on github.

Keep in mind that this site emphasizes simplicity and minimalism in proofs. We aim to be clear and concise. If two results use very similar proofs then we will only present one of those proofs, and only mention or cite the other.

You can browse the list of all proofs below this section. If you would like to submit an additional proof, then read our page on contributing. In addition these proofs, we also list many useful and sometimes hard-to-find theorems at the bottom of this page.

RandNLA Proofs

Todo Note: Autogenerate this via Franklin.jl Tags

Todo Note: Make these intro dropdowns? It's a bit overwhelming visually as-is.

Oblivious Embeddings:

1. Gaussian Johnson-Lindenstrauss Lemma

2. Subspace Embedding via JL Lemma (epsilon-net)

Leverage Scores:

1. Basic Properties of Leverage Scores

2. Subspace Embedding via Leverage Score Sampling (Matrix Bernstein)

3. Active $L_2$ Regression via Leverage Score Sampling

Self-Contained Results:

1. Fast Matrix-Matrix Multiplication

2. $L_p$ Regression via Subspace Embedding

3. Power Method for Top Eigenvalue

4. Krylov Iteration for Low-Rank Approximation

5. Optimal Trace Estimation

6. Preconditioning Methods

7. Adaptive Subsampling Algorithms

Useful References

1. Approximating Common Functions with Polynomials

2. Spike Polynomials