# Multiscale estimates for the condition number of
non-harmonic Fourier matrices

Weilin Li

###### Abstract

This paper studies the extreme singular values of non-harmonic Fourier
matrices. Such a matrix can be written as $\Phi=[e^{-2\pi
ijx_{k}}]_{j=0,1,\dots,m-1,k=1,2,\dots,s}$ for some set
$\mathcal{X}=\\{x_{k}\\}_{k=1}^{s}$ and $m\geq s$. A main result provides an
explicit lower bound for the smallest singular value of $\Phi$ under the
assumption $m\geq 6s$ and without any restrictions on $\mathcal{X}$. It shows
that for an appropriate scale $\tau$ determined by a density criteria,
interactions between elements in $\mathcal{X}$ at scales smaller than $\tau$
are most significant and depends on the multiscale structure of $\mathcal{X}$
at fine scales, while distances larger than $\tau$ are less important and only
depend on the local sparsity of the far away points. Theoretical and numerical
comparisons show that the main result significantly improves upon classical
bounds and achieves the same rate that was previously discovered for more
restrictive settings.

2020 Math Subject Classification: 15A12, 15A60, 42A05, 42A15, 65F22

Keywords: Fourier matrix, singular values, trigonometric interpolation

##  1 Introduction

###  1.1 Motivation

For any
$\mathcal{X}=\\{x_{k}\\}_{k=1}^{s}\subseteq\mathbb{T}:=\mathbb{R}\setminus\mathbb{Z}$
and $m\in\mathbb{N}$, a (non-harmonic) Fourier matrix
$\Phi:=\Phi(m,\mathcal{X})$ of dimension $m\times s$ is defined as

$\Phi:=\Big{[}e^{-2\pi ijx_{k}}\Big{]}_{\begin{subarray}{c}j=0,1,\dots,m-1\\\
k=1,2,\dots,s\end{subarray}}.$

This definition generalizes the discrete (harmonic) Fourier transform matrix,
whereby $m=s$ and $\mathcal{X}$ consist of $s$ equally spaced points in
$\mathbb{T}$. Throughout the expository portions of this paper, we will
implicitly assume that $|\mathcal{X}|=s$, and we impose $m\geq s>1$ to avoid
trivialities.

Non-harmonic Fourier matrices are classical objects that appear in numerous
areas of mathematics. They provide a fundamental connection between linear
algebra and trigonometric interpolation, dating back to the work of Newton and
Lagrange. They are matrix representations of the Fourier transform, so they
naturally appear in the analysis of Fourier series [33], exponential sums
[32], and nonuniform Fourier transforms [13]. While $\Phi$ has full rank
whenever $m\geq s$ because it is a Vandermonde matrix, quantitative estimates
for its extreme singular values are of notable interest. There are important
connections to number theory [25, 30, 28], and when the rows of $\Phi$ are
viewed as elements of $\mathbb{C}^{s}$, then the squared extreme singular
values are the upper and lower fame constants [8, 12]. For numerical
applications, we require estimates to ensure that $\Phi$ can be used in
numerical schemes without incurring significant error.

While classical papers [15, 10, 5] concentrated on square matrices, tall ones,
where $m$ may be significantly larger than $s$, tend to be better conditioned.
Interest in the condition number of tall non-harmonic Fourier matrices has
been revitalized [23, 24, 23, 1, 20, 2, 3, 16, 17] partly due to modern
applications. For many signal and image processing problems, see [14, 21, 22]
and references therein, rectangular matrices appear more frequently, since $m$
represents the number of measurements or parameters, while $s$ corresponds to
the number of constraints. Parallel to this line of research, it is worth
noting that the approximation properties of trigonometric interpolation in the
$m\geq s$ regime has received interest [19, 31, 27] due to connections with
over-parameterization in machine learning.

The condition number $\kappa(\Phi)$ of $\Phi$ greatly depends on the “Rayleigh
length” $\frac{1}{m}$ versus the “geometry” of $\mathcal{X}$. The latter can
be partially described by the minimum separation of $\mathcal{X}$, defined as

$\Delta(\mathcal{X}):=\min_{j\not=k}|x_{j}-x_{k}|_{\mathbb{T}},\quad\text{and}\quad|t|_{\mathbb{T}}:=\min_{n\in\mathbb{Z}}|t-n|.$

Letting $\sigma_{k}(\Phi)$ denote the $k$-th largest singular value of $\Phi$,
it was shown in [1], inspired by [24] which was in turn proved using the
Beurling-Selberg majorant and minorant functions [30], that

$\text{if}\quad\Delta(\mathcal{X})>\frac{1}{m},\quad\text{then}\quad\sqrt{m-\frac{1}{\Delta(\mathcal{X})}}\leq\sigma_{s}(\Phi(m,\mathcal{X}))\leq\sigma_{1}(\Phi(m,\mathcal{X}))\leq\sqrt{m+\frac{1}{\Delta(\mathcal{X})}}.$
(1.1)

The intuition behind this inequality is that the columns of $\Phi$ are almost
orthogonal.

On the other hand, when $\Delta(\mathcal{X})\leq\frac{1}{m}$, simple numerical
experiments, see [20, 2], show that $\sigma_{s}(\Phi(m,\mathcal{X}))$ does not
follow the behavior in (1.1). This makes intuitive sense since if
$|x_{k}-x_{\ell}|_{\mathbb{T}}$ is small, then the $k$-th and $\ell$-th
columns of $\Phi$ are highly correlated, which results in a large condition
number. If $\kappa(\Phi)$ is significantly larger than 1, the smallest
singular value is the culprit because we have the trivial estimate
$\sigma_{1}(\Phi)\leq\|\Phi\|_{F}=\sqrt{ms}$, where $\|\cdot\|_{F}$ denotes
the Frobenius norm.

Accurate bounds for the smallest singular value have been obtained under
specific scenarios, namely when $\mathcal{X}$ can be partitioned in subsets
called “clumps”, where each clump is contained in an interval of length on the
order of $\frac{1}{m}$ and are far apart from each other. Without any
conditions on $\Delta(\mathcal{X})$ relative to $m$, in contrast to (1.1), the
results in [20, 2, 16, 3] roughly state that if each clump has cardinality at
most $\lambda$, and the clumps are sufficiently far away from each other, then

$c({\lambda,s})\sqrt{m}\,(m\Delta(\mathcal{X}))^{\lambda-1}\leq\sigma_{s}(\Phi(m,\mathcal{X}))\leq
C({\lambda,s})\sqrt{m}\,(m\Delta(\mathcal{X}))^{\lambda-1}.$ (1.2)

Since the exponent of $m\Delta(\mathcal{X})$ is $\lambda-1$, which may be
significantly smaller than $s-1$, this bound states that $\sigma_{s}(\Phi)$
depends on the local geometry of $\mathcal{X}$. It captures the intuition that
columns of $\Phi$ which correspond to different clumps are almost orthogonal
with respect to each other, so we expect the conditioning of $\Phi$ to only
depend each clump.

###  1.2 A motivational multiscale example

To better illustrate the limitations and boundaries of the state-of-the-art,
let us consider a typical set with multiscale structure such as

$\displaystyle\begin{split}\mathcal{X}&:=\mathcal{X}_{1}\cup\mathcal{X}_{2}\cup\mathcal{X}_{3},\quad\text{where}\quad\\\
\mathcal{X}_{1}:=\\{0,\tfrac{1}{90},\tfrac{2}{90},\tfrac{3}{90}\\},\quad&\mathcal{X}_{2}=\tfrac{1}{3}+\\{0,\tfrac{1}{200},\tfrac{2}{200}\\},\quad\text{and}\quad\mathcal{X}_{3}=\tfrac{2}{3}+\\{0,\tfrac{1}{500}\\}.\end{split}$
(1.3)

We have defined in $\mathcal{X}$ this way to emphasize that its three disjoint
subsets $\mathcal{X}_{1}$, $\mathcal{X}_{2}$, and $\mathcal{X}_{3}$ each have
significantly different separations and should be treated as separate scales.
The set $\mathcal{X}$ is shown in Figure 1. Our problem is to determine
behavior of $\sigma_{s}(\Phi(m,\mathcal{X}))$ as a function of $m$. Clearly
$\Phi(m,\mathcal{X})$ only has full rank when $m\geq s=9$ and (1.1) kicks in
when $m>\frac{1}{\Delta(\mathcal{X})}=500$ so it is natural to consider the
range $m\in[9,600]\cap\mathbb{N}$.

For this example, none of the bounds in [20, 2, 16, 3] are applicable, for any
$m\in[9,600]\cap\mathbb{N}$. The reason is that while $\mathcal{X}$ consists
of three “clumps” $\mathcal{X}_{1}$, $\mathcal{X}_{2}$, and $\mathcal{X}_{3}$,
they are too close to each other and do not satisfy these theorems’
assumptions. It is important to remark that the aforementioned papers
concentrated on the super-resolution limit, whereby either $m$ is sufficiently
large and there is a sequence of $\mathcal{X}_{m}$ for which
$\Delta(\mathcal{X}_{m})\to 0$, or alternatively, $m\to\infty$ and
$\Delta(\mathcal{X}_{m})\to 0$ with some relationship between $m$ and
$\Delta(\mathcal{X}_{m})$. Hence, it is not that surprising they cannot be
directly used.

Figure 1: Left: Plot of $\mathcal{X}$ defined in (1.3). Right: Plot of
$\sigma_{s}(\Phi(m,\mathcal{X}))$ and two different lower bounds as functions
of $m$ for $\mathcal{X}$ defined in (1.3).

In contrast, this experiment is for a fixed $\mathcal{X}$ and variable $m$
within a finite range. Determining $\sigma_{s}(\Phi(m,\mathcal{X}))$ is
naturally a discrete problem – there is no “large” or “small” parameters to
exploit. Nonetheless, our main theorem, Theorem 1, which is proved using
analytic tools, is applicable to this discrete problem, but with a mild
restriction that $m\geq 6s$. We are only aware of one other theorem that
applies to this example. It results from combining Gautschi [15] and Bazán
[4], which is stated in (3.1). The true $\sigma_{s}(\Phi(m,\mathcal{X}))$, our
main theorem, and the Gautschi-Bazán bound are displayed in Figure 1. We see
that our theorem offers a substantial improvement and better captures the true
behavior. Just to highlight the dramatic improvement, when $m=400$, our main
theorem underestimates the true value by a multiplicative factor of 21.0038,
whereas the Gautschi-Bazán bound is off by a factor of 1.9687e+05.

###  1.3 A main result

Providing general and accurate bounds for $\sigma_{s}(\Phi(m,\mathcal{X}))$
when $\Delta(\mathcal{X})\leq\frac{1}{m}$ is a tricky balancing act. We
require conditions on $\mathcal{X}$ that are not too restrictive, yet are
sufficiently informative enough that a resulting lower bound is not too loose.
We avoid restrictive assumptions by working with general geometric notions.

######  Definition 1.1.

Let $\tau\in(0,\frac{1}{2}]$ and $\mathcal{X}\subseteq\mathbb{T}$ be a finite
set. The $\tau$ local sparsity of $\mathcal{X}$ is

$\nu(\tau,\mathcal{X}):=\max_{x\in\mathcal{X}}\,\big{|}\\{x^{\prime}\in\mathcal{X}\colon|x-x^{\prime}|_{\mathbb{T}}\leq\tau\\}\big{|}.$

For convenience, we define $\nu(\tau,\emptyset):=0$.

The $\tau$ local sparsity is the maximum number of elements in $\mathcal{X}$
contained within a $\tau$-neighborhood of any $x\in\mathcal{X}$. By
definition, $\nu(\tau,\mathcal{X})=1$ if and only if
$\Delta(\mathcal{X})>\tau$. Importantly, we have
$\nu(\tau,\mathcal{U})\leq\nu(\tau,\mathcal{X})$ whenever
$\mathcal{U}\subseteq\mathcal{X}$. If $\tau=\frac{1}{2}$, then
$\nu(\tau,\mathcal{X})=s$, but it is possible that the local sparsity is
significantly smaller than $s$, and many examples of clumps have local
sparsity much smaller than $s$.

To simplify some of the notation that will appear in this paper, we define the
subsets,

$\mathcal{B}(x,\tau,\mathcal{X}):=\\{x^{\prime}\in\mathcal{X}\colon|x-x^{\prime}|_{\mathbb{T}}\leq\tau\\},\quad\text{and}\quad\mathcal{G}(x,\tau,\mathcal{X}):=\\{x^{\prime}\in\mathcal{X}\colon|x-x^{\prime}|_{\mathbb{T}}>\tau\\}.$

We will refer to these as the “bad” and “good” sets respectively, and this
terminology will make sense later. All lower bounds for
$\sigma_{s}(\Phi(m,\mathcal{X}))$ in this paper will use the following
assumption.

######  Definition 1.2.

For any $m\in\mathbb{N}_{+}$ and $\tau\in(0,\frac{1}{2}]$, we say a finite set
$\mathcal{X}\subseteq\mathbb{T}$ satisfies the $(m,\tau)$ density criteria if

$\frac{3\nu(\tau,\mathcal{X})}{\tau}\leq m.$

We call it the density criteria because $\frac{\nu(\tau,\mathcal{X})}{2\tau}$
can be interpreted as the density of $\mathcal{X}$ at scale $2\tau$, so the
assumption asserts that it cannot be bigger than $\frac{m}{6}$. This criteria
is not difficult to fulfill for some $\tau$. Indeed, if we assume $m\geq 6s$
and select $\tau=\frac{1}{2}$, then $3\nu(\tau,\mathcal{X})\tau^{-1}=6s\leq
m$, so the density criteria is satisfied. However, if $\mathcal{X}$ satisfies
the $(m,\tau)$ density criteria, then there are infinitely many other $\tau$
that are also valid, and the choice of $\tau$ will influence the below
estimates.

We are almost ready to present a main result. When interpreting the
expressions in this paper, we use the standard convention that the product
over an empty set is defined as 1. To simplify some of the resulting notation,
we define a special function $\phi\colon[1,\infty)\to[1,\infty)$ by

$\phi(t):=\frac{t}{\lfloor t\rfloor}.$ (1.4)

This function appears in several bounds since our methods depend on number
theoretic properties of several quantities. Note that $\phi(t)=1+o(t)$ as
$t\to\infty$.

######  Theorem 1.

Let $m,s\in\mathbb{N}_{+}$ such that $s\geq 2$ and $m\geq 6s$. Suppose
$\mathcal{X}=\\{x_{k}\\}_{k=1}^{s}\subseteq\mathbb{T}$ and there is a $\tau$
such that $\mathcal{X}$ satisfies the $(m,\tau)$ density criteria. For each
$k=1,2,\dots,s$, define
$\mathcal{G}_{k}:=\mathcal{G}(x_{k},\tau,\mathcal{X})$, the positive real
number

$\alpha_{k}:=\frac{|\mathcal{B}(x_{k},\tau,\mathcal{X})|}{2m-4\nu(\tau,\mathcal{G}_{k})\tau^{-1}},$

and the subsets

$\mathcal{I}_{k}:=\\{x\in\mathcal{X}\colon
0<|x-x_{k}|\leq\alpha_{k}\\}\quad\text{and}\quad\mathcal{J}_{k}:=\\{x\in\mathcal{X}\colon\alpha_{k}<|x-x_{k}|\leq\tau\\}.$

Then we have

