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