Small ensembles of sampling matrices constructed from coding theory

In the area of compressed sensing it is known that high-dimensional, approximately sparse signals x ∈ R^N can be accurately recovered from a small number m of linear samples. Most known recovery procedures rely in some form on a special property of the sampling matrix, called the Restricted Isometry Property (RIP). It has been shown that random Gaussian matrices possess the RIP and allow an efficient reconstruction of the signal, for instance, by linear programming or by other methods, and similar results are known for the ensembles of random binary matrices. We pursue a link between coding theory and compressed sensing, discussing the construction problem of sampling matrices with short sketches. The best known constructions of “small-bias probability spaces” (aka codes with narrow distance distribution) account for deterministic sampling matrices with sketch length m = O(k³ log N/log k) while the best randomized constructions require only m = Ω(k log(N/k)) samples, where k is the number of essential entries of the signal. We address the construction problem of sampling matrices in the region between these two extremes, allowing the sketch length of order k² log N. We show that in this case it is possible to construct ensembles of sampling matrices of size much smaller than the ensembles known previously. For instance, the number of random bits required to construct a matrix in one of our ensembles equals O(k² log k logN), which compares favorably with the previously known estimate of O(kN log(N/k)) random bits for ensembles of random binary matrices.