$\frac{1}{\sigma_{s}^{2}(\Phi(m,\mathcal{X}))}\leq\sum_{k=1}^{s}2^{\nu(\tau,\mathcal{G}_{k})}\frac{2\alpha_{k}}{1-2\alpha_{k}}\prod_{x\in\mathcal{J}_{k}}\phi\Big{(}\frac{1}{2|x-x_{k}|_{\mathbb{T}}}\Big{)}^{2}\prod_{x\in\mathcal{I}_{k}}\frac{\alpha_{k}^{2}}{(1-2\alpha_{k})^{2}|x-x_{k}|_{\mathbb{T}}^{2}},$
(1.5)

and in particular,

${\sigma_{s}(\Phi(m,\mathcal{X}))}\geq\min_{1\leq k\leq s}\
\Big{\\{}\frac{1}{\sqrt{4s\alpha_{k}}}\frac{1}{\sqrt{2^{\nu(\tau,\mathcal{G}_{k})}}}\frac{1}{2^{|\mathcal{J}_{k}|}}\prod_{x\in\mathcal{I}_{k}}\frac{|x-x_{k}|_{\mathbb{T}}}{2\alpha_{k}}\Big{\\}}.$
(1.6)

$x_{k}$$2\alpha_{k}$$2\tau$ Figure 2: An example of the three scale
decomposition provided by Theorem 1. The red, orange, and blue points belong
to $\mathcal{I}_{k}$, $\mathcal{J}_{k}$, and $\mathcal{G}_{k}$ respectively.

Both inequalities provide a multiscale lower bound for the smallest singular
value. All numerical simulations in this paper use inequality (1.5), which
provides either the same or better estimate compared to (1.6). We provide an
explanation for the latter since this is simpler to understand. Here, for each
reference point $x_{k}\in\mathcal{X}$, the ranges $(\tau,\frac{1}{2}]$,
$(\alpha_{k},\tau]$, and $(0,\alpha_{k}]$ consists of the coarse,
intermediate, and small scales, respectively. An example is shown in Figure 2.
Points in the coarsest scale contribute the least, since
$\nu(\tau,\mathcal{G}_{k})\leq s-1$ and may be significantly smaller than
$s-1$. Each element in $\mathcal{J}_{k}$ contributes a constant factor.
Finally, the finest scales are dominant. Notice that each term inside the
product in (1.6) is bounded above by $\frac{1}{2}$ but may be significantly
smaller depending on the multiscale structure of $\mathcal{X}$. For instance,
when $m$ is fixed and $\Delta(\mathcal{X})\to 0$, the lower bound goes to 0,
as expected.

There is a detailed comparisons section that serves as an expanded version of
Section 1.1. There, we will see that our theorem captures the scaling and
localization phenomena that are missing from the classical Gautschi-Bazán
bound. In the case of clumps, we will provide a variation of the main theorem,
stated in Theorem 2, which provides an estimate equivalent to the lower bound
in (1.2) modulo universal constants, while holding under tremendously weaker
assumptions. The numerical simulations section compares our results with the
numerically computed value of $\sigma_{s}(\Phi)$ for a variety of sets and
under various regimes. There, we also provide more details regarding the
motivational example in Section 1.2. These examples illustrate the efficacy
and flexibility of our results.

###  1.4 Organization

Section 2 states all additional main results, Theorems 2 and 3. There, we
develop the main tool called the polynomial method and introduce two specific
interpolation problems that are connected to the main theorems. Section 3
provides more detailed comparisons with earlier work on the condition number
of non-harmonic Fourier matrices. Section 4 is dedicated to examples and
numerical simulations, with comparisons to the predictions provided by this
paper. Section 5 addresses the “good” and “bad” interpolation problems, and
their relationships to other results. Section 6 contains proofs of the main
theorems.

###  1.5 Notation

We use $\mathbb{Z}$, $\mathbb{N}$, $\mathbb{N}_{+}$, $\mathbb{R}$, and
$\mathbb{C}$ to denote the integers, naturals, positive naturals, reals, and
complex numbers, respectively. The torus is
$\mathbb{T}:=\mathbb{R}/\mathbb{Z}$ which we normally identify with $[0,1)$
via $x\mapsto\text{mod}(x,1)$. We let $\|\cdot\|_{p}$ and $\|\cdot\|_{L^{p}}$
denote the $\ell^{p}$ and $L^{p}$ norms respectively, for $1\leq p\leq\infty$.
The Fourier transform of a $f\in L^{2}(\mathbb{T})$ is denoted
$\widehat{f}\colon\mathbb{Z}\to\mathbb{C}$. We use the $2\pi$ convention so
that $\widehat{f}(k):=\int_{\mathbb{T}}f(x)e^{-2\pi ikx}\,dx$ and the Fourier
transform is unitary. We say $f$ is a trigonometric polynomial of degree $m-1$
if its Fourier transform is supported in $\\{0,1,\dots,m-1\\}$. We let
$\mathcal{P}_{m}$ be the set of all trigonometric polynomials of degree at
most $m-1$. The canonical basis vectors for $\mathbb{R}^{d}$ is denoted
$\\{e_{k}\\}_{k=1}^{d}$.

##  2 Additional main results and proof strategy

###  2.1 Other main results

Motivated by inverse problems where only weak information about $\mathcal{X}$
is known or can be reasonably assumed, we provide a different lower bound for
$\sigma_{s}(\Phi)$ in terms of any lower bound for $\Delta(\mathcal{X})$.
Throughout this paper, $\psi\colon[-\frac{1}{2},\frac{1}{2}]\to\mathbb{R}$ is
defined as

$\psi(t):=\Big{|}\frac{\sin(\pi t)}{\pi t}\Big{|},$ (2.1)

which is the absolute value of the sinc kernel restricted to
$[-\frac{1}{2},\frac{1}{2}]$.

######  Theorem 2.

Let $m,s\in\mathbb{N}_{+}$ such that $s\geq 2$ and $m\geq 6s$, and let
$\delta\in(0,\frac{1}{m}]$. Suppose $\mathcal{X}\subseteq\mathbb{T}$ is a set
of cardinality $s$ with $\Delta(\mathcal{X})\geq\delta$, and there is a $\tau$
such that $\mathcal{X}$ satisfies the $(m,\tau)$ density criteria. For each
$k=1,2,\dots,s$, define
$\mathcal{G}_{k}:=\mathcal{G}(x_{k},\tau,\mathcal{X})$, and the positive
natural numbers

$r_{k}:=|\mathcal{B}(x_{k},\tau,\mathcal{X})|\quad\text{and}\quad
n_{k}:=\Big{\lfloor}m-\frac{2\nu(\tau,\mathcal{G}_{k})}{\tau}\Big{\rfloor}.$

Then we have

$\frac{1}{\sigma_{s}^{2}(\Phi(m,\mathcal{X}))}\leq\frac{4e^{2}}{\pi^{2}}\sum_{k=1}^{s}2^{\nu(\tau,\mathcal{G}_{k})}\frac{\phi(\frac{n_{k}}{r_{k}})}{r_{k}n_{k}}\Big{(}\frac{4e\phi(\frac{n_{k}}{r_{k}})}{\pi\psi(\frac{n_{k}\delta}{2})n_{k}\delta}\Big{)}^{2r_{k}-2},$
(2.2)

and in particular,

$\sigma_{s}(\Phi(m,\mathcal{X}))\geq\frac{\pi}{2e}\sqrt{\frac{m}{6s}}\,\min_{1\leq
k\leq
s}\,\sqrt{\frac{r_{k}}{2^{\nu(\tau,\mathcal{G}_{k})}}}\Big{(}\frac{m\delta}{12e}\Big{)}^{r_{k}-1}.$
(2.3)

We emphasize that $\delta$ is an independent parameter, so the theorem is
applicable to sets for which $\Delta(\mathcal{X})$ is arbitrarily small. This
theorem is written with emphasis on $\delta$. The exponent on
$\frac{1}{\delta}$ is $2r_{k}-2$, which shows that interactions between $x$
and $x_{k}$ at scales smaller than $\tau$ are most significant. This theorem
assumes that $\delta\leq\frac{1}{m}$, which is not prohibitive since estimate
(1.1) can be used whenever $\delta>\frac{1}{m}$. The assumption
$\delta\leq\frac{1}{m}$ can be relaxed by adapting this theorem’s proof, but
this would add additional complications that is beyond the scope of this
paper.

There is a striking resemblance between inequalities (1.2) and (2.3). We will
explain in the comparisons section that under all known scenarios for which
the former holds, the later is also applicable and provides an equivalent
inequality. The main strength of (2.3), as well as all theorems in this paper,
is that it holds under dramatically weaker conditions and applies to
significantly more general sets beyond just clumps clumps.

Compared to Theorem 1, Theorem 2 is easier to employ since it requires less
information about $\mathcal{X}$, but it generally yields a looser bound. This
is expected since the right side of inequalities (2.2) and (2.3) only contain
$\delta$, as opposed to pairwise distances between elements of $\mathcal{X}$.
Both theorems give similar predictions if all small scales are on the order of
$\delta$, though Theorem 2 has the better universal constants. For sets with
many scales between $\delta$ and $\tau$, it is generally advisable to use
Theorem 1 instead.

While this paper focuses on the smallest singular value, the techniques
developed in this paper provide a straightforward and nontrivial upper bound
for the largest singular value.

######  Theorem 3.

Let $m,s\in\mathbb{N}_{+}$ such that $m\geq s$. For any
$\mathcal{X}\subseteq\mathbb{T}$ of cardinality $s$ and
$\tau\in(0,\frac{1}{2}]$ such that $m>\frac{1}{\tau}$, we have

$\sigma_{1}(\Phi(m,\mathcal{X}))\leq\sqrt{\nu(\tau,\mathcal{X})\Big{(}m+\frac{1}{\tau}\Big{)}}.$

For comparison purposes, recall the trivial bound
$\sigma_{1}(\Phi)\leq\|\Phi\|_{F}=\sqrt{ms}$. Observe that Theorem 3 provides
a significantly better upper bound if the $\tau$ local sparsity of
$\mathcal{X}$ is much smaller than $s$. For example, if we were to apply the
above for $\tau=\frac{2}{m}$, then
$\sigma_{1}(\Phi)=\sqrt{3\nu(\tau,\mathcal{X})m/2}$, which is better than the
trivial bound if $3\nu(\tau,\mathcal{X})<s/2$.

###  2.2 The polynomial method

The primary method that we will use to lower bound $\sigma_{s}(\Phi)$, or more
precisely, upper bound $\frac{1}{\sigma_{s}(\Phi)}$, is through a “dual”
relationship with minimum norm trigonometric interpolation. This duality was
introduced in [20, Proposition 2.12]: For any integers $m\geq s\geq 1$, finite
set $\mathcal{X}\subseteq\mathbb{T}$ of cardinality $s$, and unit vector
$v\in\mathbb{C}^{s}$ such that
$\Phi(m,\mathcal{X})v=\sigma_{s}(\Phi(m,\mathcal{X}))$, we have

$\sigma_{s}(\Phi(m,\mathcal{X}))=\max\Big{\\{}\frac{1}{\|f\|_{L^{2}}}\colon
f\in\mathcal{P}_{m}\text{ and }f(x_{k})=v_{k}\text{ for each }k\Big{\\}}.$
(2.4)

We refer to this equation as the duality principle, since it provides a
connection between the smallest singular value to minimum norm trigonometric
interpolation. There are related concepts [11, 7, 6] for $\mathbb{R}$ instead
of $\mathbb{T}$, but another main difference is that our $\mathcal{X}$ is
arbitrary and can be completely nonuniform.

It may be helpful to explain the intuition behind this duality. Suppose $v$
satisfies the hypothesis of this proposition and we examine all solutions $u$
to $\Phi^{*}u=v$. Due to the singular value decomposition, any minimum
$\ell^{2}$ norm vector $u$ that is consistent with this system will have norm
$1/\sigma_{s}(\Phi)$. Note that $\Phi^{*}$ is the matrix representation of the
linear transform that maps Fourier coefficients of functions in
$\mathcal{P}_{m}$ to their restriction on $\mathcal{X}$. Using the
Plancherel’s theorem allows us to pass from the Fourier coefficients to
polynomials. It follows from this discussion that a $f\in\mathcal{P}_{m}$
which achieves equality in (2.4) is necessarily a $f$ whose Fourier
coefficients are $u/\sigma_{s}(\Phi)$ where $u$ is any unit norm left singular
vector of $\Phi$ which corresponds to $\sigma_{s}(\Phi)$.

The duality principle provides a natural and constructive avenue for lower
bounding $\sigma_{s}(\Phi)$. However, since we have no exploitable information
on $v$, we construct interpolants for arbitrary $v$, and then estimate them in
$L^{2}$ uniformly in $v$. This leads us to the subsequent definition and
lemma.

######  Definition 2.1.

For any set $\mathcal{X}=\\{x_{k}\\}_{k=1}^{s}\subseteq\mathbb{T}$, we say
$\\{f_{k}\\}_{k=1}^{s}$ is a family of Lagrange interpolants for $\mathcal{X}$
if $f_{k}(x_{\ell})=\delta_{k,\ell}$ for each $1\leq k,\ell\leq s$.

######  Lemma 2.2.

For any $m,s\in\mathbb{N}_{+}$ with $m\geq s$ and
$\mathcal{X}\subseteq\mathbb{T}$ of cardinality $s$, if
$\\{f_{k}\\}_{k=1}^{s}\subseteq\mathcal{P}_{m}$ is a family of Lagrange
interpolants for $\mathcal{X}$, then

$\frac{1}{\sigma_{s}^{2}(\Phi(m,\mathcal{X}))}\leq\sum_{k=1}^{s}\|f_{k}\|_{L^{2}}^{2}.$

###### Proof.

Let $v\in\mathbb{C}^{s}$ be any unit norm vector such that $\Phi
v=\sigma_{s}(\Phi)$. Since $f=\sum_{k=1}^{s}v_{k}f_{k}$ interpolates $v$ on
$\mathcal{X}$, by equation (2.4) and Cauchy-Schwarz, we have

$\frac{1}{\sigma_{s}}\leq\|f\|_{L^{2}}\leq\sum_{k=1}^{s}|v_{k}|\|f_{k}\|_{L^{2}}\leq\Big{(}\sum_{k=1}^{s}\|f_{k}\|_{L^{2}}^{2}\Big{)}^{1/2}\Big{(}\sum_{k=1}^{s}|v_{k}|^{2}\Big{)}^{1/2}=\Big{(}\sum_{k=1}^{s}\|f_{k}\|_{L^{2}}^{2}\Big{)}^{1/2}.$

∎

This lemma was implicitly used in [20], and allows us to reduce the problem of
lower bounding $\sigma_{s}(\Phi)$ into constructing Lagrange interpolants. One
strength of this method is that it does not require any information about the
singular vectors of $\Phi$, which is usually more difficult to analyze than
the singular values. However, if we had additional information about them,
such as localization properties, then the $L^{2}$ estimate provided here can
be improved.

The next proposition is a new result, which serves as a converse to Lemma 2.2.
It shows that any lower bound on the smallest singular value provides the
existence of polynomials with prescribed interpolation properties.

######  Proposition 2.3.

If $\mathcal{X}\subseteq\mathbb{T}$ is a non-empty finite set with cardinality
$s$, then for any $w\in\mathbb{C}^{s}$ and integer $m\geq s$, there exits
$f\in\mathcal{P}_{m}$ such that $f|_{\mathcal{X}}=w$,

$\|f\|_{L^{2}}\leq\frac{\|w\|_{2}}{\sigma_{s}(\Phi(m,\mathcal{X}))}\quad\text{and}\quad\|f\|_{L^{\infty}}\leq\frac{\sqrt{m}\,\|w\|_{2}}{\sigma_{s}(\Phi(m,\mathcal{X}))}.$

###### Proof.

