text: We focus on a multidimensional field with uncorrelated spectrum and study the quality of the reconstructed signal when the field samples are irregularly spaced and affected by independent and identically distributed noise. More specifically, we apply linear reconstruction techniques and take the mean-square error (MSE) of the field estimate as a metric to evaluate the signal reconstruction quality. We find that the MSE analysis could be carried out by using the closed-form expression of the eigenvalue distribution of the matrix representing the sampling system. Unfortunately, such distribution is still unknown. Thus, we first derive a closed-form expression of the distribution moments, and we find that the eigenvalue distribution tends to the Marcenko-Pastur distribution as the field dimension goes to infinity. Finally, by using our approach, we derive a tight approximation to the MSE of the reconstructed field.
  @cite_37: Recently, it has been observed that a sparse trigonometric polynomial, i.e., having only a small number of nonzero coefficients, can be reconstructed exactly from a small number of random samples using basis pursuit (BP) or orthogonal matching pursuit (OMP). In this paper, it is shown that recovery by a BP variant is stable under perturbation of the samples values by noise. A similar partial result for OMP is provided. For BP, in addition, the stability result is extended to (nonsparse) trigonometric polynomials that can be well approximated by sparse ones. The theoretical findings are illustrated by numerical experiments.
  @cite_8: 1. Basic Concepts. 2. Nonparametric Methods. 3. Parametric Methods for Rational Spectra. 4. Parametric Methods for Line Spectra. 5. Filter Bank Methods. 6. Spatial Methods. Appendix A: Linear Algebra and Matrix Analysis Tools. Appendix B: Cramer-Rao Bound Tools. Bibliography. References Grouped by Subject. Subject Index.
  @cite_9: 1. Introduction F. Marvasti. 2. An Introduction to Sampling Analysis P.L. Butzer, et al 3. Lagrange Interpolation and Sampling Theorems A.I. Zayed, P.L. Butzer. 4. Random Topics in Nonuniform Sampling F. Marvasti. 5. Iterative and Noniterative Recovery of Missing Samples for 1- D Band-Limited Signals P.J.S.G. Ferreira. 6. Numerical and Theoretical Aspects of Nonuniform Sampling of Band-Limited Images K. Grochenig, T. Strohmer. 7. The Nonuniform Discrete Fourier Transform S. Bagchi, S.K. Mitra. 8. Reconstruction of Stationary Processes Sampled at Random Times B. Lacaze. 9. Zero Crossings of Random Processes with Application to Estimation and Detection J. Barnett. 10. Magnetic Resonance Image Reconstruction from Nonuniformly Sampled k-Space Data F.T.A.W. Wajer, et al 11. Irregular and Sparse Sampling in Exploration Seismology A.J.W. Duijndam, et al 12. Randomized Digital Optimal Control W.L. de Koning, L.G. van Willigenburg. 13. Prediction of Band-Limited Signals from Past Samples and Applications to Speech Coding D.H. Muler, Y. Wu. 14. Frames, Irregular Sampling, and a Wavelet Auditory Model J.J. Benedetto, S. Scott. 15. Application of the Nonuniform Sampling to Motion Compensated Prediction A. Sharif, et al 16. Applications of Nonuniform Sampling to Nonlinear Modulation, A D and D A Techniques F. Marvasti, M. Sandler. 17. Applications to Error Correction Codes F. Marvasti. 18. Application of Nonuniform Sampling to Error Concealment M. Hasan, F. Marvasti. 19. Sparse Sampling in Array Processing S. Holm, et al 20. Fractional Delay Filters: Design and Applications V. Valimaki, T.I. Laakso.
  @cite_1: In [10, 11, 12] we introduced a new family of algorithms for the reconstruction of a band—limited function from its irregularly sampled values. In this paper we carry out an error analysis of these algorithms and discuss their numerical stability. As special cases we also obtain more precise error estimates in the case of the regular sampling theorem.
  @cite_32: Abstract We study the problem of reconstructing a multivariate trigonometric polynomial having only few non-zero coefficients from few random samples. Inspired by recent work of Candes, Romberg and Tao we propose to recover the polynomial by Basis Pursuit, i.e., by l 1 -minimization. In contrast to their work, where the sampling points are restricted to a grid, we model the random sampling points by a continuous uniform distribution on the cube, i.e., we allow them to have arbitrary position. Numerical experiments show that with high probability the trigonometric polynomial can be recovered exactly provided the number N of samples is high enough compared to the “sparsity”—the number of non-vanishing coefficients. However, N can be chosen small compared to the assumed maximal degree of the trigonometric polynomial. We present two theorems that explain this observation. One of them provides the analogue of the result of Candes, Romberg and Tao. The other one is a result toward an average case analysis and, unexpectedly connects to an interesting combinatorial problem concerning set partitions, which seemingly has not yet been considered before. Although our proofs follow ideas of they are simpler.
  @cite_0: 
  @cite_27: This article discusses modern techniques for nonuniform sampling and reconstruction of functions in shift-invariant spaces. It is a survey as well as a research paper and provides a unified framework for uniform and nonuniform sampling and reconstruction in shift-invariant subspaces by bringing together wavelet theory, frame theory, reproducing kernel Hilbert spaces, approximation theory, amalgam spaces, and sampling. Inspired by applications taken from communication, astronomy, and medicine, the following aspects will be emphasized: (a) The sampling problem is well defined within the setting of shift-invariant spaces. (b) The general theory works in arbitrary dimension and for a broad class of generators. (c) The reconstruction of a function from any sufficiently dense nonuniform sampling set is obtained by efficient iterative algorithms. These algorithms converge geometrically and are robust in the presence of noise. (d) To model the natural decay conditions of real signals and images, the sampling theory is developed in weighted L p-spaces.
  @cite_12: In many Applications one seeks to recover an entire function of exponential type from its non-uniformly spaced samples. Whereas the mathematical theory usually addresses the question of when such a function in L 2 (R) can be recovered, numerical methods operate with a finite-dimensional model. The numerical reconstruction or approximation of the original function amounts to the solution of a large linear system. We show that the solutions of a particularly efficient discrete model in which the data are fit by trigonometric polynomials converge to the solution of the original infinite-dimensional reconstruction problem. This legitimatizes the numerical computations and explains why the algorithms employed produce reasonable results. The main mathematical result is a new type of approximation theorem for entire functions of exponential type from a finite number of values. From another point of view our approach provides a new method for proving sampling theorems.
  @cite_11: Summary. We present a new “second generation” reconstruction algorithm for irregular sampling, i.e. for the problem of recovering a band-limited function from its non-uniformly sampled values. The efficient new method is a combination of the adaptive weights method which was developed by the two first named authors and the method of conjugate gradients for the solution of positive definite linear systems. The choice of ”adaptive weights” can be seen as a simple but very efficient method of preconditioning. Further substantial acceleration is achieved by utilizing the Toeplitztype structure of the system matrix. This new algorithm can handle problems of much larger dimension and condition number than have been accessible so far. Furthermore, if some gaps between samples are large, then the algorithm can still be used as a very efficient extrapolation method across the gaps.
summary: Relevant to our work is the literature on spectral analysis, where, however, several studies deal with regularly sampled signals (e.g., @cite_8 and references therein). An excellent guide to irregular sampling is @cite_9 , which presents a large number of techniques, algorithms, and applications. Reconstruction techniques for irregularly or randomly sampled signals can be found in @cite_11 @cite_32 @cite_1 , just to name few. In particular, Feichtinger and Gr "ochenig in @cite_1 provide an error analysis of an iterative reconstruction algorithm taking into account round-off errors, jitters, truncation errors and aliasing. From the theoretical point of view, irregular sampling has been studied in @cite_11 @cite_32 @cite_37 @cite_0 @cite_1 @cite_27 @cite_12 and references therein.