A. Yu and A. Townsend

# On the stability of unevenly spaced samples for interpolation and
quadrature††thanks: Submitted to the editors . This work is partially
supported by the National Science Foundation grants DMS-1818757, DMS-1952757
and DMS-2045646.

Annan Yu Center for Applied Mathematics, Cornell University, Ithaca, NY 14853.
<EMAIL_ADDRESS>Alex Townsend Department of Mathematics, Cornell
University, Ithaca, NY 14853<EMAIL_ADDRESS>
###### 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 $\leq\alpha
h$, where $0\leq\alpha<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 $0\leq\alpha<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
$0\leq\alpha<1/4$, we show that a small amount of oversampling extends our
results to the case when $1/4\leq\alpha<1/2$.

###### keywords:

trigonometric interpolation, quadrature, Kadec-$1/4$ theorem, nonuniform
discrete Fourier transformation, sampling theory

42A15, 65D32, 94A20

##  1 Introduction

In signal processing, function approximation, and econometrics, unevenly
spaced time series data naturally occur. For example, natural disasters occur
at irregular time intervals [25], observational astronomy takes measurements
of celestial bodies at times determined by cloud coverage and planetary
configurations [31], clinical trials may monitor health diagnostics at
irregular time intervals [29], and wireless sensors only record information
when a state changes to conserve battery life [14]. In most applications, the
samples can usually be considered as obtained from perturbed equally spaced
nodes. Therefore, a common approach to deal with unevenly spaced samples is to
first transform the data into equally spaced observations using some form of
low-order interpolation [11]. However, transforming data in this way can
introduce a number of significant and hard-to-quantify biases [28, 26].
Ideally, unevenly spaced time series are analyzed in the original form and
there seems to be limited theoretical results on this in approximation theory
[3].

Suppose that there is an unknown $2\pi$-periodic function
$f:[-\pi,\pi)\rightarrow\mathbb{C}$ that is sampled at $2N+1$ unevenly spaced
nodes, and one would like to recover $f$ via interpolation or compute
integrals involving $f$. How much does the uneven distribution of the samples
impact the quality of interpolation or quadrature? To make progress on this
question, we assume that the unevenly spaced nodes can be viewed as perturbed
equally spaced nodes. That is, we have acquired samples $f_{-N},\ldots,f_{N}$
from $f$ at nodes that are perturbed from equally spaced nodes, i.e.,

(1) $f_{j}=f(\tilde{x}_{j}),\qquad\tilde{x}_{j}=(j+\delta_{j})h\qquad-N\leq
j\leq N,$

where $h=2\pi/(2N+1)$ is the grid spacing and $\delta_{j}$ is the perturbation
of $jh$ with $|\delta_{j}|\leq\alpha$ for some $0\leq\alpha<1/2$ (see Fig. 1).
We call the nodes $\tilde{x}_{-N},\ldots,\tilde{x}_{N}$ a set of
$\alpha$-perturbed nodes. Here, we assume that $\alpha<1/2$ so that nodes
cannot coalesce. When $\alpha=0$ the nodes are equally spaced and we are in a
classical setting of approximation theory. In particular, when $\alpha=0$, one
can use the fast Fourier transform (FFT) [7] to compute interpolants that
converge rapidly to $f$ [33]. Moreover, the associated quadrature estimate is
the trapezoidal rule, which is numerically stable and can be geometrically
convergent for computing integrals involving $f$ [17, 30]. Surprisingly, there
has been far less theoretical attention on the case when $\alpha\neq 0$,
despite it appearing in numerous applications and many encouraging numerical
observations [2, 30]. A notable exception is Austin and Trefethen’s work [3],
where they showed that interpolants and the quadrature at perturbed grids
converge when the underlying function $f$ is twice continuously differentiable
and $\alpha<1/2$. Using a discrete analogue of the Kadec-1/4 theorem [18], we
strengthen these results when $\alpha<1/4$.

$-\pi$$\pi$$0$$h$$2h$$3h$$4h$$-h$$-2h$$-3h$$-4h$$h=\frac{2\pi}{9}$ Figure 1:
Nine equally spaced nodes (black dots) on $[-\pi,\pi)$. The intervals (red)
show where the unevenly spaced function samples can be when $\alpha=1/3$ in
Eq. 1.

There are several aspects of unevenly spaced samples that we investigate:

  * •

Conditioning of a nonuniform discrete Fourier transform. The analogue of the
FFT for unevenly spaced nodes is the nonuniform discrete Fourier transform
(NUDFT). There are many variants of the NUDFT, but we focus on the one that is
closely related to Eq. 1 and common in signal processing [4]. Let $N$ be an
integer and $\underline{c}=\left(c_{-N},\ldots,c_{N}\right)^{\top}$ be a
vector. The NUDFT task related to Eq. 1 is to compute the vector
$\underline{f}=\left(f_{-N},\ldots,f_{N}\right)^{\top}$, defined by the
following sums:

(2) $f_{j}=\sum_{k=-N}^{N}c_{k}e^{-i\tilde{x}_{j}k},\qquad-N\leq j\leq N.$

As Eq. 2 involves $2N+1$ sums each with $2N+1$ terms, the naive algorithms for
computing $\underline{f}$ require $\mathcal{O}(N^{2})$ operations; however,
there are efficient algorithms that require only $\mathcal{O}(N\log N)$
operations [5]. The NUDFT task has an inverse for any perturbed grid with
$0\leq\alpha<1/2$, which aims to recover the vector $\underline{c}$ from
$\underline{f}$. We show that for $\alpha<1/4$, the NUDFT task and its inverse
have a condition number that can be bounded independent of $N$ when
$\alpha<1/4$ (see Corollary 2.5).

  * •

Trigonometric interpolation. A trigonometric polynomial $q$ of degree $\leq n$
is a function defined on $[-\pi,\pi)$ of the form

(3) $q(x)=\sum_{k=-n}^{n}c_{k}e^{ikx},\qquad c_{k}\in\mathbb{C}.$

We denote the space of all trigonometric polynomials of degree $\leq n$ by
$\mathcal{T}_{n}$. The goal of trigonometric interpolation is to find
coefficients $c_{-n},\ldots,c_{n}$ such that $q$ interpolates $f$ at the
samples, i.e., $q(\tilde{x}_{j})=f_{j}$ for $-N\leq j\leq N$. Since the
summand in Eq. 3 can be reversed, an algorithm to find the coefficients is the
inverse NUDFT when $n=N$. We show that interpolants at $\alpha$-perturbed
nodes converge to $f$ for all differentiable functions whose derivative has
bounded variation when $0\leq\alpha<1/4$ (see Theorem 3.1 and Theorem 5.3).

  * •

Exact quadrature. A quadrature rule is a method for numerical integration that
approximates the integral of $f$ by a weighted sum of the function’s samples,
i.e.,

(4)
$I=\int_{-\pi}^{\pi}f(x)dx\approx\tilde{I}_{N}=\sum_{j=-N}^{N}\tilde{w}_{j}f(\tilde{x}_{j}).$

Here, $\tilde{x}_{-N},\ldots,\tilde{x}_{N}$ are called the quadrature nodes
and $\tilde{w}_{-N},\ldots,\tilde{w}_{N}$ the quadrature weights. Given
quadrature nodes, it is often desirable to design the quadrature weights so
that Eq. 4 is exact for all trigonometric polynomials in $\mathcal{T}_{n}$ for
some $n$. When $n=N$, the exact condition uniquely defines a quadrature rule
for any $\alpha<1/2$. While quadrature rules at $\alpha$-perturbed nodes can
have negative weights for any $\alpha>0$ (see Theorem 4.1), we show that the
absolute sums of the weights, i.e., $\sum_{j=-N}^{N}|\tilde{w}_{j}|$, is
bounded independent of $N$ for $\alpha<1/4$ (see Theorem 4.3), which shows
that the quadrature rules are numerically stable. We provide an explicit upper
bound on $|I-\tilde{I}_{N}|$ and conclude that
$\lim_{N\rightarrow\infty}\tilde{I}_{N}=I$ for all continuous periodic
functions when $\alpha<1/4$.

  * •

Marcinkiewicz–Zygmund inequalities. The stability of quadrature and
interpolation is closely connected to so-called Marcinkiewicz–Zygmund (MZ)
inequalities [22, 15]. We show that the following MZ inequality holds for all
$q\in\mathcal{T}_{N}$:

(5)
$\frac{(1-\varphi_{\alpha})^{2}}{2\pi}\\!\int_{-\pi}^{\pi}|q(x)|^{2}dx\leq\frac{1}{2N+1}\sum_{j=-N}^{N}\left|q(\tilde{x}_{j})\right|^{2}\leq\frac{(1+\varphi_{\alpha})^{2}}{2\pi}\\!\int_{-\pi}^{\pi}|q(x)|^{2}dx,$

where $\tilde{x}_{-N},\ldots,\tilde{x}_{N}$ are any $\alpha$-perturbed nodes
in Eq. 1 with $\alpha<1/4$ and
$\varphi_{\alpha}=1-\cos(\pi\alpha)+\sin(\pi\alpha)$. Other MZ inequalities at
perturbed nodes are found in [21, 23]. We use the MZ inequality in Eq. 5 to
derive explicit error bounds and the rate of convergence of quadrature rules
and interpolants at $\alpha$-perturbed nodes when $0\leq\alpha<1/4$.

While our proof techniques work primarily for $0\leq\alpha<1/4$ when $N=n$
(see Section 5), we show that oversampling, i.e., $N>n$, allows us to extend
our results to the case when $1/4\leq\alpha<1/2$. By oversampling by a factor
of $1+\epsilon$, i.e., $N=\lceil(1+\epsilon)n\rceil$ for any $\epsilon>0$, we
show that the same convergence results for interpolation and quadrature carry
over to when $1/4\leq\alpha<1/2$ (see Section 6), improving on a result by
Mhaskar, Narcowich, and Ward [22, Cor. 4.1].

Many results in this paper are motivated by Austin’s thesis [2]. In
particular, for $0\leq\alpha<1/4$, we prove Conjecture 3.10 of [2] on the
$2$-norm Lebesgue constant (see Corollary 2.7) and Conjecture 3.14 on the
absolute sum of the quadrature weights (see Theorem 4.3). Our results for
interpolation also confirm Conjecture 3.7. Moreover, we provide an answer to
questions regarding the signs of quadrature weights raised in section 3.5.2 of
[2] (see Theorem 4.1 and Theorem B.5).

The paper is structured as follows. In Section 2, we prove a discrete version
of the Kadec-$1/4$ theorem that leads to a condition number bound on the
nonuniform discrete Fourier transform and discuss its consequences. In Section
3 and Section 4, we study the interpolation and quadrature rules at
$\alpha$-perturbed nodes. In Section 5 we look at further consequences of MZ
inequalities. Finally, in Section 6, we investigate what happens when in the
oversampling setting.

##  2 The Kadec-$\mathbf{1/4}$ theorem and its consequences

In sampling theory, the Kadec-$1/4$ theorem shows that the Fourier modes
$\left\\{e^{i\lambda_{k}x}\right\\}$ for $k\in\mathbb{Z}$ form a Riesz basis
when $|\lambda_{k}-k|\leq\alpha$ and $0\leq\alpha<1/4$ [18], which in signal
processing means that one can recover a square-integrable function if given
its inner-products with $\left\\{e^{i\lambda_{k}x}\right\\}$. While the
standard setting for Kadec’s theorem applies to perturbing an infinite number
of Fourier wave numbers from integers $k$ to $\lambda_{k}$, we show that there
is a discrete analogue when perturbing a finite number of nodes. It has
consequences for the condition number of the NUDFT and MZ inequalities.

For an integer $N$ and $\alpha$-perturbed nodes $\\{\tilde{x}_{j}\\}$, let $F$
be the DFT matrix given by

$F_{jk}=e^{-2\pi ijk/(2N+1)},\qquad-N\leq j,k\leq N,$

and $\tilde{F}$ be a NUDFT matrix given by

(6) $\tilde{F}_{jk}=e^{-i\tilde{x}_{j}k}=e^{-2\pi
i(j+\delta_{j})k/(2N+1)},\qquad-N\leq j,k\leq N.$

The matrix $\tilde{F}$ is of interest because the sums in Eq. 2 can be neatly
written as the matrix-vector product $\tilde{F}\underline{c}=\underline{f}$.
Therefore, the action of $\tilde{F}$ onto a vector is equivalent to evaluating
a trigonometric polynomial of degree $N$ at
$\tilde{x}_{-N},\ldots,\tilde{x}_{N}$. This can be performed in
$\mathcal{O}(N\log N)$ operations [27] and in Chebfun (a MATLAB package for
computing with functions) [8] can be implemented as follows:

     N = 1e4; alpha = 0.1; h = 2*pi/(2*N+1);
     tilde_x = (-N:N)’*h + alpha*(2*rand(2*N+1,1)-1)*h; % perturbed nodes
     c = randn(2*N+1,1);                                % trig coeffs
     Fc = exp(1i*tilde_x*N).*chebfun.nufft(c,tilde_x/(2*pi)); %\tilde{F}*c

An alternative algorithm that has even faster execution times is available in
the fiNUFFT package [5].

We now show that $\tilde{F}$ and $F$ are relatively close in the sense of
their distance in the spectral norm. Our proof follows from a similar strategy
to the proof of Kadec’s theorem [34].

######  Theorem 2.1.

