Electrical Engineering Systems Seminar

Wednesday February 15, 2012 4:00 PM

Group-testing meets compressive sensing: Novel LP-based decoding algorithms for non-linear (disjunctive) measurements

Speaker: Sidharth Jaggi, Dept. of Information Engineering, Chinese University of Hong Kong
Location: Moore B280
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.
Series Electrical Engineering Systems Seminar Series

Contact: Shirley Slattery at 626-395-4715 shirley@systems.caltech.edu