Recovering a signal from too few samples

A signal with 128 values needs 128 numbers to pin it down. That is the ordinary rule of counting, and for most signals it is the end of the story. But if you already know that almost every value is zero, you can often recover the whole signal, exactly, from far fewer measurements. The catch is in that “if”.

A picture rebuilt from a star of samples

In 2004 Emmanuel Candes, Justin Romberg and Terence Tao reported an experiment they called puzzling. They took a standard test image, the Logan-Shepp phantom, and kept only part of its Fourier transform: “512 samples along each of 22 radial lines” through the frequency plane. Filling every missing frequency with zero gave a picture full of artefacts. Instead they searched for the image with the smallest total variation, the sum of the jumps between neighbouring pixels, that still matched every sample they had kept. “The reconstruction is exact,” they wrote. By their account the samples came at a rate “almost 50 times smaller than the Nyquist rate”, the rate the usual theory asks for, and they got the same perfect result on many similar test phantoms.

Why that should be impossible

A signal of length N has N unknowns. Measure fewer than N of its frequencies and infinitely many signals agree with what you measured. Zero-fill picks the one with the least energy, which is why it smears. What rescues the phantom is that it is simple: flat regions with a few sharp edges, so its jumps are few. Mousavi, Rezaee and Ayanzadeh's survey puts the promise of the field carefully: compressive sensing samples sparse signals below the Nyquist-Shannon rate. Sparse means that, in some basis, almost all the coefficients are zero.

Count the spikes, not the samples

Candes, Romberg and Tao make this exact in one dimension. Their signal is a set of T spikes, and they observe its Fourier coefficients on a set of frequencies Ω. Their Theorem 1.1, for a prime length, says that if a signal has no more than half as many spikes as there are observed frequencies, no other signal that sparse fits the same data. So the information is there. Finding it directly means testing every possible set of spike positions, and the survey notes that the problem is NP-hard.

The trick is to change the question. Among all signals that fit the measurements, pick the one whose absolute values add up to the least. That is the L1 norm, and minimising it is a convex problem that a linear program solves. The paper's key result is that this cheap answer and the spike-counting answer agree “for an overwhelming percentage” of choices, as long as the number of spikes is at most a constant times the number of frequencies divided by the logarithm of N. Theorem 1.3 states it as a probability: at least 1 − O(N^−M) when the frequencies are picked at random.

How many is few enough

The theorem's constant is small; they give α(M) as about 1/[29.6(M+1)]. Their experiments are kinder. With N = 512 and 100 trials per setting, they report that once at least 32 frequencies are kept, a signal with at most a fifth as many spikes as frequencies is recovered perfectly about 80% of the time, and at an eighth the rate is practically 100%. The widget's version is smaller, 128 real-valued slots, and you can count its successes yourself. For a real signal a frequency and its mirror image carry the same information, so its 20 frequencies are 40 measured numbers and, in the paper's counting, 40 observed coefficients. With 100 draws each, L1 is exact in all 100 at 5 spikes (an eighth), in 98 at 8 (a fifth), in 90 at 10 (a quarter), in 9 at 16 and in none at 20 or more (our arithmetic, from the widget's own code). At this size the widget does at least as well as the paper's landmarks. Recovery does not fade gently; it falls off a cliff as the spikes outgrow the measurements.

Two ways to break it

The first is to give up sparsity. Push the spike slider to 128 and every slot is nonzero; with all 63 frequencies measured, 126 numbers for 128 unknowns, L1 is exact in none of 100 draws. With the same 126 numbers it is exact in all 100 at 84 spikes and in about 82 of 100 at 100 spikes (our arithmetic; the count can differ by one between browsers): what fails at 128 is not the number of measurements but the sparsity. The second is to sample in a pattern. The paper's Dirac comb is a row of equally spaced spikes whose spectrum is another comb. In the widget, 16 spikes 8 slots apart have, among frequencies 1 to 63, energy only at 16, 32 and 48. Measure all the rest, 60 of 63, and every measurement reads zero; no method can tell that signal from silence. The same comb measured at 60 random frequencies is recovered exactly in about 95 of 100 draws (our arithmetic). This is why the theorem insists on random frequencies. The paper closes by noting that for other pairs of bases, the number of samples needed depends on how incoherent the two bases are: the more incoherent, the fewer needed. The survey makes that a number, the mutual coherence, the largest correlation between two columns of the measurement matrix.

What stays true in practice

Real signals are rarely spikes, but the survey says signals across a wide range of applications are observed to be sparse, “possibly after a change of basis”. The phantom is an example: its pixels are not sparse, but its jumps are. Minimising total variation is the L1 idea applied to differences between neighbours. With noise in the measurements the answer is no longer exact; the survey's Theorem 3.5 bounds how far it can land from the truth instead.

In short

Fewer measurements than unknowns can pin a signal down exactly when two things hold: the signal is sparse in some basis you know, and the measurements are spread out enough to see every part of it. Then the smallest-L1 signal that fits the data is the right one. Take away either condition and the recovery fails.