Lecture notes
These are the lecture notes for a short course "Streaming etc.", given at Rice University in Spring'09.
Introduction to streaming algorithms. Estimating the number of distinct elements and the L0 norm.
Estimating the L2 norm.
Estimating the Lp norms using p-stable distributions.
Heavy hitters and sparse approximations.
Compressive sensing. Sparse recovery using sparse matrices. RIP1 principle. State of the art table.
Lower bounds for streaming and compressed sensing.