2016 TUM Summer School on Mathematical Methods for High-Dimensional Data Analysis, Notes on sketching and streaming

You may also find these lecture notes and these videos helpful (from lectures 1—3, 5, and 6).

1. Monday, Jul. 18 — introduction, basic tail bounds, Morris' algorithm.
2. Monday, Jul. 18 — necessity of approximate/randomized guarantees, distinct elements, k-wise independence.
3. Thursday, Jul. 21 — turnstile model, linear sketching, AMS sketch, CountMin sketch (point query, heavy hitters, sparse recovery), deterministic point query via incoherence.

BibTeX file.

• Exercises

• Solutions