# 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.