## DIMACS TR: 2005-40

## Combinatorial Algorithms for Compressed Sensing

### Authors: Graham Cormode and S. Muthukrishnan

**
ABSTRACT
**

In sparse approximation theory, the fundamental problem is to reconstruct
a signal A \in R^n from linear measurements (A,psi_i) with respect to a
dictionary of psi_i's. Recently, there is focus on the novel direction of
Compressed Sensing where the reconstruction can be done with very
few---O(k log n)---linear measurements over a modified dictionary if the
signal is compressible, that is, its information is concentrated in k
coefficients. In particular, these results prove that there exists a
single O(k log n) x n measurement matrix such that any such signal can be
reconstructed from these measurements, with error at most O(1) times the
worst case error for the class of such signals. Compressed sensing has
generated tremendous excitement both because of the sophisticated
underlying Mathematics and because of its potential applications.
In this paper, we address outstanding open problems in Compressed Sensing.
Our main result is an explicit construction of a non-adaptive measurement
matrix and the corresponding reconstruction algorithm so that with number
of measurements polynomial in k, log n, 1/epsilon, we can reconstruct any
compressible signal upto 1+epsilon error. This is the first known
polynomial time explicit construction of any such measurement matrix. Our
result not only improves the error guarantee from O(1) to 1 + \epsilon but
also improve the reconstruction time from poly(n) to poly(k log n).

Our second result is a randomized construction of a measurement matrix of
size O(k polylog n) that works for each signal with high probability and
gives per-instance approximation guarantee rather than over the class of
all signals. Previous work on Compressed Sensing does not provide such
per-instance approximation guarantee; our result improves the best known
number of measurements known from prior work in other areas including
Learning Theory Streaming algorithms and Complexity Theory for this case.
Our approach is combinatorial. In particular, we use two parallel sets of
group tests, one to filter and the other to certify and estimate; the
resulting algorithms are quite simple to implement.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2005/2005-40.pdf

DIMACS Home Page