Robust sparse recovery and applications: order-optimal measurements and complexity

Sidharth Jaggi
Professor, The Chinese University of Hong Kong
Given on: March 1st, 2013

Abstract

Sparse recovery problems are usually in the setting in which a vector x with ambient dimension n has only k "significant" entries. This vector x is "compressively measured" (with possibly "noisy" measurements) as y, where y has just m<

We consider three sparse recovery problems: * Compressive Sensing: A linear problem in which y is a (possibly noisy) linear transform of x, a vector in R^n. * Group Testing: A non-linear problem in which y is a binary vector comprising of (possibly noisy) disjunctive measurements of a binary x vector. * Network tomography: A linear problem in which x, a vector in R^n, denotes network parameters (such as edge/node delays) to be estimated via constrained, end-to-end measurements (such as path delays).

In each of these cases we present sparse recovery algorithms that have good reconstruction performance, and have information-theoretically order-optimal decoding complexity and number of measurements (O(k) measurements and decoding complexity for compressive sensing and network tomography, and O(k log(n)) measurements and decoding complexity for group testing.)

Bio

B.Tech. ('00), EE, IIT Bombay, MS/Ph.D. ('05) EE, CalTech, Postdoctoral Associate ('06) LIDS, MIT, Assistant Professor, ('07-present), Dept. of Information Engineering, The Chinese University of Hong Kong. Research interests: Network coding and network error-correcting algorithms, coding theory, steganography, group testing, compressive sensing.