Suppose that $\left|\delta_{j}\right|\leq\alpha<1/4$ for all $-N\leq j\leq N$
in Eq. 6, then

(7)
$\left\|F-\tilde{F}\right\|_{2}\leq\varphi_{\alpha}\|F\|_{2},\qquad\varphi_{\alpha}=1-\cos(\pi\alpha)+\sin(\pi\alpha),$

where $\|\cdot\|_{2}$ is the spectral norm.

######  Proof 2.2.

Since $\|F-\tilde{F}\|_{2}=\|F^{\top}-\tilde{F}^{\top}\|_{2}$ and
$\|F\|_{2}=\|F^{\top}\|_{2}$, where superscript ‘$\top$’ denotes the matrix
transpose, we prove that
$\|F^{\top}-\tilde{F}^{\top}\|_{2}\leq\varphi_{\alpha}\|F^{\top}\|_{2}$. Let
$\underline{c}=(c_{-N},\ldots,c_{N})^{\top}$ be a vector of unit length so
that $\|\underline{c}\|_{2}=1$. We have

(8)
$(F^{\top}-\tilde{F}^{\top})\underline{c}=\sum_{j=-N}^{N}e^{-ij\underline{t}}\circ\left(\underline{\mathbbm{1}}-e^{-i\delta_{j}\underline{t}}\right)c_{j},$

where $\underline{t}=(t_{-N},\ldots,t_{N})^{\top}$ with $t_{k}=2\pi k/(2N+1)$,
‘$\circ$’ is the Hadamard product denoting entry-by-entry multiplication
between vectors, $\underline{\mathbbm{1}}$ is the column vector of all ones,
and the exponential function of a vector is applied entrywise. As in [34], for
each $-N\leq j\leq N$, we write

$\displaystyle\underline{\mathbbm{1}}-e^{-i\delta_{j}\underline{t}}$
$\displaystyle=\underbrace{\left(1-\frac{\sin(\pi\delta_{j})}{\pi\delta_{j}}\right)\underline{\mathbbm{1}}}_{A_{j}}+\underbrace{\sum_{\ell=1}^{\infty}\frac{(-1)^{\ell}2\delta_{j}\sin(\pi\delta_{j})}{\pi(\ell^{2}-\delta_{j}^{2})}\cos(\ell\underline{t})}_{B_{j}}$
$\displaystyle\qquad-\underbrace{i\sum_{\ell=1}^{\infty}\frac{(-1)^{\ell}2\delta_{j}\cos(\pi\delta_{j})}{\pi(\ell-1/2)^{2}-\pi\delta_{j}^{2}}\sin\left(\left(\ell-\frac{1}{2}\right)\underline{t}\right)}_{C_{j}},$

where $\sin$ and $\cos$ of a vector is applied entrywise. By substituting this
expression into Eq. 8, we can bound
$\|(F^{\top}-\tilde{F}^{\top})\underline{c}\|_{2}$ by separately bounding
$\sum_{j=-N}^{N}A_{j}\circ e^{-ij\underline{t}}c_{j},\sum_{j=-N}^{N}B_{j}\circ
e^{-ij\underline{t}}c_{j},$ and $\sum_{j=-N}^{N}C_{j}\circ
e^{-ij\underline{t}}c_{j}$.

Bounding $\mathbf{\sum_{j=-N}^{N}A_{j}\circ e^{-ij\underline{t}}c_{j}}$. Since
$\left|\delta_{j}\right|\leq\alpha<1/4$, from elementary calculus, we have
that $\max_{j}\left(1-\sin(\pi\delta_{j})/(\pi\delta_{j})\right)\leq
1-\sin(\pi\alpha)/(\pi\alpha)$. Also, since
$\\{e^{-ij\underline{t}}\\}_{j=-N}^{N}$ is an orthogonal set and $A_{j}$ is a
constant vector, $\\{A_{j}\circ e^{-ij\underline{t}}c_{j}\\}_{j=-N}^{N}$ is a
set of orthogonal vectors. Hence, by the Pythagorean Theorem, we have

(9) $\displaystyle\left\lVert\sum_{j=-N}^{N}A_{j}\circ
e^{-ij\underline{t}}c_{j}\right\rVert_{2}^{2}\\!=\\!\\!\sum_{j=-N}^{N}\\!\\!\left\lVert
A_{j}\circ
e^{-ij\underline{t}}c_{j}\right\rVert_{2}^{2}\leq\\!\left(1-\frac{\sin(\pi\alpha)}{\pi\alpha}\right)^{2}\\!\\!\\!\\!\sum_{j=-N}^{N}\\!\\!\left\lVert
e^{-ij\underline{t}}c_{j}\right\rVert_{2}^{2}$
$\displaystyle\qquad\qquad\qquad=\left(1-\frac{\sin(\pi\alpha)}{\pi\alpha}\right)^{2}\left\lVert\sum_{j=-N}^{N}e^{-ij\underline{t}}c_{j}\right\rVert_{2}^{2}\leq\left(1-\frac{\sin(\pi\alpha)}{\pi\alpha}\right)^{2}\\!\|F^{\top}\|_{2}^{2}.$

Bounding $\mathbf{\sum_{j=-N}^{N}B_{j}\circ e^{-ij\underline{t}}c_{j}}$. Let
$D_{\ell,j}=\left((-1)^{\ell}2\delta_{j}\sin(\pi\delta_{j})\right)/\left(\pi(\ell^{2}-\delta_{j}^{2})\right)$.
Since $|D_{\ell,j}|=\mathcal{O}(\ell^{-2})$ and $\left|\cos(\ell
t_{k})e^{-ijt_{k}}c_{j}\right|\leq 1$, we have by the Fubini–Tonelli Theorem
that

$\sum_{j=-N}^{N}\\!\\!B_{j}\circ
e^{-ij\underline{t}}c_{j}=\\!\\!\sum_{j=-N}^{N}\\!\\!\left[\sum_{\ell=1}^{\infty}D_{\ell,j}\cos(\ell\underline{t})\right]\circ
e^{-ij\underline{t}}c_{j}=\sum_{\ell=1}^{\infty}\sum_{j=-N}^{N}\\!\\!\left[D_{\ell,j}\cos(\ell\underline{t})\circ
e^{-ij\underline{t}}c_{j}\right].$

Define
$\underline{v}^{\ell}=\sum_{j=-N}^{N}\left[D_{\ell,j}\cos(\ell\underline{t})\circ
e^{-ij\underline{t}}c_{j}\right]$. Since $|\cos(\ell
t_{k})e^{-ijt_{k}}c_{j}|\leq 1$, there exists $C>0$, independent of $\ell$,
such that $\left\lVert\underline{v}^{\ell}\right\rVert_{2}\leq
C\max_{j}\left|D_{\ell,j}\right|$. Since
$\max_{j}\left|D_{\ell,j}\right|=\mathcal{O}(\ell^{-2})$, we have
$\sum_{\ell=1}^{\infty}\left\lVert\underline{v}^{\ell}\right\rVert_{2}<\infty$.
Hence, by Minkowski’s inequality for integrals, we have
$\left\lVert\sum_{\ell=1}^{\infty}\underline{v}^{\ell}\right\rVert_{2}\leq\sum_{\ell=1}^{\infty}\left\lVert\underline{v}^{\ell}\right\rVert_{2}$
and

$\displaystyle\left\lVert\sum_{j=-N}^{N}B_{j}\circ
e^{-ij\underline{t}}c_{j}\right\rVert_{2}$
$\displaystyle=\left\lVert\sum_{\ell=1}^{\infty}\underline{v}^{\ell}\right\rVert_{2}\leq\sum_{\ell=1}^{\infty}\left\lVert\underline{v}^{\ell}\right\rVert_{2}=\sum_{\ell=1}^{\infty}\left\lVert\cos(\ell\underline{t})\circ\sum_{j=-N}^{N}D_{\ell,j}e^{-ij\underline{t}}c_{j}\right\rVert_{2}$
$\displaystyle\stackrel{{\scriptstyle(*)}}{{\leq}}\sum_{\ell=1}^{\infty}\left\lVert\cos(\ell\underline{t})\right\rVert_{\infty}\left\lVert\sum_{j=-N}^{N}D_{\ell,j}e^{-ij\underline{t}}c_{j}\right\rVert_{2}$
$\displaystyle\stackrel{{\scriptstyle(**)}}{{\leq}}\sum_{\ell=1}^{\infty}\max_{j}\left|D_{\ell,j}\right|\left\lVert\sum_{j=-N}^{N}e^{-ij\underline{t}}c_{j}\right\rVert_{2}\leq\|F^{\top}\|_{2}\sum_{\ell=1}^{\infty}\max_{j}\left|D_{\ell,j}\right|,$

where ($*$) follows by applying Hölder’s inequality and ($**$) holds due to
the orthogonality of $\\{e^{-ij\underline{t}}c_{j}\\}_{j=-N}^{N}$. Since
$\sum_{\ell=1}^{\infty}2\alpha/[\pi(\ell^{2}-\alpha^{2})]$ is the partial
fraction expansion of $[1/(\pi\alpha)-\cot(\pi\alpha)]$ and $|D_{\ell,j}|$ is
maximized when $|\delta_{j}|=\alpha$, we have

$\sum_{\ell=1}^{\infty}\max_{j}\left|D_{\ell,j}\right|\leq\sum_{\ell=1}^{\infty}\frac{2\alpha\sin(\pi\alpha)}{\pi(\ell^{2}-\alpha^{2})}=\frac{\sin(\pi\alpha)}{\pi\alpha}-\cos(\pi\alpha).$

Hence, we find that

(10) $\left\lVert\sum_{j=-N}^{N}B_{j}\circ
e^{-ij\underline{t}}c_{j}\right\rVert_{2}\leq\left(\frac{\sin(\pi\alpha)}{\pi\alpha}-\cos(\pi\alpha)\right)\|F^{\top}\|_{2}.$

Bounding $\mathbf{\sum_{j=-N}^{N}C_{j}\circ e^{-ij\underline{t}}c_{j}}$. Let
$E_{\ell,j}\\!=\\!\\!\left((-1)^{\ell}2\delta_{j}\\!\cos(\pi\delta_{j})\right)\\!/\\!\\!\left(\pi[(\ell-1/2)^{2}\\!-\delta_{j}^{2}]\right)$.
Then, we have that

$\left\lVert\sum_{j=-N}^{N}\\!\\!C_{j}\circ
e^{-ij\underline{t}}c_{j}\right\rVert_{2}\\!\\!\leq\\!\sum_{\ell=1}^{\infty}\left\lVert\sin\\!\left(\\!\left(\ell-\frac{1}{2}\right)\\!\underline{t}\right)\\!\circ\\!\\!\\!\sum_{j=-N}^{N}\\!\\!E_{\ell,j}e^{-ij\underline{t}}c_{j}\right\rVert_{2}\\!\\!\\!\leq\\!\|F^{\top}\|_{2}\\!\sum_{\ell=1}^{\infty}\\!\max_{j}\left|E_{\ell,j}\right|.$

Since $\sum_{\ell=1}^{\infty}2\alpha/(\pi[(\ell-1/2)^{2}-\alpha^{2}])$ is the
partial fraction expansion of $\tan(\pi\alpha)$ and $|E_{\ell,j}|$ is
maximized when $|\delta_{j}|=\alpha$, we find that

$\sum_{\ell=1}^{\infty}\max_{j}\left|E_{\ell,j}\right|\leq\sum_{\ell=1}^{\infty}\frac{2\alpha\cos(\pi\alpha)}{\pi((\ell-1/2)^{2}-\alpha^{2})}=\sin(\pi\alpha).$

Hence, we conclude that

(11) $\left\lVert\sum_{j=-N}^{N}C_{j}\circ
e^{-ij\underline{t}}c_{j}\right\rVert_{2}\leq\sin(\pi\alpha)\|F^{\top}\|_{2}.$

The statement of the theorem follows by combining Eq. 9, Eq. 10, and Eq. 11.

Since $F/\sqrt{2N+1}$ is a unitary matrix, we find that
$\|F\|_{2}=\sqrt{2N+1}$. Therefore, Theorem 2.1 shows that
$\|\tilde{F}-F\|_{2}\leq\varphi_{\alpha}\sqrt{2N+1}$. It is not immediately
obvious that Theorem 2.1 is a discrete analogue of Kadec’s theorem. We can
write $\tilde{F}=F+E$ with $\|E\|_{2}\leq\varphi_{\alpha}\|F\|_{2}$, so we
have

(12) $\|\tilde{F}\|_{2}\leq(1+\varphi_{\alpha})\|F\|_{2}.$

Moreover, since all the singular values of $F$ are $\sqrt{2N+1}$, for
$0\leq\alpha<1/4$ (as this ensures that $\varphi_{\alpha}<1$) we find the
following bound on the inverse NUDFT by Weyl’s inequality:

(13) $\|\tilde{F}^{-1}\|_{2}\leq\frac{1}{\left\lVert
F\right\rVert_{2}-\left\lVert
E\right\rVert_{2}}\leq\frac{1}{(1-\varphi_{\alpha})\|F\|_{2}}.$

Hence, Theorem 2.1 gives the following discrete version of Kadec’s theorem,
which is an analogue of the frame bound for Riesz bases in sampling theory.

######  Corollary 2.3.

Under the same assumptions as Theorem 2.1, we have

