ELEC 631 - Advanced Digital Signal Processing: Streaming Algorithms and Dimensionality Reduction - Spring 2009
This course covers a new approach to dealing with large data sets based on the concept of approximate "sketches". Sketches can be exponentially shorter than the original data yet retain important and useful information, including the number of distinct elements in the data set, the "similarity" between the data elements, and so on. Applications include data compression, approximate query processing in databases, network measurement, and signal processing/acquisition.
Topics include sketching, heavy hitters, sparse approximation, dimensionality reduction and the Johnson-Lindenstrauss lemma, compressive sensing. Useful tools we will see along the way include communication complexity, statistics, geometric functional analysis, and combinatorial group testing.
Instructors:
Piotr Indyk
indyk@mit.edu
indyk@mit.edu
Location: Duncan Hall 1044
Time: Friday 2-5pm
Our special guest Piotr Indyk will lecture in January and February. In March, students will read classic and recent papers and present to the rest of the class in a debate format. Students will also complete a group project.
The course is open to students from any department with some background in probability and analysis.
Class grade will be based on:
- class participation (20%)
- paper presentation (30%)
- group project (50%)