Signal sampling

Discrete representation of continuous signals and converse



When we can approximate discrete systems with continuous ones and vice versa. Sampling theorems. Nyquist rates, Compressive sampling, nonuniform signal sampling, signatures of rough paths, etc.

TODO: just write this as a basis decomp.

There are a few ways to frame this. Traditionally in electrical engineering applications we talk about Shannon sampling theorems, Nyquist rates and so on. 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\).1 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 non-uniform 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.

More abstractly there is a 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. (Vetterli, Marziliano, and Blu 2002) 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 (M. Unser 2000), 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 (Adcock et al. 2014; Adcock and Hansen 2016) with more or less the same framework. Looks interesting.

Most of the above use some variant of minimum \(L_2\) norm error when reconstructing the signal. However, there are more reconstruction errors; for example I might wish to find some representation of a signal which is best with respect to some kind of transformation, e.g. in an inverse problem.

Or I might wish to sample a random signal, which is especially useful in functional Bayes inverse problems.

References

Adcock, Ben, and Anders C. Hansen. 2016. β€œGeneralized Sampling and Infinite-Dimensional Compressed Sensing.” Foundations of Computational Mathematics 16 (5): 1263–323.
Adcock, Ben, Anders C. Hansen, and 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, edited by Holger Boche, Robert Calderbank, Gitta Kutyniok, and Jan VybΓ­ral, 143–67. Applied and Numerical Harmonic Analysis. Cham: Springer International Publishing.
Adcock, Ben, Anders Hansen, Bogdan Roman, and Gerd Teschke. 2014. β€œGeneralized Sampling: Stable Reconstructions, Inverse Problems and Compressed Sensing over the Continuum.” In Advances in Imaging and Electron Physics, edited by Peter W. Hawkes, 182:187–279. Elsevier.
Aldroubi, Akram, and Karlheinz GrΓΆchenig. 2001. β€œNonuniform Sampling and Reconstruction in Shift-Invariant Spaces.” SIAM Review 43 (4): 585–620.
Amini, Arash, and 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).
Babu, Prabhu, and Petre Stoica. 2010. β€œSpectral Analysis of Nonuniformly Sampled Data – a Review.” Digital Signal Processing 20 (2): 359–78.
Baisch, Stefan, and GΓΆtz H. R. Bokelmann. 1999. β€œSpectral Analysis with Incomplete Time Series: An Example from Seismology.” Computers & Geosciences 25 (7): 739–50.
Bartlett, M. S. 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.
Borcea, Liliana, Vladimir Druskin, and Leonid Knizhnerman. 2005. β€œOn the Continuum Limit of a Discrete Inverse Spectral Problem on Optimal Finite Difference Grids.” Communications on Pure and Applied Mathematics 58 (9): 1231–79.
Bostan, E., U. S. Kamilov, M. Nilchian, and M. Unser. 2013. β€œSparse Stochastic Processes and Discretization of Linear Inverse Problems.” IEEE Transactions on Image Processing 22 (7): 2699–2710.
BrΓ©maud, Pierre, Laurent MassouliΓ©, and Andrea Ridolfi. 2005. β€œPower Spectra of Random Spike Fields and Related Processes.” Advances in Applied Probability 37 (4): 1116–46.
BretΓ³, Carles, Daihai He, Edward L. Ionides, and Aaron A. King. 2009. β€œTime Series Analysis via Mechanistic Models.” The Annals of Applied Statistics 3 (1): 319–48.
Broersen, P. M. T., and R. Bos. 2006. β€œEstimating Time-Series Models from Irregularly Spaced Data.” In IEEE Transactions on Instrumentation and Measurement, 55:1124–31.
Broersen, Petrus MT. 2006. Automatic Autocorrelation and Spectral Analysis. Secaucus, NJ, USA: Springer.
Broersen, Piet M. T. 2005. β€œTime Series Analysis for Irregularly Sampled Data.” IFAC Proceedings Volumes, 16th IFAC World Congress, 38 (1): 154–59.
Broersen, Piet M. T., Stijn de Waele, and Robert Bos. 2004. β€œAutoregressive Spectral Analysis When Observations Are Missing.” Automatica 40 (9): 1495–1504.
Bui-Thanh, Tan, and Quoc P. Nguyen. 2016. β€œFEM-Based Discretization-Invariant MCMC Methods for PDE-Constrained Bayesian Inverse Problems.” Inverse Problems & Imaging 10 (4): 943.
Cauchemez, Simon, and Neil M. Ferguson. 2008. β€œLikelihood-Based Estimation of Continuous-Time Epidemic Models from Time-Series Data: Application to Measles Transmission in London.” Journal of The Royal Society Interface 5 (25): 885–97.
Cochran, W.T., James W. Cooley, D.L. Favin, H.D. Helms, R.A. Kaenel, W.W. Lang, Jr. Maling G.C., D.E. Nelson, C.M. Rader, and Peter D. Welch. 1967. β€œWhat Is the Fast Fourier Transform?” Proceedings of the IEEE 55 (10): 1664–74.
Coulaud, Benjamin, and FrΓ©dΓ©ric JP Richard. 2018. β€œA Consistent Framework for a Statistical Analysis of Surfaces Based on Generalized Stochastic Processes.”
D’Ambrogi, Barbara, Sari MΓ€enpÀÀ, and Markku Markkanen. 1999. β€œDiscretization Independent Retrieval of Atmospheric Ozone Profile.” Geophysica 35 (1-2): 87–99.
Dumitrescu, Bogdan. 2017. Positive trigonometric polynomials and signal processing applications. Second edition. Signals and communication technology. Cham: Springer.
Eldar, Y. C., and A. V. Oppenheim. 2000. β€œFilterbank Reconstruction of Bandlimited Signals from Nonuniform and Generalized Samples.” IEEE Transactions on Signal Processing 48 (10): 2864–75.
Feichtinger, Hans G., and Karlheinz GrΓΆchenig. 1989. β€œMultidimensional Irregular Sampling of Band-Limited Functions in Lp-Spaces.” In Multivariate Approximation Theory IV, 135–42. International Series of Numerical Mathematics / Internationale Schriftenreihe Zur Numerischen Mathematik / SΓ©rie Internationale d’Analyse NumΓ©rique. BirkhΓ€user Basel.
β€”β€”β€”. 1992. β€œIterative Reconstruction of Multivariate Band-Limited Functions from Irregular Sampling Values.” SIAM Journal on Mathematical Analysis 23 (1): 244–61.
β€”β€”β€”. 1994. β€œTheory and Practice of Irregular Sampling.” Wavelets: Mathematics and Applications 1994: 305–63.
Feichtinger, Hans G., Karlheinz GrΓΆchenig, and Thomas Strohmer. 1995. β€œEfficient Numerical Methods in Non-Uniform Sampling Theory.” Numerische Mathematik 69 (4): 423–40.
Feichtinger, Hans G., and Thomas Strohmer. 1992. β€œFast Iterative Reconstruction of Band-Limited Images from Non-Uniform Sampling Values.” In SpringerLink, 231:82–89. Springer Berlin Heidelberg.
Feichtinger, Hans G., and Thomas Werther. 2000. β€œImproved Locality for Irregular Sampling Algorithms.” In IEEE International Conference on Acoustics, Speech, and Signal Processing, 2000. ICASSP ’00. Proceedings, 6:3834–3837 vol.6.
Fessler, Jeffrey A., and Bradley P. Sutton. 2003. β€œNonuniform Fast Fourier Transforms Using Min-Max Interpolation.” IEEE Transactions on Signal Processing 51 (2).
Finzi, Marc, Roberto Bondesan, and Max Welling. 2020. β€œProbabilistic Numeric Convolutional Neural Networks.” arXiv:2010.10876 [Cs], October.
GarcΓ­a, Antonio G. 2002. β€œA Brief Walk Through Sampling Theory.” In Advances in Imaging and Electron Physics, edited by Peter W. Hawkes, 124:63–137. Elsevier.
Gray, R. 1984. β€œVector Quantization.” IEEE ASSP Magazine 1 (2): 4–29.
Greengard, L., and J. Lee. 2004. β€œAccelerating the Nonuniform Fast Fourier Transform.” SIAM Review 46 (3): 443–54.
GrΓΆchenig, Karlheinz. 1992. β€œReconstruction Algorithms in Irregular Sampling.” Mathematics of Computation 59 (199): 181–94.
β€”β€”β€”. 1993. β€œA Discrete Theory of Irregular Sampling.” Linear Algebra and Its Applications 193 (November): 129–50.
Jones, Richard H. 1981. β€œFitting a Continuous Time Autoregression to Discrete Data.” In Applied Time Series Analysis II, 651–82.
β€”β€”β€”. 1984. β€œFitting Multivariate Models to Unequally Spaced Data.” In Time Series Analysis of Irregularly Observed Data, 158–88. Springer.
Kazhdan, Michael, Matthew Bolitho, and Hugues Hoppe. 2006. β€œPoisson Surface Reconstruction.” In Sgp06: Eurographics Symposium on Geometry Processing, 1:0. The Eurographics Association.
Lahalle, E., G. Fleury, and A. Rivoira. 2004. β€œContinuous ARMA Spectral Estimation from Irregularly Sampled Observations.” In Proceedings of the 21st IEEE Instrumentation and Measurement Technology Conference, 2004. IMTC 04, 2:923–927 Vol.2.
Landau, H. J. 1967. β€œNecessary Density Conditions for Sampling and Interpolation of Certain Entire Functions.” Acta Mathematica 117 (1): 37–52.
Larsson, Erik K., and Torsten SΓΆderstrΓΆm. 2002. β€œIdentification of Continuous-Time AR Processes from Unevenly Sampled Data.” Automatica 38 (4): 709–18.
Lasanen, Sari. 2002. β€œDiscretizations of Generalized Random Variables with Applications to Inverse Problems.”
Lassas, Matti, Eero Saksman, and Samuli Siltanen. 2009. β€œDiscretization-Invariant Bayesian Inversion and Besov Space Priors.” Inverse Problems and Imaging 3 (1): 87–122.
Lii, Keh-Shin, and Elias Masry. 1992. β€œModel Fitting for Continuous-Time Stationary Processes from Discrete-Time Data.” Journal of Multivariate Analysis 41 (1): 56–79.
Luschgy, H. 1996. β€œLinear Estimators and Radonifying Operators.” Theory of Probability & Its Applications 40 (1): 167–75.
Mandelbaum, Avi. 1984. β€œLinear Estimators and Measurable Linear Transformations on a Hilbert Space.” Zeitschrift FΓΌr Wahrscheinlichkeitstheorie Und Verwandte Gebiete 65 (3): 385–97.
Maravic, I., and M. Vetterli. 2005. β€œSampling and Reconstruction of Signals with Finite Rate of Innovation in the Presence of Noise.” IEEE Transactions on Signal Processing 53 (8): 2788–2805.
Margolis, E., and Y.C. Eldar. 2008. β€œNonuniform Sampling of Periodic Bandlimited Signals.” IEEE Transactions on Signal Processing 56 (7): 2728–45.
Marple, S. Lawrence, Jr. 1987. Digital Spectral Analysis with Applications.
Martin, R. J. 1998. β€œAutoregression and Irregular Sampling: Filtering.” Signal Processing 69 (3): 229–48.
β€”β€”β€”. 1999. β€œAutoregression and Irregular Sampling: Spectral Estimation.” Signal Processing 77 (2): 139–57.
Marvasti, F. A., and 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–63.
Marvasti, F., M. Analoui, and M. Gamshadzahi. 1991. β€œRecovery of Signals from Nonuniform Samples Using Iterative Methods.” IEEE Transactions on Signal Processing 39 (4): 872–78.
Marvasti, Farokh. 2012. Nonuniform Sampling: Theory and Practice. Springer Science & Business Media.
Marziliano, P., M. Vetterli, and T. Blu. 2006. β€œSampling and Exact Reconstruction of Bandlimited Signals with Additive Shot Noise.” IEEE Transactions on Information Theory 52 (5): 2230–33.
Matheron, G. 1973. β€œThe Intrinsic Random Functions and Their Applications.” Advances in Applied Probability 5 (3): 439–68.
McCrorie, J. Roderick. 2002. β€œThe Likelihood of the Parameters of a Continuous Time Vector Autoregressive Model.” Statistical Inference for Stochastic Processes 5 (3): 273–86.
Mishali, M., and Y. C. Eldar. 2009. β€œBlind Multiband Signal Reconstruction: Compressed Sensing for Analog Signals.” IEEE Transactions on Signal Processing 57 (3): 993–1009.
Mishali, Moshe, and Yonina C. Eldar. 2010. β€œFrom Theory to Practice: Sub-Nyquist Sampling of Sparse Wideband Analog Signals.” IEEE Journal of Selected Topics in Signal Processing 4 (2): 375–91.
Mobli, Mehdi, and Jeffrey C. Hoch. 2014. β€œNonuniform Sampling and Non-Fourier Signal Processing Methods in Multidimensional NMR.” Progress in Nuclear Magnetic Resonance Spectroscopy 83 (November): 21–41.
Murray-Smith, Roderick, and Barak A. Pearlmutter. 2005. β€œTransformations of Gaussian Process Priors.” In Deterministic and Statistical Methods in Machine Learning, edited by Joab Winkler, Mahesan Niranjan, and Neil Lawrence, 110–23. Lecture Notes in Computer Science. Springer Berlin Heidelberg.
NiinimΓ€ki, K., S. Siltanen, and V. Kolehmainen. 2007. β€œBayesian multiresolution method for local tomography in dental x-ray imaging.” Physics in Medicine and Biology 52 (22): 6663–78.
O’Callaghan, Simon Timothy, and Fabio T. Ramos. 2011. β€œContinuous Occupancy Mapping with Integral Kernels.” In Twenty-Fifth AAAI Conference on Artificial Intelligence.
Papavasiliou, Anastasia, and Kasia B. Taylor. 2016. β€œApproximate Likelihood Construction for Rough Differential Equations.” arXiv:1612.02536 [Math, Stat], December.
Petra, Noemi, James Martin, Georg Stadler, and Omar Ghattas. 2014. β€œA Computational Framework for Infinite-Dimensional Bayesian Inverse Problems, Part II: Stochastic Newton MCMC with Application to Ice Sheet Flow Inverse Problems.” SIAM Journal on Scientific Computing 36 (4): A1525–55.
Pikkarainen, Hanna Katriina. 2006. β€œState Estimation Approach to Nonstationary Inverse Problems: Discretization Error and Filtering Problem.” Inverse Problems 22 (1): 365–79.
Piroddi, Roberta, and Maria Petrou. 2004. β€œAnalysis of Irregularly Sampled Data: A Review.” In Advances in Imaging and Electron Physics, 132:109–65. Advances in Imaging and Electron Physics. Elsevier.
SΓ€rkkΓ€, Simo. 2007. β€œOn Unscented Kalman Filtering for State Estimation of Continuous-Time Nonlinear Systems.” IEEE Transactions on Automatic Control 52 (9): 1631–41.
Scargle, Jeffrey D. 1981. β€œStudies in Astronomical Time Series Analysis. I-Modeling Random Processes in the Time Domain.” The Astrophysical Journal Supplement Series 45: 1–71.
Smith, Julius O. 2018. β€œDigital Audio Resampling Home Page.” Center for Computer Research in Music and Acoustics (CCRMA), Stanford University.
SΓΆderstrΓΆm, T., and M. Mossberg. 2000. β€œPerformance evaluation of methods for identifying continuous-time autoregressive processes.” Automatica 1 (36): 53–59.
Stark, Jaroslav. 2001. β€œDelay Reconstruction: Dynamics Versus Statistics.” In Nonlinear Dynamics and Statistics, edited by Alistair I. Mees, 81–103. BirkhΓ€user Boston.
Stoica, Petre, and Niclas Sandgren. 2006. β€œSpectral Analysis of Irregularly-Sampled Data: Paralleling the Regularly-Sampled Data Approaches.” Digit. Signal Process. 16 (6): 712–34.
Strohmer, T. 1997. β€œComputationally Attractive Reconstruction of Bandlimited Images from Irregular Samples.” IEEE Transactions on Image Processing 6 (4): 540–48.
Sun, Qiyu, and Michael Unser. 2012. β€œLeft-Inverses of Fractional Laplacian and Sparse Stochastic Processes.” Advances in Computational Mathematics 36 (3): 399–441.
Tan, V. Y. F., and V. K. Goyal. 2008. β€œEstimating Signals With Finite Rate of Innovation From Noisy Samples: A Stochastic Algorithm.” IEEE Transactions on Signal Processing 56 (10): 5135–46.
Tarczynski, A., and N. Allay. 2004. β€œSpectral Analysis of Randomly Sampled Signals: Suppression of Aliasing and Sampler Jitter.” IEEE Transactions on Signal Processing 52 (12): 3324–34.
Tobar, Felipe. 2019. β€œBand-Limited Gaussian Processes: The Sinc Kernel.” Advances in Neural Information Processing Systems 32: 12749–59.
Tropp, J., J.N. Laska, M.F. Duarte, J.K. Romberg, and R.G. Baraniuk. 2010. β€œBeyond Nyquist: Efficient Sampling of Bandlimited Signals.” IEEE Transactions on Information Theory 56: 1–26.
Unser, M. 1999. β€œSplines: A Perfect Fit for Signal and Image Processing.” IEEE Signal Processing Magazine 16 (6): 22–38.
β€”β€”β€”. 2000. β€œSampling: 50 Years After Shannon.” Proceedings of the IEEE 88 (4): 569–87.
β€”β€”β€”. 2015. β€œSampling and (Sparse) Stochastic Processes: A Tale of Splines and Innovation.” In 2015 International Conference on Sampling Theory and Applications (SampTA), 221–25.
Unser, M., A. Aldroubi, and 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.
Unser, Michael A. 1995. β€œGeneral Hilbert Space Framework for the Discretization of Continuous Signal Processing Operators.” In Wavelet Applications in Signal and Image Processing III, 2569:51–62. International Society for Optics and Photonics.
Unser, Michael A., and Pouya Tafti. 2014. An Introduction to Sparse Stochastic Processes. New York: Cambridge University Press.
Unser, Michael, and Akram Aldroubi. 1992. β€œPolynomial Splines and Wavelets-A Signal Processing Perspective.” In Wavelets, edited by Charles K Chui, 2:91–122. Wavelet Analysis and Its Applications. San Diego: Academic Press.
β€”β€”β€”. 1994. β€œA General Sampling Theory for Nonideal Acquisition Devices.” IEEE Transactions on Signal Processing 42 (11): 2915–25.
Unser, M., P. D. Tafti, A. Amini, and H. Kirshner. 2014. β€œA Unified Formulation of Gaussian Vs Sparse Stochastic Processes - Part II: Discrete-Domain Theory.” IEEE Transactions on Information Theory 60 (5): 3036–51.
Unser, M., P. D. Tafti, and Q. Sun. 2014. β€œA Unified Formulation of Gaussian Vs Sparse Stochastic Processesβ€”Part I: Continuous-Domain Theory.” IEEE Transactions on Information Theory 60 (3): 1945–62.
Venkataramani, R., and 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–83.
Vetterli, M., P. Marziliano, and T. Blu. 2002. β€œSampling Signals with Finite Rate of Innovation.” IEEE Transactions on Signal Processing 50 (6): 1417–28.
Wolfe, Stephen James. 1982. β€œOn a Continuous Analogue of the Stochastic Difference Equation Xn=[rho]Xn-1+Bn.” Stochastic Processes and Their Applications 12 (3): 301–12.
Yadrenko, Mikhail Iosifovich. 1983. Spectral theory of random fields. Translation series in mathematics and engineering. New York, NY: Optimization Software.
Yaglom, A. M. 1987. Correlation Theory of Stationary and Related Random Functions. Volume II: Supplementary Notes and References. Springer Series in Statistics. New York, NY: Springer Science & Business Media.
Yaroslavsky, Leonid P., Gil Shabat, Benny G. Salomon, Ianir A. Ideses, and 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.
Yen, J. 1956. β€œOn Nonuniform Sampling of Bandwidth-Limited Signals.” IRE Transactions on Circuit Theory 3 (4): 251–57.

  1. I’m playing fast-and-loose with definitions here β€” the spectrum in this context is the continuous Fourier spectrogram.β†©οΈŽ


No comments yet. Why not leave one?

GitHub-flavored Markdown & a sane subset of HTML is supported.