DRAFT
Caltech Logo

Electrical Engineering Systems Seminar

Wednesday, February 15, 2012
4:00pm to 5:00pm
Add to Cal
Moore B280
Group-testing meets compressive sensing: Novel LP-based decoding algorithms for non-linear (disjunctive) measurements
Sidharth Jaggi, Assistant Professor, Dept. of Information Engineering, Chinese University of Hong Kong,
Compressive sensing looks at the problem of computationally efficient recovery of sparse signals from low-dimensional (possibly noisy) linear measurements. Group-testing looks at the problem of computationally efficient recovery of sparse signals from (possibly noisy) low-dimensional non-linear (Boolean satisfiability) measurements. Motivated by the well-studied Basis Pursuit algorithm for the compressive sensing problem, we propose a class of new LP-decoding algorithms for the group-testing problem, and present novel techniques to characterize their performance based on ``perturbation analysis". These techniques themselves may be of significant interest for a suite of other problems where sparse signals need to be computationally efficiently reconstructed from low-dimensional measurements (such as error-correcting codes, distributed source coding). This is an expanded version of a talk presented at the Information Theory and Applications Workshop (2012) in San Diego. This work was done jointly with Prof. Venkatesh Saligrama of Boston University, and Eric Chan -- a sophomore at CUHK.
For more information, please contact Shirley Slattery by phone at 626-395-4715 or by email at shirley@systems.caltech.edu.