CSE 599: Sketching Algorithms

Sketching algorithms are powerful techniques to compress data in a way that lets you answer various queries. In this course, we will cover various algorithms that make use of sketching techniques. This includes:

  • Randomized algorithms for linear algebra
  • Streaming algorithms
  • Compressed sensing

Prerequisites: Linear Algebra, Probabilities. Comfortable with theory courses such as CSE 521.

Administrative Information:

  • Instructor: Yin Tat Lee
  • Office Hours: By appointment, email me at yintat@ignoreme-uw.edu
  • Lectures: Tue, Thu 10:00 – 11:20AM at Zoom
  • TA: Sally Dong (sallyqd@ignoreme-cs.washington.edu)
  • Text Book: https://www.sketchingbigdata.org/fall20/lec/notes.pdf
  • Course evaluation: 3 assignments (100%) or 1 project (100%)
  • Project ideas: https://sublinear.info/

Assignments

  • Posted and Submitted via Gradescope. I will email you whenever I post the assignment.

Class Policy

  • You may discuss assignments with others, but you must write down the solutions by yourself.
  • Assignments as well as regrade requests are to be submitted only via gradescope.
  • In general, late submissions are not accepted (the submission server closes at the deadline). Gradescope lets you overwrite previous submissions, so it is recommended to use this feature to avoid missing the submission deadline altogether.
  • We follow the standard UW CSE policy for academic integrity.
  • Please refer to university policies regarding disability accommodations or religious accommodations.

Tentative Schedule:

Counting Problems

  • Jan 05: Morris Counter
  • Jan 07: Distinct elements

Linear Sketch and Johnson-Lindenstrauss Transforms

  • Jan 12: Heavy hitter
  • Jan 14: Dynamic Spanning Tree
  • Jan 19: Norm Estimation
  • Jan 21: Norm Estimation
  • Jan 26: Sparse JL
  • Jan 28: Fast JL

Linear Algebra Applications

  • Feb 2: Approximate Matrix Multiplication
  • Feb 4: Oblivious Subspace Embedding
  • Feb 9: Low-rank Approximation

Sparse recovery

  • Feb 11: Compressive Sensing, RIP Properties
  • Feb 16: Iterative Hard Thresholding

Sparse FFT

  • Feb 18: 1-sparse Fourier Sampling
  • Feb 23: Isolation via Aliasing

Dudley’s theorem and its applications

  • Feb 25: Dudley’s theorem
  • Mar 2: Instance-wise bounds for JL

Others

  • Mar 4: Property Testing
  • Mar 9: Project Presentation
  • Mar 11: Project Presentation