Devising Measurement Matrices

 Figure from Volkan Cevher's Lions labs

The following four preprints feature different ways to build measurement matrices for compressive sensing (or related) purposes:

Nonadaptive group testing with random set of defectives via constant-weight codes by Arya Mazumdar 

In a group testing scheme, set of tests are designed to identify a small number $t$ of defective items that are present among a large number $N$ of items. Each test takes as input a group of items and produces a binary output indicating whether any defective item is present in the group. In this paper we consider the nonadaptive scenario where defective items are random and follow simple probability distributions. In particular we consider the cases where 1) each item can be defective independently with probability $\frac{t}{N}$ and 2) each $t$-set of items can be defective with uniform probability. In both cases our aim is to design a testing matrix that successfully identifies the set of defectives with high probability. Both of these models have been studied in the literature before and it is known that $O(t\log N)$ tests are necessary as well as sufficient (via random coding) in both cases. Our main focus is explicit deterministic construction of the test matrices amenable to above scenarios. One of the most popular ways of constructing test matrices relies on constant-weight error-correcting codes and their minimum distance. In particular, it is known that codes result in test matrices with $O(t^2 \log N)$ rows that identify any $t$ defectives. With our relaxed requirements, we show that using an explicit constant-weight code we may achieve a number of tests equal to $O(t \log^2 N/ \log t)$ for the first case and $O(t^{3/2} \log^{3/2} N/\log t)$ for the second case. While still away by a factor of $\frac{\log N}{\log t}$ and $\frac{\sqrt{t\log N}}{\log t}$ respectively from the optimal number of tests, one may note that our constructions are deterministic and the main contribution lies in relating the group testing properties to parameters of constant-weight codes.

Linear-time list recovery of high-rate expander codes by Brett Hemenway, Mary Wootters

We show that expander codes, when properly instantiated, are high-rate list recoverable codes with linear-time list recovery algorithms. List recoverable codes have been useful recently in constructing efficiently list-decodable codes, as well as explicit constructions of matrices for compressive sensing and group testing. Previous list recoverable codes with linear-time decoding algorithms have all had rate at most 1/2; in contrast, our codes can have rate $1 - \epsilon$ for any $\epsilon > 0$. We can plug our high-rate codes into a construction of Meir (2014) to obtain linear-time list recoverable codes of arbitrary rates, which approach the optimal trade-off between the number of non-trivial lists provided and the rate of the code. While list-recovery is interesting on its own, our primary motivation is applications to list-decoding. A slight strengthening of our result would implies linear-time and optimally list-decodable codes for all rates, and our work is a step in the direction of solving this important problem.

Deterministic construction of sparse binary and ternary matrices from existing binary sensing matrices by Pradip Sasmal, R. Ramu Naidu, C. S. Sastry, P. V. Jampana 

In the present work, we discuss a procedure for constructing sparse binary and ternary matrices from existing two binary sensing matrices. The matrices that we construct have several attractive properties such as smaller density, which supports algorithms with low computational complexity. As an application of our method, we show that a CS matrix of general row size different from $p, p^2, pq$ (for different primes $p,q$) can be constructed.

A new method on deterministic construction of the measurement matrix in compressed sensing by Qun Mo 

Construction on the measurement matrix $A$ is a central problem in compressed sensing. Although using random matrices is proven optimal and successful in both theory and applications. A deterministic construction on the measurement matrix is still very important and interesting. In fact, it is still an open problem proposed by T. Tao. In this paper, we shall provide a new deterministic construction method and prove it is optimal with regard to the mutual incoherence.

  Join the CompressiveSensing subreddit or the Google+ Community and post there !
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.