DSP is all about when you can approximate discrete systems with continuous ones and vice versa. Sampling theorems. Nyquist rates, Compressive sampling, nonuniform signal sampling, stochastic signal sampling etc.
There are a few ways to frame this. Traditionally we talk about Shannon sampling theorems, Nyquist rates and so on. To be frank, I haven’t actually read Shannon, because the setup is not useful for the types of problems I face in my work, although I’m sure it boils down to some very similar results.
The received-wisdom version of the Shannon theorem is that you can reconstruct a signal if you know it has frequencies in it that are “too high”. Specifically, if you sample a continuous time signal at intervals of \(T\) seconds, then you had better have no frequencies of period shorter than \(2T\). I’m playing fast-and-loose with definitions here - the spectrum here is the continuous Fourier spectrogram. If you do much non-trivial signal processing, (in my case I constantly need to do things like multiplying signals) it rapidly becomes impossible to maintain bounds on the support of the spectrogram (TODO explain this with diagrams)
This doesn’t tell us much about more bizarre nonuniform sampling regimes, mild violations of frequency constraints, or whether other sets of (perhaps more domain-appropriate) constraints on our signals will lead to a sensible reconstruction theory.
Let’s talk about the modern, abstract and fashionable Hilbert-space framing of this problem This way is general, and based on projections between Hilbert spaces. Nice works in this tradition are, e.g. [@VetterliSampling2002] that observes that you don’t care about Fourier spectrogram support, but rather the rate of degrees of freedom to construct a coherent sampling theory. Also accessible is [@UnserSampling2000], which constructs the problem of discretising signals as a minimal-loss projection/reconstruction problem.
More recently you have fancy persons such as Adcock and Hansen unifying compressed sensing and signal sampling [@AdcockGeneralized2014;@AdcockGeneralized2016] with more or less the same framework, so I’ll dive into their methods here.
- Garc02: Antonio G. García (2002) A Brief Walk Through Sampling Theory. In Advances in Imaging and Electron Physics (Vol. 124, pp. 63–137). Elsevier DOI
- Gröc93: Karlheinz Gröchenig (1993) A discrete theory of irregular sampling. Linear Algebra and Its Applications, 193, 129–150. DOI
- UnAl94: Michael Unser, Akram Aldroubi (1994) A general sampling theory for nonideal acquisition devices. IEEE Transactions on Signal Processing, 42(11), 2915–2925.
- GrLe04: L. Greengard, J. Lee (2004) Accelerating the Nonuniform Fast Fourier Transform. SIAM Review, 46(3), 443–454. DOI
- UnTa14: Michael A. Unser, Pouya Tafti (2014) An introduction to sparse stochastic processes. New York: Cambridge University Press
- PiPe04: Roberta Piroddi, Maria Petrou (2004) Analysis of Irregularly Sampled Data: A Review. In Advances in Imaging and Electron Physics (Vol. 132, pp. 109–165). Elsevier
- Broe06: Petrus MT Broersen (2006) Automatic autocorrelation and spectral analysis. Secaucus, NJ, USA: Springer Science & Business Media
- Mart98: R. J. Martin (1998) Autoregression and irregular sampling: Filtering. Signal Processing, 69(3), 229–248. DOI
- Mart99: R. J. Martin (1999) Autoregression and irregular sampling: Spectral estimation. Signal Processing, 77(2), 139–157. DOI
- BrWB04: Piet M. T. Broersen, Stijn de Waele, Robert Bos (2004) Autoregressive spectral analysis when observations are missing. Automatica, 40(9), 1495–1504. DOI
- MiEl09: M. Mishali, Y. C. Eldar (2009) Blind Multiband Signal Reconstruction: Compressed Sensing for Analog Signals. IEEE Transactions on Signal Processing, 57(3), 993–1009. DOI
- AmUM11: Arash Amini, Michael Unser, Farokh Marvasti (2011) Compressibility of deterministic and random infinite sequences. IEEE Transactions on Signal Processing, 59(11), 5193–5201.
- Stro97: T. Strohmer (1997) Computationally attractive reconstruction of bandlimited images from irregular samples. IEEE Transactions on Image Processing, 6(4), 540–548. DOI
- AmMa08: Arash Amini, Farokh Marvasti (2008) Convergence Analysis of an Iterative Method for the Reconstruction of Multi-Band Signals from their Uniform and Periodic Nonuniform Samples. Sampling Theory in Signal & Image Processing, 7(2).
- Star01: Jaroslav Stark (2001) Delay Reconstruction: Dynamics versus Statistics. In Nonlinear Dynamics and Statistics (pp. 81–103). Birkhäuser Boston DOI
- Smit18: Julius O. Smith (2018) Digital audio resampling home page. Center for Computer Research in Music and Acoustics (CCRMA), Stanford University
- Marp87: S. Lawrence Marple Jr. (1987) Digital spectral analysis with applications
- FeGS95: Hans G. Feichtinger, Karlheinz Gröchenig, Thomas Strohmer (1995) Efficient numerical methods in non-uniform sampling theory. Numerische Mathematik, 69(4), 423–440. DOI
- FeSt92: Hans G. Feichtinger, Thomas Strohmer (1992) Fast iterative reconstruction of band-limited images from non-uniform sampling values. In SpringerLink (Vol. 231, pp. 82–89). Springer Berlin Heidelberg DOI
- ElOp00: Y. C. Eldar, A. V. Oppenheim (2000) Filterbank reconstruction of bandlimited signals from nonuniform and generalized samples. IEEE Transactions on Signal Processing, 48(10), 2864–2875. DOI
- Unse95: Michael A. Unser (1995) General Hilbert space framework for the discretization of continuous signal processing operators. In Wavelet Applications in Signal and Image Processing III (Vol. 2569, pp. 51–62). International Society for Optics and Photonics
- AdHa16: Ben Adcock, Anders C. Hansen (2016) Generalized Sampling and Infinite-Dimensional Compressed Sensing. Foundations of Computational Mathematics, 16(5), 1263–1323. DOI
- AHRT14: Ben Adcock, Anders Hansen, Bogdan Roman, Gerd Teschke (2014) Generalized Sampling: Stable Reconstructions, Inverse Problems and Compressed Sensing over the Continuum. In Advances in Imaging and Electron Physics (Vol. 182, pp. 187–279). Elsevier DOI
- FeWe00: Hans G. Feichtinger, Thomas Werther (2000) Improved locality for irregular sampling algorithms. In IEEE International Conference on Acoustics, Speech, and Signal Processing, 2000. ICASSP ’00. Proceedings (Vol. 6, pp. 3834–3837 vol.6). DOI
- FeGr92: Hans G. Feichtinger, Karlheinz Gröchenig (1992) Iterative Reconstruction of Multivariate Band-Limited Functions from Irregular Sampling Values. SIAM Journal on Mathematical Analysis, 23(1), 244–261. DOI
- FeGr89: Hans G. Feichtinger, Karlheinz Gröchenig (1989) Multidimensional Irregular Sampling of Band-Limited Functions in Lp-Spaces. In Multivariate Approximation Theory IV (pp. 135–142). Birkhäuser Basel DOI
- Land67: H. J. Landau (1967) Necessary density conditions for sampling and interpolation of certain entire functions. Acta Mathematica, 117(1), 37–52.
- FeSu03: Jeffrey A. Fessler, Bradley P. Sutton (2003) Nonuniform Fast Fourier Transforms Using Min-Max Interpolation. IEEE Transactions on Signal Processing, 51(2). DOI
- MoHo14: Mehdi Mobli, Jeffrey C. Hoch (2014) Nonuniform sampling and non-Fourier signal processing methods in multidimensional NMR. Progress in Nuclear Magnetic Resonance Spectroscopy, 83, 21–41. DOI
- AlGr01: Akram Aldroubi, Karlheinz Gröchenig (2001) Nonuniform Sampling and Reconstruction in Shift-Invariant Spaces. SIAM Review, 43(4), 585–620. DOI
- YSSI09: Leonid P. Yaroslavsky, Gil Shabat, Benny G. Salomon, Ianir A. Ideses, Barak Fishbain (2009) Non-uniform sampling, image recovery from sparse data and the discrete sampling theorem. Journal of the Optical Society of America A, 26(3), 566. DOI
- MaEl08: E. Margolis, Y.C. Eldar (2008) Nonuniform Sampling of Periodic Bandlimited Signals. IEEE Transactions on Signal Processing, 56(7), 2728–2745. DOI
- Marv12: Farokh Marvasti (2012) Nonuniform Sampling: Theory and Practice. Springer Science & Business Media
- Yen56: J. Yen (1956) On Nonuniform Sampling of Bandwidth-Limited Signals. IRE Transactions on Circuit Theory, 3(4), 251–257. DOI
- Bart46: M. S. Bartlett (1946) On the Theoretical Specification and Sampling Properties of Autocorrelated Time-Series. Supplement to the Journal of the Royal Statistical Society, 8(1), 27–41. DOI
- MaCh90: F. A. Marvasti, L. Chuande (1990) Parseval relationship of nonuniform samples of one- and two-dimensional signals. IEEE Transactions on Acoustics, Speech, and Signal Processing, 38(6), 1061–1063. DOI
- VeBr00: R. Venkataramani, Y. Bresler (2000) Perfect reconstruction formulas and bounds on aliasing error in sub-Nyquist nonuniform sampling of multiband signals. IEEE Transactions on Information Theory, 46(6), 2173–2183. DOI
- KaBH06: Michael Kazhdan, Matthew Bolitho, Hugues Hoppe (2006) Poisson Surface Reconstruction. In SGP06: Eurographics Symposium on Geometry Processing (Vol. 1, p. 0). The Eurographics Association DOI
- UnAE92: M. Unser, A. Aldroubi, M. Eden (1992) Polynomial spline signal approximations: filter design and asymptotic equivalence with Shannon’s sampling theorem. IEEE Transactions on Information Theory, 38(1), 95–103. DOI
- UnAl92: Michael Unser, Akram Aldroubi (1992) Polynomial Splines and Wavelets-A Signal Processing Perspective. In Wavelets (Vol. 2, pp. 91–122). San Diego: Academic Press DOI
- Dumi17: Bogdan Dumitrescu (2017) Positive trigonometric polynomials and signal processing applications. Cham: Springer
- Gröc92: Karlheinz Gröchenig (1992) Reconstruction algorithms in irregular sampling. Mathematics of Computation, 59(199), 181–194. DOI
- MaAG91: F. Marvasti, M. Analoui, M. Gamshadzahi (1991) Recovery of signals from nonuniform samples using iterative methods. IEEE Transactions on Signal Processing, 39(4), 872–878. DOI
- Unse00: M. Unser (2000) Sampling: 50 years after Shannon. Proceedings of the IEEE, 88(4), 569–587. DOI
- VeMB02: M. Vetterli, P. Marziliano, T. Blu (2002) Sampling signals with finite rate of innovation. IEEE Transactions on Signal Processing, 50(6), 1417–1428. DOI
- StSa06: Petre Stoica, Niclas Sandgren (2006) Spectral Analysis of Irregularly-sampled Data: Paralleling the Regularly-sampled Data Approaches. Digit. Signal Process., 16(6), 712–734. DOI
- BaSt10: Prabhu Babu, Petre Stoica (2010) Spectral analysis of nonuniformly sampled data – a review. Digital Signal Processing, 20(2), 359–378. DOI
- TaAl04: A. Tarczynski, N. Allay (2004) Spectral analysis of randomly sampled signals: suppression of aliasing and sampler jitter. IEEE Transactions on Signal Processing, 52(12), 3324–3334. DOI
- BaBo99: Stefan Baisch, Götz H. R. Bokelmann (1999) Spectral analysis with incomplete time series: an example from seismology. Computers & Geosciences, 25(7), 739–750. DOI
- Unse99: M. Unser (1999) Splines: a perfect fit for signal and image processing. IEEE Signal Processing Magazine, 16(6), 22–38. DOI
- AdHR15: Ben Adcock, Anders C. Hansen, Bogdan Roman (2015) The Quest for Optimal Sampling: Computationally Efficient, Structure-Exploiting Measurements for Compressed Sensing. In Compressed Sensing and its Applications: MATHEON Workshop 2013 (pp. 143–167). Cham: Springer International Publishing DOI
- FeGr94: Hans G. Feichtinger, Karlheinz Gröchenig (1994) Theory and practice of irregular sampling. Wavelets: Mathematics and Applications, 1994, 305–363.
- Gray84: R. Gray (1984) Vector quantization. IEEE ASSP Magazine, 1(2), 4–29. DOI