Compressed Sensing: Missing Fourier Coefficients?

Question

This question is regarding the problem of reconstructing a signal given only a subset of the Fourier coefficients are observed:

$$\min_x \|x\|_1 \text{ subject to } y = Ax$$

where $x = (x_1,x_2,\dots,x_t)$ is a time-domain representation of our signal of interest, $y$ are $m << t$ observed or known Fourier coefficients of $x$, and $A$ is the measurement matrix.

My question. In practice, how are certain Fourier coefficients randomly sampled? For example, how does one collect these $m$ coefficients from the spectrum of $x$ in a random uniform (unbiased) fashion?

Some Additional Elaboration. I imagine that, in an MRI scan for example (which is one of the popular applications of compressed sensing thanks to Candés), shortening the amount of time used to collect Fourier coefficients means that we can only accurately capture the higher frequency components of $x$. Contrarily, shortening the number of samples taken from the underlying signal (but keeping the time fixed) results in a lower-resolution signal that may only capture the low-frequency components of $x$. Both of these methods mean that the observed Fourier coefficients are not randomly distributed on the spectrum of $x$, but are in fact biased to one end or another. However, a key assumption of the $\ell_1$ reconstruction used in compressed sensing is that (in the domain for which the $x$ is sparse, in this case some over-complete dictionary), the sampling operator must procure elements in a random fashion and the subspace generating $x$ must be incoherent (uncorrelated with canonical axes).

Answer 1

I know this has been posted long time ago, but I though it might be still useful for some people. First, I am kind of surprised that no one has yet edited this question. I have just joined and due to low rating cannot do that. But, if you are talking about compressive sensing (CS), then x is the coefficients of your signal expansion in some basis, which is called representation basis, and the representation of the signal is supposed to be sparse in this basis. So, x can only be the time domain representation of your signal, if signal is sparse in the time domain, which is not the case in general. In fact, depending on your application, your representation basis can be wavelet, Fourier (like in MRI), curvelet, etc. y, on the other hand is the measurement of the signal in another basis, which we call sensing/measurement basis. The two basis (representation and measurement) have to be incoherent for a successful reconstruction of the signal. It turns out that random matrices are incoherent with fixed basis with high probability. This basically means, in order to reconstruct a sparse signal, you just need to take a few number of random measurements. CS also provides you with a lower bound for the number of measurements you need to make in order to be able to recover your signal. This number is of the order of S.log(n/S), where S is the number of non-zero elements of your signal in its sparse representation. Back to your question, you just need to take some random measurements, where each measurement provides you with some information about the whole signal, rather that just one of its basis function at a time. If you want to have a sense of it in an application, the single pixel camera in Rice university is a good one.

About MRI, compressive sensing doesn't shorten the time of taking each sample, it just gives you the ability to reconstruct a high quality image by taking only a few random measurements, where in common practice in MRI, you need to make way more samples to build a good quality image, and since each sample takes some time you have to spend a lot of time for capturing all of these samples. So, you are not taking some samples with a bias. Another point is that as I mentioned before, in each measurement, compressive sensing randomly collects some information about the whole signal, rather than only some particular coefficients (in your case at some specific frequency).

I hope this can be helpful.