The Living Thing / Notebooks :

Nonuniformly sampled signals, inference for

Signal processing without equal bins and thus a simple Nyquist Theorem. It turns out that this is not fatal for many systems, e.g. it’s almost simple for linear systems, although it requires a leeeettle bit of stochastic calculus, at least under certain models of time discretisation.

In the non-linear case, it will probably be more irritating.

Keywords: Nonuniform sampling, irregular sampling.

Signal reconstruction

The easy problem; You have knowledge of the system’s bandwidth, and you wish to reconstruct the most likely actual form for a realisation.

Up-to-date reviews in BaSt10, PiPe04, Eng07.

This is sometimes extended to include signal reconstructions with uncertain sampling times.

I’m curious how this works with blind reconstruction, when you don’t know the exact bandwidth. FeGr94 suggests that at the very least the answer is “slowly”, if you know a bound on the signal bandwidth which is greater than the actual bandwidth.

And how can you test for violation of bandwidth?

Iterative spectral reconstruction

Thomas Strohmer and Tobias Werther have an informal illustrated tutorial on iterative reconstruction based on a spectrum of known bandwidth. Keywords: Voronoi-Allebach algorithm, Marvasti algorithm and the adaptive-weights Voronoi algorithm. Formal discussion in sundry journal papers (e.g. Stro97, FeSt92), summarised in Theory and practice of irregular sampling (FeGr94) and in various articles in Marvasti’s collection (Marv12.)

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

Implementations:

TODO: Lomb–Scargle normalized periodogram and its uses.

Model estimation/system identification

You don’t know a parameterised model for the data (and hence a precise bandwidth) and you wish to estimate it.

This is a system identification problem, although the non-uniform sampling means that it has an unusual form.

Martin (Mart99a) gives this summary:

One could consider the general problem in an approximate way as the missing data problem with a very high proportion of missing data points, but (Jone81, Jone84) this is not very realistic. This has led to the consideration of the continuous-time model […]. Masry (LiMa92) shows that the coefficients in that equation may be obtained from the [irregularly sampled autocorrelation moments, but], the estimation of these requires a large amount of data and the results are asymptotic in the limit of infinite data. The other continuous-time approach is that of Jones (Jone81, Jone84) who has used Kalman recursive estimation […] to obtain a likelihood function \(\operatorname{lik}(x|b)\) which is then maximised w.r.t. b to obtain an estimate of the true parameters.

There is a partial review and comparison of methods in StSa06, and Broe06. From the latter:

Martin (Mart99b) applied autoregressive modeling to irregularly sampled data using a dedicated method. It was particularly good in extracting sinusoids from noise in short data sets. Söderström and Mossberg (SöMo00) evaluated the performance of methods for identifying continuous-time autoregressive processes, which replace the differentiation operator by different approximations. Larsson and Söderström (LaSö02) apply this idea to randomly sampled autoregressive data. They report promising results for low-order processes. Lahalle et al (LaFR04) estimate continuous-time ARMA models. Unfortunately, their method requires explicit use of a model for irregular sampling instants. The precise shape of that distribution is very important for the result, but it is almost impossible to establish it from practical data.

No generally satisfactory spectral estimator for irregular data has been defined yet. Continuous time series models can be estimated for irregular data, and they are the only possible candidates for obtaining the Cramér-Rao lower boundary, because the true process for irregular data is a continuous-time process. Jones (Jone81) has formulated the maximum likelihood estimator for irregular observations. However, Jones (Jone84) also found that the likelihood has several local maxima and the optimisation requires extremely good initial estimates. Broersen and Bos (BrBo06) used the method of Jones to obtain maximum likelihood estimates for irregular data. If simulations started with the true process parameters as initial conditions, that was sometimes, but not always, good enough to converge to the global maximum of the likelihood. However, sometimes even those perfect and nonrealisable starting values were not capable of letting the likelihood converge to an acceptable model. So far, no practical maximum likelihood method for irregular data has solved all numerical problems, and certainly no satisfactory realisable initial conditions can be given. As an example, it has been verified in simulations that taking the estimated AR( p–1) model together with an additional zero for order p as starting values for AR( p) estimation does not always converge to acceptable AR( p) models. The model with the maximum value of the likelihood might not in all cases be accurate and many good models have significantly lower numerical values of the likelihood. Martin (Mart99a) suggests that the exact likelihood is sensitive to round-off errors. Broersen and Bos (BrBo06) calculated the likelihood as a function of true model parameters, multiplied by a constant factor. Only the likelihood for a single pole was smooth. Two poles already gave a number of sharp peaks in the likelihood, and three or more poles gave a very rough surface of the likelihood. The scene is full of local minima, and the optimisation cannot find the global minimum, unless it starts very close to it.

Slotting

Asymptotic methods based on gridding observations.

Method of transformed coefficients

Useful tool: equivalence of a continuous time Ito integral and a discrete ARIMA process (attributed by Mart98 to Bart46) also implies you can estimate the model without estimating missing data, which is satisfying, although the precise form this takes is less satisfying.

