April 2, 2013
Hosted by: Columbia University Joint CS/EE Networking Seminar Series
Speaker: Prof. Sidharth Jaggi , Assistant Professor (Dept. of Information Engineering, The Chinese University of Hong Kong)
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: (i) Compressive Sensing: A linear problem in which y is a (possibly noisy) linear transform of x, a vector in Rn. (ii) Group Testing: A non-linear problem in which y is a binary vector comprising of (possibly noisy) disjunctive measurements of a binary x vector. (iii) Network tomography: A linear problem in which x, a vector in Rn, 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.