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.