TY - GEN

T1 - Small ensembles of sampling matrices constructed from coding theory

AU - Barg, Alexander

AU - Mazumdar, Arya

PY - 2010/8/23

Y1 - 2010/8/23

N2 - In the area of compressed sensing it is known that high-dimensional, approximately sparse signals x ∈ ℝ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(k3 log N/log k) while the best randomized constructions require only m = Ω(klog(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 2 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(k2 log k log N), which compares favorably with the previously known estimate of O(k N log(N/k)) random bits for ensembles of random binary matrices.

AB - In the area of compressed sensing it is known that high-dimensional, approximately sparse signals x ∈ ℝ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(k3 log N/log k) while the best randomized constructions require only m = Ω(klog(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 2 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(k2 log k log N), which compares favorably with the previously known estimate of O(k N log(N/k)) random bits for ensembles of random binary matrices.

UR - http://www.scopus.com/inward/record.url?scp=77955684726&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77955684726&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2010.5513359

DO - 10.1109/ISIT.2010.5513359

M3 - Conference contribution

AN - SCOPUS:77955684726

SN - 9781424469604

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 1963

EP - 1967

BT - 2010 IEEE International Symposium on Information Theory, ISIT 2010 - Proceedings

T2 - 2010 IEEE International Symposium on Information Theory, ISIT 2010

Y2 - 13 June 2010 through 18 June 2010

ER -