Popular overviews seem to be PiPe04, and Mart99b.

I think this hinges always on Skorohod embedding-type approaches to continuous systems.

The Skorohod embedding question asks: can all centered random walks be constructed in this fashion, by stopping Brownian motion at a sequence of stopping time? With the strong Markov property, it immediately reduces the question of whether all centered finite-variance distributions X can be expressed as B_T for some integrable stopping time T.

State filters

(Note that you can also do the signal reconstruction problem using state filters, but I’m interested here in doing system identification using state filters.) Jones (Jone81, Jone84) gave this a go; while Mart99a mentioned problems, I’m curious when it does work, since this seems natural, simple, and easier to make robust against model violations than the other methods.

Jone84:

It is well known that if a univariate continuous time autoregression is sampled at equally spaced time intervals, the resulting, discrete time process is ARMA(p,p-1). If the sampling includes observational error, the resulting process is ARMA(p,p); however, these 2p parameters depend only on the p continuous time autoregression coefficients and the observational error variance. Modeling, the process as a continuous time autoregression with observational error may be much more parsimonious than modeling the discrete time process, whether or not the data are equally spaced. The direct modeling of observational error has the effect of smoothing noisy data and may eliminate the need for moving average terms.

Refs

AlGr01
Aldroubi, A., & Gröchenig, K. (2001) Nonuniform Sampling and Reconstruction in Shift-Invariant Spaces. SIAM Review, 43(4), 585–620. DOI.
AmMa08
Amini, A., & Marvasti, F. (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).
BaSt10
Babu, P., & Stoica, P. (2010) Spectral analysis of nonuniformly sampled data – a review. Digital Signal Processing, 20(2), 359–378. DOI.
BaBo99
Baisch, S., & Bokelmann, G. H. R.(1999) Spectral analysis with incomplete time series: an example from seismology. Computers & Geosciences, 25(7), 739–750. DOI.
Bart46
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. DOI.
Broe06
Broersen, P. M.(2006) Automatic autocorrelation and spectral analysis. . Secaucus, NJ, USA: Springer Science & Business Media
BrBo06
Broersen, P. M. T., & Bos, R. (2006) Estimating time-series models from irregularly spaced data. IEEE Transactions on Instrumentation and Measurement, 55(4), 1124–1131. DOI.
BrWB04
Broersen, Piet M. T., de Waele, S., & Bos, R. (2004) Autoregressive spectral analysis when observations are missing. Automatica, 40(9), 1495–1504. DOI.
ElOp00
Eldar, Y. C., & Oppenheim, A. V.(2000) Filterbank reconstruction of bandlimited signals from nonuniform and generalized samples. IEEE Transactions on Signal Processing, 48(10), 2864–2875. DOI.
Eng07
Eng, F. (2007) Non-uniform sampling in statistical signal processing. . Department of Electrical Engineering, Linköpings universitet, Linköping
FeGr89
Feichtinger, H. G., & Gröchenig, K. (1989) Multidimensional Irregular Sampling of Band-Limited Functions in Lp-Spaces. In Multivariate Approximation Theory IV (pp. 135–142). Birkhäuser Basel DOI.
FeGr92
Feichtinger, H. G., & Gröchenig, K. (1992) Iterative Reconstruction of Multivariate Band-Limited Functions from Irregular Sampling Values. SIAM Journal on Mathematical Analysis, 23(1), 244–261. DOI.
FeGr94
Feichtinger, H. G., & Gröchenig, K. (1994) Theory and practice of irregular sampling. Wavelets: Mathematics and Applications, 1994, 305–363.
FeGS95
Feichtinger, H. G., Gröchenig, K., & Strohmer, T. (1995) Efficient numerical methods in non-uniform sampling theory. Numerische Mathematik, 69(4), 423–440. DOI.
FeSt92
Feichtinger, H. G., & Strohmer, T. (1992) Fast iterative reconstruction of band-limited images from non-uniform sampling values. In SpringerLink (Vol. 231, pp. 82–89). Springer Berlin Heidelberg DOI.
FeWe00
Feichtinger, H. G., & Werther, T. (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.
FeSu03
Fessler, J. A., & Sutton, B. P.(2003) Nonuniform Fast Fourier Transforms Using Min-Max Interpolation. IEEE Transactions on Signal Processing, 51(2). DOI.
GrLe04
Greengard, L., & Lee, J. (2004) Accelerating the Nonuniform Fast Fourier Transform. SIAM Review, 46(3), 443–454. DOI.
Gröc92
Gröchenig, K. (1992) Reconstruction algorithms in irregular sampling. Mathematics of Computation, 59(199), 181–194. DOI.
Gröc93
Gröchenig, K. (1993) A discrete theory of irregular sampling. Linear Algebra and Its Applications, 193, 129–150. DOI.
Jone81
Jones, R. H.(1981) Fitting a continuous time autoregression to discrete data. In Applied time series analysis II (pp. 651–682).
Jone84
Jones, R. H.(1984) Fitting multivariate models to unequally spaced data. In Time series analysis of irregularly observed data (pp. 158–188). Springer
KaBH06
Kazhdan, M., Bolitho, M., & Hoppe, H. (2006) Poisson Surface Reconstruction. In SGP06: Eurographics Symposium on Geometry Processing (Vol. 1, p. 0). The Eurographics Association DOI.
LaFR04
Lahalle, E., Fleury, G., & Rivoira, A. (2004) Continuous ARMA spectral estimation from irregularly sampled observations. In Proceedings of the 21st IEEE Instrumentation and Measurement Technology Conference, 2004. IMTC 04 (Vol. 2, p. 923–927 Vol.2). DOI.
Land67
Landau, H. J.(1967) Necessary density conditions for sampling and interpolation of certain entire functions. Acta Mathematica, 117(1), 37–52.
LaSö02
Larsson, E. K., & Söderström, T. (2002) Identification of continuous-time AR processes from unevenly sampled data. Automatica, 38(4), 709–718. DOI.
LiMa92
Lii, K.-S., & Masry, E. (1992) Model fitting for continuous-time stationary processes from discrete-time data. Journal of Multivariate Analysis, 41(1), 56–79. DOI.
MaEl08
Margolis, E., & Eldar, Y. C.(2008) Nonuniform Sampling of Periodic Bandlimited Signals. IEEE Transactions on Signal Processing, 56(7), 2728–2745. DOI.
Marp87
Marple, S. L., Jr. (1987) Digital spectral analysis with applications.
Mart98
Martin, R. J.(1998) Autoregression and irregular sampling: Filtering. Signal Processing, 69(3), 229–248. DOI.
Mart99a
Martin, R. J.(1999a) Autoregression and irregular sampling: Spectral estimation. Signal Processing, 77(2), 139–157. DOI.
Mart99b
Martin, Richard James. (1999b, April 2) Irregularly Sampled Signals: Theories and Techniques for Analysis.
MaCh90
Marvasti, F. A., & Chuande, L. (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.
MaAG91
Marvasti, F., Analoui, M., & Gamshadzahi, M. (1991) Recovery of signals from nonuniform samples using iterative methods. IEEE Transactions on Signal Processing, 39(4), 872–878. DOI.
Marv12
Marvasti, Farokh. (2012) Nonuniform Sampling: Theory and Practice. . Springer Science & Business Media
MiEl09
Mishali, M., & Eldar, Y. C.(2009) Blind Multiband Signal Reconstruction: Compressed Sensing for Analog Signals. IEEE Transactions on Signal Processing, 57(3), 993–1009. DOI.
MoHo14
Mobli, M., & Hoch, J. C.(2014) Nonuniform sampling and non-Fourier signal processing methods in multidimensional NMR. Progress in Nuclear Magnetic Resonance Spectroscopy, 83, 21–41. DOI.
PiPe04
Piroddi, R., & Petrou, M. (2004) Analysis of Irregularly Sampled Data: A Review. In Advances in Imaging and Electron Physics (Vol. 132, pp. 109–165). Elsevier
SöMo00
Söderström, T., & Mossberg, M. (2000) Performance evaluation of methods for identifying continuous-time autoregressive processes. Automatica, 1(36), 53–59. DOI.
Star01
Stark, Jaroslav. (2001) Delay Reconstruction: Dynamics versus Statistics. In A. I. Mees (Ed.), Nonlinear Dynamics and Statistics (pp. 81–103). Birkhäuser Boston DOI.
SBDH03
Stark, J., Broomhead, D. S., Davies, M. E., & Huke, J. (2003) Delay Embeddings for Forced Systems II Stochastic Forcing. Journal of Nonlinear Science, 13(6), 519–577. DOI.
StSa06
Stoica, P., & Sandgren, N. (2006) Spectral Analysis of Irregularly-sampled Data: Paralleling the Regularly-sampled Data Approaches. Digit. Signal Process., 16(6), 712–734. DOI.
Stro97
Strohmer, T. (1997) Computationally attractive reconstruction of bandlimited images from irregular samples. IEEE Transactions on Image Processing, 6(4), 540–548. DOI.
TaAl04
Tarczynski, A., & Allay, N. (2004) Spectral analysis of randomly sampled signals: suppression of aliasing and sampler jitter. IEEE Transactions on Signal Processing, 52(12), 3324–3334. DOI.
VeBr00
Venkataramani, R., & Bresler, Y. (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.
VeMB02
Vetterli, M., Marziliano, P., & Blu, T. (2002) Sampling signals with finite rate of innovation. IEEE Transactions on Signal Processing, 50(6), 1417–1428. DOI.
Wert99
Werther, T. (1999) Reconstruction from irregular samples with improved locality. . na
YSSI09
Yaroslavsky, L. P., Shabat, G., Salomon, B. G., Ideses, I. A., & Fishbain, B. (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.
Yen56
Yen, J. (1956) On Nonuniform Sampling of Bandwidth-Limited Signals. IRE Transactions on Circuit Theory, 3(4), 251–257. DOI.