Note that $m\geq s$ implies $\Phi:=\Phi(m,\mathcal{X})$ is injective due to
the Vandermonde determinant theorem. We have the singular value decomposition
$\Phi=\sum_{k=1}^{s}\sigma_{k}u_{k}v_{k}^{*}$, where the $v_{k}$’s and
$u_{k}$’s are orthonormal and the $\sigma_{k}$’s are the nonzero singular
values of $\Phi$.

For any $w\in\mathbb{C}^{s}$, we have $w=\sum_{k=1}^{s}b_{k}v_{k}$ for some
$b\in\mathbb{C}^{s}$ such that $\|b\|_{2}=\|w\|_{2}$. For each $k$, we define
$f_{k}\in\mathcal{P}_{m}$ such that $\widehat{f_{k}}=u_{k}/\sigma_{k}$. Using
again that $\Phi^{*}$ is the matrix representation of the operator that maps
the Fourier coefficients of a function in $\mathcal{P}_{m}$ to its values on
$\mathcal{X}$, a direct calculation then yields that
$f|_{\mathcal{X}}=\Phi^{*}\widehat{f_{k}}=v_{k}$.

From here we see that $f:=\sum_{k=1}^{s}b_{k}f_{k}$ satisfies
$f|_{\mathcal{X}}=w$. Moreover, since the $u_{k}$’s are orthonormal, an
application of Parseval’s shows that the $f_{k}$’s are $L^{2}$ orthogonal, and
so

$\|f\|_{L^{2}}^{2}=\sum_{k=1}^{s}|b_{k}|^{2}\|f_{k}\|_{L^{2}}^{2}=\sum_{k=1}^{s}\frac{|b_{k}|^{2}}{\sigma_{k}^{2}}\leq\frac{\|w\|_{2}^{2}}{\sigma_{s}^{2}}.$

For the $L^{\infty}$ bound, we use that $f\in\mathcal{P}_{m}$, and Cauchy-
Schwarz, to get

$\|f\|_{L^{\infty}}\leq\|\widehat{f}\|_{\ell^{1}}\leq\sqrt{m}\,\|\widehat{f}\|_{\ell^{2}}=\sqrt{m}\,\|f\|_{L^{2}}.$

∎

We loosely refer to the strategy provided by the results of this subsection as
the polynomial method. A primary usefulness of this connection between
$\sigma_{s}(\Phi)$ and trigonometric interpolation is that it can be used
employ tools from Fourier analysis and polynomial approximation, instead of
solely working with matrices. While this connection is helpful, it is only
useful if one can construct Lagrange interpolants with small norm, otherwise
the resulting lower bounds for $\sigma_{s}(\Phi)$ would be quite loose.

###  2.3 Outline of the main proofs – an abstract perspective

The proofs of Theorems 1 and 2 are based on the following general recipe. Due
to the polynomial method, we only need to provide the existence of Lagrange
interpolants with suitably small norms and degree at most $m-1$. Note that
$\mathcal{P}_{m}$ enjoys numerous algebraic properties. In addition to being
vector space, if $f\in\mathcal{P}_{m}$ and $g\in\mathcal{P}_{n}$, then
$fg\in\mathcal{P}_{m+n-1}$. It is also a shift invariant space, namely,
$f\in\mathcal{P}_{m}$ if and only if $f(\cdot-t)\in\mathcal{P}_{m}$ for any
$t\in\mathbb{T}$.

We start the proof by fixing any $x_{k}\in\mathcal{X}$ and concentrate on
establishing a polynomial $f_{k}\in\mathcal{P}_{m}$ that interpolates the data
points $(\mathcal{X},e_{k})$ where $e_{k}\in\mathbb{R}^{s}$ is the $k$-th
canonical basis vector. Constructing a Lagrange interpolant of
$(\mathcal{X},e_{k})$ is straightforward, but doing so in a naive manner leads
to loose estimates. It is worth using the standard Lagrange interpolant
$\ell_{k}\in\mathcal{P}_{s}$ as a benchmark. Note that it has a pointwise
upper bound,

$\|\ell_{k}\|_{L^{\infty}}\leq\prod_{j\not=k}\frac{2}{|e^{2\pi ix_{k}}-e^{2\pi
ix_{j}}|}=2^{s-1}\prod_{j\not=k}\frac{1}{|e^{2\pi ix_{k}}-e^{2\pi ix_{j}}|}.$
(2.5)

The right hand side grows exponentially in $s$ and this product consists of
$s-1$ terms. It is significantly larger compared to the norms of polynomials
that we will construct. The main deficiency of $\ell_{k}$ is that
$\deg(\ell_{k})=s-1$, so it does not take advantage of the possibility that
interpolants can be selected from $\mathcal{P}_{m}$ where $m$ can be
significantly larger than $s$. From this point of view, we interpret $m$ as
the number of parameters or degrees of freedom, and $s$ as the number of
constraints.

Addition of two polynomials results in polynomial whose degree is the max,
while multiplication adds their degrees. It is intuitive that points in
$\mathcal{X}$ near $x_{k}$ require larger norm polynomials to interpolate,
since we need $f_{k}(x_{k})=1$, yet $f_{k}$ can potentially have many nearby
zeros, whereas further away points require smaller norms. Hence, it is natural
to decompose

$\mathcal{X}=\mathcal{B}_{k}\cup\mathcal{G}_{k},$

where the “bad” $\mathcal{B}_{k}$ and “good” $\mathcal{G}_{k}$ sets contain
the points near and far away from $x_{k}$, respectively. The scale $\tau$ at
which these sets are selected is important. Hence interpolating the data
$(\mathcal{X},e_{k})$ amounts to finding and multiplying Lagrange interpolants
of $(\mathcal{B}_{k},e_{k})$ and $(\mathcal{G}_{k}\cup\\{x_{k}\\},e_{k})$,
where the two $e_{k}$’s here may have different lengths.

The interpolation problem for the good set is handled in Section 5.1. Although
each element of $\mathcal{G}_{k}$ is sufficiently far away from $x_{k}$,
points in $\mathcal{G}_{k}$ can still be close together, so it is not clear
that there is even any advantage of splitting $\mathcal{X}$ into the good and
bad sets. To deal with this, we will employ Proposition 5.1 to further
decompose,

$\mathcal{G}_{k}=\mathcal{G}_{k,1}\cup\dots\cup\mathcal{G}_{k,\nu_{k}},$

where $\nu_{k}:=\nu(\tau,x_{k},\mathcal{G}_{k})$ and
$\Delta(\mathcal{G}_{k,j})$ is suitably controlled from below. By using
Proposition 2.3 and (1.1), we obtain the existence of an interpolant for the
data $(\mathcal{G}_{k,j}\cup\\{x_{k}\\},e_{k})$ for each $j$, which are
multiplied together.

The interpolation problem for the bad set is handled in Section 5.2. The
starting point is a basic observation that the standard Lagrange interpolant
for $(\mathcal{B}_{k},e_{k})$ can be pointwise bounded by the distances
between elements of $\mathcal{B}_{k}$ and $x_{k}$ as seen in (2.5). Note that
if $q|t|_{\mathbb{T}}\leq\frac{1}{2}$ for some $q\in\mathbb{N}_{+}$, then
$|qt|_{\mathbb{T}}=q|t|_{\mathbb{T}}$. Hence, if we shift and dilate the
elements of $\mathcal{B}_{k}$, and use a Lagrange interpolant for the dilated
points,

$h_{k}(x)=\prod_{j\in\mathcal{B}_{k}\setminus\\{x_{k}\\}}\frac{e^{2\pi
iq_{j}x}-e^{2\pi iq_{j}x_{j}}}{e^{2\pi iq_{j}x_{k}}-e^{2\pi iq_{j}x_{j}}},$

then this polynomial will have significantly smaller norm and larger degree
compared to the standard Lagrange interpolant $\ell_{k}$. Here, each $q_{j}$
will need to be chosen so that the degree of $h_{k}$ is not too large. While
this idea

Finally, the desired Lagrange interpolant for $(\mathcal{X},e_{k})$ is found
by multiplying the individual interpolants for the good and bad sets. Doing
this for each $k$ yields a family of Lagrange interpolants for $\mathcal{X}$
in $\mathcal{P}_{m}$, allowing us to employ Lemma 2.2.

Carrying out these steps requires exploiting the advantages of several
seemingly disparate techniques and approaches. Inspired by interpolation
results [11, 7], the polynomial method was introduced in [20] to deal with
more structured sets and is further refined in this paper to handle more
abstract sets. The initial decomposition of $\mathcal{X}$ into
$\mathcal{B}_{k}$ and $\mathcal{G}_{k}$ is inspired by the classical Calderón-
Zygmund decomposition [29] and the scale $\tau$ is determined by the density
criteria. While we were able to find prior work closely related to our density
criteria, it is important to mention that there are intimate connections
between density of sets and sampling [18]. Compared to [11], we allow for
fully nonuniform sets as opposed to subsets of a lattice. Our method for
dealing with the good set requires the lower bound in (1.1), which was proved
in [1] by using powerful machinery developed for analytic number theory [30].
Finally, the method for dealing with the bad set using local dilation methods
was originally employed in [20] and we make significant improvements to in
this paper in order to handle a much broader class of sets.

##  3 Comparison with prior art

###  3.1 Comparison to classical estimates

A primary distinction between classical versus modern papers on the
conditioning of non-harmonic Fourier matrices is really a tale of square
versus rectangular matrices. The paper [5] showed that for a $s\times s$
matrix, it is perfectly conditioned if and only if $\mathcal{X}$ is some shift
of $\\{\frac{k}{s}\\}_{k=1}^{s}$. It is natural to wonder whether it is
possible to relax both sides of this characterization. It would be a delicate
task, since [10] established that if $\mathcal{X}$ consists of the first $s$
terms of the Van Der Corput sequence, then $\kappa(\Phi(s,\mathcal{X}))=1$
only if $\log_{2}(s)$ is an integer, but grows like $\sqrt{s}$ otherwise. This
example illustrates that it is possible for $\kappa(\Phi(s,\mathcal{X}))$ to
be unbounded in $s$ even if $\mathcal{X}$ is “spread out” in $\mathbb{T}$.

The results listed in the previous paragraph illustrate the brittleness of
square matrices, while rectangular ones are much more robust. Any $m\times s$
sub-matrix of the $m\times m$ discrete Fourier transform matrix is perfectly
conditioned even though the nodes are not uniformly spaced on the circle. More
generally, notice from inequality (1.1) that $\Delta(\mathcal{X})>\frac{1}{m}$
implies the conditioning of $\Phi(m,\mathcal{X})$ can be bounded uniformly in
$m$. It is important to mention that this only applies to rectangular matrices
since $\Delta(\mathcal{X})>\frac{1}{m}$ implies that $m>s$. These observations
should be compared with the ones listed in the previous paragraph for square
matrices.

Results for square matrices can be used to deduce bounds for rectangular ones,
beyond the trivial relationship
$\sigma_{s}(\Phi(m,\mathcal{X}))\geq\sigma_{s}(\Phi(s,\mathcal{X}))$. We first
start with Gautschi [15, Theorem 1],

$\|\Phi(s,\mathcal{X})^{-1}\|_{\infty}\leq\max_{1\leq k\leq
s}\prod_{x\in\mathcal{X}\setminus\\{x_{k}\\}}\frac{2}{|e^{2\pi ix}-e^{2\pi
ix_{k}}|}.$

Here, $\|\cdot\|_{p}$ denotes the $\ell^{p}\to\ell^{p}$ operator norm. Next,
Bazán [4, Theorem 1] showed that whenever $\frac{m}{s}\in\mathbb{N}$, then

$\|\Phi(m,\mathcal{X})^{\dagger}\|_{2}\leq\sqrt{\frac{s}{m}}\,\|\Phi(s,\mathcal{X})^{-1}\|_{2}.$

Combining the above two inequalities, that
$\|A\|_{2}\leq{\sqrt{s}}\|A\|_{\infty}$ if $A\in\mathbb{C}^{s\times s}$, and
$\sigma_{s}(\Phi(m,\mathcal{X}))\geq\sigma_{s}(\Phi(\lfloor\frac{m}{s}\rfloor
s,\mathcal{X}))$, we obtain

$\sigma_{s}(\Phi(m,\mathcal{X}))\geq\sqrt{\frac{\lfloor\frac{m}{s}\rfloor}{s}}\,\min_{1\leq
k\leq s}\prod_{x\in\mathcal{X}\setminus\\{x_{k}\\}}\frac{|e^{2\pi ix}-e^{2\pi
ix_{k}}|}{2}.$ (3.1)

Throughout the paper, we refer to (3.1) as the Gautschi-Bazán theorem.

Note that if $|x-x_{k}|_{\mathbb{T}}$ is small, then $|e^{2\pi ix}-e^{2\pi
ix_{k}}|$ is comparable to $|x-x_{k}|_{\mathbb{T}}$. Comparing with Theorem 1,
we see that inequality (3.1) differs in two main aspects. First, (3.1) does
not exhibit localization since this product is taken over all
$x\in\mathcal{X}\setminus\\{x_{k}\\}$, whereas in our theorem, the product is
over all $x\in\mathcal{I}_{k}$ while the further away elements are less
significant. Second, (3.1) does not include a scaling factor in front of
$|e^{2\pi ix}-e^{2\pi ix_{k}}|$. In our theorem, notice that each term has a
helpful $\alpha_{k}$ factor, which could be on the order of $\frac{1}{m}$. The
localization and scaling phenomenon manifest when we consider rectangular
Fourier matrices. Examining the proof of [4, Theorem 1], we see that is treats
tall Fourier matrices as $\lfloor\frac{m}{s}\rfloor$ independent $s\times s$
blocks, and does not fully exploit the algebraic structure of tall Fourier
matrices.

Continuing the remarks made in the previous paragraph, there is an elementary
explanation for why tall Fourier matrices should behave differently from
square ones. Notice that $(\Phi^{*}\Phi)_{j,k}=D_{m}(x_{j}-x_{k}),$ where
$D_{m}(t):=\sum_{k=0}^{m-1}e^{2\pi ikt}$ is the Dirichlet kernel. We easily
see that $|D_{m}(t)|$ is on the order of $m$ on the interval
$[-\frac{1}{m},\frac{1}{m}]$ and decays at a rate of $|t|^{-1}$ away from $0$.
This means that the Gram matrix $\Phi^{*}\Phi$, for fixed $\mathcal{X}$ and
increasing $m$, becomes increasingly diagonally dominant. Basic tools such as
the Gershgorin circle theorem fail to provide any meaningful results when
$\Delta(\mathcal{X})<\frac{1}{m}$ and $s\geq 3$ since the row/columns norms of
$\Phi^{*}\Phi$ exceed 1.

###  3.2 Comparison to clumps

Clumps models for $\mathcal{X}$ were independently introduced in [20, 2] and
were used to control the conditioning of tall non-harmonic Fourier matrices.
There are some subtle differences between the definitions in these papers, so
to facilitate the presentation and to avoid giving two separate definitions,
we work with the following boarder definition that encapsulates both
frameworks. For sets $\mathcal{U},\mathcal{V}\subseteq\mathbb{T}$, we define
the diameter and distance,

$\text{diam}(\mathcal{U}):=\sup_{u,u^{\prime}\in\mathcal{U}}|u-u^{\prime}|_{\mathbb{T}}\quad\text{and}\quad\text{dist}(\mathcal{U},\mathcal{V}):=\inf_{u\in\mathcal{U},v\in\mathcal{V}}|u-v|_{\mathbb{T}}.$

######  Definition 3.1.

A set $\mathcal{X}\subseteq\mathbb{T}$ consists of separated clumps with
parameters $(s,\delta,r,\lambda,\alpha,\beta)$ if the following hold. We have
$|\mathcal{X}|=s$, $\Delta(\mathcal{X})\geq\delta$, and there is a disjoint
union

