We study the problem of recovering a high-dimensional sparse signal
based on random projections defined by various classes of measurement
matrices.  While significant work has focused on sparse recovery
methods using dense measurement matrices, a number of recent results
have investigated the use of sparse measurement matrices.  Sparse
matrices can reduce computational complexity and storage costs, as
well as communication and latency in distributed sensor network
applications.  However, measurement sparsity can potentially hurt
performance by requiring more measurements to recover the signal.
Therefore, an important question is to characterize the tradeoff
between the sparsity of the measurement matrix and the number of
measurements needed to recover.  We first address this question in an
information-theoretic setting, providing limits on the performance of
any recovery method.  We then present two computationally efficient
recovery methods, and compare their performance in terms of
computational complexity and sampling efficiency.