(14)
$(1-\varphi_{\alpha})^{2}\|\underline{c}\|_{2}^{2}\leq\frac{1}{2N+1}\|\tilde{F}\underline{c}\|_{2}^{2}\leq(1+\varphi_{\alpha})^{2}\|\underline{c}\|_{2}^{2},\qquad\underline{c}\in\mathbb{C}^{2N+1},$

where $\varphi_{\alpha}$ is given in Eq. 7.

######  Proof 2.4.

The inequalities follow immediately from Eq. 12, Eq. 13, and the definition of
the spectral norm.

When $\alpha\geq 1/4$, we believe that there is no constant $C_{1}>0$ that is
independent of $N$ such that
$C_{1}\|\underline{c}\|_{2}^{2}\leq\tfrac{1}{2N+1}\|\tilde{F}\underline{c}\|_{2}^{2}$.
This is because Levinson has showed that $\left\\{e^{i\lambda_{k}x}\right\\}$
for $k\in\mathbb{Z}$ does not always form a Riesz basis when
$|\lambda_{k}-k|\geq 1/4$ [18]. Instead, since $\tilde{F}^{-1}$ exists for any
perturbed nodes with $1/4\leq\alpha<1/2$ (as $\tilde{F}$ is a Vandermonde
matrix), there must be a $C_{1}>0$ that depends on $N$ such that
$C_{1}\rightarrow 0$ as $N\rightarrow\infty$. Therefore, $\alpha=1/4$ is less
of a significant threshold in the discrete setting than in sampling theory.
From [2, Chapt. 4], it is likely that one can show that
$C_{1}=\Omega(N^{-4\alpha})$;111For two functions $g_{1}(N)$ and $g_{2}(N)$,
one writes $g_{1}(N)=\Omega(g_{2}(N))$ if there is a constant $C>0$ that is
independent of $N$ such that $g_{1}(N)\geq Cg_{2}(N)$ for all $N$. however,
this is not asymptotically tight. We do not know how to improve the lower
bounds on $C_{1}$ for $1/4\leq\alpha<1/2$.

###  2.1 The condition number of a NUDFT matrix

Of course, Eq. 14 also has something to say about the condition number of the
NUDFT matrix in Eq. 6. While there are many different versions of a NUDFT
matrix, we expect that similar bounds can be derived for their condition
numbers.

######  Corollary 2.5.

Under the same assumptions as Theorem 2.1, the condition number of $\tilde{F}$
can be bounded independently of $N$:

$\kappa_{2}(\tilde{F})=\left\lVert\tilde{F}\right\rVert_{2}\left\lVert\tilde{F}^{-1}\right\rVert_{2}\leq\frac{1+\varphi_{\alpha}}{1-\varphi_{\alpha}},$

where $\varphi_{\alpha}$ is given in Eq. 7.

######  Proof 2.6.

The bound follows immediately from Eq. 12 and Eq. 13.

Many fast algorithms for computing $\tilde{F}^{-1}\underline{f}$ rely on a
Krylov solver and an $\mathcal{O}(N\log N)$ complexity matrix-vector product
for $\smash{\tilde{F}}$ and $\smash{\tilde{F}^{\top}}$ [9]. The number of
required iterations of the Krylov solver depends on $\kappa_{2}(\tilde{F})$.
Corollary 2.5 shows that for perturbed equally spaced grids with a fixed
constant $0\leq\alpha<1/4$, the number of iterations is independent of $N$.
This means that these Krylov-based algorithms for computing
$\tilde{F}^{-1}\underline{f}$ only require $\mathcal{O}(N\log N)$ operations
when $0\leq\alpha<1/4$, which theoretically justifies previous numerical
observations [27, Fig. 4]. In Chebfun [8], a Krylov-based inverse NUDFT is
implemented in the chebfun.inufft command [27]:

     N = 1e4; alpha = 0.1; h = 2*pi/(2*N+1);
     tilde_x = (-N:N)’*h + alpha*(2*rand(2*N+1,1)-1)*h; % perturbed nodes
     fx = randn(2*N+1,1);                               % func samples
     cfs = chebfun.inufft(exp(-1i*tilde_x*N).*fx,tilde_x/(2*pi));%trig cfs

However, we believe that Krylov-based algorithms do not have an
$\mathcal{O}(N\log N)$ complexity when $1/4\leq\alpha<1/2$. Instead, in the
regime $1/4\leq\alpha<1/2$, other $\mathcal{O}(N\log N)$ algorithms can be
used for the inverse NUDFT [10, Sect. 4], though we are not aware of any
publicly available code.

###  2.2 Marcinkiewicz–Zygmund inequalities

Equation 14 can also be rephrased as an MZ inequality at perturbed nodes.
While more general MZ inequalities are available in the literature (see [21])
and will be discussed in Section 5, the inequalities here have explicit
bounds.

######  Corollary 2.7.

Let $\tilde{x}_{-N},\ldots,\tilde{x}_{N}$ be $\alpha$-perturbed nodes with
$0\leq\alpha<1/4$. The following MZ inequalities hold:

(15)
$\frac{(1\\!-\\!\varphi_{\alpha})^{2}}{2\pi}\int_{-\pi}^{\pi}\\!|q(x)|^{2}dx\leq\sum_{j=-N}^{N}\\!\frac{\left|q(\tilde{x}_{j})\right|^{2}}{2N\\!+\\!1}\leq\frac{(1\\!+\\!\varphi_{\alpha})^{2}}{2\pi}\int_{-\pi}^{\pi}\\!|q(x)|^{2}dx,\quad
q\\!\in\\!\mathcal{T}_{N},$

where $\varphi_{\alpha}$ is given in Eq. 7.

######  Proof 2.8.

Let $q(x)=\sum_{k=-N}^{N}c_{k}e^{ikx}=\sum_{k=-N}^{N}c_{-k}e^{-ikx}$ be a
trigonometric polynomial in $\mathcal{T}_{N}$. Note that we have the matrix
equation $\tilde{F}\underline{c}=\underline{q}$ with $\tilde{F}$ in Eq. 6,
where $\underline{c}=(c_{N},\ldots,c_{-N})^{\top}$ and
$\underline{q}=(q(\tilde{x}_{-N}),\ldots,q(\tilde{x}_{N}))^{\top}$. The result
follows from Eq. 14, the definition of $\|\tilde{q}\|_{2}^{2}$, and Parseval’s
Theorem, i.e.,
$\left\lVert\underline{c}\right\rVert_{2}^{2}=\tfrac{1}{2\pi}\int_{-\pi}^{\pi}|q(x)|^{2}dx$.

The MZ inequalities in Eq. 15 confirms that the 2-norm Lebesgue constant,
which is denoted by $\tilde{\Lambda}_{2N+1}^{(2)}$ (see [2, sect. 3.4.1]), is
bounded in $N$ when $0\leq\alpha<1/4$. In particular, we have
$\tilde{\Lambda}_{2N+1}^{(2)}\leq 1/(1-\varphi_{\alpha})$ for all
$0\leq\alpha<1/4$ and integer $N$. The MZ inequalities are also useful for
studying quadrature weights and the rate of convergence of quadrature rules
and interpolation at perturbed nodes [15, 6, 19]. By calculating the explicit
constants in these bounds, we can give explicit error estimates, as opposed to
asymptotic convergence bounds (see Sections 3 and 4).

##  3 Interpolation at unevenly spaced samples

At equally spaced nodes, trigonometric interpolation enjoys rapid convergence
to functions. Suppose that $f:[-\pi,\pi)\rightarrow\mathbb{C}$ is a continuous
periodic function and that $q_{N}(x)$ is its trigonometric interpolant in
$\mathcal{T}_{N}$ at the equally spaced nodes $x_{j}=jh$ for $-N\leq j\leq N$,
where $h=2\pi/(2N+1)$. Then, if $f$ is $\sigma\geq 1$ times differentiable and
$f^{(\sigma)}$ is of bounded variation $V$ on $[-\pi,\pi)$, then [33, Thm.
4.2]

(16) $\|f-q_{N}\|_{L^{\infty}}\leq\frac{2V}{\pi\sigma N^{\sigma}},$

where throughout this paper,
$\left\lVert\cdot\right\rVert_{L^{r}}=\left\lVert\cdot\right\rVert_{L^{r}([-\pi,\pi))}$
is the standard $L^{r}([-\pi,\pi))$ norm induced by the Lebesgue measure on
$[-\pi,\pi)$. While if $f$ is analytic with $|f(z)|\leq M$ in the open strip
of half-width $\rho_{0}>0$ along the real axis in the complex plane, one has
exponential convergence [33, Thm. 4.2]:

(17) $\|f-q_{N}\|_{L^{\infty}}\leq\frac{4Me^{-\rho_{0}N}}{e^{\rho_{0}}-1}.$

One wonders if trigonometric interpolants at perturbed equally spaced nodes
enjoy the same kind of rapid convergence. When $\alpha<1/4$, we can show that
one loses at most a factor of $\sqrt{N}$ in the convergence rate via the MZ
inequality in Eq. 15.

######  Theorem 3.1.

Let $f:[-\pi,\pi)\rightarrow\mathbb{C}$ be a continuous periodic function and
$0\leq\alpha<1/4$. For any $\alpha$-perturbed nodes of size $2N+1$, if
$\tilde{q}_{N}\in\mathcal{T}_{N}$ is the corresponding interpolant of $f$,
then

$\left\lVert
f-\tilde{q}_{N}\right\rVert_{L^{\infty}}\leq\left(1+\frac{\sqrt{2N+1}}{\cos(\pi\alpha)-\sin(\pi\alpha)}\right)\min_{q\in\mathcal{T}_{N}}\left\lVert
f-q\right\rVert_{L^{\infty}}.$

######  Proof 3.2.

First, note that for any trigonometric polynomial $q\in\mathcal{T}_{N}$ we
have by Young’s inequality and Parseval’s Theorem that

$\left\lVert q\right\rVert_{L^{\infty}}=\frac{1}{2\pi}\left\lVert
p*q\right\rVert_{L^{\infty}}\leq\frac{1}{2\pi}\left\lVert
p\right\rVert_{L^{2}}\left\lVert
q\right\rVert_{L^{2}}=\sqrt{\frac{2N+1}{2\pi}}\left\lVert
q\right\rVert_{L^{2}},$

where $(p\ast q)(x)=\int_{-\pi}^{\pi}p(x-s)q(s)ds$ and
$p(x)=\sum_{j=-N}^{N}e^{ijx}$. If $\tilde{x}_{-N},\ldots,\tilde{x}_{N}$ are
the perturbed nodes and $q$ is any polynomial in $\mathcal{T}_{N}$, then, by
Eq. 15, we have

$\displaystyle\left\lVert f-\tilde{q}_{N}\right\rVert_{L^{\infty}}$
$\displaystyle\leq\left\lVert f-q\right\rVert_{L^{\infty}}+\left\lVert
q-\tilde{q}_{N}\right\rVert_{L^{\infty}}$ $\displaystyle\leq\left\lVert
f-q\right\rVert_{L^{\infty}}+\sqrt{\frac{2N+1}{2\pi}}\left\lVert
q-\tilde{q}_{N}\right\rVert_{L^{2}}$ $\displaystyle\leq\left\lVert
f-q\right\rVert_{L^{\infty}}+\frac{1}{1-\varphi_{\alpha}}\sqrt{\sum_{j=-N}^{N}\left|q(\tilde{x}_{j})-f(\tilde{x}_{j})\right|^{2}}$
$\displaystyle\leq\left(1+\frac{1}{1-\varphi_{\alpha}}\sqrt{2N+1}\right)\left\lVert
f-q\right\rVert_{L^{\infty}},$

where $\varphi_{\alpha}$ is given by Eq. 7. The result follows by selecting
$q$ to be the best fit polynomial in $\mathcal{T}_{N}$ to $f$ in
$\|\cdot\|_{L^{\infty}}$ and noting that
$1-\varphi_{\alpha}=\cos(\pi\alpha)-\sin(\pi\alpha)$.

Using Eq. 16 and Eq. 17 along with the same smoothness conditions, we find
that for any $0\leq\alpha<1/4$ and $\rho<\rho_{0}$, we have

(18)
$\|f-\tilde{q}_{N}\|_{L^{\infty}}=\mathcal{O}(N^{1/2-\sigma}),\quad\|f-\tilde{q}_{N}\|_{L^{\infty}}=\mathcal{O}(e^{-\rho
N}),$

respectively. This means that with unevenly spaced samples, one can safely use
$\tilde{q}_{N}$ as a surrogate for $f$, and the price to pay for perturbed
samples is minimal when $\alpha$ is small. In Theorem 5.3, we show that the
convergence rates in Eq. 18 can be slightly improved. Convergence results of
interpolants at $\alpha$-perturbed nodes in the $L^{2}$ norm are also possible
to derive from the MZ inequality in Eq. 15 by using [15, Thm 2.2].

One can easily do unevenly spaced trigonometric interpolation in Chebfun via
the chebfun.interp1 command. For example, below we compute a trigonometric
polynomial that interpolates $\cos(x)$ at $\alpha$-perturbed nodes:

     N = 1e2; alpha = 0.1; h = 2*pi/(2*N+1);
     tilde_x = (-N:N)’*h + alpha*(2*rand(2*N+1,1)-1)*h; % perturbed nodes
     qN = chebfun.interp1(tilde_x, cos(tilde_x), ’periodic’, [-pi pi]);

Instead of using an optimal complexity algorithm based on the NUDFT, this code
uses the so-called trigonometric barycentric formula [33]. This approach has
some advantages as there is a convenient way to update the formula when a new
interpolation node becomes available.