$\mathcal{X}=\mathcal{C}_{1}\cup\mathcal{C}_{2}\cup\cdots\cup\mathcal{C}_{r},$
(3.2)

where each $\mathcal{C}_{k}$ is called a clump and for all distinct $j,k$,

$\max_{1\leq k\leq
r}|\mathcal{C}_{k}|=\lambda,\quad\text{diam}(\mathcal{C}_{k})\leq\alpha,\quad\text{and}\quad{\rm
dist}(\mathcal{C}_{j},\mathcal{C}_{k})>\beta>\alpha\quad\text{if $r\geq 2$}.$

A few remarks are in order. For a fixed $\mathcal{X}$, the choice of
parameters is not unique and it is usually advisable to minimize for
$\lambda$. If $r=1$, then $s=\lambda$ and $\beta$ is not a meaningful
parameter since there is only a single clump – this is why the clump
separation requirement is necessary only when $r\geq 2$. It is natural to
place restrictions on the parameters, such as $\alpha\leq\frac{1}{2}$,
$\delta(\lambda-1)\leq\alpha$, and $(\alpha+\beta)r\leq 1$. Notice
$\beta>\alpha$ is included in the assumption so that distances between clumps
exceeds within a clump. As we will see, a major drawback of [20, 2, 16, 3] is
that additional assumptions beyond these natural restrictions are needed to
invoke these results.

There is a stark conceptual distinction between the clumps decomposition
(3.2), which groups the elements of $\mathcal{X}$ by their spatial locations,
versus Proposition 5.1, which decomposes $\mathcal{X}$ into disjoint subsets
that each have unit local sparsity. An example is shown in Figure 3.

(a) Example set

(b) Clumps decomposition

(c) Sparsity decomposition

Figure 3: Clumps versus sparsity decomposition.

There are natural situations where a set consisting of separated clumps also
satisfies the requirements of our main results, as shown in the next
proposition.

######  Proposition 3.2.

Let $m,s\in\mathbb{N}_{+}$ with $m\geq 6s$. Suppose $\mathcal{X}$ consists of
separated clumps with parameters $(s,r,\delta,\lambda,\alpha,\beta)$ such that
$\delta\leq\frac{1}{m}$ and $\beta\geq\frac{3\lambda}{m}$ provided that $r>1$.
If $r=1$, set $\tau=\frac{1}{2}$, otherwise let $\tau=\beta$. Then
$\mathcal{X}$ satisfies the $(m,\tau)$ density criteria, and the conclusions
of Theorems 1 and 2 hold. In particular, we have

$\sigma_{s}(\Phi(m,\mathcal{X}))\geq\frac{\pi}{2e}\sqrt{\frac{m}{6s2^{\lambda}}}\Big{(}\frac{m\delta}{12e}\Big{)}^{\lambda-1}.$

###### Proof.

We first claim that $\mathcal{X}$ satisfies the $(m,\tau)$ density criteria.
This trivially holds when $r=1$ because then $\tau=\frac{1}{2}$ and so
$\nu(\tau,\mathcal{X})=|\mathcal{X}|=s=\lambda$. From here onward, assume that
$r>1$. For any $x\in\mathcal{X}$, let $\mathcal{C}_{x}$ be the clump that $x$
belongs to. Since $\beta>\alpha$ by definition, we see that

$\mathcal{C}_{x}=\\{x^{\prime}\in\mathcal{X}\colon|x-x^{\prime}|_{\mathbb{T}}\leq\beta\\},$

otherwise it would contradict the assumption that any two clumps are separated
by distances strictly larger than $\beta$ and that ${\rm
diam}(\mathcal{C}_{x})\leq\alpha<\beta$. This shows that
$\nu(\tau,\mathcal{X})\leq\lambda$, and since there is a clump that has
cardinality exactly equal to $\lambda$, we see that
$\nu(\tau,\mathcal{X})=\lambda$. We have $\beta\geq\frac{3\lambda}{m}$ by
assumption, and so

$\frac{3\nu(\tau,\mathcal{X})}{\tau}=\frac{3\lambda}{\beta}\leq m.$

We have shown that the assumptions of Theorem 2 are satisfied. For each $k$ in
the right side of (2.3), we use that $r_{k}\leq\nu(\tau,\mathcal{X})=\lambda$
and $\nu(\tau,\mathcal{G}_{k})\leq\nu(\tau,\mathcal{X})=\lambda$ to complete
the proof. ∎

In the following comparisons, as usual, we let $m$ and $s$ denote the number
of rows and columns of $\Phi$. We will only compare the general scaling of the
model parameters and do not compare universal constants, since the latter can
be improved by optimizing their proofs and by providing more accurate but
complicated expressions. When comparing our main theorems with other papers,
we will generally ignore distinctions between $m-1$, $m$, and $2m$.

The result [20, Theorem 2.7] shows that if $\mathcal{X}$ consists of separated
clumps with parameters $(s,\delta,r,\lambda,\frac{1}{m},\beta)$ such that

$m\geq
s^{2}\quad\text{and}\quad\beta\geq\frac{20}{m-1}\sqrt{\frac{s\lambda^{5}}{(m-1)\delta}}\quad\text{if}\quad
r>1,$ (3.3)

then there exist explicit universal constants $C>0$ and $c\in(0,1)$ such that

$\sigma_{s}(\Phi(m,\mathcal{X}))\geq
C\sqrt{\frac{m-1}{\lambda}}\big{(}c(m-1)\delta\big{)}^{\lambda-1}.$

One main drawback of condition (3.3) is that $\beta\to\infty$ as $\delta\to
0$, so for sufficiently small $\delta$, the theorem only applies when there is
only a single clump. Some improvements to the explicit constants and
variations of this inequality can be found in [16]. All results in this paper
also require separation conditions for which $\beta\to\infty$ as $\delta\to
0$.

Proposition 3.2 shows that under the same hypotheses (3.3), this paper’s main
results are applicable and they yield the same
$\sqrt{m}(cm\delta)^{\lambda-1}$ rate. Note however that Proposition 3.2
requires significantly less separation between clumps, a weaker condition on
$m$ versus $s$, and it removes the artificial behavior that $\beta$ explodes
for small $\delta$.

Moving on, [3, Theorem 2.2] shows that if $\mathcal{X}$ consists of separated
clumps with parameters $(s,\delta,r,\lambda,\alpha,\beta)$ such that

$\frac{c_{1}(\lambda)s}{\pi\beta}\leq m\leq\frac{c_{2}(\lambda)}{\pi
s\alpha},$ (3.4)

for some $c_{1}(\lambda),c_{2}(\lambda)>0$ depending only on $\lambda$, then
there is an explicit universal constant $C^{\prime}>0$ such that

$\sigma_{s}\big{(}\Phi(2m+1,\mathcal{X})\big{)}\geq
C^{\prime}\sqrt{m}\,\Big{(}\frac{m\delta}{16e}\Big{)}^{\lambda-1}.$

Note we made some adjustments to the constants in these expression since that
paper identifies $\mathbb{T}$ with $[-\pi,\pi)$ as opposed to $[0,1)$ in our
paper.

Although $c_{1},c_{2}$ are not given explicitly, [3, Section 6.3] shows that
$c_{1}(\lambda)>C(1+\lambda^{9})$ for some universal $C>0$ and
$c_{2}(\lambda)\leq 2\pi$. Hence, condition (3.4) requires, for all
sufficiently large $\lambda$,

$\alpha\leq\frac{2}{sm}\quad\text{and}\quad\beta\geq\frac{C(1+\lambda^{9})s}{m}\geq\frac{3\lambda}{m}.$

This establishes that Proposition 3.2 is also applicable and provides a lower
bound with the same rate, but again, under significantly weaker assumptions.

###  3.3 Other related work

Clumps models were also introduced in [2] to bound the smallest singular value
of “continuous” versions of $\Phi$. Corollary 3.6 of this reference assumes
that $\mathcal{X}$ consists of separated clumps and with the additional
requirement that ${\rm diam}(\mathcal{X})\leq\frac{1}{\pi s^{2}}$. It is not
possible rescale this result, so we cannot provide a reasonable comparison.
Nevertheless, the restriction that $\mathcal{X}$ is contained in an interval
of length $\frac{1}{\pi s^{2}}$ is removed in a follow-up result [3], which we
already compared to. The “colliding nodes” model, where $\mathcal{X}$ can be
decomposed into clumps where each one has exactly two elements, was studied in
[17]. This is much more restrictive than the clumps model and can be treated
with specialized tools that cannot be extend to more complicated and general
sets.

##  4 Numerical simulations and examples

###  4.1 Setup and definitions

When comparing the true value of $\sigma_{s}(\Phi)$ and our estimated one, we
use our most accurate estimate (1.5) from Theorem 1. The software that
reproduces the figures that appear in this paper are publicly available on the
author’s Github 111https://github.com/weilinlimath, which is also linked to
the author’s personal website 222https://weilinli.ccny.cuny.edu.

The behavior of Fourier matrices was numerically evaluated in [20, 3, 2, 16]
under the super-resolution limit, whereby $m$ is sufficiently large and there
is a family of $\\{\mathcal{X}_{m}\\}_{m=1}^{\infty}$ for which
$\Delta(\mathcal{X}_{m})\to 0$, or alternatively, $m\to\infty$ and
$\Delta(\mathcal{X}_{m})\to 0$ with some relationship between $m$ and
$\Delta(\mathcal{X}_{m})$. This is an important scaling in the theory of
super-resolution and the behavior of $\sigma_{s}(\Phi)$ greatly simplifies in
this scenario. The main results of this paper can be used for the super-
resolution limit as well and would give equivalent predictions up to implicit
constants, see Proposition 3.2. One can consider a complementary scaling,
called the well-separated case, whereby $\mathcal{X}$ is fixed and
$m\to\infty$. In this case, (1.1) is applicable.

Rather than look at either scaling again, we look at more challenging
examples. In the absence of a “large” or “small” parameter, determining
$\sigma_{s}(\Phi(m,\mathcal{X}))$ is naturally a discrete problem.
Nonetheless, even though our main theorem is proved using analytic tools, it
only requires a weak assumption that $m\geq 6s$, so it is applicable to a
greater variety of examples. We are only aware of one other result with this
generality, which is the Gautschi-Bazán bound in (3.1). The discussion there
highlighted the two differences between this estimate and ours, scaling and
localization.

Since we provide lower bounds for the smallest singular value, it makes sense
to quantify the quality of approximation by a multiplicative factor. That is,
we define the

$\text{inaccuracy factor}:=\frac{\text{true value}}{\text{estimated value}}$

Of course, inaccuracy factor $\geq 1$, so smaller values are better.

###  4.2 The motivational example revisited

Here, we provide additional details for the motivational example in Section
1.2. First, notice that for a fixed $\mathcal{X}$, the set of $\tau$ for which
the $(m,\tau)$ density criteria is satisfied are nested increasing sets as $m$
increases. More precisely, if we define

$\mathcal{S}(m,\mathcal{X}):=\\{\tau\colon\mathcal{X}\text{ satisfies the
}(m,\tau)\text{ density criteria}\\},$

then $\mathcal{S}(m,\mathcal{X})\subseteq\mathcal{S}(m+1,\mathcal{X})$. So as
$m$ increases, we have the option of choosing $\tau:=\tau(m)$ smaller in order
to reduce the number $x\in\mathcal{X}$ that are close to each $x_{k}$.
However, we do not simply define

$\tau(m):=\operatorname*{arg\,min}\mathcal{S}(m)$

because $\alpha_{k}$ may increase when $\tau$ decreases. Choosing an optimal
$\tau$ is beyond the scope of this paper, but it is not difficult to select
reasonable a candidate based on intuition, and trial and error.

Figure 4: Plot of $\nu(\tau,\mathcal{X})$ as a function of
$\tau\in(0,\frac{1}{2}]$.

Returning back to the motivational example, after some calculations, we define

$\tau:=\begin{cases}\ \frac{2}{30}&\text{if }m\in(450,600],\\\ \
\frac{3}{10}&\text{if }m\in[54,450].\end{cases}$

For these corresponding values of $\tau$, it can be easily checked that
$\nu(\tau,\mathcal{X})=3,4$ and that $\mathcal{X}$ satisfies the $(m,\tau)$
density criteria. To visualize the former, we have plotted
$\nu(\tau,\mathcal{X})$ as a function of $\tau$ in Figure 4. Note that our
choices for $\tau$ are not optimized, but were chosen according to reasonable
heuristics.

As shown in Figure 1, our theorem yields a significantly more accurate
prediction, which becomes more apparent as $m$ increases. This occurs because
the effective scale should decrease in $m$ and the effective distance between
nearby elements is scaled, neither of which are captured in Gautschi-Bazán’s
theorem. The results in [20, 16] are not applicable for any
$m\in[9,600]\cap\mathbb{N}$, because the separation condition (3.3) is not
fulfilled. [2] cannot be used since $\mathcal{X}$ is not contained in an
interval of length $\frac{1}{\pi s^{2}}$, and it is unclear whether [3] is
applicable since (3.4) has an implicit constant.

###  4.3 Another multiscale example

Unlike the motivational example in Section 1.2 where $\mathcal{X}$ was fixed
and $m$ varies, we consider the reverse situation where $m$ is fixed and we
have a family of sets $\mathcal{X}(\varepsilon)$ parameterized by a
$\varepsilon\in(0,1]$. Consider the set

$\displaystyle\begin{split}\mathcal{X}(\varepsilon)&:=\mathcal{X}_{1}(\varepsilon)\cup\mathcal{X}_{2}(\varepsilon)\cup\mathcal{X}_{3}(\varepsilon),\quad\text{where}\quad\\\
\mathcal{X}_{1}(\varepsilon)=\varepsilon\\{0,\tfrac{1}{90},\tfrac{2}{90},\tfrac{3}{90}\\},\quad&\mathcal{X}_{2}(\varepsilon)=\tfrac{1}{3}+\varepsilon\\{0,\tfrac{1}{200},\tfrac{2}{200}\\},\quad\text{and}\quad\mathcal{X}_{3}(\varepsilon)=\tfrac{2}{3}+\varepsilon\\{0,\tfrac{1}{500}\\}.\end{split}$
(4.1)

We have defined $\mathcal{X}(\varepsilon)$ in this way to emphasize that while
$\varepsilon$ controls the minimum separation since
$\Delta(\mathcal{X}(\varepsilon))=\frac{\varepsilon}{500}$, the three sets
$\mathcal{X}_{1}$, $\mathcal{X}_{2}$, and $\mathcal{X}_{3}$ are still of
different scales for each $\varepsilon$.

Since $\Delta(\mathcal{X}(\varepsilon))\leq\frac{1}{500}$ for any
$\varepsilon$, we consider only $m\leq 500$. If we pick $\tau=\frac{3}{10}$,
then $\nu(\tau,\mathcal{X}(\varepsilon))=4$ for all $\varepsilon$. For two
separate experiments, we select $m=400$ and $m=100$. Note that
$\mathcal{X}(\varepsilon)$ satisfies the $(m,\tau)$ density criteria for all
values of $\varepsilon$.

Figure 5: For $\mathcal{X}$ defined in (4.1), plot of
$\sigma_{s}(\Phi(m,\mathcal{X}(\varepsilon)))$, main theorem, and Gautschi-
Bazán bound, as a function of $\varepsilon$, with $m=400$ on the left and
$m=100$ on the right.

