Robust Sparse Recovery and Applications: Order-Optimal Measurements and Complexity

April 2, 2013
10:30am-11:30am
CEPSR 1021
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)

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: (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.)

Speaker Biography

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.


500 W. 120th St., Mudd 1310, New York, NY 10027    212-854-3105               
©2014 Columbia University