##  4 Quadrature at unevenly spaced samples

Another important computational task is approximating integrals from knowledge
of function samples at unevenly spaced nodes. While the quadrature rule at
equally spaced nodes is the trapezoidal rule that enjoys perfect stability,
positive quadrature weights, and rapid convergence, we wonder how much
perturbing the nodes changes things. We are particularly interested in the
signs of the quadrature weights [13, 22], the boundedness of the absolute sum
of the quadrature weights [2, 22], and the convergence rate of quadrature
rules at perturbed nodes [3, 30, 15].

###  4.1 Are quadrature weights at perturbed nodes nonnegative?

It is highly desirable to use quadrature rules for which all the weights are
non-negative as such rules are perfectly stable. The absolute condition number
of the integral $\int_{-\pi}^{\pi}f(x)dx$ is $2\pi$, while the absolute
condition number of the quadrature rule in Eq. 4 is
$\sum_{j=-N}^{N}|\tilde{w}_{j}|$. Since Eq. 4 is exact, we know that
$\smash{\sum_{j=-N}^{N}\tilde{w}_{j}=\int_{-\pi}^{\pi}1dx=2\pi}$ and hence the
quadrature rule is perfectly stable when $\tilde{w}_{j}\geq 0$ for $-N\leq
j\leq N$. Since the trapezoidal rule has all nonnegative weights, one might
expect that quadratures at $\alpha$-perturbed nodes also have non-negative
weights for sufficiently small $\alpha>0$. Surprisingly, we find that this is
not case and now give a quadrature rule at $\alpha$-perturbed nodes with a
negative weight for any fixed $\alpha>0$.

For any $\alpha>0$ and integer $N$, consider the following perturbed grid
where the nodes are maximally perturbed in an alternating fashion (see Fig.
2):

(19) $\tilde{x}_{j}=\begin{cases}(j-\alpha)h,&-N\leq j\leq-1,j=\text{
even},\\\ (j+\alpha)h,&-N\leq j\leq-1,j=\text{ odd},\\\ 0,&j=0,\\\
(j-\alpha)h,&1\leq j\leq N,j=\text{ odd},\\\ (j+\alpha)h,&1\leq j\leq
N,j=\text{ even},\\\ \end{cases}\qquad h=\frac{2\pi}{2N+1}.$

$-\pi$$\pi$$0$$h$$2h$$3h$$4h$$-h$$-2h$$-3h$$-4h$$h=\frac{2\pi}{9}$ Figure 2:
For any $\alpha>0$ and sufficiently large $N$, a quadrature rule at
$\alpha$-perturbed nodes with negative weights can be constructed by maximally
perturbing equally spaced nodes in an alternating fashion, as depicted.

Associated with the perturbed nodes in Eq. 19 is an exact quadrature rule such
that

(20)
$\int_{-\pi}^{\pi}q(x)dx=\sum_{j=-N}^{N}\tilde{w}_{j}q(\tilde{x}_{j}),\qquad
q\in\mathcal{T}_{N}.$

We now show that $\tilde{w}_{0}$ is negative if $N$ is taken to be
sufficiently large. This means that the quadrature rule in Eq. 20 is
unfortunately not perfectly stable.

######  Theorem 4.1.

For any $\alpha>0$ and sufficiently large even integer $N$, the quadrature
weight $\tilde{w}_{0}$ in Eq. 20 associated with the perturbed nodes in Eq. 19
is negative.

######  Proof 4.2.

Let $\ell_{0}$ be the trigonometric Lagrange polynomial for $\tilde{x}_{0}$
associated with the perturbed nodes in Eq. 19, i.e., [16]

(21) $\ell_{0}(x)=\prod_{j=-N,j\neq
0}^{N}\frac{\sin\left(\frac{x-\tilde{x}_{j}}{2}\right)}{\sin\left(\frac{\tilde{x}_{0}-\tilde{x}_{j}}{2}\right)}.$

Note that $\ell_{0}\in\mathcal{T}_{N}$ satisfies $\ell_{0}(\tilde{x}_{j})=0$
for $-N\leq j\leq N$ and $j\neq 0$ as well as $\ell_{0}(\tilde{x}_{0})=1$.
Therefore, using the fact that Eq. 20 is an exact quadrature rule, we have

$\tilde{w}_{0}=\sum_{j=-N}^{N}\tilde{w}_{j}\ell_{0}(\tilde{x}_{j})=\int_{-\pi}^{\pi}\ell_{0}(x)dx=\frac{2\pi}{2N+1}\sum_{j=-N}^{N}\ell_{0}(jh),$

where in the last equality we used the fact that the trapezoidal rule at
equally spaced nodes is exact. Now, we have

$\tilde{w}_{0}=\frac{2\pi}{2N+1}\left(1+\sum_{\begin{subarray}{c}j=-N\\\ j\neq
0\end{subarray}}^{N}\ell_{0}(jh)\right).\\\ $

Since $N$ is an even integer, by Lemma A.1 and the fact that
$(2/\pi)x\leq\sin(x)\leq x$ for $x\in[0,\pi/2]$, we have

$\displaystyle\sum_{\begin{subarray}{c}j=-N\\\ j\neq
0\end{subarray}}^{N}\ell_{0}(jh)\leq-2\sum_{j=1}^{N}\frac{\sin\left(\alpha
h/2\right)}{\sin\left((jh+\alpha
h)/2\right)}\leq-\frac{4}{\pi}\sum_{j=1}^{N}\frac{\alpha h}{jh+\alpha
h}\rightarrow-\infty$

as $N\rightarrow\infty$. Hence, for a sufficiently large even $N$, we have
$\tilde{w}_{0}<0$.

Theorem 4.1 tells us that, no matter how small, a perturbation of equally
spaced nodes can cause the corresponding quadrature rule to have a negative
weight. However, when $\alpha$ is small, $N$ must be extremely large for this
to happen for the perturbed nodes in Eq. 19. In fact, the proof in Theorem 4.1
requires that $N$ is even and so large that

$1-\frac{4\alpha}{\pi}\sum_{j=1}^{N}\frac{1}{j+\alpha}<0,$

which is ensured when $N\geq\exp({\tfrac{\pi}{4\alpha}+\tfrac{1}{2}})$.222Note
that $\sum_{j=1}^{N}1/(j+\alpha)>\sum_{j=1}^{N}1/(j+1)>\log(N)-1/2$. Thus,
while quadrature at $\alpha$-perturbed nodes can have negative weights when
$\alpha=1/5$ and $N$ is an even integer $\geq 83$, for $\alpha=10^{-2}$
negative weights are only ensured when $N$ is even and $N>2.12\times 10^{34}$!
One may wonder if there are more devilish perturbations than in Eq. 19, which
guarantee negative weights for much smaller $N$. In Appendix B, we show that
there are no such perturbations in the sense that it is required that
$\log(N)=\Omega(1/\alpha)$ to have a quadrature rule at $\alpha$-perturbed
nodes with a negative weight. The analysis in Appendix B is quite explicit.
For example, we know that when $\alpha=10^{-2}$, all quadrature rules at
$\alpha$-perturbed nodes with $N<9.4\times 10^{6}$ have positive weights. So,
when $\alpha$ is small, such quadrature rules are perfectly stable for all
practical $N$; however, for large perturbations one does begin to get
concerned about their potential numerical instability.

###  4.2 Bounding the absolute sum of the quadrature weights

To analyze the stability of quadrature rules at $\alpha$-perturbed nodes
further, we take a look at the absolute sum of the quadrature weights as this
is the absolute condition number of computing the quadrature rule. Since we
are considering exact quadrature rules, there is a close connection between
the NUDFT matrix, $\tilde{F}$, in Eq. 6 and quadrature weights. In fact, since
$e^{ijx}\in\mathcal{T}_{N}$ for $-N\leq j\leq N$, the quadrature rule must
integrate them exactly. This means that the following linear system must be
satisfied:

(22)
$\tilde{F}^{\top}\underline{\tilde{w}}=2\pi\underline{e}_{0},\qquad\underline{e}_{0}=\left(0,\ldots,0,1,0,\ldots,0\right)^{\top}$

where $\underline{\tilde{w}}=(\tilde{w}_{-N},\ldots,\tilde{w}_{N})^{\top}$ is
the vector of quadrature weights. This means that the quadrature weights
associated with $\alpha$-perturbed nodes are simple to compute:

      N = 1e3; alpha = 0.1; h = 2*pi/(2*N+1);
      tilde_x = (-N:N)’*h + alpha*(2*rand(2*N+1,1)-1)*h; % perturbed nodes
      tF = exp(-1i*tilde_x*(-N:N));                      % NUDFT matrix
      e0 = zeros(2*N+1,1); e0(N+1)=1; w = tF’\(2*pi*e0); % quad wts

There are also $\mathcal{O}(N\log N)$ algorithms for solving the linear system
in Eq. 22 as it is equivalent to an inverse NUDFT (type I) [27].

We can also use the results in Section 2 to get a bound on
$\sum_{j=-N}^{N}|\tilde{w}_{j}|$.

######  Theorem 4.3.

Let $0\leq\alpha<1/4$ and $N$ be a positive integer. For any quadrature rule
at $\alpha$-perturbed nodes that is exact for $\mathcal{T}_{N}$, we have

$\sum_{j=-N}^{N}\left|\tilde{w}_{j}\right|\leq\frac{2\pi}{\cos(\pi\alpha)-\sin(\pi\alpha)},$

where $\tilde{w}_{-N},\ldots,\tilde{w}_{N}$ are the quadrature rule’s weights.

######  Proof 4.4.

Let $q(x)=\sum_{k=-N}^{N}c_{k}e^{ikx}$ be the trigonometric polynomial in
$\mathcal{T}_{N}$ such that

$q(\tilde{x}_{j})=\text{sgn}(\tilde{w}_{j}),\qquad-N\leq j\leq N,$

where $\text{sgn}(w)=-1$ if $w<0$ and $\text{sgn}(w)=1$ for $w\geq 0$. Then,
by Corollary 2.7 and Hölder’s inequality, we have

$\displaystyle\sum_{j=-N}^{N}\left|\tilde{w}_{j}\right|$
$\displaystyle=\sum_{j=-N}^{N}\tilde{w}_{j}q(\tilde{x}_{j})=\int_{-\pi}^{\pi}q(x)dx\leq\int_{-\pi}^{\pi}|q(x)|dx\leq\sqrt{2\pi}\left(\int_{-\pi}^{\pi}|q(x)|^{2}dx\right)^{1/2}$
$\displaystyle\leq\frac{\sqrt{2\pi}}{\cos(\pi\alpha)-\sin(\pi\alpha)}\sqrt{\frac{2\pi}{2N+1}\sum_{j=-N}^{N}\left|q(\tilde{x}_{j})\right|^{2}}=\frac{2\pi}{\cos(\pi\alpha)-\sin(\pi\alpha)}.$

While quadrature rules at $\alpha$-perturbed nodes can have negative weights
for any $\alpha>0$, Theorem 4.3 shows that they are relatively stable for
small $\alpha$. For example, when $\alpha=1/5$, while there is a negative
weight for $N\geq 83$ with the nodes in Eq. 19, the condition number of the
quadrature rule is $\leq 4.53\times(2\pi)$.

###  4.3 Convergence rates of quadrature rules at perturbed nodes

By Pólya’s celebrated theorem [24], Theorem 4.3 tells us that the quadrature
rule associated with perturbed nodes when $0\leq\alpha<1/4$ converges when the
integrand is continuous. That is, for any continuous periodic function
$f:[-\pi,\pi)\rightarrow\mathbb{C}$ we have

$\tilde{I}_{N}=\sum_{j=-N}^{N}\tilde{w}_{j}f(\tilde{x}_{j})\rightarrow
I=\int_{-\pi}^{\pi}f(x)dx\quad\text{ as }\quad N\rightarrow\infty$

provided that $|\tilde{x}_{j}-jh|<\alpha h$ for $-N\leq j\leq N$ and
$0\leq\alpha<1/4$, where $h=2\pi/(2N+1)$. In fact, together with [15, Thm.
2.7] and Corollary 2.7, we have that

$\left|\tilde{I}_{N}(f)-I(f)\right|\leq\frac{4\pi}{\cos(\pi\alpha)-\sin(\pi\alpha)}\min_{q\in\mathcal{T}_{N}}\left\lVert
f-q\right\rVert_{L^{\infty}}$

for any continuous periodic function $f$. Therefore, if $f$ is $\sigma\geq 1$
times differentiable and $f^{(\sigma)}$ is of bounded variation $V$ on
$[-\pi,\pi)$, then provided $0\leq\alpha<1/4$ (see Eq. 16),

(23)
$\left|\tilde{I}_{N}(f)-I(f)\right|\leq\frac{8V\pi}{(\cos(\pi\alpha)-\sin(\pi\alpha))\sigma}N^{-\sigma}.$

Alternatively, if $f$ is analytic with $|f(z)|\leq M$ in the open strip of
half-width $\rho_{0}>0$ along the real axis in the complex plane, we have (see
Eq. 17)

$\left|\tilde{I}_{N}(f)-I(f)\right|\leq\frac{16M\pi}{\cos(\pi\alpha)-\sin(\pi\alpha)}\frac{e^{-\rho_{0}N}}{e^{\rho_{0}}-1}.$