The results are shown in Figure 5. We see from the simulations that our lower
bound matches the true behavior of the smallest singular value. Notice that
for both experiments, $\sigma_{s}(\Phi)$ is piece-wise linear, which is
expected. Indeed, our theory states that the only significant interactions
between $x,x^{\prime}\in\mathcal{X}$ are those for which
$|x-x^{\prime}|\leq\tau$. For $\tau=\frac{3}{10}$, the sets $\mathcal{X}_{1}$,
$\mathcal{X}_{2}$, and $\mathcal{X}_{3}$ do not have significant interactions
due to our choice of $\tau$. They also have cardinality 4, 3, and 2
respectively for all $\varepsilon$, and the interactions between elements in
each $\mathcal{X}_{k}$ scales linearly with $\varepsilon$. Hence, according to
Theorem 1, we expect

$\sigma_{s}(\Phi(m,\mathcal{X}(\varepsilon)))\gtrsim
c_{1}\varepsilon^{3}+c_{2}\varepsilon^{2}+c_{3}\varepsilon^{1},$

for some universal constants that can be explicitly computed. Hence, as
$\varepsilon$ varies, depending on the regime of $\varepsilon$ and the size of
$c_{1},c_{2},c_{3}$, the dominant term in this inequality changes. In fact,
Figure Fig. 5a shows that $\log(\sigma_{s}(\Phi))$ consists of three linear
pieces. For the left graph in Figure 5, the three piece-wise linear graphs
have slopes are approximately $3.0055$, $2.0321$, and $0.9485$, which is
consistent with our prediction.

###  4.4 Sparse spike train

In this example, we consider an extreme situation where $\tau$ cannot be
chosen on the order of $\frac{1}{m}$ even though the number of elements in an
interval of length $\frac{2}{m}$ is at most 3. For any
$\varepsilon\in(0,\frac{1}{2}]$ and $s\in[5,30]\cap\mathbb{N}_{+}$, we set
$m=200$ and consider the following set,

$\mathcal{X}(s,\varepsilon)=(1-\varepsilon)\\{0,\tfrac{1}{m},\dots,\tfrac{s-1}{m}\\}.$
(4.2)

Our choice of $m$ and $s$ here are arbitrary and we could have considered
larger or smaller $m$ provided that $s$ is sufficiently small compared to $m$.

Figure 6: For $\mathcal{X}$ defined in (4.2), $m=200$, and
$\varepsilon=0.1,0.3,0.5$, graphs of
$\sigma_{s}(\Phi(m,\mathcal{X}(s,\varepsilon)))$ and (1.5) are shown in solid
and dashed respectively.

It was shown in [24] that for fixed $\varepsilon$, provided that $s\geq C\log
m$, then $\sigma_{s}(\Phi(m,\mathcal{X}(s,\varepsilon)))\asymp
e^{-c\varepsilon s}$ for some unspecified universal $C,c>0$. This is an
important example as it has several implications. First, it shows that even if
$\mathcal{X}$ consists of clumps, they need to be sufficiently far apart for
the lower bound in (1.2) to be valid, otherwise there is a contradiction.
However, it does not provide a quantitative bound on the clump separation.
Second, it implies that $\Delta(\mathcal{X})\geq\frac{1}{m}$ in the absence of
additional assumptions is necessary. This also explains why the density
criteria is necessary.

Notice at $\nu(\frac{1}{m},\mathcal{X}(s,\varepsilon))\leq 3$ for all
$\varepsilon\in(0,\frac{1}{2}]$, so at first glance, it may seem temping to
set $\tau$ on the order of $\frac{1}{m}$. This would violate the $(m,\tau)$
density criteria, since it is not hard to see that there is no
$\tau<\frac{3s}{m}$ for which $\mathcal{X}(s,\varepsilon)$ satisfies the
$(m,\tau)$ density criteria. On the other hand, if $\tau\geq\frac{3s}{m}$,
then $\nu(\tau,\mathcal{X}(s,\varepsilon))=s$ and consequently, $\mathcal{X}$
satisfies the $(m,\tau)$ density criteria. The graph of
$\nu(\tau,\mathcal{X})$ as a function of $\tau$ is shown in Figure 6. Thus, we
are in the extreme case where we should just pick $\tau=\frac{1}{2}$, and so
$\mathcal{X}$ satisfies the $(m,\tau)$ density criteria due to $m\geq 6s$.
Intuitively, $\mathcal{X}$ is an example of a high density set.

Figure 6 plots both the exact values of
$\sigma_{s}(\Phi(m,\mathcal{X}(s,\varepsilon)))$ and the lower bound (1.5) as
functions of $s$ and for $\varepsilon=0.1,0.3,0.5$. The numerical simulations
indicate that $\log(\sigma_{s}(\Phi(m,\mathcal{X}(s,\varepsilon))))$ is well
approximated by an affine function of $s$, namely,

$\log(\sigma_{s}(m,\mathcal{X}(s,\varepsilon)))=b(\varepsilon,m)-c(\varepsilon,m)s+\text{less
significant terms depending on $s$}.$

This behavior is consistent with our theorem. Since $\tau=\frac{1}{2}$, and
$\mathcal{G}_{k}=\emptyset$ for each $k$, a calculation shows that

$\alpha_{k}=\frac{s}{2m-8s}\geq\frac{s}{2m}.$

This implies there is a $k$ for which $\mathcal{I}_{k}$ contains exactly $s-1$
terms and that in our theorem, the dominant term in $\log(\sigma_{s}(\Phi))$
is linear in $s$. This is validated by the simulations shown in Figure 6.

###  4.5 Colliding clumps

Here we introduce an example where there are two localized sets that are
progressive being pushed towards each other. To make this notion more precise,
we fix $m=100$ and for sufficiently small $\beta>0$, define

$\mathcal{C}_{1}:=\\{0,\tfrac{1}{2m},\tfrac{2}{2m}\\},\quad\mathcal{C}_{2}(\beta):=\beta+\tfrac{1}{m}+\mathcal{C}_{1},\quad\text{and}\quad\mathcal{X}(\beta):=\mathcal{C}_{1}\cup\mathcal{C}_{2}(\beta).$
(4.3)

As $\beta\to 0$, the two sets $\mathcal{C}_{1}$ and $\mathcal{C}_{2}(\beta)$
become closer and $\sigma_{s}(\Phi(m,\mathcal{X}(\beta)))\to 0$ as $\beta\to
0$. Note we can think of $\mathcal{C}_{1}$ and $\mathcal{C}_{2}(\beta)$ as
clumps with separation $\beta$. Eventually for sufficiently small $\beta$, we
should think of $\mathcal{X}(\beta)$ as just a single clump as opposed to two
separate ones.

Figure 7: For $m=100$ and $\mathcal{X}(\beta)$ defined in (4.3), plot of
$\sigma_{s}(\Phi(m,\mathcal{X}(\beta)))$, our main theorem, and the Gautschi-
Bazán bound as a function of $\beta\in[\frac{0.1}{m},\frac{20}{m}]$.

To employ Theorem 2, we pick $\tau=\beta$ if $\beta\geq\frac{18}{m}$,
otherwise we set $\tau=\frac{1}{2}$. Our choice of $\tau$ is consistent with
Proposition 3.2, but we picked a bigger constant (18 instead of 9) in front of
$\frac{1}{m}$ to temper the growth of several implicit constants in our
estimates. For this example, the clumps bounds [20, 16] do not apply since
$\mathcal{C}_{1}$ and $\mathcal{C}_{2}$ are not far apart. The results of this
experiment are shown in Figure 7. This behavior of $\sigma_{s}(\Phi)$
undergoes a phase transition at $\beta\approx\frac{1}{m}$ since for
$\beta\gg\frac{1}{m}$, it is intuitive that $\mathcal{X}(\beta)$ should be
treated as two clumps instead of just one. There are some fluctuations in the
graph of $\sigma_{s}(\Phi)$ due to number theoretic reasons since
$\mathcal{X}(\beta)$ is a partial unitary matrix if it is a subset of the
lattice with spacing $\frac{1}{2m}$. Our estimate is significantly better than
the Gautschi-Bazán’s theorem. For example, at $\beta=0.1=\frac{10}{m}$, the
former has an inaccuracy factor of 66.1225, while the latter is 1.9916e+05.

##  5 Two trigonometric interpolation problems

###  5.1 Small norm Lagrange interpolants

In this section, we study the interpolation problem for the “good” set
$\mathcal{G}\subseteq\mathbb{T}$ where all elements of $\mathcal{G}$ are away
from zero, and we would like to find a trigonometric polynomial that vanishes
on $\mathcal{G}$ and equals 1 at 0. Since we do not want to place any
assumptions on $\Delta(\mathcal{G})$, which we allow to be arbitrarily small,
this is a delicate problem. We will construct a polynomial that is
significantly better behaved than the standard Lagrange interpolant.

A key observation is the following sparsity decomposition which essentially
states that a set can be decomposed into disjoint sets, each with unit local
sparsity and minimum separation that is well-controlled. The key is that the
number of sets equals the local sparsity of the original set, and not the
cardinality. While this decomposition is intuitive, some care is taken with
the proof due to the periodic boundary conditions that are imposed on us due
to working with the torus.

######  Proposition 5.1.

For any $\tau\in(0,\frac{1}{2}]>0$ and non-empty
$\mathcal{W}\subseteq\mathbb{T}$, letting $\nu:=\nu(\tau,\mathcal{W})$, there
exist non-empty disjoint subsets
$\mathcal{W}_{1},\mathcal{W}_{2},\dots,\mathcal{W}_{\nu}\subseteq\mathcal{W}$
such that their union is $\mathcal{W}$ and $\Delta(\mathcal{W}_{k})>\tau$ for
each $k$.

###### Proof.

Since the statement we are proving is invariant under periodic shifts, we can
assume that $w_{1}:=0\in\mathcal{W}$. We sort the elements of $\mathcal{W}$ by
$w_{1},w_{2},\dots,w_{n}$ sorted counterclockwise and provide a greedy method
for generating the desired sets
$\mathcal{W}_{1},\mathcal{W}_{2},\dots,\mathcal{W}_{\nu}.$ We initialize these
sets to be empty and we add $w_{\ell}\in\mathcal{W}$ to one of these sets
until all elements of $\mathcal{W}$ have been exhausted. We say $w_{\ell}$ has
been assigned if it has been placed in a $\mathcal{W}_{k}$, and unassigned
otherwise. We start by placing $w_{1}\in\mathcal{W}_{1}$. For each unassigned
$w_{\ell}\in\mathcal{W}$, we consider the set of
$\mathcal{U}_{\ell}:=\mathcal{W}\cap[w_{\ell}-\tau,w_{\ell}+\tau]$ and place
$w_{\ell}$ in an arbitrary $\mathcal{W}_{k}$ that does not contain any
assigned elements in $\mathcal{U}_{\ell}$. This is always possible since
$|\mathcal{U}_{\ell}|\leq\nu$ for all $\ell$. By construction,
$\mathcal{W}_{1},\dots,\mathcal{W}_{\nu}$ are disjoint and
$\Delta(\mathcal{W}_{k})>\tau$. To see why
$\mathcal{W}_{1},\mathcal{W}_{2},\dots,\mathcal{W}_{\nu}$ are each nonempty,
by definition of the $\tau$ density, there is a $\ell$ such that
$[w_{\ell}-\tau,w_{\ell}+\tau]$ contains exactly $\nu$ elements of
$\mathcal{W}$ and they are necessarily placed in different
$\mathcal{W}_{k}$’s. ∎

The usefulness of this decomposition for controlling the conditioning of
Fourier matrices is not obvious, but it will be made more clear in the
following proof.

######  Proposition 5.2.

Let $\mathcal{G}\subseteq\mathbb{T}$ be a non-empty finite set such that for
some $\tau\in(0,\frac{1}{2}]$, we have $|w|_{\mathbb{T}}>\tau$ for all
$w\in\mathcal{G}$. Suppose $m,r\in\mathbb{N}_{+}$ such that
$\nu(\tau,\mathcal{G})\leq r$ and $m>\frac{1}{\tau}$. Then there is
$f\in\mathcal{P}_{r(m-1)+1}$ such that $f(0)=1$, $f$ vanishes on
$\mathcal{G}$, and

$\|f\|_{L^{2}}\leq\frac{1}{\sqrt{m}}\Big{(}1+\frac{1}{m\tau-1}\Big{)}^{r/2}\quad\text{and}\quad\|f\|_{L^{\infty}}\leq\Big{(}1+\frac{1}{m\tau-1}\Big{)}^{r/2}.$

###### Proof.

Let $\nu:=\nu(\tau,\mathcal{G})$. By Proposition 5.1, there exists a disjoint
decomposition,

$\mathcal{G}=\mathcal{G}_{1}\cup\mathcal{G}_{2}\cup\cdots\cup\mathcal{G}_{\nu},\quad\text{where}\quad\mathcal{G}_{k}\not=\emptyset\quad\text{and}\quad\Delta(\mathcal{G}_{k})>\tau.$

The assumption that $|w|_{\mathbb{T}}>\tau$ for all $w\in\mathcal{G}$ implies
$\Delta(\mathcal{G}_{k}\cup\\{0\\})>\tau$. Using the assumption
$m>\frac{1}{\tau}$, we invoke the lower bound in (1.1), which implies

$\sigma_{\min}\big{(}\Phi\big{(}m,\mathcal{G}_{k}\cup\\{0\\}\big{)}\big{)}\geq\sqrt{m-\frac{1}{\tau}}.$

By Proposition 2.3, applied to the data points
$(\\{0\\}\cup\mathcal{G}_{k},e_{1})$, there exists a $f_{k}\in\mathcal{P}_{m}$
such that

$f_{k}(0)=1,\quad
f_{k}|_{\mathcal{G}_{k}}=0,\quad\|f_{k}\|_{L^{2}}\leq\frac{1}{\sqrt{m}}\sqrt{\frac{m\tau}{m\tau-1}}\quad\text{and}\quad\|f_{k}\|_{L^{\infty}}\leq\sqrt{\frac{m\tau}{m\tau-1}}.$
(5.1)

Let $f$ be the product of $f_{1},f_{2},\dots,f_{\nu}$. It follows immediately
from (5.1) that $f(0)=1$ and $f|_{\mathcal{G}}=0$. The claimed bounds for
$\|f\|_{L^{2}}$ and $\|f\|_{L^{\infty}}$ follow from Hölder’s inequality.
Moreover, we readily see that

$\deg(f)=\sum_{k=1}^{\nu}\deg(f_{k})\leq\nu(m-1)\leq r(m-1).$

∎

These polynomials can be numerically computed. First, we compute the
decomposition of $\mathcal{G}$ outlined in Proposition 5.1, which can be done
constructively using the greedy method described in its proof. Second, for
each $\mathcal{G}_{k}$ in this decomposition, we find an interpolant $f_{k}$
of the data $(\\{0\\}\cup\mathcal{G}_{k},e_{1})$ via Proposition 2.3. This can
also be done numerically since $\widehat{f_{k}}$ is precisely a scaled left
singular vector of $\Phi(m,\\{0\\}\cup\mathcal{G}_{k})$, see the discussion
following (2.4). Finally, these interpolants are then multiplied together to
yield the desired $f$.

We refer to a $f$ generated by this proposition as a small norm Lagrange
interpolant. While each $f_{k}$ is found by minimizing a $L^{2}$ norm with
interpolation constraints, it is not necessarily true that $f$ is also a
minimum norm interpolant. Nonetheless, it is the pointwise bound that is
important for this paper, and it is not clear any of the $f_{k}$’s or $f$ are
extremal in the $L^{\infty}$ norm.

To provide an example, consider the set,

