Course Title

Linear Sketch and Its Applications in Data Streams and Compressive Sensing


  • Aug. 30, 2012: Webpage created


Qin Zhang

Place and Time

See below. Note: time slots can be different for different lectures.

Course plan

Lecture Date and Venue Content Literature
 1  Sep. 3, 1:30-3pm, at 3405   Introduction to linear sketch and the streaming model, distinct elements  [Mut05], [Ind07] Lecture 1
 2  Sep. 4, 1:30-3pm, at 3405   L2 norm, stable distribution, Lp (p>2) norms  [Ind07] Lecture 3, [Ind06]
 3  Sep. 5, 1:30-3pm, at 3405   Heavy hitters, L1/L2 point query  [Ind07] Lecture 4
 4  Sep. 10, 1:30-3pm, at 3405   Introduction to compressive sensing, for each L1/L1, for all L1/L2  [GI10], [Ind07] Lecture 5-6
 5  Sep. 12, 4:30-6pm, at 3301A   For all L1/L2 (cont.)  [Ind07] Lecture 5-6, [Rice] Chapter 4  
 6*  Sep. 17, 1:30-3pm, at 3405   Introduction to communication complexity, sparse recovery lower bounds    [JW11], [DIPW10]
 7    L0 sampling, graph algorithms  [AGM12a], [AGM12b]


Still under construction. A temporary draft here