Electrical Engineering Systems Seminar

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.