Sparse Measurement Matrices: What are they good for ? (Part deux)

With regards to sparse measurement matrices [ Sparse Measurement Matrices: What are they good for ?], Phil Schniter reminded of this contribution (the first version was 2010) where, according to the authors we have 

"The first deterministic construction of compressed sensing measurement matrices with an order-optimal number of measurements."

 The paper is  LDPC Codes for Compressed Sensing by Alexandros Dimakis, Roxana Smarandache,  and Pascal Vontobel, The construction is in Corollary 18: 

Let dv, dc ∈ Z>0. Consider a measurement matrix HCS ∈ {0, 1} m×n whose Tanner graph is a (dv, dc)-regular bipartite graph with Ω(log n) girth. This measurement matrix succeeds in recovering a randomly supported k = αn sparse vector with probability 1 − o(1) if α is below some threshold function α'(dv, dc, m/n).

Also of related interest is Sparse Binary Matrices of LDPC codes for Compressed Sensing by Weizhi Lu ,Kidiyo Kpalma , Joseph Ronsin. but the authors do not seem to be aware of the LDPC codes for CS paper.mentioned above.

ThankPhil !

Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.