Theorem 1.1 of [3] also provides convergence rates on $|I-I_{N}|$ for
quadratures rules associated with perturbed nodes. While their convergence
rates hold for any $0\leq\alpha<1/2$, our rates are a strict improvement for
differentiable functions for any $0\leq\alpha<1/4$. In particular, when
$\alpha$ is close to $1/4$, the convergence rate in Eq. 23 is almost an order
of $N$ improvement.

##  5 Further consequences of MZ inequalities

MZ inequalities are closely connected to the convergence of interpolation and
quadrature. Up to now, we have only explored MZ inequalities using the $L^{2}$
norm, even though MZ inequalities in other $L^{r}$ norms are also useful for
$1\leq r\leq\infty$. The beauty of focusing on the $L^{2}$-based MZ
inequalities is that we derived explicit constants in the bounds (see Eq. 24).
However, $L^{r}$-based MZ inequalities are extensively studied and a
significant amount is known at perturbed nodes [23, 21, 20].

######  Proposition 5.1.

Fix $1\leq r<\infty$ and constants $C_{1},C_{2}>0$. For any $0<\alpha<1/2$
such that $\alpha\geq\min\\{1/(2r),(r-1)/(2r)\\}$, there exists an integer $N$
and a set of $\alpha$-perturbed nodes $\tilde{x}_{-N},\ldots,\tilde{x}_{N}$
such that the following inequalities do not hold:

(24)
$C_{1}\int_{-\pi}^{\pi}|q(x)|^{r}dx\leq\frac{1}{2N+1}\sum_{j=-N}^{N}\left|q(\tilde{x}_{j})\right|^{r}\leq
C_{2}\int_{-\pi}^{\pi}|q(x)|^{r}dx.$

Conversely, if $\alpha<\min\\{1/(2r),(r-1)/(2r)\\}$, then there exist
constants $C_{1},C_{2}>0$ (depending on $r$) such that Eq. 24 holds for all
$\alpha$-perturbed nodes and all $q\in\mathcal{T}_{N}$.

######  Proof 5.2.

A proof of this statement can be found in [21, Thm. 1.1] and [23, Thm. 5].

When $r=2$, Eq. 24 are the MZ inequalities found in Eq. 15 and we know that
one can take $C_{1}=(1-\varphi_{\alpha})^{2}/(2\pi)$ and
$C_{2}=(1+\varphi_{\alpha})^{2}/(2\pi)$. Proposition 5.1 tells us that
Corollary 2.7 is sharp in the sense that for any $\alpha>1/4$ the constants
$C_{1}$ and $C_{2}$ must depend on $N$. As $r$ varies between $1\leq
r<\infty$, the value of $\min\\{1/(2r),(r-1)/(2r)\\}$ takes the maximum value
of $1/4$ at $r=2$. This tells us that MZ inequalities cannot help us extend
our results in this paper to the $1/4\leq\alpha<1/2$ regime. On the other
hand, the failure of MZ inequalities when $1/4\leq\alpha<1/2$ does not seem to
cause problems for interpolation and quadrature when $\alpha\geq 1/4$. In
fact, for each $N$, one can find a set of $1/4$-perturbed nodes that do not
satisfy an MZ inequality for any $L^{r}$ norm but the associated exact
quadrature rule has bounded absolute sum of its weights [21]. Hence, while
$\alpha=1/4$ is a theoretically important threshold for NUDFT conditioning and
MZ inequalities, we find no indication that it is a threshold for
interpolation and quadrature, which agrees with the findings in [3].

However, we can use Proposition 5.1 to improve the rates of convergence of
interpolants at perturbed nodes when $0\leq\alpha<1/4$, and derive a
convergence rate that depends on $\alpha$ for differentiable functions.

######  Theorem 5.3.

Let $f:[-\pi,\pi)\rightarrow\mathbb{C}$ be a continuous periodic function and
$0\leq\alpha<1/4$. For any $\alpha$-perturbed nodes of size $2N+1$, let
$\tilde{q}_{N}\in\mathcal{T}_{N}$ be the corresponding interpolant of $f$.
Then, for any $\alpha<\alpha_{0}<1/2$, we have

(25) $\left\lVert
f-\tilde{q}_{N}\right\rVert_{L^{\infty}}=\mathcal{O}(N^{2{\alpha_{0}}})\min_{q\in\mathcal{T}_{N}}\left\lVert
f-q\right\rVert_{L^{\infty}}.$

######  Proof 5.4.

Without loss of generality, assume $\alpha<(1-2\alpha_{0})/2$.333If
$\alpha\geq(1-2\alpha_{0})/2$, then one can pick some $\alpha_{1}$ such that
$\alpha<\alpha_{1}<\alpha_{0}$ and $\alpha<(1-2\alpha_{1})/2$. Since Eq. 25
holds if $\alpha_{0}$ is replaced by $\alpha_{1}$, it also holds for
$\alpha_{0}$. Let $r=1/(2\alpha_{0})$ so that Eq. 24 holds and let
$r^{\prime}=1/(1-2\alpha_{0})$ so that $1/r+1/r^{\prime}=1$. For any
$q\in\mathcal{T}_{N}$, by Young’s inequality, we have

$\left\lVert q\right\rVert_{L^{\infty}}=\frac{1}{2\pi}\left\lVert
p*q\right\rVert_{L^{\infty}}\leq\frac{1}{2\pi}\left\lVert
p\right\rVert_{L^{r^{\prime}}}\left\lVert q\right\rVert_{L^{r}}\leq
C(2N+1)^{1/r}\left\lVert q\right\rVert_{L^{r}},$

where $C$ is a constant independent of $N$ and $p(x)=\sum_{j=-N}^{N}e^{ijx}$.
Here, we also used the fact that the $L^{r^{\prime}}$ norm of $p$ is
$\mathcal{O}(N^{1/r})$ [1, Lem. 2.1]. By Eq. 24, we have

$\displaystyle\left\lVert f-\tilde{q}_{N}\right\rVert_{L^{\infty}}$
$\displaystyle\leq\left\lVert f-q\right\rVert_{L^{\infty}}+\left\lVert
q-\tilde{q}_{N}\right\rVert_{L^{\infty}}$ $\displaystyle\leq\left\lVert
f-q\right\rVert_{L^{\infty}}+C(2N+1)^{1/r}\left\lVert
q-\tilde{q}_{N}\right\rVert_{L^{r}}$ $\displaystyle\leq\left\lVert
f-q\right\rVert_{L^{\infty}}+CC_{1}^{-1/r}\left(\sum_{j=-N}^{N}\left|q(\tilde{x}_{j})-f(\tilde{x}_{j})\right|^{r}\right)^{1/r}$
$\displaystyle\leq\left(1+CC_{1}^{-1/r}(2N+1)^{1/r}\right)\left\lVert
f-q\right\rVert_{L^{\infty}},$

where $C_{1}>0$ is independent of $N$. The result follows by selecting $q$ to
be the closest polynomial in $\mathcal{T}_{N}$ to $f$ in
$\|\cdot\|_{L^{\infty}}$.

By controlling the Lebesgue constant, Austin and Trefethen proved that if $f$
has $\sigma$ derivatives and $\sigma>4\alpha$, then $\left\lVert
f-\tilde{q}_{N}\right\rVert_{L^{\infty}}=\mathcal{O}(N^{4\alpha-\sigma})$ and
$\left|\tilde{I}_{N}(f)-I(f)\right|=\mathcal{O}(N^{4\alpha-\sigma})$ [3]. They
also conjectured that the factor $4\alpha$ in the exponent can be improved to
$2\alpha$. Theorem 5.3 proves that the convergence rate for interpolants is
arbitrarily close to what they conjectured as when $f$ has $\sigma$
derivatives we know that $\min_{q\in\mathcal{T}_{N}}\left\lVert
f-q\right\rVert_{L^{\infty}}=\mathcal{O}(N^{-\sigma})$. The convergence rate
for quadrature rules is even better than conjectured. (See Section 4.3.)

##  6 Oversampling with unevenly spaced samples

Most of the results in the paper so far assumed that $0\leq\alpha<1/4$ as MZ
inequalities may not hold for all $\alpha$-perturbed nodes when $\alpha\geq
1/4$ (see Proposition 5.1). In this section, we briefly discuss oversampling,
where one assumes that there are more unevenly spaced samples than the number
of coefficients in the desired trigonometric approximant. A small amount of
oversampling allows us to use MZ inequalities to extend our results to the
$1/4\leq\alpha<1/2$ regime. The oversampling regime is studied in
approximation theory [15], including the higher dimensional setting [22].
Here, we restate existing results in terms of our notation and present sharper
statements in one dimension.

Let $0\leq\alpha<1/2$ and $\varepsilon>0$ be an oversampling rate. Suppose one
has $\alpha$-perturbed samples of $f$ at
$\tilde{x}_{-N},\ldots,\tilde{x}_{N}$. Since we are oversampling, we want to
find a trigonometric polynomial of degree $\leq n$ (see Eq. 3) that “fits” the
samples of the function as best as possible, where $n$ is an integer such that
$n\leq\lfloor(1-\varepsilon)N\rfloor$. Since there is typically no hope of a
trigonometric polynomial interpolant, a common approach is to compute an
approximant by solving a least squares problem. To do this, we first construct
a tall-skinny NUDFT matrix given by

(26) $\tilde{F}_{jk}=e^{-i\tilde{x}_{j}k},\qquad-N\leq j\leq N,\quad-n\leq
k\leq n$

and then solve $\tilde{F}\underline{c}=\underline{f}$ for the vector
$\underline{c}$, where
$\underline{f}=\left(f(\tilde{x}_{-N}),\ldots,f(\tilde{x}_{N})\right)^{\top}$.
The least-squares approximant to $f$ can be formed as

(27) $\tilde{q}_{n}(x)=\sum_{k=-n}^{n}c_{k}e^{-ikx}.$

For notational consistency, we continue to assume that there is an odd number
of samples; however, all results in this section hold for an even number of
samples too.

###  6.1 Oversampled Marcinkiewicz–Zygmund inequalities

In Section 2, we saw the MZ inequality is closely related to the NUDFT
condition number via Parseval’s theorem. Below, we state the MZ inequality in
the oversampling case and then discuss its consequences for the condition
number of $\tilde{F}$ in Eq. 26.

Let $0\leq\alpha<1/2$ and $\varepsilon>0$. If
$\tilde{x}_{-N},\ldots,\tilde{x}_{N}$ are $\alpha$-perturbed nodes and
$n=\lfloor(1-\varepsilon)N\rfloor$. Then, it is easy to verify that

$\liminf_{R\rightarrow\infty}\left(\liminf_{N\rightarrow\infty}\frac{\min_{x\in[-\pi,\pi)}\left|\\{\tilde{x}_{j}\\}_{j=-N}^{N}\cap(x,x+R/n)\right|}{R}\right)\geq\frac{1}{(1-\varepsilon)\pi}.$

When this condition is satisfied, Ortega-Cerdà and Saludes [23] proved that
the MZ inequality in Eq. 24 holds for any $1\leq r<\infty$ and
$q\in\mathcal{T}_{N}$, where the constants $C_{1},C_{2}>0$ are independent of
$N,n,$ and $\tilde{x}_{j}$, but possibly depend on $\alpha,\varepsilon$, and
$r$.

###  6.2 The condition number of a rectangular NUDFT matrix

Let $\tilde{F}$ be the NUDFT matrix given in Eq. 26. Then, for any vector
$\underline{c}\in\mathbb{C}^{2n+1}$, we can rewrite Eq. 24 for $r=2$ using
Parseval’s theorem to obtain

$2\pi
C_{1}\left\lVert\underline{c}\right\rVert_{2}^{2}\leq\frac{1}{2N+1}\left\lVert\tilde{F}\underline{c}\right\rVert_{2}^{2}\leq
2\pi C_{2}\left\lVert\underline{c}\right\rVert_{2}^{2},$

where $C_{1},C_{2}>0$ are constants that only depend on $\alpha$ and
$\varepsilon$. This immediately gives us a bound on the spectral norm of
$\tilde{F}$, i.e., $\|\tilde{F}\|_{2}\leq\sqrt{2\pi C_{2}(2N+1)}$. We also
have

$\left\lVert\tilde{F}^{\dagger}\underline{f}\right\rVert_{2}^{2}\leq\frac{1}{2\pi
C_{1}(2N+1)}\left\lVert\tilde{F}\tilde{F}^{\dagger}\underline{f}\right\rVert_{2}^{2}\leq\frac{1}{2\pi
C_{1}(2N+1)}\left\lVert\underline{f}\right\rVert_{2}^{2},\qquad\underline{f}\in\mathbb{C}^{2N+1},$

where $\tilde{F}^{\dagger}$ is the Moore–Penrose pseudoinverse of $\tilde{F}$.
Here, the second inequality follows from the fact that
$\|\tilde{F}\tilde{F}^{\dagger}\|_{2}=1$. We find that
$\|\tilde{F}^{\dagger}\|_{2}\leq 1/\sqrt{2\pi C_{1}(2N+1)}$ and hence, the
condition number of $\tilde{F}$ is bounded independently of $N$ and $n$:

$\kappa_{2}(\tilde{F})=\left\lVert\tilde{F}\right\rVert_{2}\left\lVert\tilde{F}^{\dagger}\right\rVert_{2}\leq\sqrt{\frac{C_{2}}{C_{1}}}.$

