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.
- Instructor: Yin Tat Lee
- Office Hours: By appointment, email me at firstname.lastname@example.org
- Lectures: Tue, Thu 10:00 – 11:20AM at Zoom
- TA: Sally Dong (email@example.com)
- Text Book: https://www.sketchingbigdata.org/fall20/lec/notes.pdf
- Course evaluation: 3 assignments (100%) or 1 project (100%)
- Project ideas: https://sublinear.info/
- Posted and Submitted via Gradescope. I will email you whenever I post the assignment.
- 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.
- 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
- Feb 11: Compressive Sensing, RIP Properties
- Feb 16: Iterative Hard Thresholding
- 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
- Mar 4: Property Testing
- Mar 9: Project Presentation
- Mar 11: Project Presentation