Random sampling vs uniform sampling
The key idea is that the random sampling approach enforces more constraints on the resulting signal than the uniform sampling approach does.

The POCS (projections onto convex sets) algorithm used for the reconstruction of the randomly sampled signal is the key piece: it enforces:


That the signal must be from this spectrum.
That the signal is real-valued.
What we know about the signal's spectrum (the randomly sampled Fourier coefficients).
What we know about the signal's time-domain form.


The uniform sampling approach makes no attempt to enforce the bold constraint.

Here's an example which shows:


Top left: Uniform undersampling and reconstruction using the FFT only.
Top right: Random undersampling and reconstruction using the FFT only.
Bottom left: Reconstruction using POCS


As you can see, that final constrain really improves the reconstruction hugely.





R Code Below

#30219

T &lt;- 128
N &lt;- 5

x &lt;- rep(0, T)
x[sample(T,N)] &lt;- rep(1,N)

X &lt;- fft(x);
Xu &lt;- rep(0, T)
Xu[seq(1,T,4)] &lt;- X[seq(1,T,4)];
xu &lt;- fft(Xu, inverse = TRUE)*4/T;

par(mfrow=c(2,2))
plot(x, type="l", lwd = 5, ylim = c(0,1.2))
lines(abs(xu), col="red")
title('Original (black) &amp; reconstructed\n from uniform undersampling (red)')

Xr &lt;- rep(0,T)
r_ix &lt;- sample(T,T/4)
Xr[r_ix] &lt;- X[r_ix]
xr &lt;- fft(Xr, inverse = TRUE)*4/T

plot(x, type="l", lwd = 5, ylim = c(0,1.2))
lines(abs(xr), col="red")
#lines(Re(xr), col="blue")
#lines(Im(xr), col="green")
title('Original (black) &amp; reconstructed\n from non-uniform undersampling (red)')

#soft thresh function

softThresh &lt;- function(vals_to_threshold, lambda)
{
  ix &lt;- which(abs(vals_to_threshold) &lt; lambda)
  vals_to_threshold[ix] &lt;- rep(0, length(ix))

  ix &lt;- which(vals_to_threshold &gt;= lambda)
  vals_to_threshold[ix] &lt;- vals_to_threshold[ix] - lambda

  ix &lt;- which(vals_to_threshold &lt;= -lambda)
  vals_to_threshold[ix] &lt;- vals_to_threshold[ix] + lambda

  return(vals_to_threshold)
}

# POCS
lambda &lt;- 0.1
Xhat &lt;- Xr
for (iteration in seq(1,100))
{
  # 1. Compute the inverse FT to get estimate
  xhat &lt;- Re(fft(Xhat, inverse = TRUE)/T)
  # 2. Apply Softrhesh in the time domain
  xhat &lt;- softThresh(xhat, lambda)
  # 3. Find the FFT
  Xhat &lt;- fft(xhat)
  # 4. Enforce known values
  Xhat[r_ix] &lt;- X[r_ix]
}

plot(x, type="l", lwd = 5, ylim = c(0,1.2))
lines(xhat, col="red")
title('Reconstructed using POCS')