$\mathcal{G}_{\varepsilon}=\Big{(}\frac{1}{4}+\\{0,\varepsilon,2\varepsilon\\}\Big{)}\cup\Big{(}\frac{1}{2}+\\{0,\varepsilon\\}\Big{)}\cup\Big{(}\frac{3}{4}+\\{0,\varepsilon,\dots,3\varepsilon\\}\Big{)}.$
(5.2)

Set $\tau=\frac{1}{5}$ and for all sufficiently small $\varepsilon$, say
$\varepsilon=\frac{1}{300}$, we have $\nu(\tau,\mathcal{G}_{\varepsilon})=4$.
Pick $m=\frac{2}{\tau}=10$ so that Proposition 5.2 is applicable with
reasonable constant. Graphs of the real part of the four interpolants
$f_{1},f_{2},f_{3},f_{4}$ generated by Proposition 5.2 are shown in Figure 8.

Figure 8: For the zero set $\mathcal{G}_{\varepsilon}$ defined in (5.2) with
$\varepsilon=\frac{1}{300}$, the four small norm Lagrange interpolants each of
degree $9$ are displayed.

The interpolant in Proposition 5.2 enjoys many favorable and surprising
properties. First, in the absence of additional assumptions, it is degree-
optimal. Notice that $\Delta(\\{0\\}\cup\mathcal{G}_{k})>\tau$ and
$0\not\in\mathcal{G}$ imply that $(|\mathcal{G}_{k}|+1)\tau<1$. This in turn
establishes

$|\mathcal{G}|\leq\nu\max_{1\leq k\leq\nu}|\mathcal{G}_{k}|\leq
r\Big{\lfloor}\frac{1}{\tau}-1\Big{\rfloor}.$

This inequality is sharp since it is possible to provide an example of a
$\mathcal{G}$ such that these inequalities are achieved. On the other hand,
with the only stipulation that $m>\frac{1}{\tau}$, the theorem provides a
polynomial of degree $r(m-1)$ that has up to $r\lfloor\frac{1}{\tau}-1\rfloor$
zeros. Hence it is not possible to reduce the degree of this interpolant in
general.

Second, the proposition provides an interpolant whose pointwise norm is
significantly smaller than that of the usual Lagrange interpolant. If we pick
a reasonable $m$ such as $m\geq 2\tau$, we see that $\|f\|_{L^{\infty}}\leq
2^{\nu(\tau,\mathcal{G})/2}$. On the other hand, according to (2.5), the
standard Lagrange interpolant $\ell\in\mathcal{P}_{|\mathcal{G}|}$ has
pointwise norm,

$\|\ell\|_{L^{\infty}}\leq
2^{|\mathcal{G}|}\prod_{w\in\mathcal{G}}\frac{1}{|1-e^{2\pi iw}|}.$

Not only do we have $\nu(\tau,\mathcal{G})\leq|\mathcal{G}|$, the left hand
side is significantly smaller for many interesting sets, not to mention that
$|1-e^{2\pi w}|$ is on the order of $\tau\leq\frac{1}{2}$. We will see later
on that the reduction from an exponent of $|\mathcal{G}|$ to
$\nu(\tau,\mathcal{G})$ is yet another manifestation of rectangular versus
square Fourier matrices.

Proposition 5.2 has not been previously discovered. It is a “sign dependent”
statement, since it only concerns the interpolation of very specific data
points, namely $(0,1)$ and $(w,0)$, where each $w$ is sufficiently far away
from 0. These data points can be viewed as point evaluations of specific
functions, such as a compactly supported cutoff function sufficiently
localized near 0. This proposition does not hold if we replace the 0’s with
any other number.

The sign dependence of can also be seen by reformulating this result in linear
algebra terms. Consider the set $\mathcal{G}_{\varepsilon}$ defined in (5.2).
If ${f_{\varepsilon}}$ is the small norm Lagrange interpolant of
$(\\{0\\}\cup\mathcal{G}_{\varepsilon},e_{1})$, then its Fourier coefficients
satisfy the linear system,

$\Phi(m,\\{0\\}\cup\mathcal{G}_{\varepsilon})^{*}\widehat{f_{\varepsilon}}=e_{1}.$

For the same choices of $\varepsilon,\tau,m$ from earlier, by Parseval’s, we
see that

$\|\widehat{f_{\varepsilon}}\|_{\ell^{2}}=\|f_{\varepsilon}\|_{L^{2}}\leq\|f_{\varepsilon}\|_{L^{\infty}}\leq
2^{\nu(\tau,\mathcal{G}_{\varepsilon})/2}=4,$

which is bounded independent of $\varepsilon$, even though
$\sigma_{\min}(\Phi(m,\\{0\\}\cup\mathcal{G}_{\varepsilon}))\to 0$ as
$\varepsilon\to 0$. This is again because the singular values only depend on
the nodes $\\{0\\}\cup\mathcal{G}_{\varepsilon}$ and not on the data points
themselves, so are sign independent quantities.

On the other hand, many interpolation methods, are what we refer to as “sign
independent” results – methods that depend on the data locations $\mathcal{G}$
and some norm of the data values (which is agnostic to signs). For instance,
[9, Theorem 2.1] is a sign independent result for trigonometric interpolation
and requires the interpolant to have degree that scales inversely proportional
to the minimum separation of the nodes. Hence, an interpolant of data defined
on $\\{0\\}\cup\mathcal{G}_{\varepsilon}$ via this result would have degree
that scales proportional to $\frac{1}{\varepsilon}$. In contrast, notice that
$\deg(f_{\varepsilon})=4\cdot 9=36$ does not depend on $\varepsilon$, so the
degree of $f_{\varepsilon}$ does not explode as $\varepsilon\to 0$. This is
crucial for the purposes of this paper, since we do not want high degree
interpolants in view of the polynomial method while at the same time allowing
the minimum separation to be arbitrary. Additionally, interpolation results
such as [26], which is proved using functional analysis, is also sign
independent.

###  5.2 Construction of local Lagrange polynomials

In this section, we study the interpolation problem for the “bad” set
$\mathcal{B}$. It contains $0$, all other elements in $\mathcal{B}$ are close
to zero, and we place no assumptions on $\Delta(\mathcal{B})$. We seek a
trigonometric polynomial $f$ such that $f(0)=1$ and $f$ vanishes on
$\mathcal{B}\setminus\\{0\\}$.

Recall the special function $\psi$ that was defined in (2.1). It naturally
appears from the following calculation. For all $|t|\leq\frac{1}{2}$, we have

$|1-e^{2\pi it}|^{2}=2-2\cos(2\pi t)=4\pi^{2}t^{2}\Big{(}\frac{\sin(\pi
t)}{\pi t}\Big{)}^{2}=4\pi^{2}t^{2}\psi(t)^{2}.$ (5.3)

It is important to remark here that $\psi$ is defined on
$[-\frac{1}{2},\frac{1}{2}]$ and not on $\mathbb{R}$. We have the basic bound
that $\psi(t)\geq\psi(\frac{1}{2})=\frac{2}{\pi}$ since it is decreasing away
from zero in its domain.

We have our first result for the bad set, which will be used in the proof of
Theorem 1.

######  Lemma 5.3.

Suppose $\mathcal{B}\subseteq\mathbb{T}$ is a finite set such that
$0\in\mathcal{B}$, and there exist $\tau\in(0,\frac{1}{2}]$ and
$r\in\mathbb{N}_{+}$ such that $|\mathcal{B}|\leq r$ and
$|w|_{\mathbb{T}}\leq\tau$ for all $w\in\mathcal{B}$. For any
$n\in\mathbb{N}_{+}$ such that $n\geq r$, define the subsets

$\mathcal{I}:=\Big{\\{}w\in\mathcal{B}\colon
0<|w|_{\mathbb{T}}\leq\frac{r}{2n}\Big{\\}}\quad\text{and}\quad\mathcal{J}:=\mathcal{B}\setminus(\mathcal{I}\cup\\{0\\}).$

Then there exists a $f\in\mathcal{P}_{n}$ such that $f$ vanishes on
$\mathcal{B}\setminus\\{0\\}$, $f(0)=1$, and

$\|f\|_{L^{2}}\leq\frac{1}{\sqrt{\lfloor\frac{n}{r}\rfloor}}\prod_{w\in\mathcal{J}}\frac{1}{2\lfloor\frac{1}{2|w|_{\mathbb{T}}}\rfloor|w|_{\mathbb{T}}}\prod_{w\in\mathcal{I}}\frac{1}{2\lfloor\frac{n}{r}\rfloor|w|_{\mathbb{T}}}.$

###### Proof.

We first deal with the $\mathcal{B}=\\{0\\}$ case, in which case
$\mathcal{I}=\mathcal{J}=\emptyset$. Then we define $f$ to be a normalized
Dirichlet kernel,

$f(x):=\frac{1}{n}\sum_{\ell=0}^{n-1}e^{2\pi i\ell x}.$

Notice that $f(0)=1$ and $f\in\mathcal{P}_{n}$. Moreover, an application of
Parseval establishes that for any $r\in\mathbb{N}_{+}$, we have

$\|f\|_{L^{2}}\leq\frac{1}{\sqrt{n}}\leq\frac{1}{\sqrt{\lfloor\frac{n}{r}\rfloor}}.$

This takes care of the $\mathcal{B}=\\{0\\}$ case. From here onward, assume
that $|\mathcal{B}|\geq 2$. For each $w\in\mathcal{B}$, we define the natural
number $q(w)$ where

$q(w)=q:=\Big{\lfloor}\frac{n}{r}\Big{\rfloor}\quad\text{if
}w\in\mathcal{I},\quad\text{and}\quad
q(w)=\Big{\lfloor}\frac{1}{2|w|_{\mathbb{T}}}\Big{\rfloor}\quad\text{if}w\in\mathcal{J}.$

We readily verify that $q(w)|w|_{\mathbb{T}}\leq\frac{1}{2}$ for all
$w\in\mathcal{I}\cup\mathcal{J}$, which implies

$|q(w)w|_{\mathbb{T}}=q(w)|w|_{\mathbb{T}}\quad\text{for each}\quad
w\in\mathcal{I}\cup\mathcal{J}.$ (5.4)

In particular, this implies $|q(w)w|_{\mathbb{T}}\not=0$ whenever
$w\in\mathcal{I}\cup\mathcal{J}$. This enables us to define the polynomials,

$h_{0}(x):=\prod_{w\in\mathcal{I}}\frac{e^{2\pi iq(w)x}-e^{2\pi
iq(w)w}}{1-e^{2\pi iq(w)w}},\quad\text{and}\quad
g(x):=\prod_{w\in\mathcal{J}}\frac{e^{2\pi iq(w)x}-e^{2\pi iq(w)w}}{1-e^{2\pi
iq(w)w}}.$

By construction, $h_{0}$ vanishes on $\mathcal{I}$ and $h_{0}(0)=1$. For each
$\ell=1,2,\dots,q-1$, we define the functions

$h_{\ell}(x):=e^{2\pi i\ell x}h_{0}(x)\quad\text{and}\quad
h:=\frac{1}{q}\sum_{\ell=0}^{q-1}h_{\ell}.$

Using that $|h_{\ell}|=|h_{0}|$, we see that $h(0)=1$ and $h$ also vanishes on
$\mathcal{I}$. Note that $h_{\ell}$ is a trigonometric polynomial whose
frequencies are in $\ell+\\{0,q,\dots|\mathcal{I}|q\\}$. This implies that
$\\{h_{\ell}\\}_{\ell=0}^{q-1}$ are $L^{2}$ orthogonal,
$\deg(h)\leq|\mathcal{I}|q+q-$, and by orthogonality,

$\|h\|_{L^{2}}^{2}=\frac{1}{q^{2}}\sum_{\ell=1}^{q-1}\|h_{\ell}\|_{L^{2}}^{2}=\frac{1}{q^{2}}\sum_{\ell=1}^{q-1}\|h_{0}\|_{L^{2}}^{2}\leq\frac{1}{q}\|h_{0}\|_{L^{\infty}}^{2}.$
(5.5)

We define $f:=gh$. By construction, $f(0)=1$ and $f$ vanishes on
$\mathcal{B}\setminus\\{0\\}$. We bound the degree of $f$. Note for each
$w\in\mathcal{J}$, we have $|w|_{\mathbb{T}}>\frac{r}{n}$ and so
$q(w)\leq\frac{n}{2r}$. This implies, together with the assumption
$|\mathcal{B}|\leq r$, that

$\displaystyle\deg(f)=|\mathcal{I}|q+q-1+\sum_{w\in\mathcal{J}}q(w)\leq\frac{n(|\mathcal{I}|+1)}{r}-1+\frac{n|\mathcal{J}|}{2r}\leq\frac{n|\mathcal{B}|}{r}-1\leq
n-1.$

It remains to obtain the desired bound for $\|f\|_{L^{2}}$. Using (5.5), we
get

$\displaystyle\|f\|_{L^{2}}\leq\frac{1}{\sqrt{q}}\|h\|_{L^{\infty}}\|g\|_{L^{\infty}}\leq\frac{1}{\sqrt{q}}\prod_{w\in\mathcal{U}\cup\mathcal{V}}\frac{2}{|1-e^{2\pi
iq(w)w}|}.$

Combining this with (5.4), equation (5.3), and that $\psi(t)\geq\frac{2}{\pi}$
for $|t|\leq\frac{1}{2}$, we obtain

$\displaystyle\|f\|_{L^{2}}\leq\frac{1}{\sqrt{q}}\prod_{w\in\mathcal{B}}\frac{1}{2q(w)|w|_{\mathbb{T}}}.$

Using the definition of $q$ and $q(w)$ yields the claimed upper bound for
$\|f\|_{L^{2}}$. ∎

The following is our second result for the bad set, which will be used in the
proof of Theorem 2.

######  Lemma 5.4.

Let $n,r\in\mathbb{N}_{+}$ such that $n\geq r$ and $\delta\in(0,\frac{1}{n}]$.
Suppose $\mathcal{B}\subseteq\mathbb{T}$ is a finite set such that
$0\in\mathcal{B}$, $|\mathcal{B}|=r$ and
$\delta\leq\Delta(\mathcal{B})\leq\frac{1}{n}$. Then there exists a
$f\in\mathcal{P}_{n}$ such that $f$ vanishes on $\mathcal{B}\setminus\\{0\\}$,
$f(0)=1$, and

$\|f\|_{L^{2}}\leq\frac{2e}{\pi
r}\frac{1}{\sqrt{\lfloor\frac{n}{r}\rfloor}}\Big{(}\frac{4e}{\pi\psi(\frac{n\delta}{2})r\lfloor\frac{n}{r}\rfloor\delta}\Big{)}^{r-1}.$

###### Proof.

We define the subsets,

$\mathcal{I}:=\Big{\\{}w\in\mathcal{B}\colon
0<|w|_{\mathbb{T}}\leq\frac{r}{2n}\Big{\\}}\quad\text{and}\quad\mathcal{J}:=\mathcal{B}\setminus(\mathcal{I}\cup\\{0\\}).$

We first deal with the $\mathcal{B}=\\{0\\}$ case, in which case $r=1$ and
$\mathcal{I}=\mathcal{J}=\emptyset$. Similar to the proof of Lemma 5.3, we
define $f(x):=\frac{1}{n}\sum_{\ell=0}^{n-1}e^{2\pi i\ell x}.$ Then $f(0)=1$,
$f\in\mathcal{P}_{n}$, and $\|f\|_{L^{2}}\leq\frac{1}{\sqrt{n}}.$ Since
$\frac{2e}{\pi}\geq 1$, this proves the $\mathcal{B}=\\{0\\}$ case.

