On the stability of unevenly spaced samples for interpolation and quadrature

DOI10.1007/S10543-023-00965-ZarXiv2202.04722MaRDI QIDQ6390655

Alex Townsend, Annan Yu

Publication date: 9 February 2022

Abstract: Unevenly spaced samples from a periodic function are common in signal processing and can often be viewed as a perturbed equally spaced grid. In this paper, we analyze how the uneven distribution of the samples impacts the quality of interpolation and quadrature. Starting with equally spaced nodes on $[-pi,pi)$ with grid spacing $h$, suppose the unevenly spaced nodes are obtained by perturbing each uniform node by an arbitrary amount $leqalphah$, where $0leqalpha<1/2$ is a fixed constant. We prove a discrete version of the Kadec-1/4 theorem, which states that the nonuniform discrete Fourier transform associated with perturbed nodes has a bounded condition number independent of $h$, for any $alpha<1/4$. We go on to show that unevenly spaced quadrature rules converge for all continuous functions and interpolants converge uniformly for all differentiable functions whose derivative has bounded variation when $0leqalpha<1/4$. Though, quadrature rules at perturbed nodes can have negative weights for any $alpha>0$, we provide a bound on the absolute sum of the quadrature weights. Therefore, we show that perturbed equally spaced grids with small $alpha$ can be used without numerical woes. While our proof techniques work primarily when $0leqalpha<1/4$, we show that a small amount of oversampling extends our results to the case when $1/4leqalpha<1/2$.

Mathematics Subject Classification ID

Trigonometric interpolation (42A15) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Numerical methods for discrete and fast Fourier transforms (65T50) Fourier and Fourier-Stieltjes transforms and other transforms of Fourier type (42A38) Numerical quadrature and cubature formulas (65D32) Sampling theory in information and communication theory (94A20)

This page was built for publication: On the stability of unevenly spaced samples for interpolation and quadrature

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6390655)