# Can the Nyquist sample rate be extended to stochastic sampling?

It appears there are lots of questions here about Nyquist, and a few questions about stochastic sampling here. But I haven't found any that address quite what I'm after. This is the closest I've found here, and searching around has led me to some work on Compressed Sensing, but I have no idea how to navigate that field.

So there's the Nyquist sampling rate: given a signal composed of frequencies lower than $$F$$, Nyquist gives a lower bound on sampling frequency necessary to reconstruct the signal.

But I think that's usually applied when trying to find an appropriate fixed sample rate. So I'm curious if there is an extension to stochastic sampling: for the same signal as above, assume it is sampled such that the space between samples is distributed by Poisson $$\mathcal{P}(\lambda)$$ (or some other friendly distribution with parameters $$\theta$$.)

I'm hoping there exists a high probability bound on the ability to reconstruct the signal based on the sampling distribution.

Or, if signal reconstruction isn't well defined in this setting, perhaps there is an expression that can be derived that connects the source signal's frequency composition, the sampling distribution parameters, and the maximum mutual information between the source signal and the stochastically sampled signal.

But I have no idea if either actually exist. Can anyone help me figure this out?

• I think, as long the mean sampling frequency fulfills the Nyquist criteria, you're good to go. So, for well behaved distributions with known mean, you won't need any extra math, aside from the required special handling of the non-uniform samples themselves. – Max Jan 21 at 8:05
• And furthermore, what is "best case" and "worst case" would depend on the mean sampling rate versus the length of the acquired signal. Which implies that there might be isolated segments of the signal that have been sampled in the worst case and you would not be able to "observe" the frequencies of interest. @Max, do you think you could turn the comment into an answer so that we can close the question gracefully? – A_A Jan 21 at 9:52

As long the mean sampling frequency fulfills the Nyquist criteria, you're good to go. So, for well behaved distributions with known mean, you won't need any extra math, aside from the required special handling of the non-uniform samples themselves.

• This is a very nice result. Much simpler than I expected. Do you know of a source I could read that derives it and shows assumptions? – kdbanman Jan 21 at 19:59
• bayes.wustl.edu/glb/trans.pdf This should be a good read. – Max Jan 22 at 8:10
• A more extensive read would be Marvasti (ed), F. (2000). Nonuniform Sampling, Theory and Practice. New York: Kluwer Academic/Plenum Publishers. – Max Jan 22 at 8:28
• Those are both good resources to follow up with. I’m interested to see how the constraints are constructed on sampling (like total sampling time, nonuniformity properties). – kdbanman Jan 22 at 19:55