From here onward assume that $r\geq 2$. We enumerate the elements of
$\mathcal{B}$ as $0=w_{0},w_{1},\dots,w_{r-1}$ where
$|w_{k}|_{\mathbb{T}}\leq|w_{k+1}|_{\mathbb{T}}$ for each $k$. For reasons
that will become apparent later, for any $d\in\mathbb{N}_{+}$, we define the
following arithmetic progression, $0,-1,1,-2,2,-3,3,\dots$, which we enumerate
by $a_{0},a_{1},\dots$. We define the natural numbers $q_{1},\dots,q_{r-1}$ as

$q_{k}:=q:=\Big{\lfloor}\frac{n}{r}\Big{\rfloor}\quad\text{if
}w_{k}\in\mathcal{I},\quad\text{and}\quad
q_{k}:=\Big{\lfloor}\frac{q|a_{k}|\delta}{|w_{k}|_{\mathbb{T}}}\Big{\rfloor}\quad\text{if
}w_{k}\in\mathcal{J}.$

We need to set the stage before we explicitly construct $f$. For each
$w_{k}\in\mathcal{I}$, we immediately get
$q_{k}|w_{k}|_{\mathbb{T}}\leq\frac{1}{2}$ by definition of $q$ and
$\mathcal{I}$. For each $w_{k}\in\mathcal{J}$, we use that
$|a_{k}|\leq\frac{r}{2}$ regardless of the parity of $r$ and the assumption
$\delta\leq\frac{1}{n}$ to see that $q_{k}|w_{k}|_{\mathbb{T}}\leq
q|a_{k}|\delta\leq\frac{1}{2}$. This implies

$|q_{k}w_{k}|_{\mathbb{T}}=q_{k}|w_{k}|_{\mathbb{T}}\quad\text{for each}\quad
w_{k}\in\mathcal{B}\setminus\\{0\\}.$ (5.6)

This enables us to define the polynomials,

$h_{0}(x):=\prod_{w\in\mathcal{I}}\frac{e^{2\pi iqx}-e^{2\pi iqw}}{1-e^{2\pi
iqw}},\quad\text{and}\quad g(x):=\prod_{w_{k}\in\mathcal{J}}\frac{e^{2\pi
iq_{k}x}-e^{2\pi iq_{k}w_{k}}}{1-e^{2\pi iq_{k}w_{k}}}.$

We repeat the same sub-argument that appeared in the proof of Lemma 5.3. We
define the function $h(x):=\frac{1}{q}\sum_{\ell=0}^{q-1}e^{2\pi i\ell
x}h_{0}(x)$, and we see that
$\|h\|_{L^{2}}\leq\frac{1}{\sqrt{q}}\|h_{0}\|_{L^{\infty}}.$ Thus, we define
$f=gh$ and so

$\|f\|_{L^{2}}\leq\frac{1}{\sqrt{q}}\|h_{0}\|_{L^{\infty}}\|g\|_{L^{\infty}}\leq\frac{1}{\sqrt{q}}\prod_{w\in\mathcal{I}}\frac{2}{|1-e^{2\pi
iqw}|}\prod_{w_{k}\in\mathcal{J}}\frac{2}{|1-e^{2\pi iq_{k}w_{k}}|}.$ (5.7)

By construction, $f$ satisfies the desired interpolation properties. We argue
that $f\in\mathcal{P}_{n}$. Notice that $\deg(h_{0})=q|\mathcal{I}|$ and
$\deg(h)=q|\mathcal{I}|+q-1$. On the other hand, for each
$w_{k}\in\mathcal{J}$, using that $|a_{k}|\leq\frac{r}{2}$,
$\delta\leq\frac{1}{n}$, and $|w_{k}|_{\mathbb{T}}>\frac{r}{2n}$, we see that
$q_{k}\leq q$. Thus,

$\displaystyle\deg(f)=q(|\mathcal{I}|+1)-1+\sum_{w_{k}\in\mathcal{J}}q_{k}$
$\displaystyle\leq
q(|\mathcal{I}|+|\mathcal{J}|+1)-1\leq\frac{n|\mathcal{B}|}{r}-1\leq n-1.$

It remains to upper bound $\|f\|_{L^{2}}$. By (5.6), we see that
$|q_{k}w_{k}|_{\mathbb{T}}=q_{k}|w_{k}|_{\mathbb{T}}\geq q|a_{k}|\delta/2$.
Using this inequality on the right side of (5.7), we get

$\|f\|_{L^{2}}\leq\frac{1}{\sqrt{q}}\prod_{w\in\mathcal{I}}\frac{2}{\sqrt{2-2\cos(2\pi
q|w|_{\mathbb{T}})}}\prod_{w_{k}\in\mathcal{J}}\frac{2}{\sqrt{2-2\cos(2\pi
q|a_{k}|\delta/2)}}.$

We claim that

$\|f\|_{L^{2}}\leq\frac{1}{\sqrt{q}}\prod_{w_{k}\in\mathcal{I}}\frac{2}{\sqrt{2-2\cos(2\pi
q|a_{k}|\delta)}}\prod_{w_{k}\in\mathcal{J}}\frac{2}{\sqrt{2-2\cos(2\pi
q|a_{k}|\delta/2)}}$ (5.8)

Recall that $\Delta(\mathcal{I}\cup\\{0\\})\geq\delta$ and that
$0\not\in\mathcal{I}$. To upper bound the first product in (5.8), we let
$\ell:=|\mathcal{I}|$ and define the auxiliary function,

$\gamma(t_{1},t_{2},\dots,t_{\ell}):=\sum_{k=1}^{\ell}\frac{1}{1-\cos(2\pi
q|t_{k}|)},$

where $\delta\leq|t_{k}|\leq\frac{1}{2q}$ for each $k$ and
$|t_{j}-t_{k}|\geq\delta$ for each $j\not=k$. Clearly this function increases
if any $t_{j}$ is made smaller while the remaining $t_{k}$’s are fixed. We
claim that $\gamma$ is maximized precisely when $t_{1},t_{2},\dots,t_{\ell}$
is $a_{1}\delta,a_{2}\delta,\dots,a_{\ell}\delta$. To see this, we list
$t_{1},t_{2},\dots,t_{\ell}$ as $\\{u_{1},\dots,u_{a},v_{1},\dots,v_{b}\\}$
where $a+b=\ell$ and

$u_{a}<\cdots<u_{1}\leq-\delta<0<\delta\leq v_{1}<\cdots<v_{b}.$

If $b\geq 1$, we can assume that $v_{1}=\delta$ since a shift of all
$v_{1},\dots,v_{b}$ by the same amount towards 0 increases the value of
$\gamma$. If $a\geq 1$, we can likewise assume that $u_{1}=-\delta$. Finally,
$\gamma$ is further increased if all the $u$’s and $v$’s are fixed except
$v_{2}$ is replaced with $2\delta$, then $v_{3}$ is moved to $3\delta$, etc.
Likewise, $\gamma$ is increased if $u_{2}$ is replaced to $-2\delta$, etc.
Hence, we see that $\gamma(t_{1},t_{2},\dots,t_{\ell})$ is dominated by
$\gamma(-a\delta,\dots,-\delta,\delta,\dots,b\delta)$. If $|a-b|>1$, then by
reflecting elements across the origin and shifting again, we see that
$\gamma(-a\delta,\dots,-\delta,\delta,\dots,b\delta)$ is further dominated by
$\gamma(a_{1}\delta,a_{2}\delta,\dots,a_{\ell}\delta)$. This establishes
inequality (5.8).

We continue with the upper bound for $\|f\|_{L^{2}}$. Note that
$q|a_{k}|\delta\leq\frac{n\delta}{2}$ and that $\psi$ is decreasing on
$[0,\frac{1}{2}]$. Continuing from (5.8) and using (5.3), we see that

$\|f\|_{L^{2}}\leq\frac{1}{\sqrt{q}}\prod_{w_{k}\in\mathcal{I}}\frac{1}{\pi\psi(q|a_{k}|\delta)q|a_{k}|\delta}\prod_{w_{k}\in\mathcal{J}}\frac{2}{\pi\psi(q|a_{k}|\delta/2)q|a_{k}|\delta}\leq\frac{1}{\sqrt{q}}\prod_{k=1}^{r-1}\frac{2}{\pi\psi(\frac{n\delta}{2})q|a_{k}|\delta}.$
(5.9)

To control the product over $k$, first note that

$C_{d}:=\prod_{k=1}^{d}|a_{k}|=\begin{cases}\ \ \ \
\big{(}\frac{d}{2}\,!\,\big{)}\big{(}\frac{d}{2}\,!\,\big{)}&\quad\text{if $d$
is even},\vskip 6.0pt plus 2.0pt minus 2.0pt\\\ \
\big{(}\frac{d+1}{2}\,!\big{)}\big{(}\frac{d-1}{2}\,!\,\big{)}&\quad\text{if
$d$ is odd}.\end{cases}$

Recall the well known inequalities $k!\geq\sqrt{2\pi k}\,(\frac{k}{e})^{k}$
and $1+t\leq e^{t}$ for all $t\geq 0$. We have $C_{1}=1$, and for $d\geq 2$,
we have

$\displaystyle\frac{(d+1)^{d}}{C_{d}}$ $\displaystyle\leq\frac{(2e)^{d}}{\pi
d}\,\Big{(}\frac{d+1}{d}\Big{)}^{d}\leq\frac{(2e)^{d}e}{\pi
d}\leq\frac{(2e)^{d}2e}{\pi(d+1)}\quad\text{if $d$ is even},$
$\displaystyle\frac{(d+1)^{d}}{C_{d}}$
$\displaystyle=\frac{2(d+1)^{d-1}}{(\frac{d-1}{2}!)^{2}}\leq\frac{2(2e)^{d-1}}{\pi(d-1)}\Big{(}\frac{d+1}{d-1}\Big{)}^{d-1}\leq\frac{2(2e)^{d-1}e^{2}}{\pi(d-1)}\leq\frac{(2e)^{d}2e}{\pi(d+1)}\quad\text{if
$d$ is odd}.$

Using these and the definition of $q$ in (5.9) completes the proof.

∎

##  6 Proofs of the main results

###  6.1 Proof of Theorem 1

###### Proof.

Let us first set the stage and discuss several immediate implications of the
assumptions. Fix any $1\leq k\leq s$ and for convenience, we define

$n_{k}:=\Big{\lfloor}m-\frac{2\nu(\tau,\mathcal{G}_{k})}{\tau}\Big{\rfloor}.$

Note that $\nu(\tau,\mathcal{G}_{k})\leq\nu(\tau,\mathcal{X})$ since
$\mathcal{G}_{k}\subseteq\mathcal{X}$. Also using the assumptions $m\geq 6s$
and ${3\nu(\tau,\mathcal{X})}\leq\tau m$, we have

$m-\frac{2\nu(\tau,\mathcal{G}_{k})}{\tau}\geq
m-\frac{2\nu(\tau,\mathcal{X})}{\tau}\geq\frac{m}{3}\geq 2s.$ (6.1)

As immediate consequences of this inequality, we have $n_{k}\in\mathbb{N}_{+}$
and that $\alpha_{k}>0$. Since
$\nu(\tau,\mathcal{B}_{k})\leq\nu(\tau,\mathcal{X})$ due to
$\mathcal{B}_{k}\subseteq\mathcal{X}$, we use the assumption
${3\nu(\tau,\mathcal{X})}\leq\tau m$ to see that

$\alpha_{k}\leq\frac{\nu(\tau,\mathcal{X})}{2m-4\nu(\tau,\mathcal{X})\tau^{-1}}\leq\frac{\nu(\tau,\mathcal{X})}{6\nu(\tau,\mathcal{X})\tau^{-1}-4\nu(\tau,\mathcal{X})\tau^{-1}}\leq\frac{\tau}{2}.$
(6.2)

We first deal with the “good” set $\mathcal{G}_{k}$. If
$\mathcal{G}_{k}=\emptyset$, then $\nu(\tau,\mathcal{G}_{k})=0$ and we set
$g_{k}:=1$. Otherwise, we assume $\mathcal{G}_{k}\not=\emptyset$. We apply
Proposition 5.2, where $\mathcal{G}_{k}-x_{k}$, $\lceil\frac{2}{\tau}\rceil$,
and $\nu(\tau,\mathcal{G}_{k})$ play the roles of $\mathcal{B}$, $m$ and $r$
respectively, in the referenced proposition’s notation. This provides us with
a polynomial, which after shifting by $x_{k}$, we call it
$g_{k}\in\mathcal{P}_{\nu(\tau,\mathcal{G}_{k})(\lceil\frac{2}{\tau}\rceil-1)+1}$
such that $g_{k}(x_{k})=1$, $g_{k}$ vanishes on $\mathcal{G}_{k}$, and

$\|g_{k}\|_{L^{\infty}}\leq\Big{(}1+\frac{1}{\lceil\frac{2}{\tau}\rceil\tau-1}\Big{)}^{\nu(\tau,\mathcal{G}_{k})/2}\leq
2^{\nu(\tau,\mathcal{G}_{k})/2}.$ (6.3)

Note that this statement is still valid in the corner case that
$\mathcal{G}_{k}=\emptyset$ since in this case, we have
$\nu(\tau,\mathcal{G}_{k})=0$, which is consistent with
$\|g_{k}\|_{L^{\infty}}=1$ and $g_{k}\in\mathcal{P}_{1}$.

Now we deal with the “bad” set
$\mathcal{B}_{k}:=\mathcal{B}(x_{k},\tau,\mathcal{X})$. We use the shorthand
notation $r_{k}:=|\mathcal{B}_{k}|$. We are ready to employ Lemma 5.3, where
$\mathcal{B}_{k}-x_{k}$, $n_{k}$, and $r_{k}$ play the roles of $\mathcal{B}$,
$n$, and $r$ respectively, in the referenced lemma’s notation. Note that
$n_{k}\geq s$ from (6.1). The lemma provides us with a polynomial, and after
shifting by $x_{k}$, we call it $b_{k}\in\mathcal{P}_{n_{k}}$ such that
$b_{k}$ vanishes on $\mathcal{B}_{k}\setminus\\{x_{k}\\}$, $b_{k}(x_{k})=1$,
and $b_{k}$ enjoys the estimates,

$\|b_{k}\|_{L^{2}}\leq\sqrt{\frac{1}{\lfloor\frac{n_{k}}{r_{k}}\rfloor}}\prod_{x\in\mathcal{J}_{k}}\frac{1}{2\lfloor\frac{1}{2|x-x_{k}|_{\mathbb{T}}}\rfloor|x-x_{k}|_{\mathbb{T}}}\
\prod_{x\in\mathcal{I}_{k}}\frac{1}{2\lfloor\frac{n_{k}}{r_{k}}\rfloor|x-x_{k}|_{\mathbb{T}}}.$

Now we perform some algebraic manipulations and simplifications. First note
that $\frac{1}{\alpha_{k}}\leq\frac{2n_{k}+2}{r_{k}}$, and
$\lfloor\frac{n_{k}}{r_{k}}\rfloor\geq\frac{n_{k}}{r_{k}}-\frac{r_{k}-1}{r_{k}}$
since $r_{k}\in\mathbb{N}_{+}$. Together, they imply that

$\frac{1}{2\lfloor\frac{n_{k}}{r_{k}}\rfloor}\leq\frac{1}{\frac{1}{\alpha_{k}}-2}=\frac{\alpha_{k}}{1-2\alpha_{k}}.$

Using these observations and the definition of $\phi$ in the previous upper
bound for $\|b_{k}\|_{L^{2}}$, we have

$\|b_{k}\|_{L^{2}}\leq\sqrt{\frac{2\alpha_{k}}{1-2\alpha_{k}}}\prod_{x\in\mathcal{J}_{k}}\phi\Big{(}\frac{1}{2|x-x_{k}|_{\mathbb{T}}}\Big{)}\
\prod_{x\in\mathcal{I}_{k}}\frac{\alpha_{k}}{(1-2\alpha_{k})|x-x_{k}|_{\mathbb{T}}}.$
(6.4)

