Order-optimal compressive sensing for k-sparse signals with noisy tails: O(k) measurements, O(k) steps

----------------------------------------------------------------------
               Joint Seminar
Department of Electronic & Computer Engineering
Department of Computer Science and Engineering
----------------------------------------------------------------------
Speaker:        Prof. Sidharth Jaggi
                Department of Information Engineering
                The Chinese University of Hong Kong

Title:          "Order-optimal compressive sensing for k-sparse signals with
                noisy tails: O(k) measurements, O(k) steps"

Date:           Thursday, 31 May 2012

Time:           11:00 am - 12:00 noon

Venue:          Rm 2463, 2/F (Lift 25 or 26), HKUST

*Supported by the IEEE Information Theory Society, Hong Kong Chapter


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.


*******************
Biography:

Sidharth Jaggi received his Bachelor of Technology degree from the Indian
Institute of Technology in 2000, and his Master of Science and Ph.D.
degrees from the California institute of Technology in 2001 and 2006
respectively, all in electrical engineering. He was awarded the Caltech
Division of Engineering Fellowship 2001-'02, and the Microsoft Research
Fellowship for the years 2002-'04. He interned at Microsoft Research,
(Redmond, WA, USA) in the summers of 2002-'03 and engaged in research on
network coding. He spent 2006 as a Postdoctoral Associate at the
Laboratory of Information and Decision Systems at the Massachusetts
Institute of Technology. He joined the Department of Information
Engineering, the Chinese University of Hong Kong in 2007.

Sidharth's research interests lie at the intersection of information
theory, algorithms, and networking. He is currently particularly
interested in the field of network coding
http://www.ifp.uiuc.edu/~koetter/NWC/index.html which neatly merges
practice and theory in all three of these fields. However, his interests
are eclectic (above all, he likes a good challenge) and he has dabbled in
communication complexity, quantum computation, coding theory, random
matrix theory, and signal.

Copyright 2012 Department of Electronic & Computer Engineering