Sushil Subramanian – Weblog

Essays on engineering, music, culture and their curious intersections – by Sushil Subramanian

Archive for May 2009

Compressed Sensing: Transmit Nothing – Receive Everything

with 2 comments

(I wrote this article on request from my friend Ved Deshpande, for the Mathematics Department, IIT Kharagpur, newsletter, Xponent, as a guest article. There may be some technical mistakes in this article, however, this is how I understood compressed sensing.)

What we know:

In the last 5 years, the discipline of Applied Mathematics, particularly in Communications and Signal Processing has seen a spectacular shift in paradigm. In Sping 2004, David Donoho’s (Stanford) former PhD. student, Emmanuel Candes (presently at CalTech.) first discussed the idea of compressed sensing. From these meetings germinated a novel and phenomenal method of sensing and estimating signals, which Donoho developed. Simultaneously, with the help of post doctoral student Justin Romberg (now at GeorgiaTech.) and Field’s Medalist Terence Tao (UCLA), Candes also nurtured the same idea, which developed into a unique set of papers on compressed sensing. This article is an attempt to expose the beauty of their findings, which often go unnoticed in mathematics and applied sciences.

Consider a digital signal x(n) where  1 \leq n \leq N   i.e., the signal has restricted length. In the 1930’s, work done by Shannon, Whittaker and Nyquist suggests that the above signal can be reconstructed with zero-error, if it had at least  2N samples to begin with. This is equivalent to saying, that if  can be represented as a unique linear combination of  unique functions (often called a basis), then a matrix of dimension  2N \times N has to sample the signal for perfectly obtaining the original basis. Since the basis in consideration and the signal x are related by a unique linear combination, if the basis is obtained perfectly,  x can simply be obtained by the relation  x = \psi \theta \mathrm{,} where  \theta is the basis of length N and  \psi is a unique, invertible  N \times N matrix called the transform matrix. For example, some of us may be familiar with the Fourier basis, where \psi is full of  e^{2\pi j n k / N} terms, where n and k are the matrix indices.

The Paradigm Shift:

Let us think of the entire problem in a different way. Let’s say we want to reproduce the signal most of the times. This means, if we try to reconstruct the signal infinite times in infinite different experiments, we will converge to a probability of reconstruction,  P. If we can make P high enough, we can think of posing relaxations on other constraints in the problem. What will be truly interesting is we could manage to get away with sampling the signal with a matrix of dimension K \times N where K is allowed to be lesser than N. A bold statement saying that it is indeed possible, in the form of a big blow to the age old theory of Shannon, was declared by Candes and Donoho in their groundbreaking papers in 2004. On the downside however, this works for a specific set of signals only known as sparse signals. In a nutshell, Candes and Donoho said that if the basis is sparse, i.e. it contains very few non-zero elements, then it is possible to sample the signal with a matrix of size K \times N often called a matrix of transformation to a lesser rank, and still manage to get back x.

Suppose, the basis \theta is S-\mathrm{sparse} i.e. S out of the N elements of the basis are non-zero. Now we use a K \times N matrix for sampling. Thus the resulting signal is of length K which can be represented as y = \phi x = \phi \psi \theta. This signal has been proven to be enough to get back \theta. Amazingly, Candes and Donoho also showed that as long as \psi and \phi are highly incoherent (a mathematical formulation of how unrelated the matrices are), \phi can be completely random! Further, K can be as less as S \log N and the probability of failure \left(1-P \right) is about e^{-1/N}. If S = 3 and N = 100 it implies K \approx 14 which is way lesser than that predicted by Shannon! At first it may seem that y being a K-\mathrm{length} vector means that to obtain \theta we actually have more variables than equations (if \phi and \psi are assumed known). However, this problem is cleverly overcome by Candes and Donoho using the concepts of linear programming and convex optimization often used in electrical engineering and operations research.

The Implications:

Compressed sensing (aptly termed, as we compress the way we measure or “sense” as mentioned above) has far reaching implications in the applied sciences and engineering fields. One application is in underwater communications. In underwater communication channels, signals are usually distorted by a channel response which can be modeled as a sparse signal, very similar to the basis described above. The transmitted signal convolves as a matrix similar to \psi, and the signal is then available to a receiver. Now that we know that the channel response is sparse, we can measure the signal to obtain a K-\mathrm{length} signal that can perfectly give us back the channel response! This channel response comes in very handy in finally removing the Gaussian noise from the data. Thus, in effect, we are measuring a signal as if nearly nothing has been transmitted and every required information is available!

The DSP Lab at Rice University have archived and update all the latest literature on compressed sensing. Visit them at: http://www.dsp.ece.rice.edu/cs/.

Advertisements

Written by sushilsub

May 16, 2009 at 2:59 pm

Posted in Blog Entries

Tagged with ,