Compressed Sensing: Extending Reed-Solomon codes.

Mehmet Akçakaya and Vahid Tarokh have written a series of papers where they use the theoretical framework of algebraic coding/decoding to do Compressive sampling. The measurement matrices are what they call Vandermonde frames that generalize Reed-Solomon codes using Vandermonde matrices. Reconstruction of the signal can be computed using many well known Reed-Solomon type decoding algorithms. In the noiseless case, they have better recovery results (in regards to sparsity) than previously.


Shannon Theoretic Limits on Noisy Compressive Sampling by Mehmet Akçakaya, Vahid Tarokh. The abstract reads:

In this paper, we study the number of measurements required to recover a sparse signal in ${\mathbb C}^M$ with $L$ non-zero coefficients from compressed samples in the presence of noise. For a number of different recovery criteria, we prove that $O(L)$ (an asymptotically linear multiple of $L$) measurements are necessary and sufficient if $L$ grows linearly as a function of $M$. This improves on the existing literature that is mostly focused on variants of a specific recovery algorithm based on convex programming, for which $O(L\log(M-L))$ measurements are required. We also show that $O(L\log(M-L))$ measurements are required in the sublinear regime ($L = o(M)$).

On Sparsity, Redundancy and Quality of Frame Representations by Mehmet Akçakaya, Vahid Tarokh. The abstract reads:

We consider approximations of signals by the elements of a frame in a complex vector space of dimension N and formulate both the noiseless and the noisy sparse representation problems. The noiseless representation problem is to find sparse representations of a signal r given that such representations exist. In this case, we explicitly construct a frame, referred to as the Vandermonde frame, for which the noiseless sparse representation problem can be solved uniquely using O(N2) operations, as long as the number of non-zero coefficients in the sparse representation of r is N for some 0    0.5, thus improving on a result of Candes and Tao [4]. The noisy sparse representation problem is to find sparse representations of a signal r satisfying a distortion criterion. In this case, we establish a lower bound on the trade-off between the sparsity of the representation, the underlying distortion and the redundancy of any given frame.

A Frame Construction and A Universal Distortion Bound for Sparse Representations by Mehmet Akçakaya, Vahid Tarokh.The abstract reads:

We consider approximations of signals by the elements of a frame in a complex vector space of dimension N and formulate both the noiseless and the noisy sparse representation problems. The noiseless representation problem is to find sparse representations of a signal r given that such representations exist. In this case, we explicitly construct a frame, referred to as the Vandermonde frame, for which the noiseless sparse representation problem can be solved uniquely using O(N^2) operations, as long as the number of non-zero coefficients in the sparse representation of r is N for some 0    0.5. It is known that   0.5 cannot be relaxed without violating uniqueness. The noisy sparse representation problem is to find sparse representations of a signal r satisfying a distortion criterion. In this case, we establish a lower bound on the trade-off between the sparsity of the representation, the underlying distortion and the redundancy of any given frame.