Non-uniform signal sampling

Discrete sample representation of continuous signals without a grid

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.

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

This problem AFAICT becomes much easier if one can use use priors to provide a theoretically tractable model of the nonuniformly sampled signal. The Gaussian process formalism for probabilistic spectral analysis, is one such method 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.

Adcock, Ben, and Anders C. Hansen. 2016. “Generalized Sampling and Infinite-Dimensional Compressed Sensing.” Foundations of Computational Mathematics 16 (5): 1263–1323. https://doi.org/10.1007/s10208-015-9276-6.

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. https://doi.org/10.1016/B978-0-12-800146-2.00004-7.

Aldroubi, Akram, and Karlheinz Gröchenig. 2001. “Nonuniform Sampling and Reconstruction in Shift-Invariant Spaces.” SIAM Review 43 (4): 585–620. https://doi.org/10.1137/S0036144501386986.

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). http://bigwww.epfl.ch/amini/Papers/It_Convergence.pdf.

Babu, Prabhu, and Petre Stoica. 2010. “Spectral Analysis of Nonuniformly Sampled Data – a Review.” Digital Signal Processing 20 (2): 359–78. https://doi.org/10.1016/j.dsp.2009.06.019.

Benedetto, John J. 1992. “Irregular Sampling and Frames.” In Wavelets: A Tutorial in Theory and Applications, edited by CHARLES K. Chui, 2:445–507. Wavelet Analysis and Its Applications. San Diego: Academic Press. https://doi.org/10.1016/B978-0-12-174590-5.50020-4.

Broersen, Piet M. T. 2005. “Time Series Analysis for Irregularly Sampled Data.” IFAC Proceedings Volumes, 16th IFAC World Congress, 38 (1): 154–59. https://doi.org/10.1016/S1474-6670(16)36038-4.

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. https://doi.org/10.1109/TIM.2006.876389.

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. https://doi.org/10.1109/78.869037.

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. https://doi.org/10.1007/978-3-0348-7298-0_15.

———. 1994. “Theory and Practice of Irregular Sampling.” Wavelets: Mathematics and Applications 1994: 305–63. https://www.researchgate.net/profile/Hans_Feichtinger/publication/243775135_Theory_and_Practice_of_Irregular_Sampling/links/0deec532a001998e22000000.pdf.

———. 1992. “Iterative Reconstruction of Multivariate Band-Limited Functions from Irregular Sampling Values.” SIAM Journal on Mathematical Analysis 23 (1): 244–61. https://doi.org/10.1137/0523013.

Feichtinger, Hans G., Karlheinz Gröchenig, and Thomas Strohmer. 1995. “Efficient Numerical Methods in Non-Uniform Sampling Theory.” Numerische Mathematik 69 (4): 423–40. https://doi.org/10.1007/s002110050101.

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. https://doi.org/10.1007/3-540-57233-3_10.

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–7 vol.6. https://doi.org/10.1109/ICASSP.2000.860239.

Fessler, Jeffrey A., and Bradley P. Sutton. 2003. “Nonuniform Fast Fourier Transforms Using Min-Max Interpolation.” IEEE Transactions on Signal Processing 51 (2). https://doi.org/10.1109/TSP.2002.807005.

Greengard, L., and J. Lee. 2004. “Accelerating the Nonuniform Fast Fourier Transform.” SIAM Review 46 (3): 443–54. https://doi.org/10.1137/S003614450343200X.

Gröchenig, Karlheinz. 1992. “Reconstruction Algorithms in Irregular Sampling.” Mathematics of Computation 59 (199): 181–94. https://doi.org/10.1090/S0025-5718-1992-1134729-0.

———. 1993. “A Discrete Theory of Irregular Sampling.” Linear Algebra and Its Applications 193 (November): 129–50. https://doi.org/10.1016/0024-3795(93)90275-S.

Haris, Asad, Ali Shojaie, and Noah Simon. n.d. “Wavelet Regression and Additive Models for Irregularly Spaced Data,” 11.

Jones, Richard H. 1984. “Fitting Multivariate Models to Unequally Spaced Data.” In Time Series Analysis of Irregularly Observed Data, 158–88. Springer. http://link.springer.com/chapter/10.1007/978-1-4684-9403-7_8.

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–27 Vol.2. https://doi.org/10.1109/IMTC.2004.1351213.

Larsson, Erik K., and Torsten Söderström. 2002. “Identification of Continuous-Time AR Processes from Unevenly Sampled Data.” Automatica 38 (4): 709–18. https://doi.org/10.1016/S0005-1098(01)00244-8.

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. https://doi.org/10.1109/TSP.2005.850321.

Margolis, E., and Y. C. Eldar. 2008. “Nonuniform Sampling of Periodic Bandlimited Signals.” IEEE Transactions on Signal Processing 56 (7): 2728–45. https://doi.org/10.1109/TSP.2008.917416.

Martin, R. J. 1999. “Autoregression and Irregular Sampling: Spectral Estimation.” Signal Processing 77 (2): 139–57. https://doi.org/10.1016/S0165-1684(99)00029-8.

———. 1998. “Autoregression and Irregular Sampling: Filtering.” Signal Processing 69 (3): 229–48. https://doi.org/10.1016/S0165-1684(98)00105-4.

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–3. https://doi.org/10.1109/29.56070.

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. https://doi.org/10.1109/78.80909.

Marvasti, Farokh. 2012. Nonuniform Sampling: Theory and Practice. Springer Science & Business Media. http://books.google.com?id=n3fgBwAAQBAJ.

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. https://doi.org/10.1016/j.pnmrs.2014.09.002.

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. http://bcl.hamilton.ie/~barak/papers/MLW-Jul-2005.pdf.

O’Callaghan, Simon Timothy, and Fabio T. Ramos. 2011. “Continuous Occupancy Mapping with Integral Kernels.” In Twenty-Fifth AAAI Conference on Artificial Intelligence. https://www.aaai.org/ocs/index.php/AAAI/AAAI11/paper/view/3784.

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. http://linkinghub.elsevier.com/retrieve/pii/S1076567004320033.

Saatçi, Yunus. 2012. “Scalable Inference for Structured Gaussian Process Models.” Ph.D., University of Cambridge. https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.610016.

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. https://doi.org/10.1016/j.dsp.2006.08.012.

Strohmer, T. 1997. “Computationally Attractive Reconstruction of Bandlimited Images from Irregular Samples.” IEEE Transactions on Image Processing 6 (4): 540–48. https://doi.org/10.1109/83.563319.

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. https://doi.org/10.1109/TSP.2008.928510.

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. https://doi.org/10.1109/TSP.2004.837436.

Unser, M. 2000. “Sampling: 50 Years After Shannon.” Proceedings of the IEEE 88 (4): 569–87. https://doi.org/10.1109/5.843002.

———. 2015. “Sampling and (Sparse) Stochastic Processes: A Tale of Splines and Innovation.” In 2015 International Conference on Sampling Theory and Applications (SampTA), 221–25. https://doi.org/10.1109/SAMPTA.2015.7148884.

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. https://doi.org/10.1109/18.868487.

Vetterli, M., P. Marziliano, and T. Blu. 2002. “Sampling Signals with Finite Rate of Innovation.” IEEE Transactions on Signal Processing 50 (6): 1417–28. https://doi.org/10.1109/TSP.2002.1003065.

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. https://doi.org/10.1364/JOSAA.26.000566.

Yen, J. 1956. “On Nonuniform Sampling of Bandwidth-Limited Signals.” IRE Transactions on Circuit Theory 3 (4): 251–57. https://doi.org/10.1109/TCT.1956.1086325.