I'm trying to wrap my head around compressed sensing, so I've been reading this intro to the topic.

I'm completely keeping up when they discuss exploiting the sparsity of a signal in some domain to compress it. I also think I get why you'd want to choose a sensing matrix that is incoherent with the basis in which your signal is sparse.

The point where my understanding breaks down is the "Undersampling and Sparse Signal Recovery" section.

Concretely, let's say I have a signal f of length n. I have a sensing matrix which is incoherent with the basis in which f is sparse that is m x n, and m < n.

If I understand correctly, I'm supposed to measure the signal by taking its inner product with each row of my sensing matrix, so I'll end up with samples of length m.

As I understand it, compressed sensing is useful in cases when sampling at the Nyquist/Shannon frequency is prohibitively expensive or slow. I must be missing something really fundamental, but didn't I have to do the work to acquire all samples of f so that it could be correlated with my sensing matrix? As I understand it, I've compressed the data now, which is great, but I didn't save any energy in the acquisition process.

  • $\begingroup$ This was also the paper I started with, it was very informative! $\endgroup$
    – Eric
    Commented Oct 13, 2012 at 20:21
  • $\begingroup$ This tutorial is very easy to understand for all beginner out there youtube.com/watch?v=RvMgVv-xZhQ $\endgroup$
    – MimSaad
    Commented Oct 23, 2020 at 11:09

1 Answer 1


Just to restate everything for clarity, the Compressed Sensing problem is defined as the following: given a signal $x$ of length $N$, we measure the projection of $x$ by some projection operator, $\Phi$ of size $M \times N$,

$$ y = \Phi x,$$

where $y$ is are our $M$ measurements of the original signal. We could also state this in terms of the inner products of $x$ with the rows of $\Phi$,

$$ y_i = \left< \phi_i, x\right>.$$

In the CS sampling procedure we have an inherent dimensionality reduction since we are taking a projection of $x$. The degree of this dimensionality reduction is usually referred to in terms of the ratio $\frac{M}{N}$ (aka the subsampling ratio or "Subrate"). By obtaining $y$ during acquisition we are simultaneously performing acquisition and dimensionality-reduction rather than full-resolution sampling followed by compression (DCT, DWT, etc.). The measurements $y$ are read off of the sensor, quantized (still an open problem, but decent results can be obtained through simple scalar quantization. See Laska's dissertation for more novel approaches), entropy coded (pick your flavor), and then transmitted or stored.

You touch on a good key point when it comes to CS signal acquisition, namely, if the calculation of this projection is costly then the advantage of CS for acquisition systems would appear small. However, depending on the context and type of signal, such projections can be accomplished in the analog domain (requiring no computation). The single-pixel camera (SPC) is a great example of this.

Single Pixel Camera

Researchers have also been able to greatly reduce sampling times for MRI using CS techniques. Specifically, conventional MRI techniques sample along different radial lines within the frequency domain. Each radial line is a measurement of the MRI device requiring some sampling time. Traditionally, for higher resolution MRI, more radial lines must be acquired, incurring longer acquisition time (problematic for the MRI of small children). However, this process can also be characterized as linear projections within the frequency domain. Because of this, CS techniques can be used to recover MRI images from many fewer measurements, allowing for high resolution MRI with much shorter MRI appointments. This was, in fact, the context in which CS was first applied. For more info, this paper by Lustig et al might be a good starting point.

In summation, the usefulness of CS to a particular context really depends on how you implement the projection. Getting it right can require some out-of-the-box thinking to come up with a novel sensing strategy. Thankfully, frameworks such as the SPC are generalizeable to a wide range of different signal contexts, so we don't have to re-invent the wheel every time.

  • $\begingroup$ Thanks @Eric, this is a really great answer! All of the applications of CS that you've mentioned seem to be for things that are static, e.g., a still image or a human body (provided it doesn't wiggle!). Are there any applications of CS to time-varying signals, e.g., audio? Designing a sensor for signals of that nature seems kind of brain-bending and maybe impossible. $\endgroup$ Commented Oct 13, 2012 at 20:36
  • $\begingroup$ @JohnVinyard Actually, yes. Take a look at Analog to Information Conversion for CS on continuous time signals. Additionally, there actually a number of papers on CS & video acquisition. There are some caveats and trade-offs, of course. Check out Chapter 4 & 5 of BCS of Images and Video and also CS-MUVI. $\endgroup$
    – Eric
    Commented Oct 13, 2012 at 23:08
  • $\begingroup$ @JohnVinyard Additional note, for some reason our department's web service is bonkered today. Give the BCS of Images and Video link some time to get sorted out. $\endgroup$
    – Eric
    Commented Oct 13, 2012 at 23:10
  • $\begingroup$ @JohnVinyard: The cochlea converts audio into a frequency-domain representation (where most sounds are sparse) before measuring it. I wonder if it only sends the strongest frequencies to the brain for processing, making it a form of compressive sensing and that's why we have things like auditory masking. (huh: web.mit.edu/newsoffice/2009/bio-electronics-0603.html) $\endgroup$
    – endolith
    Commented Oct 14, 2012 at 1:43
  • $\begingroup$ @JohnVinyard in this same paper they state: "if the signal is sufficiently sparse, exact recovery occurs" (i.e. by solving the L1-norm minimization). BUT what if the signal is not sparse... is the result completely unknown/structured. I'm trying to understand what might happen in this case. $\endgroup$
    – val
    Commented Feb 14, 2014 at 3:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.