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 <- 128
N <- 5
x <- rep(0, T)
x[sample(T,N)] <- rep(1,N)
X <- fft(x);
Xu <- rep(0, T)
Xu[seq(1,T,4)] <- X[seq(1,T,4)];
xu <- 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) & reconstructed\n from uniform undersampling (red)')
Xr <- rep(0,T)
r_ix <- sample(T,T/4)
Xr[r_ix] <- X[r_ix]
xr <- 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) & reconstructed\n from non-uniform undersampling (red)')
#soft thresh function
softThresh <- function(vals_to_threshold, lambda)
{
ix <- which(abs(vals_to_threshold) < lambda)
vals_to_threshold[ix] <- rep(0, length(ix))
ix <- which(vals_to_threshold >= lambda)
vals_to_threshold[ix] <- vals_to_threshold[ix] - lambda
ix <- which(vals_to_threshold <= -lambda)
vals_to_threshold[ix] <- vals_to_threshold[ix] + lambda
return(vals_to_threshold)
}
# POCS
lambda <- 0.1
Xhat <- Xr
for (iteration in seq(1,100))
{
# 1. Compute the inverse FT to get estimate
xhat <- Re(fft(Xhat, inverse = TRUE)/T)
# 2. Apply Softrhesh in the time domain
xhat <- softThresh(xhat, lambda)
# 3. Find the FFT
Xhat <- fft(xhat)
# 4. Enforce known values
Xhat[r_ix] <- X[r_ix]
}
plot(x, type="l", lwd = 5, ylim = c(0,1.2))
lines(xhat, col="red")
title('Reconstructed using POCS')