# Random sampling vs uniform sampling

In this paper of Lustig, he speaks about a something which appears unintuitive: sampling at random may exhibit better performance than sampling uniformly. I tried to understand this starting from page 15 of these slides, but I can't really make sense of anything.

Why, if we take random permutation of frequency coefficients, do we get a better reconstruction in terms of signal similarity? Why does this give better reconstruction, and what's the intuition behind the phenomenon?

• Not an expert at all in this field but, if the technique is based on CS, then reconstruction can be achieved with less samples than with uniform sampling, as a long as the data matrix is sparse. If you compare both systems at a given sampling rate, as you you need less samples with CS, then extra samples can be used to further increase performance. – vaz Apr 20 '16 at 13:41
• @vaz by CS I guess you mean compressed sensing (en.wikipedia.org/wiki/Compressed_sensing) – Olli Niemitalo Apr 20 '16 at 14:12
• @OlliNiemitalo Yes, sorry. The paper cited in the question is about compressed sensing. – vaz Apr 20 '16 at 14:35

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')