UB - University at Buffalo, The State University of New York

This page refers to the Fall 2011 offering of CSE 709 only. The information on this page does not necessarily apply to every offering of CSE 709.

Fall 2011

37274

Dr. Atri Rudra

Compressed Sensing, Group testing, Compression, Dimensionality Reduction

Compressed Sensing and Group testing are compression/dimensional reduction techniques that allow one to "compress" a high-dimensional vector with N coordinates into a low-dimensional vector with t elements such that from the compressed vector, one can recover a good approximation of the k most significant components of the original vector. (In particular, when k is small, one can get away with a t value that is exponentially smaller than N.)

Group testing was formulated in 1943 while compressed sensing was defined recently in 2006. Both have many practical (and theoretical!) applications. E.g., group testing was originally design to help identify WW-II draftees with syphilis and has since found many applications in diverse areas such as DNA library screening, drug testing, live-baiting DoS attackers, and broadcast encryption. Compressed sensing has applications in image processing and other related fields.

This seminar is part 1 of a two semester sequence of seminars on compressed sensing and group testing and will be co-taught by Hung Ngo and Atri Rudra. (For fall 2011, register for CSE 709.) This semester we will study the theoretical basics of compressed sensing and group testing and next semester (Spring 2012) we will study their generalization and applications.

The seminar will be half lectures presented by Hung and Atri and half presentations by students, which will be either research papers or from existing course notes.

If you have any questions, feel free to contact Hung or Atri by email.

None presently available.

Mathematical Maturity. We will be doing proofs in the seminar so as long as your comfortable with proof, you'll be fine. Some level of comfort with discrete probability theory is helpful.