Robust sparse recovery and applications: order-optimal measurements and complexitySidharth Jaggi 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< 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.)
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. |