We find this a remarkable bound because as soon as there is a small amount of
oversampling, the condition number of $\tilde{F}$ can be bounded independently
of $N$ and $n$, even in the $1/4\leq\alpha<1/2$ regime. In contrast, we
believe that when $N=n$, the condition number of $\tilde{F}$ grows slowly with
$N$ when $1/4\leq\alpha<1/2$.

###  6.3 Convergence of least-squares approximation at unevenly spaced samples

Let $f:[-\pi,\pi)\rightarrow\mathbb{C}$ be a continuous periodic function and
let $\tilde{q}_{n}$ be the least-squares approximant in Eq. 27. Then, by
definition of $\tilde{q}_{n}$, we have that
$\sum_{j=-N}^{N}\left|f(\tilde{x}_{j})-\tilde{q}_{n}(\tilde{x}_{j})\right|^{2}\leq\sum_{j=-N}^{N}\left|f(\tilde{x}_{j})-q(\tilde{x}_{j})\right|^{2}$
for any $q\in\mathcal{T}_{n}$. Hence, we find that

$\displaystyle\sum_{j=-N}^{N}\left|q(\tilde{x}_{j})-\tilde{q}_{n}(\tilde{x}_{j})\right|^{2}\leq\sum_{j=-N}^{N}(\left|q(\tilde{x}_{j})-f(\tilde{x}_{j})\right|+\left|f(\tilde{x}_{j})-\tilde{q}_{n}(\tilde{x}_{j})\right|)^{2}$
$\displaystyle=\sum_{j=-N}^{N}(\left|q(\tilde{x}_{j})-f(\tilde{x}_{j})\right|^{2}+\left|f(\tilde{x}_{j})-\tilde{q}_{n}(\tilde{x}_{j})\right|^{2}+2\left|q(\tilde{x}_{j})-f(\tilde{x}_{j})\right|\left|f(\tilde{x}_{j})-\tilde{q}_{n}(\tilde{x}_{j})\right|)$
$\displaystyle\leq
4\sum_{j=-N}^{N}\left|q(\tilde{x}_{j})-f(\tilde{x}_{j})\right|^{2},$

where the last inequality follows from the Cauchy–Schwarz inequality. By a
similar argument to the proof of Theorem 3.1, we find that

$\left\|f-\tilde{q}_{n}\right\|_{L^{\infty}}\leq\left(1+\sqrt{\frac{2(2n+1)}{C_{1}\pi}}\right)\min_{q\in\mathcal{T}_{n}}\|f-q\|_{L^{\infty}}.$

The reader can now use their favorite bounds on
$\min_{q\in\mathcal{T}_{n}}\|f-q\|_{L^{\infty}}$ (see Eqs. 16 and 17).

###  6.4 Nonexact quadrature rules

There also exists a quadrature rule that is exact for all
$q\in\mathcal{T}_{n}$ such that [15, Thm. 2.7]

$\left|\tilde{I}_{n}(f)-I(f)\right|\leq
2\pi\left(1+\sqrt{\frac{C_{2}}{C_{1}}}\right)\min_{q\in\mathcal{T}_{n}}\left\lVert
f-q\right\rVert_{L^{\infty}},\quad\tilde{I}_{n}(f)=\sum_{j=-N}^{N}\tilde{w}_{j}f(\tilde{x}_{j})$

for all continuous periodic $f$. In Lemma 3.6 of [15], it is shown that the
quadrature weights $\tilde{w}_{j}$ are the least-squares solution of the
underdetermined system
$\tilde{F}^{\top}\underline{\tilde{w}}=2\pi\underline{e}_{0}$, where
$\underline{e}_{0}$ is the zero vector except at its central entry is $1$.

From numerical experiments, we observer that while oversampling usually avoids
negative weights and also reduces the absolute sum of the weights, it is much
more unpredictable as $n$ and $N$ vary. We know that oversampling by a minimal
amount gives us good rates of convergence for any $\alpha<1/2$. A natural
question to ask is how much we need to oversample before we can guarantee that
the quadrature weights are non-negative. Again, this problem was studied in
[22] for higher dimensions. A translation of their one dimensional technique
states that if $n\leq N/\pi$, then for every $N$ there exists a quadrature
rule, $\tilde{I}_{n}$, that is exact for $q\in\mathcal{T}_{n}$ and has non-
negative weights.

##  Appendix A A quadrature weight at perturbed nodes is negative

To show that the perturbed nodes in Eq. 19 have an associated quadrature
weight that is negative when $N$ is sufficiently large, we need a few
trigonometric inequalities that are technical to derive.

Let $p,q,r>0$ be such that $0<q-p-2r<q-p+2r<\pi$. The following trigonometric
inequality holds:

(28) $\displaystyle\sin(p-r)\sin(q+r)$
$\displaystyle=\frac{\cos(q-p+2r)-\cos(p+q)}{2}$
$\displaystyle<\frac{\cos(q-p-2r)-\cos(p+q)}{2}=\sin(p+r)\sin(q-r).$

The next lemma bounds the values of $\ell_{0}$, the trigonometric Lagrange
polynomial for $\tilde{x}_{0}$ associated with
$\\{\tilde{x}_{j}\\}_{j=-N}^{N}$ (see Eq. 21), at an equally spaced node. This
helps us bound the weight $\tilde{w}_{0}$ in Theorem 4.1.

######  Lemma A.1.

Suppose $N$ is even and $\tilde{x}_{-N},\ldots,\tilde{x}_{N}$ are the
perturbed nodes given in Eq. 19. We have

(29) $\left|\ell_{0}(kh)\right|=-\ell_{0}(kh)\geq\frac{\sin\\!\left(\alpha
h/2\right)}{\sin\\!\left((\left|k\right|+\alpha)h/2\right)},\qquad-N\leq k\leq
N,\quad k\neq 0,$

where $h=2\pi/(2N+1)$.

######  Proof A.2.

Since $\ell_{0}(-x)=\ell_{0}(x)$ for all $x$, it suffices to show that Eq. 29
holds for $k>0$. By a simple counting argument, one can verify that
$\ell_{0}(kh)=\prod_{j=-N,j\neq
0}^{N}(\sin((kh-\tilde{x}_{j})/2)/\sin(-\tilde{x}_{j}/2))\leq 0$. Let
$s(x)=\sin(\left|xh/2\right|)$. Then, the numerator of
$\left|\ell_{0}(kh)\right|$ can be written as

$\displaystyle\prod_{\begin{subarray}{c}j=-N,\\\ j\neq
0\end{subarray}}^{N}\sin\left(\left|\frac{kh-\tilde{x}_{j}}{2}\right|\right)$
$\displaystyle=\\!\\!\\!\\!\prod_{j=-N}^{-N+k-1}\\!\\!\\!\\!\\!\sin\\!\left(\left|\frac{kh-\tilde{x}_{j}}{2}\right|\right)\\!\\!\\!\\!\prod_{j=-N+k}^{-1}\\!\\!\\!\\!\\!\sin\\!\left(\left|\frac{kh-\tilde{x}_{j}}{2}\right|\right)\\!\\!\prod_{j=1}^{k}\\!\sin\\!\left(\left|\frac{kh-\tilde{x}_{j}}{2}\right|\right)\\!\\!\\!\prod_{j=k+1}^{N}\\!\\!\\!\sin\\!\left(\left|\frac{kh-\tilde{x}_{j}}{2}\right|\right)$
$\displaystyle=\\!\\!\\!\\!\prod_{j=N-k+1}^{N}\\!\\!\\!\\!s(j\\!+\\!(-1)^{j+k}\alpha)\\!\\!\\!\\!\prod_{j=k+1}^{N}\\!\\!\\!\\!s(j\\!+\\!(-1)^{j+k}\alpha)\\!\\!\prod_{j=0}^{k-1}\\!\\!s(j\\!+\\!(-1)^{j+k+1}\alpha)\\!\\!\prod_{j=1}^{N-k}\\!\\!s(j\\!+\\!(-1)^{j+k}\alpha)$
$\displaystyle=\prod_{j=1}^{N}s(j\\!+\\!(-1)^{j+k}\alpha)\prod_{j=k+1}^{N}s(j\\!+\\!(-1)^{j+k}\alpha)\prod_{j=0}^{k-1}s(j\\!+\\!(-1)^{j+k+1}\alpha).$

Similarly, the denominator of $\left|\ell_{0}(kh)\right|$ can be written as

$\displaystyle\prod_{\begin{subarray}{c}j=-N,\\\ j\neq
0\end{subarray}}^{N}\sin\left(\left|\frac{\tilde{x}_{j}}{2}\right|\right)=\prod_{j=1}^{N}\sin^{2}\left(\left|\frac{\tilde{x}_{j}}{2}\right|\right)=\prod_{j=1}^{N}(s(j+(-1)^{j}\alpha))^{2}.$

Using Eq. 28, we find the for every odd $1\leq j\leq N$, we have

(30) $s(j+\alpha)s((j+1)-\alpha)\geq s(j-\alpha)s((j+1)+\alpha).$

Hence, for every odd $m_{1}$ and even $m_{2}$ such that $1\leq m_{1}<m_{2}\leq
N$, Eq. 30 gives us

(31)
$\prod_{j=m_{1}}^{m_{2}}s(j+(-1)^{j+1}\alpha)\geq\prod_{j=m_{1}}^{m_{2}}s(j+(-1)^{j}\alpha).$

We now consider the cases when $k$ is even and odd separately.

Case I: $\mathbf{k}$ is even. If $k$ is even, then we have

$\displaystyle-\ell_{0}(kh)$
$\displaystyle=\left|\ell_{0}(kh)\right|=\left(\prod_{j=1}^{k-2}\frac{s(j+(-1)^{j+1}\alpha)}{s(j+(-1)^{j}\alpha)}\right)\frac{s(k-1+\alpha)}{s(k-1-\alpha)}\frac{s(\alpha)}{s(k+\alpha)}$
$\displaystyle\geq\frac{s(\alpha)}{s(k+\alpha)}=\frac{\sin(\alpha
h/2)}{\sin((k+\alpha)h/2)},$

where we used Eq. 31 with $m_{1}=1$ and $m_{2}=k-2$.

Case II: $\mathbf{k}$ is odd. If $k$ is odd, then we have the following
inequality on $-\ell_{0}(kh)$:

$\displaystyle-\ell_{0}(kh)$
$\displaystyle=\left|\ell_{0}(kh)\right|\geq\left(\prod_{j=k+2}^{N}\frac{s(j+(-1)^{j+1}\alpha)}{s(j+(-1)^{j}\alpha)}\right)\frac{s(k+1-\alpha)}{s(k+1+\alpha)}\frac{s(\alpha)}{s(k-\alpha)}$
$\displaystyle\geq\frac{s(k+1-\alpha)}{s(k+1+\alpha)}\frac{s(\alpha)}{s(k-\alpha)}\geq\frac{s(\alpha)}{s(k+\alpha)}=\frac{\sin(\alpha
h/2)}{\sin((k+\alpha)h/2)},$

where the sequence of three inequalities are obtained from Eq. 31 by setting
(1) $m_{1}=1$ and $m_{2}=N$, (2) $m_{1}=k+2$ and $m_{2}=N$, and (3) $m_{1}=k$
and $m_{2}=k+1$, respectively. The proof is complete.

##  Appendix B Only large quadrature rules at perturbed nodes can have
negative weights

For any $0<\alpha<1/2$, we define $N^{\rm neg}_{\alpha}$ to be the smallest
integer such that for $N=N^{\rm neg}_{\alpha}$ there exists a set of
$\alpha$-perturbed quadrature nodes $\\{\tilde{x}_{j}\\}_{j=-N}^{N}$ so that
the associated exact quadrature rule on $\mathcal{T}_{N}$ has a negative
weight. By Theorem 4.1, we know that $N^{\rm neg}_{\alpha}$ is finite for
every $\alpha$. Here, we derive an implicit lower bound Eq. 34 on $N^{\rm
neg}_{\alpha}$ and provide a closed formula in Eq. 36, which proves
$\log(N^{\rm neg}_{\alpha})=\Theta(\alpha^{-1})$ as $\alpha\rightarrow 0$.
This is a rather technical result.

First, we define an equivalence relation on the indices. Let $-N\leq j,k\leq
N$ and define $d(j,k)=\min\\{\left|j-k\right|,2N+1-\left|j-k\right|\\}$. For a
fixed $j$, define an equivalence class on $\\{-N,\ldots,j-1,j+1,\ldots,N\\}$
by $k_{1}\sim_{j}k_{2}$ if and only if $d(j,k_{1})=d(j,k_{2})$ and denote the
equivalence class by $S^{j}_{d(j,k_{1})}$. Note that each of
$S^{j}_{1},\ldots,S^{j}_{N}$ contains exactly $2$ elements.

######  Lemma B.1.

Let $0\leq\alpha<1/2$, $h=2\pi/(2N+1)$, and $\\{\tilde{x}_{k}\\}_{k=-N}^{N}$
be a set of $\alpha$-perturbed nodes. For fixed $-N\leq j\leq N$ and for any
$-N\leq k\leq N$ with $k\neq j$, we have

(32) $\left|\frac{\prod_{m=-N,m\neq
j,k}^{N}\sin\\!\left(\frac{x_{k}-\tilde{x}_{m}}{2}\right)}{\prod_{m=-N,m\neq
j}^{N}\sin\\!\left(\frac{\tilde{x}_{j}-\tilde{x}_{m}}{2}\right)}\right|\leq\frac{1}{\sin\\!\left(\frac{d(j,k)h}{2}\right)}\prod_{m=1}^{N}\frac{\sin^{2}\\!\left(\frac{mh+\alpha
h}{2}\right)}{\sin\\!\left(\frac{mh-2\alpha
h}{2}\right)\sin\\!\left(\frac{mh}{2}\right)},$

