Compressive sensing

Wow, there are a lot of papers about it but when it comes to getting an intuitive idea of how it works all the magazine articles, online videos, and tutorial PDFs really suck :-)

Where did you start with the topic?

Alex

Quote:

Original post by redtea I've just found out about compressive sensing, there are a lot of papers about it here: Compressive Sensing Given a sparse array of data you take a snap shot of it with a few small random projections. Later you can recreate the sparse array exactly from the small random projections using a relatively simple minimization procedure.

I wonder how this compares with traditional sparse array techniques (say, for space efficiency). Any ideas?

-Will Dwinnell
Data Mining in MATLAB

When you are reconstructing the sparse array you try to do 2 things at the same time.
1/ You put the data from the reconstruction array through the same random projections as the data from the original array was put through and by adjusting the data in the reconstruction array you try to get the random projections to match those of the original array.
2/ You try to minimize the sum of the abs (ie sum of magnitudes) of the data in the reconstruction array.

In practice it is not very difficult to do both things. If you use the OCT to do the random projections then you can almost force a matching using the fact that OCT's are invertible.

What they mean by a sparse array in this case is an array of data with a lot of redundant information. For example a typical digital picture. Apparently compressive sensing gives compression almost as good as wavelets. Together with the error correction ability I think it is well worth persisting to find out what it is all about.

I guess the point is to do the compression in the original continuous domain rather than sampling to the discrete domain and compressing that. Maybe there's more to it that I'm missing but those 'tutorial' papers are inpenetrable to me.

I'd have to think about the theorem that they reference. Of the sources you cited the most comprehensible so far is this one (which you'd expect since it appeared in the IEEE Signal Processing Magazine rather than in a journal or at a conference.) If you've done some DSP it's not too difficult.

This blog spot seems to be one of the better places to start:

Nuit Blanche

If you quickly scan through some of papers on the subject they seem to be able to do some amazing things. If you can't understand the maths immediately anyway have a look at some of the pictures and results. This thing has emerged from the Digital Signal Processing (DSP) community and hence makes heavy use of their terminology and way of thinking.
I think it is pretty exciting but I do want to be able to implement the basic ideas in my own code. That will take some effort given the nature of the papers available.