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 (material from lectures 1, 2, 3, 5, 6).
  1. Monday, Jul. 18 — introduction, basic tail bounds, Morris' algorithm. [PDF][TeX]
  2. Monday, Jul. 18 — necessity of approximate/randomized guarantees, distinct elements, k-wise independence. [PDF][TeX]
  3. Thursday, Jul. 21 — turnstile model, linear sketching, AMS sketch, CountMin sketch (point query, heavy hitters, sparse recovery), deterministic point query via incoherence. [PDF][TeX]
  4. Bibliography file. [bib]

    Exercises. [PDF][TeX]
    Solutions. [PDF][TeX]