where $x_{k}=\tilde{x}_{j}+(k-j)h$.444Note that we do not necessarily have
$\left|x_{k}-\tilde{x}_{k}\right|\leq\alpha h$ for all $k$. Instead, we have
$\left|x_{k}-\tilde{x}_{k}\right|\leq 2\alpha h$.

######  Proof B.2.

Let $d=d(j,k)$ and $j^{\prime}$ be the element in $S^{k}_{d}$ that is not
equal to $j$. Then, we can write the numerator and denominator of Eq. 32 as

$\displaystyle A$ $\displaystyle=\prod_{\begin{subarray}{c}m=-N,\\\ m\neq
j,k\end{subarray}}^{N}\\!\sin\left(\\!\frac{x_{k}\\!-\\!\tilde{x}_{m}}{2}\\!\right)=\sin\left(\\!\frac{x_{k}\\!-\\!\tilde{x}_{j^{\prime}}}{2}\\!\right)\\!\prod_{\begin{subarray}{c}m=1,m\neq
d,\\\
S^{k}_{m}=\\{k_{1},k_{2}\\}\end{subarray}}^{N}\\!\left[\sin\left(\\!\frac{x_{k}\\!-\\!\tilde{x}_{k_{1}}}{2}\\!\right)\sin\left(\frac{x_{k}\\!-\\!\tilde{x}_{k_{2}}}{2}\\!\right)\right],$
$\displaystyle B$ $\displaystyle=\prod_{\begin{subarray}{c}m=-N,\\\ m\neq
j\end{subarray}}^{N}\\!\sin\left(\\!\frac{\tilde{x}_{j}\\!-\\!\tilde{x}_{m}}{2}\\!\right)=\\!\prod_{\begin{subarray}{c}m=1,\\\
S^{j}_{m}=\\{k_{1},k_{2}\\}\end{subarray}}^{N}\\!\left[\sin\left(\\!\frac{\tilde{x}_{j}\\!-\\!\tilde{x}_{k_{1}}}{2}\\!\right)\sin\left(\\!\frac{\tilde{x}_{j}\\!-\\!\tilde{x}_{k_{2}}}{2}\\!\right)\right].$

Suppose $S_{m}^{k}=\\{k_{1},k_{2}\\}$, where $1\leq m\leq N$. Then, we know
that
$d_{\mathbb{T}}(e^{ix_{k}},e^{i\tilde{x}_{k_{1}}})+d_{\mathbb{T}}(e^{ix_{k}},e^{i\tilde{x}_{k_{2}}})\leq
2mh+2\alpha h$ and
$d_{\mathbb{T}}(e^{ix_{k}},e^{i\tilde{x}_{k_{1}}}),d_{\mathbb{T}}(e^{ix_{k}},e^{i\tilde{x}_{k_{2}}})\leq
mh+2\alpha h$, where
$d_{\mathbb{T}}(e^{ix},e^{iy})=\min\\{\left|x-y\right|,2\pi-\left|x-y\right|\\}$
is the “distance” between $e^{ix}$ and $e^{iy}$ on the unit circle for
$x,y\in[-\pi,\pi)$. Therefore, by elementary calculus, we have

$\left|\sin\left(\frac{x_{k}-\tilde{x}_{k_{1}}}{2}\right)\sin\left(\frac{x_{k}-\tilde{x}_{k_{2}}}{2}\right)\right|\leq\sin^{2}\left(\frac{mh+\alpha
h}{2}\right),$

where the lefthand side of the inequality above is maximized when
$d_{\mathbb{T}}(e^{ix_{k}},e^{i\tilde{x}_{k_{1}}})=d_{\mathbb{T}}(e^{ix_{k}},e^{i\tilde{x}_{k_{2}}})=mh+\alpha
h$. Similarly, suppose $S_{m}^{j}=\\{k_{1},k_{2}\\}$. We have
$d_{\mathbb{T}}(e^{i\tilde{x}_{j}},e^{i\tilde{x}_{k_{1}}})+d_{\mathbb{T}}(e^{i\tilde{x}_{j}},e^{i\tilde{x}_{k_{2}}})\geq
2mh-2\alpha h$ and
$d_{\mathbb{T}}(e^{i\tilde{x}_{j}},e^{i\tilde{x}_{k_{1}}}),d_{\mathbb{T}}(e^{i\tilde{x}_{j}},e^{i\tilde{x}_{k_{2}}})\geq
mh-2\alpha h$. Hence,

$\left|\sin\left(\frac{\tilde{x}_{j}-\tilde{x}_{k_{1}}}{2}\right)\sin\left(\frac{\tilde{x}_{j}-\tilde{x}_{k_{2}}}{2}\right)\right|\geq\sin\left(\frac{mh-2\alpha
h}{2}\right)\sin\left(\frac{mh}{2}\right),$

where the lefthand side of the inequality above is minimized when
$d_{\mathbb{T}}(e^{i\tilde{x}_{j}},e^{i\tilde{x}_{k_{i}}})=mh$ and
$d_{\mathbb{T}}(e^{i\tilde{x}_{j}},e^{i\tilde{x}_{k_{3-i}}})=mh-2\alpha h$ for
$i=1$ or $2$. This gives us

$\displaystyle\left|\frac{A}{B}\right|\leq\frac{\sin\left(\\!\frac{dh+2\alpha
h}{2}\\!\right)\prod_{m=1,m\neq d}^{N}\sin^{2}\left(\\!\frac{mh+\alpha
h}{2}\\!\right)}{\prod_{m=1}^{N}\sin\left(\\!\frac{mh-2\alpha
h}{2}\\!\right)\sin\left(\\!\frac{mh}{2}\\!\right)}\leq\frac{1}{\sin\left(\\!\frac{dh}{2}\\!\right)}\prod_{m=1}^{N}\frac{\sin^{2}\left(\\!\frac{mh+\alpha
h}{2}\\!\right)}{\sin\left(\\!\frac{mh-2\alpha
h}{2}\\!\right)\sin\left(\\!\frac{mh}{2}\\!\right)},$

as desired.

It is worth observing that $A/B$ in the proof of Lemma B.1 is almost the
Lagrange polynomial at $x_{j}$. This connection is made precise in the next
lemma.

######  Lemma B.3.

Using the same notation as Lemma B.1, if $\ell_{j}$ is the $j$th trigonometric
Lagrange basis polynomial for $\tilde{x}_{j}$ associated with
$\\{\tilde{x}_{k}\\}_{k=-N}^{N}$, then

(33)
$\left|\ell_{j}(x_{k_{1}})+\ell_{j}(x_{k_{2}})\right|\leq\frac{\pi\alpha}{d}\prod_{m=1}^{N}\frac{(m+\alpha)^{2}}{(m-2\alpha)m},$

where $S^{j}_{d}=\\{k_{1},k_{2}\\}$.

######  Proof B.4.

Let $d=d(j,k)$ and suppose that $1\leq d\leq N$. For $i=1,2$, we have

$\displaystyle\ell_{j}(x_{k_{i}})$ $\displaystyle=\frac{\prod_{m=-N,m\neq
j}^{N}\sin\left(\frac{x_{k_{i}}-\tilde{x}_{m}}{2}\right)}{\prod_{m=-N,m\neq
j}^{N}\sin\left(\frac{\tilde{x}_{j}-\tilde{x}_{m}}{2}\right)}=\frac{\sin\left(\frac{x_{k_{i}}-\tilde{x}_{k_{i}}}{2}\right)\prod_{m=-N,m\neq
j,k_{i}}^{N}\sin\left(\frac{x_{k_{i}}-\tilde{x}_{m}}{2}\right)}{\prod_{m=-N,m\neq
j}^{N}\sin\left(\frac{\tilde{x}_{j}-\tilde{x}_{m}}{2}\right)}.$

By Lemma B.1, we find that

$\displaystyle\left|\frac{\prod_{m=-N,m\neq
j,k_{i}}^{N}\sin\left(\frac{x_{k_{i}}-\tilde{x}_{m}}{2}\right)}{\prod_{m=-N,m\neq
j}^{N}\sin\left(\frac{\tilde{x}_{j}-\tilde{x}_{m}}{2}\right)}\right|\leq\frac{\pi}{dh}\prod_{m=1}^{N}\frac{(mh+\alpha
h)^{2}}{(mh-2\alpha
h)(mh)}=\frac{\pi}{dh}\prod_{m=1}^{N}\frac{(m+\alpha)^{2}}{(m-2\alpha)m},$

where we need the fact that $(2/\pi)x\leq\sin x$ for all $0\leq x\leq\pi/2$
and the fact that $\sin y/\sin x\leq y/x$ for all $0<x\leq y<\pi$. We now
prove Eq. 33 by considering the cases
$\ell_{j}(x_{k_{1}})\ell_{j}(x_{k_{2}})\leq 0$ and
$\ell_{j}(x_{k_{1}})\ell_{j}(x_{k_{2}})>0$ separately.

Case 1: $\mathbf{\ell_{j}(x_{k_{1}})\ell_{j}(x_{k_{2}})\leq 0}$. Since
$d_{\mathbb{T}}(e^{ix_{k_{i}}},e^{i\tilde{x}_{k_{i}}})\leq 2\alpha h$ for
$i=1,2$, we have

$\displaystyle\left|\ell_{j}(x_{k_{1}})+\ell_{j}(x_{k_{2}})\right|\leq\max\\{\left|\ell_{j}(x_{k_{1}})\right|,\left|\ell_{j}(x_{k_{2}})\right|\\}$
$\displaystyle\qquad\leq\max_{i=1,2}\left[\frac{d_{\mathbb{T}}(e^{ix_{k_{i}}},e^{i\tilde{x}_{k_{i}}})}{2}\right]\frac{\pi}{dh}\prod_{m=1}^{N}\frac{(m+\alpha)^{2}}{(m-2\alpha)m}\leq\frac{\pi\alpha}{d}\prod_{m=1}^{N}\frac{(m+\alpha)^{2}}{(m-2\alpha)m},$

where we used the fact that $\sin(x)\leq x$ for all $0\leq x\leq\pi/2$.

Case 2: $\mathbf{\ell_{j}(x_{k_{1}})\ell_{j}(x_{k_{2}})>0}$. We claim that

$\frac{\prod_{m=-N,m\neq
j,k_{1}}^{N}\sin\left(\frac{x_{k_{1}}-\tilde{x}_{m}}{2}\right)}{\prod_{m=-N,m\neq
j}^{N}\sin\left(\frac{\tilde{x}_{j}-\tilde{x}_{m}}{2}\right)}\frac{\prod_{m=-N,m\neq
j,k_{2}}^{N}\sin\left(\frac{x_{k_{2}}-\tilde{x}_{m}}{2}\right)}{\prod_{m=-N,m\neq
j}^{N}\sin\left(\frac{\tilde{x}_{j}-\tilde{x}_{m}}{2}\right)}<0.$

The claim follows because if we assume, without loss of
generality,555Otherwise, swap the roles of $k_{1}$ and $k_{2}$. that
$k_{1}<k_{2}$, then there are an even number of integers $m$, not including
$j$, such that $k_{1}<m<k_{2}$.666Note that $j$ may not be between $k_{1}$ and
$k_{2}$. However, the claim follows regardless of how $j$ compares to $k_{1}$
and $k_{2}$. When $m\neq k_{1},k_{2}$, the signs of
$\sin((x_{k_{1}}-\tilde{x}_{m})/2)$ and $\sin((x_{k_{2}}-\tilde{x}_{m})/2)$
are different if and only if $k_{1}<m<k_{2}$. The claim follows from the fact
that
$\sin((x_{k_{2}}-\tilde{x}_{k_{1}})/2)\sin((x_{k_{1}}-\tilde{x}_{k_{2}})/2)<0$
because the remaining terms multiply to a positive number. Hence, we have
$\sin((x_{k_{1}}-\tilde{x}_{k_{1}})/2)\sin((x_{k_{2}}-\tilde{x}_{k_{2}})/2)<0$
so that $(x_{k_{1}}-\tilde{x}_{k_{1}})(x_{k_{2}}-\tilde{x}_{k_{2}})<0$. Let
$\delta:=\tilde{x}_{j}-jh$. Then, $x_{k_{i}}-\tilde{x}_{k_{i}}<\alpha
h+\delta$ if $x_{k_{i}}-\tilde{x}_{k_{i}}>0$ and
$\tilde{x}_{k_{i}}-x_{k_{i}}<\alpha h-\delta$ if
$x_{k_{i}}-\tilde{x}_{k_{i}}<0$. Hence,
$(x_{k_{1}}-\tilde{x}_{k_{1}})(x_{k_{2}}-\tilde{x}_{k_{2}})<0$ implies
$d_{\mathbb{T}}(e^{ix_{k_{1}}},e^{i\tilde{x}_{k_{1}}})+d_{\mathbb{T}}(e^{ix_{k_{2}}},e^{i\tilde{x}_{k_{2}}})\leq
2\alpha h$. By elementary calculus, we find that

$\left|\sin\left(\frac{x_{k_{1}}-\tilde{x}_{k_{1}}}{2}\right)\right|+\left|\sin\left(\frac{x_{k_{2}}-\tilde{x}_{k_{2}}}{2}\right)\right|\leq
2\sin\left(\frac{\alpha h}{2}\right)\leq\alpha h.$

