[A&C Seminar] Robust sparse recovery and applications: order-optimal measurements and complexity
Speaker: Sidharth (Sid) Jaggi, The Chinese University of Hong Kong
Date: Friday, March 8 2013
Time: 3:00PM to 4:00PM
Location: 32-G575
Host: Piotr Indyk
Contact: Eric Price, ecprice@mit.edu
Relevant URL: http://www.mit.edu/~ecprice/algcompsem/
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.)
See other events happening in March 2013
