What is meant by “stochastic sampling”?

What exactly is meant by "stochastic sampling" and is it profoundly different from the regular Nyquist-Shannon sampling theorem? Is it related to sampling a stochastic process?

Stochastic sampling doesn't have anything to do with sampling stochastic waveforms. It simply means that instead of sampling at regular intervals, the waveform is sampled randomly.

Recall that in a sampling scheme per the Nyquist-Shannon sampling theorem, a continuous signal $x(t)$ on $\mathbb{R}$ is sampled as $x[n]=x(nT),\ n\in\mathbb{Z}$, where $T$ is the sampling interval and $f_s=1/T$ is the sampling frequency. If the maximum frequency in the signal is $f_{max}$, then $f_s$ must be such that $f_s\geq 2f_{max}$ so as to avoid aliasing. For ease of comparison with stochastic sampling later on in the answer, let me redefine the sampling in a slightly different form than usual as

\begin{align} s(t)&=\sum_{n=0}^{f_s\tau -1}\delta(t-nT)\\ x[n]&=x(t)\cdot s(t) \end{align} where $\delta(t)$ is the Dirac delta function and $x(t)$ is only sampled on the interval $[0,\tau]$.

If you actually think about it, regular sampling is pretty limiting in practice. Aliasing crops up in several places, and probably a well known and visible effect is the Moiré patterns which can be reproduced at home by taking a photo of regular patterns displayed on a television (examples below).

However, this is always a problem with cameras, but never with your eyes if you were to see the pattern directly! The reason is because the photoreceptors in your retina are not laid out in a regular pattern unlike the CCD in a camera. The idea behind (not necessarily the idea that led to its development) stochastic sampling is very similar to the non-regular layout of photoreceptors in the eye. It is an anti-aliasing technique which works by breaking up the regularity in the sampling.

In stochastic sampling, every point in the signal has a non-zero probability of being sampled (unlike regular sampling where certain sections will never be sampled). A simple uniform stochastic sampling scheme can be implemented over the same interval $[0,\tau]$ as

\begin{align} s(t)&=\sum_{n=0}^{f_s \tau -1}\delta(t-t_n),\quad t_n\sim \mathcal{U}(0,\tau)\\ x[n]&=x(t)\cdot s(t) \end{align}

where $\mathcal{U}(0,\tau)$ is the uniform distribution on the interval $[0,\tau]$.

By sampling stochastically, there is no "Nyquist frequency" to talk about, so aliasing will no longer be a problem as before. However, this comes at a price. What you gain in anti-aliasing, you lose by noise in the system. The stochastic sampling introduces high-frequency noise, although for several applications (especially in imaging), aliasing is a much stronger nuisance than noise (e.g., you can see the Moiré patterns easily in the above images, but to a lesser extent the speckle noise).

As far as I know, stochastic sampling schemes are almost always used in spatial sampling (in image processing, computer graphics, array processing, etc.) and sampling in the time domain is still predominantly regular (I'm not sure if people even bother with stochastic sampling in the time domain). There are several different stochastic sampling schemes such as Poisson sampling, jittered sampling, etc., which you can look up if you're interested. For a general, low key introduction to the topic, see

M. A. Z. Dippé and E. H. Wold, "Antialiasing Through Stochastic Sampling", SIGGRAPH, Vol. 19, No. 5, pp. 69-78, 1985.

• There are some applications of stochastic sampling schemes in the time domain; random sampling intervals can be used in compressed sensing, although the technique is not universally applicable. – Jason R Aug 21 '11 at 18:28
• @JasonR Thanks. I am aware of the application in compressed sensing, but it works only because of the sparsity condition, which is why I didn't mention it. (besides, the examples I've seen in compressed sensing are also mostly with images/spatial sampling, but that could just be my bias from selective reading) – Lorem Ipsum Aug 21 '11 at 18:33
• could be improved of an example of an image that was extrapolated from stochastic sampling. – CyberMen May 29 '12 at 13:59