Putting this together we obtain

$\displaystyle\left|\ell_{j}(x_{k_{1}})+\ell_{j}(x_{k_{2}})\right|=\left|\ell_{j}(x_{k_{1}})\right|+\left|\ell_{j}(x_{k_{2}})\right|$
$\displaystyle\;\;\leq\left(\left|\sin\left(\\!\\!\frac{x_{k_{1}}\\!-\\!\tilde{x}_{k_{1}}}{2}\\!\\!\right)\right|+\left|\sin\left(\\!\\!\frac{x_{k_{2}}\\!-\\!\tilde{x}_{k_{2}}}{2}\\!\\!\right)\right|\right)\frac{\pi}{dh}\prod_{m=1}^{N}\\!\frac{(m+\alpha)^{2}}{(m-2\alpha)m}\leq\frac{\pi\alpha}{d}\prod_{m=1}^{N}\\!\frac{(m+\alpha)^{2}}{(m-2\alpha)m},$

as desired.

We are now ready to prove a lower bound on $N^{\rm neg}_{\alpha}$.

######  Theorem B.5.

We have

(34) $g(N^{\rm neg}_{\alpha})>\frac{1}{\pi\alpha},\qquad
g(N):=\prod_{m=1}^{N}\left[\frac{(m+\alpha)^{2}}{(m-2\alpha)m}\right]\left[\sum_{d=1}^{N}\frac{1}{d}\right]$

for $0<\alpha<1/2$.

######  Proof B.6.

We define $g:\mathbb{N}\rightarrow\mathbb{R}$ as in Eq. 34. It suffices to
show that $g(N)\leq 1/(\pi\alpha)$ implies that a quadrature rule at
$\alpha$-perturbed nodes of degree $N$ contains no negative weight. Let
$\\{\tilde{x}_{j}\\}_{j=-N}^{N}$ be a set of $\alpha$-perturbed nodes. Let
$\tilde{w}_{j}$ be the quadrature weight associated with $\tilde{x}_{j}$ and
let $\ell_{j}$ be the corresponding trigonometric Lagrange basis polynomial.
Let $\\{x_{k}\\}_{k=-N}^{N}$, which may depend on $j$, be defined as in Lemma
B.1. Then, we have
$\tilde{w}_{j}=(2\pi/(2N+1))\sum_{k=-N}^{N}\ell_{j}(x_{k})$. By Lemma B.3, we
have

$\displaystyle\sum_{k=-N}^{N}\ell_{j}(x_{k})=\ell_{j}(x_{j})+\sum_{k=-N,k\neq
j}^{N}\ell_{j}(x_{k})\geq
1-\sum_{d=1,S^{j}_{d}=\\{k_{1},k_{2}\\}}^{N}\left|\ell_{j}(x_{k_{1}})+\ell_{j}(x_{k_{2}})\right|$
$\displaystyle\qquad\geq
1-\sum_{d=1}^{N}\left[\frac{\pi\alpha}{d}\prod_{m=1}^{N}\frac{(m+\alpha)^{2}}{(m-2\alpha)m}\right]=1-\pi\alpha\prod_{m=1}^{N}\left[\frac{(m+\alpha)^{2}}{(m-2\alpha)m}\right]\left[\sum_{d=1}^{N}\frac{1}{d}\right]\geq
0.$

This proves all quadrature weights are non-negative.

For small $\alpha$, we can make the statement in Theorem B.5 more explicit.

######  Corollary B.7.

For $0<\alpha<0.15$ and a real number $L>0$ such that

(35) $(\alpha+L)e^{4L}\leq\frac{\Gamma(1+\alpha)^{2}}{\pi\Gamma(1-2\alpha)},$

where $\Gamma$ is the gamma function, we find that $N^{\rm neg}_{\alpha}$
satisfies the following inequality:

(36) $\log(N^{\rm neg}_{\alpha}+1+\alpha)+\frac{1}{2N^{\rm
neg}_{\alpha}-1}>(1-\gamma)+\frac{L}{\alpha},$

where $\gamma\approx 0.57722$ is the Euler–Mascheroni constant [12].

######  Proof B.8.

We aim to show that Eq. 35 implies Eq. 36. We first use Gautschi’s inequality
[32] to obtain

(37)
$\prod_{m=1}^{N}\frac{(m\\!+\\!\alpha)^{2}}{(m\\!-\\!2\alpha)m}=\frac{\Gamma(1\\!-\\!2\alpha)\Gamma(N\\!+\\!1\\!+\\!\alpha)^{2}}{\Gamma(N\\!+\\!1\\!-\\!2\alpha)\Gamma(N\\!+\\!1)\Gamma(1\\!+\\!\alpha)^{2}}\leq\frac{\Gamma(1\\!-\\!2\alpha)}{\Gamma(1\\!+\\!\alpha)^{2}}(N\\!+\\!1\\!+\\!\alpha)^{4\alpha}.$

Assume that $\log(N+1+\alpha)+1/(2N-1)\leq(1-\gamma)+L/\alpha$, for an integer
$N>0$. We have $\log(N+1+\alpha)\leq L/\alpha$. Hence, $N+1+\alpha\leq
e^{L/\alpha}$. By Eq. 37, we find that

$g(N)\leq\frac{\Gamma(1\\!-\\!2\alpha)}{\Gamma(1\\!+\\!\alpha)^{2}}(N\\!+\\!1\\!+\\!\alpha)^{4\alpha}\left(\log(N)\\!+\\!\gamma\\!+\\!\frac{1}{2N\\!-\\!1}\right)\leq\frac{\Gamma(1\\!-\\!2\alpha)}{\Gamma(1\\!+\\!\alpha)^{2}}e^{4L}\left(1\\!+\\!\frac{L}{\alpha}\right)\leq\frac{1}{\pi\alpha},$

where we used the fact that
$\sum_{d=1}^{N}d^{-1}\leq\log(N)+\gamma+1/(2N-1)\leq 1+L/\alpha$ [12] and the
last inequality follows from Eq. 35. Since $g(N)$ is an increasing function of
$N$, we know from Eq. 34 that $N<N^{\rm neg}_{\alpha}$. Moreover, this holds
for all $N>1$ that satisfies
$\log(N+1+\alpha)+1/(2N-1)\leq(1-\gamma)+L/\alpha$. When $\alpha<0.15$, we see
that $N^{\rm neg}_{\alpha}\geq 2$ by Eq. 34 and this proves Eq. 36.

Corollary B.7 implies that $\log(N^{\rm neg}_{\alpha})=\Omega(\alpha^{-1})$
and by Theorem 4.1, we conclude that $\log(N^{\rm
neg}_{\alpha})=\Theta(\alpha^{-1})$ as $\alpha\rightarrow 0$.

## Acknowledgments

We are thankful for many conversations with Anthony Austin, Nick Trefethen,
and Kuan Xu regarding unevenly spaced trigonometric interpolation over several
years. In private communication, Heather Wilber gave an initial proof of the
discrete Kadec-1/4 theorem in December 2017, which we adapted for our
purposes. It was Laurent Demanet who brought our attention to the conditioning
of NUDFT matrices and we also benefited from Alex Barnett’s wisdom on the
subject. The research direction became more focused after brain storming
sessions during Cornell’s math REU program in 2021 and we thank Aparna Gupte,
Yunan Yang, and Liu Zhang for discussions regarding the MZ inequalities and
quadrature rules.

## References

  * [1] B. Anderson, J. M. Ash, R. L. Jones, D. G. Rider, and B. Saffari, Exponential sums with coefficients $0$ or $1$ and concentrated $L^{p}$ norms, Annales de l’Institut Fourier, 57 (2007), pp. 1377–1404.
  * [2] A. Austin, Some New Results on and Applications of Interpolation in Numerical Computation, Mathematical Institute, University of Oxford, 2016.
  * [3] A. P. Austin and L. N. Trefethen, Trigonometric interpolation and quadrature in perturbed points, SIAM J. Numer. Anal., 55 (2017), pp. 2113–2122.
  * [4] S. Bagchi and S. K. Mitra, The nonuniform discrete Fourier transform and its applications in signal processing, vol. 463, Springer Science & Business Media, 2012.
  * [5] A. H. Barnett, J. Magland, and L. af Klinteberg, A parallel nonuniform fast Fourier transform library based on an “exponential of semicircle” kernel, SIAM J. Sci. Comp., 41 (2019), pp. C479–C504.
  * [6] C. K. Chui and L. Zhong, Polynomial interpolation and Marcinkiewicz–Zygmund inequalities on the unit circle, J. Math. Anal. Appl., 233 (1999), pp. 387–405.
  * [7] J. W. Cooley and J. W. Tukey, An algorithm for the machine calculation of complex Fourier series, Math. Comp., 19 (1965), pp. 297–301.
  * [8] T. A. Driscoll, N. Hale, and L. N. Trefethen, Chebfun guide, Pafnuty Publications.
  * [9] A. Dutt and V. Rokhlin, Fast Fourier transforms for nonequispaced data, SIAM J. Sci. Comp., 14 (1993), pp. 1368–1393.
  * [10] A. Dutt and V. Rokhlin, Fast Fourier transforms for nonequispaced data, II, Appl. Comput. Harm. Anal., 2 (1995), pp. 85–100.
  * [11] A. Eckner, Algorithms for unevenly-spaced time series: Moving averages and other rolling operators, in Working Paper, 2012.
  * [12] L. Euler, Inventio summae cuiusque seriei ex dato termino generali, Commentarii academiae scientiarum Petropolitanae, (1741), pp. 9–22.
  * [13] F. Filbir and H. N. Mhaskar, A quadrature formula for diffusion polynomials corresponding to a generalized heat kernel, J. Four., Anal. Appl., 16 (2010), pp. 629–657.
  * [14] S. Gowrishankar, T. Basavarajuand, D. Manjaiah, and S. Sarkar, Issues in wireless sensor networks, Proceedings of the World Congress on Engineering, July 2008.
  * [15] K. Gröchenig, Sampling, Marcinkiewicz–Zygmund inequalities, approximation, and quadrature rules, J. Approx. Theory, 257 (2020), pp. 1–20.
  * [16] P. Henrici, Barycentric formulas for interpolating trigonometric polynomials and their conjugates, Numer. Math., 33 (1979), pp. 225–234.
  * [17] D. B. Hunter, The evaluation of integrals of periodic analytic functions, BIT Numer. Math., 11 (1971), pp. 175–180.
  * [18] M. Kadets, The exact value of the Paley–Wiener constant, Dokl. Akad. Nauk SSSR, (1964), pp. 1253–1254.
  * [19] R. Konstantin and S. Winfried, Marcinkiewicz–Zygmund-type inequalities trigonometric interpolation on non-uniform grids and unconditional Schauder bases in Besov spaces on the torus, Z. Anal. Anwend., 16 (1997), pp. 669–687.
  * [20] D. Lubinsky, Marcinkiewicz–Zygmund inequalities: methods and results, in Recent Progress in Inequalities, Springer, 1998, pp. 213–240.
  * [21] J. Marzo and K. Seip, The Kadets 1/4 theorem for polynomials, Mathematica Scandinavica, 104 (2009), pp. 311–318.
  * [22] H. N. Mhaskar, F. J. Narcowich, and J. D. Ward, Spherical Marcinkiewicz–Zygmund inequalities and positive quadrature, Math. Comp., 70 (2000), pp. 1113–1130.
  * [23] J. Ortega-Cerdà and J. Saludes, Marcinkiewicz–Zygmund inequalities, J. Approx. Theory, 145 (2007), pp. 237–252.
  * [24] G. Pólya, Über die konvergenz von quadraturverfahren, Math. Z., 37 (1933).
  * [25] R. Quan, Risk assessment of flood disaster in Shanghai based on spatial-temporal characteristics analysis from 251 to 2000, Environmental Earth Sciences, 72 (2014), pp. 4627–4638.
  * [26] K. Rehfeld, N. Marwan, J. Heitzig, and J. Kurths, Comparison of correlation analysis techniques for irregularly sampled time series, Nonlinear Processes in Geophysics, 18 (2011), pp. 389–404.
  * [27] D. Ruiz-Antolin and A. Townsend, A nonuniform fast Fourier transform based on low rank approximation, SIAM J. Sci. Comp., 40 (2018), pp. A529–A547.
  * [28] M. Scholes and J. Williams, Estimating betas from nonsynchronous data, Journal of Financial Economics, 5 (1977), pp. 309–327.
  * [29] F. Stahl and R. Johansson, Diabetes mellitus modeling and short-term prediction based on blood glucose measurements, Mathematical Biosciences, 217 (2009), pp. 101–117.
  * [30] L. Trefethen and J. Weideman, The exponentially convergent trapezoidal rule, SIAM Review, 56 (2014), pp. 385–458.
  * [31] R. Vio, T. Strohmer, and W. Wamsteker, On the reconstruction of irregularly sampled time series, Publications of the Astronomical Society of the Pacific, 112 (2000), pp. 74–90.
  * [32] J. Wendel, Note on the gamma function, Amer. Math. Monthly, (1948), pp. 563–564.
  * [33] G. B. Wright, M. Javed, H. Montanelli, and L. N. Trefethen, Extension of Chebfun to periodic functions, SIAM J. Sci. Comp., 37 (2015), pp. C554–C573.
  * [34] R. Young, An Introduction to Nonharmonic Fourier Series, Elsevier Science, 1981.