Sidharth Jaggi, CUHK, Hong Kong

Title: Order-optimal Compressive Sensing for k-parse Signals with Noisy Tails: O(k) Measurements, O(k) Steps

Abstract:
Suppose x is any exactly k-sparse vector in R^n. We present a class of algorithms that we call SHO-FA (for Short&Fast) that with high probability (over “sparse” measurement matrices) can reconstruct x. The SHO-FA algorithms are the first that have both order-optimal measurement complexity O(k), and order optimal decoding complexity of a total of O(k) arithmetic operations over log(n)-bit numbers. In addition, our SHO-FA algorithms are robust to random noise, and (random) approximate sparsity. In particular, for k = O(n^{1−∆}) for any ∆ > 0 suppose the measured vector equals A(x+z)+e, where z and e correspond respectively to the source tail and measurement noise. Under mild statistical assumptions on z and e our decoding algorithm reconstructs x with an estimation error of O(||z||_1 + ||e||_1). The SHO-FA algorithms work with high probability over measurement matrices, z, and e, and still require only O(k) steps and O(k) measurements. This is in contrast to most existing algorithms which focus on the “worst-case” z model, where it is known Omega(k log(n/k)) measurements are necessary. We describe applications of these results for the MAC (Multiple Access Channel) problem.