Can the measurement matrix used for compressive sensing be a sparse matrix?

Question

I am interested in analyzing Compressive Mechanism: Utilizing Sparse Representation in Differential Privacy. In my research, the measurement matrix $A\mathbb \in R^{m \times n}$ needs to be sparse. The problem is that $n$ is potentially huge, for instance, it may be greater than $50,000,000,000$. Hence, sparsity is necessary if the matrix is going to be represented in memory. Using single-precision floating point numbers, where $m=\Theta(\log(n))$, a dense matrix will need more than 6000 gigabytes of memory!

I tried looking up sparse constructions for the measurement matrix but it does not google well; the word "sparse" is pretty common in compressive sensing literature. Also I discovered that the Restricted Isometry Property is not the only property that is sufficient for compressive sensing [2], rendering the search even harder.

For my purposes, it would be equally good to find a sparse construction for the measurement matrix, or alternatively finding out that such a construction is computationally infeasible (NP-hard, in the spirit of [3] and [4]), so I can dismiss this method altogether.

[2] B.S. Kashin and V.N.Temlyakov, A Remark on Compressed Sensing

[3] Afonso S. Bandeira, Edgar Dobriban, Dustin G. Mixon, William F. Sawin, Certifying the Restricted Isometry Property is Hard

[4] Andreas M. Tillmann, Marc E. Pfetsch, The Computational Complexity of the Restricted Isometry Property, the Nullspace Property, and Related Concepts in Compressed Sensing

Answer 1

Here are constructions I listed a while ago [1]:

• The RIP(1) ensembles of Indyk et al
• The sparse Johnson-Lindenstrauss Transforms ,
• Achioloptas' Database friendly Random Projections
• The "magic" Matrices of Krzakala et al  (see also their recent extension)
• The Light Chinese Design
• The LDPC deterministic construction of Dimakis et al
• The Binary Incoherent Matrices of Bailey, Iwen and Spencer (these matrices are sparse when multiplied with a discrete Fourier transform matrix

)

[1] http://nuit-blanche.blogspot.com/2012/03/sparse-measurement-matrices-what-are.html