Columbia University Joint CS/EE Networking Seminar Series


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

Prof. Sidharth Jaggi

Dept. of Information Engineering, The Chinese University of Hong Kong

Apr. 2, 10:30AM, CEPSR 1021 (CISE Conference Room)



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 less than n components, and the goal is to reconstruct (a good approximation to) x. 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, andO(k log(n)) measurements and decoding complexity for group testing.)

Speaker Biography: 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.