Non-uniform signal sampling

Discrete sample representation of continuous signals without a grid

January 8, 2019 — August 8, 2023

dynamical systems
Hilbert space
signal processing
statistics
time series
Figure 1

Signal sampling without a uniform grid and thus a simple Nyquist Theorem. It turns out that this generalisation is not necessarily fatal for the theory.

There are reviews in a functional analysis setting (Piroddi and Petrou 2004; Babu and Stoica 2010; Unser 2000; Adcock et al. 2014; Adcock and Hansen 2016).

This problem, as far as I can tell, becomes much easier to state if one can use priors to provide a theoretically tractable model of the non-uniformly sampled signal. The Gaussian process formalism for probabilistic spectral analysis is one such method and is even computationally tractable using the methods of e.g. Saatçi (2012).

For FFT of unevenly sampled points, you can try the Non-uniform FFT (“NuFFT”).

Implementations of non-uniform sampling methods:

🏗 Lomb—Scargle periodogram and its uses.

1 Neural methods

For now, see implicit neural representations and neural ODEs.

2 References

Adcock, and Hansen. 2016. “Generalized Sampling and Infinite-Dimensional Compressed Sensing.” Foundations of Computational Mathematics.
Adcock, Hansen, Roman, et al. 2014. “Generalized Sampling: Stable Reconstructions, Inverse Problems and Compressed Sensing over the Continuum.” In Advances in Imaging and Electron Physics.
Aldroubi, and Gröchenig. 2001. “Nonuniform Sampling and Reconstruction in Shift-Invariant Spaces.” SIAM Review.
Amini, and 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.
Babu, and Stoica. 2010. “Spectral Analysis of Nonuniformly Sampled Data – a Review.” Digital Signal Processing.
Benedetto. 1992. “Irregular Sampling and Frames.” In Wavelets: A Tutorial in Theory and Applications. Wavelet Analysis and Its Applications.
Broersen, Piet M. T. 2005. “Time Series Analysis for Irregularly Sampled Data.” IFAC Proceedings Volumes, 16th IFAC World Congress,.
Broersen, P. M. T., and Bos. 2006. “Estimating Time-Series Models from Irregularly Spaced Data.” In IEEE Transactions on Instrumentation and Measurement.
Du, Collins, Tenenbaum, et al. 2021. “Learning Signal-Agnostic Manifolds of Neural Fields.” In Advances in Neural Information Processing Systems.
Dupont, Kim, Eslami, et al. 2022. “From Data to Functa: Your Data Point Is a Function and You Can Treat It Like One.” In Proceedings of the 39th International Conference on Machine Learning.
Eldar, and Oppenheim. 2000. “Filterbank Reconstruction of Bandlimited Signals from Nonuniform and Generalized Samples.” IEEE Transactions on Signal Processing.
Feichtinger, and Gröchenig. 1989. “Multidimensional Irregular Sampling of Band-Limited Functions in Lp-Spaces.” In Multivariate Approximation Theory IV. International Series of Numerical Mathematics / Internationale Schriftenreihe Zur Numerischen Mathematik / Série Internationale d’Analyse Numérique.
———. 1992. “Iterative Reconstruction of Multivariate Band-Limited Functions from Irregular Sampling Values.” SIAM Journal on Mathematical Analysis.
———. 1994. “Theory and Practice of Irregular Sampling.” Wavelets: Mathematics and Applications.
Feichtinger, Gröchenig, and Strohmer. 1995. “Efficient Numerical Methods in Non-Uniform Sampling Theory.” Numerische Mathematik.
Feichtinger, and Strohmer. 1992. “Fast Iterative Reconstruction of Band-Limited Images from Non-Uniform Sampling Values.” In SpringerLink.
Feichtinger, and Werther. 2000. “Improved Locality for Irregular Sampling Algorithms.” In IEEE International Conference on Acoustics, Speech, and Signal Processing, 2000. ICASSP ’00. Proceedings.
Fessler, and Sutton. 2003. “Nonuniform Fast Fourier Transforms Using Min-Max Interpolation.” IEEE Transactions on Signal Processing.
Greengard, and Lee. 2004. “Accelerating the Nonuniform Fast Fourier Transform.” SIAM Review.
Gröchenig. 1992. “Reconstruction Algorithms in Irregular Sampling.” Mathematics of Computation.
———. 1993. “A Discrete Theory of Irregular Sampling.” Linear Algebra and Its Applications.
Haris, Simon, and Shojaie. 2018. “Wavelet Regression and Additive Models for Irregularly Spaced Data.” In Proceedings of the 32nd International Conference on Neural Information Processing Systems. NIPS’18.
Jones. 1984. “Fitting Multivariate Models to Unequally Spaced Data.” In Time Series Analysis of Irregularly Observed Data.
Lahalle, Fleury, and Rivoira. 2004. “Continuous ARMA Spectral Estimation from Irregularly Sampled Observations.” In Proceedings of the 21st IEEE Instrumentation and Measurement Technology Conference, 2004. IMTC 04.
Larsson, and Söderström. 2002. “Identification of Continuous-Time AR Processes from Unevenly Sampled Data.” Automatica.
Maravic, and Vetterli. 2005. “Sampling and Reconstruction of Signals with Finite Rate of Innovation in the Presence of Noise.” IEEE Transactions on Signal Processing.
Margolis, and Eldar. 2008. “Nonuniform Sampling of Periodic Bandlimited Signals.” IEEE Transactions on Signal Processing.
Martin. 1998. “Autoregression and Irregular Sampling: Filtering.” Signal Processing.
———. 1999. “Autoregression and Irregular Sampling: Spectral Estimation.” Signal Processing.
Marvasti, Farokh. 2012. Nonuniform Sampling: Theory and Practice.
Marvasti, F., Analoui, and Gamshadzahi. 1991. “Recovery of Signals from Nonuniform Samples Using Iterative Methods.” IEEE Transactions on Signal Processing.
Marvasti, F. A., and Chuande. 1990. “Parseval Relationship of Nonuniform Samples of One- and Two-Dimensional Signals.” IEEE Transactions on Acoustics, Speech, and Signal Processing.
Mobli, and Hoch. 2014. “Nonuniform Sampling and Non-Fourier Signal Processing Methods in Multidimensional NMR.” Progress in Nuclear Magnetic Resonance Spectroscopy.
Murray-Smith, and Pearlmutter. 2005. “Transformations of Gaussian Process Priors.” In Deterministic and Statistical Methods in Machine Learning. Lecture Notes in Computer Science.
O’Callaghan, and Ramos. 2011. “Continuous Occupancy Mapping with Integral Kernels.” In Twenty-Fifth AAAI Conference on Artificial Intelligence.
Piroddi, and Petrou. 2004. “Analysis of Irregularly Sampled Data: A Review.” In Advances in Imaging and Electron Physics. Advances in Imaging and Electron Physics.
Saatçi. 2012. “Scalable inference for structured Gaussian process models.”
Shukla, and Marlin. n.d. “A Survey on Principles, Models and Methods for Learning from Irregularly Sampled Time Series: From Discretization to Attention and Invariance.” In.
Stoica, and Sandgren. 2006. “Spectral Analysis of Irregularly-Sampled Data: Paralleling the Regularly-Sampled Data Approaches.” Digit. Signal Process.
Strohmer. 1997. “Computationally Attractive Reconstruction of Bandlimited Images from Irregular Samples.” IEEE Transactions on Image Processing.
Tan, and Goyal. 2008. “Estimating Signals With Finite Rate of Innovation From Noisy Samples: A Stochastic Algorithm.” IEEE Transactions on Signal Processing.
Tarczynski, and Allay. 2004. “Spectral Analysis of Randomly Sampled Signals: Suppression of Aliasing and Sampler Jitter.” IEEE Transactions on Signal Processing.
Unser. 2000. “Sampling: 50 Years After Shannon.” Proceedings of the IEEE.
———. 2015. “Sampling and (Sparse) Stochastic Processes: A Tale of Splines and Innovation.” In 2015 International Conference on Sampling Theory and Applications (SampTA).
Venkataramani, and Bresler. 2000. “Perfect Reconstruction Formulas and Bounds on Aliasing Error in Sub-Nyquist Nonuniform Sampling of Multiband Signals.” IEEE Transactions on Information Theory.
Vetterli, Marziliano, and Blu. 2002. “Sampling Signals with Finite Rate of Innovation.” IEEE Transactions on Signal Processing.
Xu, Wang, Jiang, et al. 2022. “Signal Processing for Implicit Neural Representations.” In.
Yaroslavsky, Shabat, Salomon, et al. 2009. “Non-Uniform Sampling, Image Recovery from Sparse Data and the Discrete Sampling Theorem.” Journal of the Optical Society of America A.
Yen. 1956. “On Nonuniform Sampling of Bandwidth-Limited Signals.” IRE Transactions on Circuit Theory.