We next define $f_{k}:=b_{k}g_{k}$. We have $f_{k}\in\mathcal{P}_{m}$ because

$\displaystyle\deg(f_{k})$
$\displaystyle=\deg(b_{k})+\deg(g_{k})\leq\nu(\tau,\mathcal{G}_{k})\Big{(}\Big{\lceil}\frac{2}{\tau}\Big{\rceil}-1\Big{)}+n_{k}-1\leq\frac{2\nu(\tau,\mathcal{G}_{k})}{\tau}+n_{k}-1\leq
m-1.$

Together with the interpolation properties of $g_{k}$ and $b_{k}$, we see that
$\\{f_{k}\\}_{k=1}^{s}\subseteq\mathcal{P}_{m}$ is a family of Lagrange
interpolants for $\mathcal{X}$. We use Hölder’s inequality and the upper
bounds (6.3) and (6.4) to get

$\|f_{k}\|_{L^{2}}\leq\sqrt{\frac{2\alpha_{k}2^{\nu(\tau,\mathcal{G}_{k})}}{1-2\alpha_{k}}}\prod_{x\in\mathcal{J}_{k}}\phi\Big{(}\frac{1}{2|x-x_{k}|_{\mathbb{T}}}\Big{)}\prod_{x\in\mathcal{I}_{k}}\frac{\alpha_{k}}{(1-2\alpha_{k})|x-x_{k}|_{\mathbb{T}}}.$

We apply Lemma 2.2 to complete the proof of (1.5).

Now we proceed to further upper bound the right side of (1.5). Using that
$\phi(t)\leq 2$ for all $t\geq 1$, that
$\alpha_{k}\leq\frac{\tau}{2}\leq\frac{1}{4}$ due to (6.2), we obtain

$\displaystyle\frac{1}{\sigma_{s}^{2}(\Phi(m,\mathcal{X}))}$
$\displaystyle\leq\sum_{k=1}^{s}\,2^{\nu(\tau,\mathcal{G}_{k})}\,4\alpha_{k}\,4^{|\mathcal{J}_{k}|}\prod_{x\in\mathcal{I}_{k}}\frac{4\alpha_{k}^{2}}{|x-x_{k}|_{\mathbb{T}}^{2}}$
$\displaystyle\leq s\ \max_{1\leq k\leq s}\ \
2^{\nu(\tau,\mathcal{G}_{k})}4\alpha_{k}4^{|\mathcal{J}_{k}|}\prod_{x\in\mathcal{I}_{k}}\frac{4\alpha_{k}^{2}}{|x-x_{k}|_{\mathbb{T}}^{2}}.$

Rearranging this inequality and taking the square root completes the proof of
(1.6). ∎

###  6.2 Proof of Theorem 2

###### Proof.

Fix any $1\leq k\leq s$. Note (6.1) showed that
$n_{k}\geq\lfloor\frac{m}{3}\rfloor$, while $n_{k}\leq m$ immediately by
definition. The proof is analogous to the proof of Theorem 1, but with a
different function for the bad set. We carry over the same notation. There we
constructed the function $g_{k}$ for the “good” set $\mathcal{G}_{k}$ such
that

$\|g_{k}\|_{L^{\infty}}\leq 2^{\nu(\tau,\mathcal{G}_{k})/2}.$ (6.5)

For the “bad” set $\mathcal{B}_{k}:=\mathcal{B}(x_{k},\tau,\mathcal{X})$, we
note that $\Delta(\mathcal{B}_{k})\geq\Delta(\mathcal{X})\geq\delta$. We use
Lemma 5.4, where $\mathcal{B}_{k}-x_{k}$, $n_{k}$ and $r_{k}$ play the roles
of $\mathcal{B}$, $n$, and $r$ respectively, in the referenced lemma’s
notation. Also note that $n_{k}\geq s\geq r_{k}$ due to (6.1), and that
$\delta\leq\frac{1}{m}\leq\frac{1}{n_{k}}$. The lemma provides us with a
polynomial, and after shifting by $x_{k}$, we call it
$b_{k}\in\mathcal{P}_{n_{k}}$ such that $b_{k}$ vanishes on
$\mathcal{B}_{k}\setminus\\{x_{k}\\}$, $b_{k}(x_{k})=1$, and $b_{k}$ enjoys
the estimate,

$\|b_{k}\|_{L^{2}}\leq\frac{2e}{\pi
r_{k}}\frac{1}{\sqrt{\lfloor\frac{n_{k}}{r_{k}}\rfloor}}\Big{(}\frac{4e}{\pi\psi(\frac{n_{k}\delta}{2})r_{k}\lfloor\frac{n_{k}}{r_{k}}\rfloor\delta}\Big{)}^{r_{k}-1}.$
(6.6)

We define $f_{k}=g_{k}b_{k}$. Repeating the same argument as in the proof of
Theorem 1 shows that $f_{k}\in\mathcal{P}_{m}$. By construction,
$\\{f_{k}\\}_{k=1}^{s}$ is a family of Lagrange polynomials for $\mathcal{X}$.
Using Hölder’s inequality, (6.5), (6.6), and the definition of $\phi$, we get

$\|f_{k}\|_{L^{2}}\leq\frac{2e}{\pi}\sqrt{\frac{2^{\nu(\tau,\mathcal{G}_{k})}\phi(\frac{n_{k}}{r_{k}})}{r_{k}n_{k}}}\Big{(}\frac{4e\phi(\frac{n_{k}}{r_{k}})}{\pi\psi(\frac{n_{k}\delta}{2})n_{k}\delta}\Big{)}^{r_{k}-1}.$

Finally, using Lemma 2.2 completes the proof of (2.2).

We proceed to make numerous simplifications of the right hand side of (2.2).
Since $\delta\leq\frac{1}{m}$ and $n_{k}\leq m$, we have
$\psi(\frac{n_{k}\delta}{2})\geq\psi(\frac{1}{2})=\frac{2}{\pi}$. Note that
(6.1) and the assumption $m\geq 6s$ imply

$r_{k}\Big{\lfloor}\frac{n_{k}}{r_{k}}\Big{\rfloor}\geq
r_{k}\Big{(}\frac{n_{k}}{r_{k}}-\frac{r_{k}-1}{r_{k}}\Big{)}=n_{k}-r_{k}+1\geq
m-\frac{2\nu(\tau,\mathcal{X})}{\tau}-r_{k}\geq\frac{m}{3}-s\geq\frac{m}{6}.$

Using these observations in (2.2) now establishes

$\frac{1}{\sigma_{s}^{2}(\Phi(m,\mathcal{X}))}\leq\frac{24e^{2}}{\pi^{2}m}\sum_{k=1}^{s}\frac{2^{\nu(\tau,\mathcal{G}_{k})}}{r_{k}}\Big{(}\frac{12e}{m\delta}\Big{)}^{2r_{k}-2}\leq\frac{24e^{2}s}{\pi^{2}m}\max_{1\leq
k\leq
s}\frac{2^{\nu(\tau,\mathcal{G}_{k})}}{r_{k}}\Big{(}\frac{12e}{m\delta}\Big{)}^{2r_{k}-2}.$

Rearranging this inequality and taking the square root completes the proof of
(2.3). ∎

###  6.3 Proof of Theorem 3

###### Proof.

Letting $\nu:=\nu(\tau,\mathcal{X})$, by the decomposition given in
Proposition 5.1, we have a disjoint union

$\mathcal{X}=\mathcal{X}_{1}\cup\mathcal{X}_{2}\cup\cdots\cup\mathcal{X}_{\nu},\quad\text{where}\quad\Delta(\mathcal{X}_{k})\geq\tau\quad\text{for
each}\quad k=1,2,\dots,\nu.$

Since the singular values of $\Phi(m,\mathcal{X})$ are invariant under
permutations of its columns, we can shuffle them so that after reshuffling,
$\Phi(m,\mathcal{X})$ becomes

$\begin{bmatrix}\Phi(m,\mathcal{X}_{1})&\Phi(m,\mathcal{X}_{2})&\cdots&\Phi(m,\mathcal{X}_{\nu})\end{bmatrix}.$

Let $u\in\mathbb{C}^{|\mathcal{X}|}$ be any unit norm vector, and likewise, we
partition $u$ into sub-vectors $u_{1},u_{2},\dots,u_{\nu}$ such that
$u_{k}\in\mathbb{C}^{|\mathcal{X}_{k}|}$. Since
$\Delta(\mathcal{X}_{k})\geq\tau$ for each $k$ and $m>\frac{1}{\tau}$, we use
the upper bound in (1.1) to get

$\displaystyle\|\Phi(m,\mathcal{X})u\|_{2}=\Big{\|}\sum_{k=1}^{\nu}\Phi(m,\mathcal{X}_{k})u_{k}\Big{\|}_{2}\leq\sqrt{m+\frac{1}{\tau}}\
\sum_{k=1}^{\nu}\|u_{k}\|_{2}.$

Using Cauchy-Schwarz and that $u$ has unit norm, we obtain

$\sum_{k=1}^{\nu}\|u_{k}\|_{2}\leq\sqrt{\nu}\,\Big{(}\sum_{k=1}^{\nu}\|u_{k}\|_{2}^{2}\Big{)}^{1/2}=\sqrt{\nu}\|u\|_{2}=\sqrt{\nu}.$

Combining the above inequalities completes the proof. ∎

## Acknowledgments

WL is supported by NSF-DMS Award #2309602, a PSC-CUNY grant, and by the City
College 21st Century Foundation.

## References

  * [1] Céline Aubel and Helmut Bölcskei.  Vandermonde matrices with nodes in the unit disk and the large sieve.  Applied and Computational Harmonic Analysis, 47(1):53–86, 2019\.
  * [2] Dmitry Batenkov, Laurent Demanet, Gil Goldman, and Yosef Yomdin.  Conditioning of partial nonuniform Fourier matrices with clustered nodes.  SIAM Journal on Matrix Analysis and Applications, 41(1):199–220, 2020.
  * [3] Dmitry Batenkov and Gil Goldman.  Single-exponential bounds for the smallest singular value of Vandermonde matrices in the sub-Rayleigh regime.  Applied and Computational Harmonic Analysis, 55:426–439, 2021.
  * [4] Fermín SV Bazán.  Conditioning of rectangular Vandermonde matrices with nodes in the unit disk.  SIAM Journal on Matrix Analysis and Applications, 21(2):679–693, 2000.
  * [5] Lihu Berman and Arie Feuer.  On perfect conditioning of Vandermonde matrices on the unit circle.  The Electronic Journal of Linear Algebra, 16:157–161, 2007.
  * [6] Arne Beurling.  Balayage of Fourier-Stieltjes transforms.  The Collected Works of Arne Beurling, 2:341–350, 1989.
  * [7] Arne Beurling.  Interpolation for an interval in $\mathbb{R}^{1}$.  The Collected Works of Arne Beurling, 2:351–365, 1989.
  * [8] Peter G Casazza and Gitta Kutyniok.  Finite frames: Theory and applications.  Springer Science & Business Media, 2012.
  * [9] Shivkumar Chandrasekaran, Karthik R Jayaraman, and Hrushikesh Narhar Mhaskar.  Minimum Sobolev norm interpolation with trigonometric polynomials on the torus.  Journal of Computational Physics, 249:96–112, 2013.
  * [10] Antonio Córdova, Walter Gautschi, and Stephan Ruscheweyh.  Vandermonde matrices on the circle: spectral properties and conditioning.  Numerische Mathematik, 57(1):577–591, 1990.
  * [11] David L. Donoho.  Superresolution via sparsity constraints.  SIAM Journal on Mathematical Analysis, 23(5):1309–1331, 1992.
  * [12] Richard J Duffin and Albert C Schaeffer.  A class of nonharmonic Fourier series.  Transactions of the American Mathematical Society, 72(2):341–366, 1952.
  * [13] Alok Dutt and Vladimir Rokhlin.  Fast Fourier transforms for nonequispaced data.  SIAM Journal on Scientific computing, 14(6):1368–1393, 1993.
  * [14] Albert C Fannjiang, Thomas Strohmer, and Pengchong Yan.  Compressed remote sensing of sparse objects.  SIAM Journal on Imaging Sciences, 3(3):595–618, 2010.
  * [15] Walter Gautschi.  On inverses of vandermonde and confluent vandermonde matrices.  Numerische Mathematik, 5:425–430, 1963.
  * [16] Stefan Kunis and Dominik Nagel.  On the smallest singular value of multivariate vandermonde matrices with clustered nodes.  Linear Algebra and its Applications, 604:1–20, 2020.
  * [17] Stefan Kunis and Dominik Nagel.  On the condition number of vandermonde matrices with pairs of nearly-colliding nodes.  Numerical Algorithms, 87:473–496, 2021.
  * [18] Henry J. Landau.  Necessary density conditions for sampling and interpolation of certain entire functions.  Acta Mathematica, 117:37–52, 1967.
  * [19] Weilin Li.  Generalization error of minimum weighted norm and kernel interpolation.  SIAM Journal on Mathematics of Data Science, 3(1):414–438, 2021\.
  * [20] Weilin Li and Wenjing Liao.  Stable super-resolution limit and smallest singular value of restricted fourier matrices.  Applied and Computational Harmonic Analysis, 51:118–156, 2021.
  * [21] Weilin Li, Wenjing Liao, and Albert Fannjiang.  Super-resolution limit of the esprit algorithm.  IEEE transactions on information theory, 66(7):4593–4608, 2020\.
  * [22] Weilin Li, Zengying Zhu, Weiguo Gao, and Wenjing Liao.  Stability and super-resolution of MUSIC and ESPRIT for multi-snapshot spectral estimation.  IEEE Transactions on Signal Processing, 70:4555–4570, 2022.
  * [23] Wenjing Liao and Albert Fannjiang.  Music for single-snapshot spectral estimation: Stability and super-resolution.  Applied and Computational Harmonic Analysis, 40(1):33–67, 2016\.
  * [24] Ankur Moitra.  Super-resolution, extremal functions and the condition number of Vandermonde matrices.  Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, 2015.
  * [25] Hugh L Montgomery.  The analytic principle of the large sieve.  Bulletin of the American Mathematical Society, 84(4):547–567, 1978\.
  * [26] Francis J. Narcowich and Joseph D. Ward.  Scattered-data interpolation on $\mathbb{R}^{n}$: error estimates for radial basis and band-limited functions.  SIAM Journal on Mathematical Analysis, 36(1):284–300, 2004.
  * [27] Kui Ren, Yunan Yang, and Björn Engquist.  A generalized weighted optimization method for computational learning and inversion.  In International Conference on Learning Representations, 2022.
  * [28] Atle Selberg and Atle Selberg.  Collected papers, volume 1.  Springer, 1989.
  * [29] Elias M. Stein.  Singular integrals and differentiability properties of functions.  Princeton university press, 1970.
  * [30] Jeffrey D. Vaaler.  Some extremal functions in Fourier analysis.  Bulletin of the American Mathematical Society, 12(2):183–216, 1985\.
  * [31] Yuege Xie, Hung-Hsu Chou, Holger Rauhut, and Rachel Ward.  Overparameterization and generalization error: weighted trigonometric interpolation.  SIAM Journal on Mathematics of Data Science, 4(2):885–908, 2022\.
  * [32] Robert M. Young.  An introduction to nonharmonic Fourier series.  Academic press, 1981.
  * [33] Antoni Zygmund.  Trigonometric Series, volume 1.  Cambridge University Press, 1959.