We study reconstruction operators on a Hilbert space that are exact on a given reconstruction subspace. Among those the reconstruction operator obtained by the least squares fit has the smallest operator norm, and therefore is most stable with respect to noisy measurements. We then construct the operator with the smallest possible quasi-optimality constant, which is the most stable with respect to a systematic error appearing before the sampling process (model uncertainty). We describe how to vary continuously between the two reconstruction methods, so that we can trade stability for quasi-optimality. As an application we study the reconstruction of a compactly supported function from nonuniform samples of its Fourier transform.
  This chapter presents methods for the reconstruction of bandlimited functions from irregular samples. The first part discusses algorithms for a constructive solution of the irregular sampling problem. An important aspect of these algorithms is the explicit knowledge of the constants involved and efficient error estimates. The second part discusses the numerical implementation of these algorithms and compares the performance of various reconstruction methods. Although most of the material has already appeared in print, several new results are included: (a) a new method to estimate frame bounds, (b) a reconstruction of band-limited functions from partial information, which is not just the samples; (c) a new result on the complete reconstruction of band-limited functions from local averages; (d) a systematic exposition of recent experimental results. 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. We give an overview of recent developments in the problem of reconstructing a band-limited signal from nonuniform sampling from a numerical analysis view point. It is shown that the appropriate design of the finite-dimensional model plays a key role in the numerical solution of the nonuniform sampling problem. In the one approach (often proposed in the literature) the finite-dimensional model leads to an ill-posed problem even in very simple situations. The other approach that we consider leads to a well-posed problem that preserves important structural properties of the original infinite-dimensional problem and gives rise to efficient numerical algorithms. Furthermore, a fast multilevel algorithm is presented that can reconstruct signals of unknown bandwidth from noisy nonuniformly spaced samples. We also discuss the design of efficient regularization methods for ill-conditioned reconstruction problems. Numerical examples from spectroscopy and exploration geophysics demonstrate the performance of the proposed methods. Abstract In this paper, we consider the problem of recovering a compactly supported multivariate function from a collection of pointwise samples of its Fourier transform taken nonuniformly. We do this by using the concept of weighted Fourier frames. A seminal result of Beurling shows that sampling points give rise to a classical Fourier frame provided they are relatively separated and of sufficient density. However, this result does not allow for arbitrary clustering of sampling points, as is often the case in practice. Whilst keeping the density condition sharp and dimension independent, our first result removes the separation condition and shows that density alone suffices. However, this result does not lead to estimates for the frame bounds. A known result of Grochenig provides explicit estimates, but only subject to a density condition that deteriorates linearly with dimension. In our second result we improve these bounds by reducing the dimension dependence. In particular, we provide explicit frame bounds which are dimensionless for functions having compact support contained in a sphere. Next, we demonstrate how our two main results give new insight into a reconstruction algorithm—based on the existing generalized sampling framework—that allows for stable and quasi-optimal reconstruction in any particular basis from a finite collection of samples. Finally, we construct sufficiently dense sampling schemes that are often used in practice—jittered, radial and spiral sampling schemes—and provide several examples illustrating the effectiveness of our approach when tested on these schemes. We provide sufficient density condition for a set of nonuniform samples to give rise to a set of sampling for multivariate bandlimited functions when the measurements consist of pointwise evaluations of a function and its first k derivatives. Along with explicit estimates of corresponding frame bounds, we derive the explicit density bound and show that, as k increases, it grows linearly in (k+1 ) with the constant of proportionality (1 e ). Seeking larger gap conditions, we also prove a multivariate perturbation result for nonuniform samples that are sufficiently close to sets of sampling, e.g. to uniform samples taken at (k+1 ) times the Nyquist rate. Additionally, in the univariate setting, we consider a related problem of so-called nonuniform bunched sampling, where in each sampling interval (s+1 ) bunched measurements of a function are taken and the sampling intervals are permitted to be of different length. We derive an explicit density condition which grows linearly in (s+1 ) for large s, with the constant of proportionality depending on the width of the bunches. The width of the bunches is allowed to be arbitrarily small, and moreover, for sufficiently narrow bunches and sufficiently large s, we obtain the same result as in the case of univariate sampling with s derivatives. 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.  We consider the problem of recovering a compactly supported function from a finite collection of pointwise samples of its Fourier transform taken nonuniformly. First, we show that under suitable conditions on the sampling frequencies---specifically, their density and bandwidth---it is possible to recover any such function @math in a stable and accurate manner in any given finite-dimensional subspace, in particular, one which is well suited for approximating @math . In practice, this is carried out using so-called nonuniform generalized sampling (NUGS). Second, we consider approximation spaces in one dimension consisting of compactly supported wavelets. We prove that a linear scaling of the dimension of the space with the sampling bandwidth is both necessary and sufficient for stable and accurate recovery. Thus wavelets are, up to constant factors, optimal spaces for reconstruction. 