# A mathematical theory of resolution limits for super-resolution of positive
sources ††thanks: This work was supported in part by the Swiss National
Science Foundation grant number 200021–200307.

Ping Liu Department of Mathematics, ETH Zürich, Rämistrasse 101, CH-8092
Zürich, Switzerland<EMAIL_ADDRESS><EMAIL_ADDRESS>habib.ammari@math.ethz.ch). Yanchen He22footnotemark: 2 Habib
Ammari22footnotemark: 2

###### Abstract

The superresolving capacity for number and location recoveries in the super-
resolution of positive sources is analyzed in this work. Specifically, we
introduce the computational resolution limit for respectively the number
detection and location recovery in the one-dimensional super-resolution
problem and quantitatively characterize their dependency on the cutoff
frequency, signal-to-noise ratio, and the sparsity of the sources. As a direct
consequence, we show that targeting at the sparest positive solution in the
super-resolution already provides the optimal resolution order. These results
are generalized to multi-dimensional spaces. Our estimates indicate that there
exist phase transitions in the corresponding reconstructions, which are
confirmed by numerical experiments. Our theory fills in an important puzzle
towards fully understanding the super-resolution of positive sources.

Mathematics Subject Classification: 65R32, 42A10, 15A09, 94A08, 94A12

Keywords: resolution limit, super-resolution, positive sources, line spectral
estimation, Vandermonde matrix, phase transition

##  1 Introduction

In recent years, the development of super-resolution optical microscopy led to
a revolutionary improvement of resolution through the use of different
technical approaches. This impressive success has generated significant
interest in studying the super-resolution algorithms and the fundamental
superresolving capability. In this paper, we aim to study the superresolving
capacity of the number and locations recovery in the super-resolution of
positive sources. To be more specific, we consider the following mathematical
model. Let $\mu=\sum_{j=1}^{n}a_{j}\delta_{y_{j}},a_{j}>0$ be a positive
discrete measure, where $y_{j}\in\mathbb{R},j=1,\cdots,n$, represent the
location of the point sources and $a_{j}>0,j=1,\cdots,n,$ their amplitudes.
Noting that $y_{j}$’s are the supports of the Dirac masses in $\mu$. In this
paper we will use support recovery instead of location reconstruction. We
denote by

$m_{\min}=\min_{j=1,\cdots,n}a_{j},\quad d_{\min}=\min_{p\neq
j}|y_{p}-y_{j}|.$

The measurement is the noisy Fourier data of $\mu$ in a bounded interval, that
is,

$\mathbf{Y}(\omega)=\mathcal{F}\mu(\omega)+\mathbf{W}(\omega)=\sum_{j=1}^{n}a_{j}e^{iy_{j}\omega}+\mathbf{W}(\omega),\quad\omega\in[-\Omega,\Omega],$
(1.1)

with $\mathbf{W}(\omega)$ being the noise and $\Omega$ the cutoff frequency of
the imaging system. We assume that

$|\mathbf{W}(\omega)|<\sigma,\quad\omega\in[-\Omega,\Omega],$

with $\sigma$ being the noise level. The above measurement model is chosen for
convenience. All the results in this paper also hold for the case when taking
measurement at a sufficient number of evenly-spaced points as what was
considered in [26]. Thus our results can be applied to practical situations
and real-world problems.

The super-resolution problem we are interested in is to recover the positive
discrete measure $\mu$ from the above noisy measurement $\mathbf{Y}$. We note
that the super-resolution problem is closely related to the line spectral
estimation problem [26] which is at the core of diverse fields such as
wireless communications and array processing. Note also that the measurement
considered in (1.1) is related to the imaging of convolution of point sources
and a band-limited point spread function $f$.

###  1.1 Literature review

Fundamental limits. In [37, 38, 17], the authors analyzed the resolution limit
in the detection of two closely-spaced point sources based on the statistical
inference theory, but their theory has not been generalized to the case when
there are more than two sources in the signal. The mathematical theory for
analyzing the fundamental limit in superresolving multiple point sources was
pioneered by Donoho [13] in 1992. In that work, he considered a grid setting
where a discrete measure is supported on a lattice with spacing $\Delta$ and
regularized by a so-called "Rayleigh index". The problem is to reconstruct the
amplitudes of the grid points from their noisy Fourier data in
$[-\Omega,\Omega]$ with $\Omega$ being the band limit. His main contribution
is estimating the corresponding minimax error in the recovery, which
emphasizes the importance of the sparsity of sources for the super-resolution.
It was improved in recent years for the case when only $n$ point sources are
presented. In [11], the authors considered resolving $n$-sparse point sources
supported on a grid and showed that the minimax error of amplitude recovery in
the presence of noise with magnitude $\sigma$ scales exactly as
$SRF^{2n-1}\sigma$, where $SRF:=\frac{1}{\Delta\Omega}$ is the super-
resolution factor. The case of multi-clustered point sources was considered in
[20, 4] and similar minimax error estimates were derived. Moreover, in [2, 5]
the authors considered the minimax error for recovering the amplitudes and
locations of off-the-grid point sources. They showed that for
$\sigma\lessapprox(SRF)^{-2p+1}$, where $p$ is the number of point sources in
a cluster, the minimax error for the amplitude and the location recoveries
scale respectively as $(SRF)^{2p-1}\sigma$, $(SRF)^{2p-2}{\sigma}/{\Omega}$,
while for the single non-clustered source away from other sources, the
corresponding minimax error for the amplitude and the location recoveries
scale respectively as $\sigma$ and ${\sigma}/{\Omega}$. We also refer the
readers to [28, 8] for understanding the resolution limit from the perspective
of sample complexity and to [42, 10] for the resolving limit of some
algorithms.

On the other hand, in order to characterize the exact resolution in resolving
multiple point sources like the classical Rayleigh limit, in the earlier works
[27, 25, 26, 24, 23] we defined the concept of "computational resolution
limit" as the minimum required distance between point sources so that their
number and locations can be stably resolved under certain noise level. By
developing a non-linear approximation theory in a so-called Vandermonde space,
we derived sharp bounds for computational resolution limits in one- and multi-
dimensional super-resolution problems. In particular, we showed that the
computational resolution limits for number and location recoveries should be
respectively
$\frac{C_{\mathrm{num}}(n,k)}{\Omega}\left(\frac{\sigma}{m_{\min}}\right)^{\frac{1}{2n-2}}$
and
$\frac{C_{\mathrm{supp}}(n,k)}{\Omega}\left(\frac{\sigma}{m_{\min}}\right)^{\frac{1}{2n-1}}$,
where $C_{\mathrm{num}}(n,k),C_{\mathrm{supp}}(n,k)$ are constants depending
only on source number $n$ and space dimensionality $k$. In this paper, we will
generalize these results to the super-resolution problem of positive sources.

Reconstruction algorithms. Due to the importance of super-resolution in
applications, a number of sophisticated super-resolution algorithms have been
developed over the years. Among those algorithms, a class of algorithms called
subspace methods have exhibited favourable performance and have been used
frequently in engineering applications. Specific examples include MUltiple
SIgnal Classification (MUSIC) [35], Estimation of Signal Parameters via
Rotational Invariance Technique (ESPRIT) [34], and Matrix Pencil Method [18].
Note that these algorithms date back to the work of Prony [32]. Despite the
appealing performance of the subspace methods in practical applications, their
stability properties are not yet well-understood. The asymptotic results on
the stability of MUSIC algorithm in the presence of Gaussian noise were
derived just slightly after its emerging [40, 9, 41]. But only until recent
years, some steps towards understanding the stability of MUSIC, ESPRIT and
Matrix-Pencil Method in the non-asymptotic regime were taken in [22], [21] and
[28], respectively. Nevertheless, the error tolerance derived in these papers
are not as strong as our estimates here for the resolution limit in location
reconstruction. On the other hand, it was shown numerically in [22, 5, 21]
that these subspace methods actually achieve the optimal resolution order.
Thus the theoretical demonstrations for the performance limits of subspace
methods in the non-asymptotic regime are still important open problems.

In recent years, inspired by the idea of sparse modeling and compressed
sensing, many sparsity promoting algorithms have been proposed for the super-
resolution problem. For example, in the groundbreaking work of Candès and
Fernandez-Granda [7], it was proved that off-the-grid sources can be exactly
recovered from their low-frequency measurements by a TV minimization under a
minimum separation condition. It invokes active researches in the off-the-grid
algorithms, among them we would like to mention the BLASSO [3, 15, 31] and the
atomic norm minimization method [44, 43]. Both methods were proved to be able
to stably recover the source under a minimum separation condition or a non-
degeneracy condition. BLASSO (Beurling LASSO) is an off-the-grid
generalization of $l^{1}$ regularization (LASSO), and exhibits excellent
performance in the off-the-grid source recovery [15, 31]. The atomic norm
minimization method is shown to form a nearly minimax optimal estimator when
tackling line spectral estimation problems [6, 43]. Nevertheless, these convex
optimization algorithms usually require a minimum separation distance of
several Rayleigh limits (see, for instance, [42, 19, 31]) for the general
source recovery, which may limit their applicability to superresolve closely-
spaced point sources.

Super-resolution of positive sources. To the best of our knowledge, the
theoretical possibility for the super-resolution of positive sources was first
considered in [14]. Specifically, the authors defined

$\omega(\sigma;\mathbf{x})=\sup\left\\{\left\|\mathbf{x}^{\prime}-\mathbf{x}\right\|_{1}:\left\|K\mathbf{x}^{\prime}-K\mathbf{x}\right\|_{2}\leqslant\sigma\text{
and }\mathbf{x}^{\prime}\geqslant 0\right\\},$

where $\boldsymbol{\mathbf{x}},\boldsymbol{\mathbf{x}}^{\prime}$ are vectors
of length $M$ (sources are on a grid) and $K$ consists of the first $m$ rows
of the $M\times M$ discrete Fourier transform, and said that $\mathbf{x}$
admits super-resolution if

$\omega(\sigma;\mathbf{x})\rightarrow 0\quad\text{ as }\sigma\rightarrow 0.$

They demonstrated for $\boldsymbol{\mathbf{x}}\geq 0$ that: (a) If
$\mathbf{x}$ has $\frac{1}{2}(m-1)$ or fewer non-zero elements then
$\boldsymbol{\mathbf{x}}$ admits super-resolution; (b) If $\frac{1}{2}(m+1)$
divides $M$, there exists $\mathbf{x}$ with $\frac{1}{2}(m+1)$ non-zero
elements yet does not admit super-resolution; (c) If $\mathbf{x}$ has more
than $m$ non-zero elements then $\boldsymbol{\mathbf{x}}$ does not admit
super-resolution. Their definition and results focused on the possibility of
overcoming Rayleigh limit in the presence of sufficient small noise and hence
demonstrated the possibility of super-resolution. See also [16] for a shorter
exposition of the same idea.

In recent years, some researchers analyzed the stability of specific super-
resolution algorithms in a non-asymptotic regime [30, 29, 12]. To be more
specific, it was shown in [30] that a simple convex optimization program can
already superresolve the positive sources (on a grid) to nearly optimal. The
authors of [30] demonstrated that under certain conditions the deviation
between the algorithm’s output $\hat{\mathbf{x}}$ and the ground truth
$\mathbf{x}$ obeys the following relation

$\|\hat{\mathbf{x}}-\mathbf{x}\|_{1}\approx
C\cdot\mathrm{SRF}^{2r}\cdot\sigma,$

where $r$ is the Rayleigh index. The theory was later generalized to the off-
the-grid setting in [29] where the authors analyzed the stability of the
reconstruction of high frequency information. In a different line of research,
the authors studied in [12] the amplitude and support recoveries of positive
discrete measures for a so-called BLASSO convex program. They demonstrated
that when $\sigma/\lambda,\sigma/d_{\min}^{2n-1}$ and
$\lambda/d_{\min}^{2n-1}$ are sufficiently small (with $\lambda$ being the
regularization parameter, $\sigma$ the noise level, $n$ the source number,
$d_{\min}$ the minimum separation distance between two sources), there exists
a unique solution to the BLASSO program consisting of exactly $n$ point
sources. The amplitudes and locations of the solution both converge toward
those of the ground truth when the noise and the regularization parameter
decay to zero faster than $d_{\min}^{2n-1}$. Note that this result is
consistent with our estimates in the current paper, showing that the BLASSO
achieves the optimal resolution order, which is quite impressive.

###  1.2 Main contribution

The main contribution of this paper is quantitative characterizations of the
resolution limits to number detection and location recovery in the super-
resolution of positive sources. Accurate detection of the source number (model
order) is important in the super-resolution problem and many parametric
estimation methods require the model order as a priori information. But there
are few theoretical results which address the issue when the number of
underlying sources is greater than two. In [27, 26], the first results for
capacity of the number detection in the super-resolution of general sources
are derived. Here we generalize the estimates to the case of positive sources,
which is also the first result for understanding the capacity of
superresolving positive sources. Specifically, we introduce the computational
resolution limit $\mathcal{D}_{num}^{+}$ for the detection of $n$ point
sources (see Definition 2.2), and derive the following sharp bounds:

$\frac{2e^{-1}}{\Omega}\Big{(}\frac{\sigma}{m_{\min}}\Big{)}^{\frac{1}{2n-2}}<\mathcal{D}_{num}^{+}\leq\frac{4.4\pi
e}{\Omega}\Big{(}\frac{\sigma}{m_{\min}}\Big{)}^{\frac{1}{2n-2}},$ (1.2)

where $\frac{\sigma}{m_{\min}}$ is viewed as the inverse of the signal-to-
noise ration (SNR). It follows that exact detection of the source number is
possible when the minimum separation distance of point sources $d_{\min}$ is
greater than $\frac{4.4\pi
e}{\Omega}\Big{(}\frac{\sigma}{m_{\min}}\Big{)}^{\frac{1}{2n-2}}$, and
impossible without additional a priori information when $d_{\min}$ is less
than
$\frac{2e^{-1}}{\Omega}\Big{(}\frac{\sigma}{m_{\min}}\Big{)}^{\frac{1}{2n-2}}$.

Following the same line of argument for the number detection problem, we also
consider the support recovery in the super-resolution of positive sources. We
introduce the computational resolution limit $\mathcal{D}_{supp}^{+}$ for the
support recovery (see Definition 2.4) and derive the following bounds:

$\frac{2e^{-1}}{\Omega}\Big{(}\frac{\sigma}{m_{\min}}\Big{)}^{\frac{1}{2n-1}}<\mathcal{D}_{supp}^{+}\leq\frac{5.88\pi
e}{\Omega}\Big{(}\frac{\sigma}{m_{\min}}\Big{)}^{\frac{1}{2n-1}}.$ (1.3)

As a consequence, the resolution limit $\mathcal{D}_{supp}^{+}$ is of the
order
$O(\frac{1}{\Omega}\Big{(}\frac{\sigma}{m_{\min}}\Big{)}^{\frac{1}{2n-1}})$.
It follows that stable recovery (in certain sense) of the source locations is
possible when the minimum separation distance of point sources $d_{\min}$ is
greater than $\frac{5.88\pi
e}{\Omega}\Big{(}\frac{\sigma}{m_{\min}}\Big{)}^{\frac{1}{2n-1}}$, and
impossible without additional a priori information when $d_{\min}$ is less
than
$\frac{2e^{-1}}{\Omega}\Big{(}\frac{\sigma}{m_{\min}}\Big{)}^{\frac{1}{2n-1}}$.
To further emphasize that the separation distance
$O\left(\frac{1}{\Omega}\Big{(}\frac{\sigma}{m_{\min}}\Big{)}^{\frac{1}{2n-1}}\right)$
is necessary for a stable location reconstruction, we construct an example
showing that if the sources are separated below the
$\frac{c}{\Omega}\Big{(}\frac{\sigma}{m_{\min}}\Big{)}^{\frac{1}{2n-1}}$ for
certain constant $c$, the recovered locations can be very unstable.

As a direct consequence of our estimates, we analyze the stability for a
sparsity-promoting algorithm ($l_{0}$ minimization) in superresolving positive
sources and show that it already achieves the optimal order of the resolution.
These estimates for the resolution limits are also generalized to multi-
dimensional spaces.

The quantitative characterizations of the resolution limits
$\mathcal{D}_{num}^{+}$ and $\mathcal{D}_{supp}^{+}$ imply phase transition
phenomena in the corresponding reconstructions, which are confirmed here by
numerical experiments.

Also, our techniques offer a way to analyze the capability of resolving
positive sources, which itself may have important applications.

###  1.3 Organization of the paper

The paper is organized in the following way. Section 2 presents the estimates
for the resolution limit in the one-dimensional super-resolution of positive
sources. Section 3 extends the estimates to multi-dimensional spaces. Section
4 proves the results in Section 2. In Sections 5 and 6, we verify the phase
transition in respectively the number detection and location recovery
problems. Section 7 concludes the paper. In Appendix A, we prove several
auxiliary lemmas and useful inequalities.

##  2 Resolution limits for super-resolution in one-dimensional space

We present in this section our main results on the resolution limit for the
super-resolution of one-dimensional positive sources. All the results shall be
proved in Section 4. We consider the case when the point sources are tightly
spaced and form a cluster. To be more specific, we define the interval

$I(n,\Omega):=\Big{[}-\frac{(n-1)\pi}{2\Omega},\quad\frac{(n-1)\pi}{2\Omega}\Big{]},$

which is of length of several Rayleigh limits and assume that $y_{j}\in
I(n,\Omega),1\leq j\leq n$. The reconstruction process is usually targeting at
some specific solutions in a so-called admissible set, which comprises of
discrete measures whose Fourier data are sufficiently close to
$\boldsymbol{\mathbf{Y}}$. In our problem, we introduce the following concept
of positive $\sigma$-admissible discrete measures. We denote in this section
$\left|\left|{f}\right|\right|_{\infty}=\max_{\omega\in[-\Omega,\Omega]}|f(\omega)|$.

######  Definition 2.1.

Given measurement $\mathbf{Y}$, we say that
$\hat{\mu}=\sum_{j=1}^{k}\hat{a}_{j}\delta_{\hat{y}_{j}},\hat{a}_{j}>0$ is a
positive $\sigma$-admissible discrete measure of $\ \mathbf{Y}$ if

$\left|\left|{\mathcal{F}[\hat{\mu}]-\mathbf{Y}}\right|\right|_{\infty}<\sigma.$

The set of positive $\sigma$-admissible measures of $\mathbf{Y}$ characterizes
all possible solutions to our super-resolution problem with the given
measurement $\mathbf{Y}$. Following similar definitions in [26, 27, 25], we
define the following computational resolution limit for the number detection
in the super-resolution of positive sources. The reason for the definition is
the fact that detecting the correct source number in $\mu$ is impossible
without additional a prior information when there exists one positive
$\sigma$-admissible measure with less than $n$ supports.

######  Definition 2.2.

The computational resolution limit to the number detection problem in the
super-resolution of one-dimensional positive source is defined as the smallest
nonnegative number $\mathcal{D}_{num}^{+}$ such that for all positive
$n$-sparse measure $\sum_{j=1}^{n}a_{j}\delta_{y_{j}},a_{j}>0,y_{j}\in
I(n,\Omega)$ and the associated measurement $\boldsymbol{\mathbf{Y}}$ in
(1.1), if

$\min_{p\neq j}|y_{j}-y_{p}|\geq\mathcal{D}_{num}^{+},$

then there does not exist any positive $\sigma$-admissible measure of $\
\mathbf{Y}$ with less than $n$ supports.

The notion of “computational resolution limit” emphasizes the essential
impossibility of correct number detection for very close source by any means.
Also, this notion depends crucially on the signal-to-noise ratio and the
sparsity of the source, which is different from all classical resolution
limits [1, 45, 33, 36, 39] that depend only on the cutoff frequency. We now
present sharp bounds for this computational resolution limit
$\mathcal{D}_{num}^{+}$. The following upper bound for it is a direct
consequence of [26, Theorem 1].

######  Theorem 2.1.

Let $\mathbf{Y}$ be a measurement generated by a positive measure
$\mu=\sum_{j=1}^{n}a_{j}\delta_{y_{j}}$, which is supported on $I(n,\Omega)$.
Let $n\geq 2$ and assume that the following separation condition is satisfied

$\min_{p\neq j}\Big{|}y_{p}-y_{j}\Big{|}\geq\frac{4.4\pi
e}{\Omega}\Big{(}\frac{\sigma}{m_{\min}}\Big{)}^{\frac{1}{2n-2}}.$ (2.1)

Then there do not exist any positive $\sigma$-admissible measures of
$\mathbf{Y}$ with less than $n$ supports.

Theorem 2.1 gives an upper bound for the computational resolution limit
$\mathcal{D}_{num}^{+}$. This upper bound is shown to be sharp for the super-
resolution of general discrete source (not positive) by a lower bound derived
in [26], but the result is unknown for the case of resolving positive sources.
We next present a lower bound of $\mathcal{D}_{num}^{+}$ which is the main
result of this paper.

######  Theorem 2.2.

For given $0<\sigma\leq m_{\min}$ and integer $n\geq 2$, there exist positive
measures $\mu=\sum_{j=1}^{n}a_{j}\delta_{y_{j}}$ with $n$ supports and
$\hat{\mu}=\sum_{j=1}^{n-1}\hat{a}_{j}\delta_{\hat{y}_{j}}$ with $(n-1)$
supports such that
$||\mathcal{F}[\hat{\mu}]-\mathcal{F}[\mu]||_{\infty}<\sigma$. Moreover,

$\min_{1\leq j\leq n}\left|{a_{j}}\right|=m_{\min},\quad\min_{p\neq
j}\left|{y_{p}-y_{j}}\right|=\frac{2e^{-1}}{\Omega}\Big{(}\frac{\sigma}{m_{\min}}\Big{)}^{\frac{1}{2n-2}}.$

The above result gives a lower bound for the computational resolution limit
$\mathcal{D}_{num}^{+}$ to the number detection problem. Combined with Theorem
2.1, it reveals that the computational resolution limit for number detection
satisfies

$\frac{2e^{-1}}{\Omega}\Big{(}\frac{\sigma}{m_{\min}}\Big{)}^{\frac{1}{2n-2}}<\mathcal{D}_{num}^{+}\leq\frac{4.4\pi
e}{\Omega}\Big{(}\frac{\sigma}{m_{\min}}\Big{)}^{\frac{1}{2n-2}}.$

We remark that similarly to the results of [2, 5, 26], our bounds are the
worst-case bounds, and one may achieve better bounds for the case of random
noise.

We now consider the location (support) recovery problem in the super-
resolution of positive sources. We first introduce the following concept of
$\delta$-neighborhood of a discrete measure.

######  Definition 2.3.

Let $\mu=\sum_{j=1}^{n}a_{j}\delta_{y_{j}}$ be a discrete measure and let
$0<\delta$ be such that the $n$ intervals $(y_{k}-\delta,y_{k}+\delta),1\leq
k\leq n$ are pairwise disjoint. We say that
$\hat{\mu}=\sum_{j=1}^{n}\hat{a}_{j}\delta_{\hat{y}_{j}}$ is within
$\delta$-neighborhood of $\mu$ if each $\hat{y}_{j}$ is contained in one and
only one of the n intervals $(y_{k}-\delta,y_{k}+\delta),1\leq k\leq n$.

According to the above definition, a measure in a $\delta$-neighbourhood
preserves the inner structure of the real source. For any stable support
recovery algorithm, the output should be a measure in some
$\delta$-neighborhood, otherwise it is impossible to distinguish which is the
reconstructed location of some $y_{j}$’s. We now introduce the computational
resolution limit for stable support recoveries. For ease of exposition, we
only consider measures supported in $I(n,\Omega)$, where $n$ is the number of
supports.

######  Definition 2.4.

The computational resolution limit to the stable support recovery problem in
the super-resolution of one-dimensional positive sources is defined as the
smallest nonnegative number $\mathcal{D}_{supp}^{+}$ such that for all
positive $n$-sparse measures
$\sum_{j=1}^{n}a_{j}\delta_{y_{j}},a_{j}>0,y_{j}\in I(n,\Omega)$ and the
associated measurement $\boldsymbol{\mathbf{Y}}$ in (1.1), if

$\min_{p\neq j}|y_{j}-y_{p}|\geq\mathcal{D}_{supp}^{+},$

then there exists $\delta>0$ such that any positive $\sigma$-admissible
measure for $\mathbf{Y}$ with $n$ supports in $I(n,\Omega)$ is within a
$\delta$-neighbourhood of $\mu$.

To state the results on the resolution limit to stable support recovery, we
introduce the super-resolution factor which is defined as the ratio between
Rayleigh limit $\frac{\pi}{\Omega}$ (for point spread function $sinc(x)^{2}$)
and the minimum separation distance of sources $d_{\min}:=\min_{p\neq
j}|y_{p}-y_{j}|$:

$SRF:=\frac{\pi}{\Omega d_{\min}}.$

As a direct consequence of [26, Theorem 2], we have the following theorem
giving the upper bound of $\mathcal{D}_{supp}^{+}$.

######  Theorem 2.3.

Let $n\geq 2$, assume that the positive measure
$\mu=\sum_{j=1}^{n}a_{j}\delta_{y_{j}}$ is supported on $I(n,\Omega)$ and that

$\min_{p\neq j}\left|y_{p}-y_{j}\right|\geq\frac{5.88\pi
e}{\Omega}\Big{(}\frac{\sigma}{m_{\min}}\Big{)}^{\frac{1}{2n-1}}.$ (2.2)

If $\hat{\mu}=\sum_{j=1}^{n}\hat{a}_{j}\delta_{\hat{y}_{j}},\hat{a}_{j}>0$
supported on $I(n,\Omega)$ is a positive $\sigma$-admissible measure for the
measurement generated by $\mu$, then $\hat{\mu}$ is within the
$\frac{d_{\min}}{2}$-neighborhood of $\mu$. Moreover, after reordering the
$\hat{y}_{j}$’s, we have

$\Big{|}\hat{y}_{j}-y_{j}\Big{|}\leq\frac{C(n)}{\Omega}SRF^{2n-2}\frac{\sigma}{m_{\min}},\quad
1\leq j\leq n,$ (2.3)

where $C(n)=n2^{4n-2}e^{2n}\pi^{-\frac{1}{2}}$.

Theorem 2.3 gives an upper bound to the computational resolution limit
$\mathcal{D}_{supp}^{+}$. We next show that the order of the upper bound is
optimal.

######  Theorem 2.4.

For given $0<\sigma\leq m_{\min}$ and integer $n\geq 2$, let

$\tau=\frac{e^{-1}}{\Omega}\
\Big{(}\frac{\sigma}{m_{\min}}\Big{)}^{\frac{1}{2n-1}}.$ (2.4)

Then there exist a positive measure $\mu=\sum_{j=1}^{n}a_{j}\delta_{y_{j}}$
with $n$ supports at
$\\{-(n-\frac{1}{2})\tau,-(n-\frac{5}{2})\tau,\cdots,(n-\frac{3}{2})\tau\\}$
and a positive measure
$\hat{\mu}=\sum_{j=1}^{n}\hat{a}_{j}\delta_{\hat{y}_{j}}$ with $n$ supports at
$\\{-(n-\frac{3}{2})\tau,-(n-\frac{7}{2})\tau,\cdots,(n-\frac{1}{2})\tau\\}$
such that

$||\mathcal{F}[\hat{\mu}]-\mathcal{F}[\mu]||_{\infty}<\sigma,\quad\min_{1\leq
j\leq n}|a_{j}|=m_{\min}.$

Since the minimum distance between $y_{j}$’s is $d_{\min}=2\tau$, thus for the
positive $\sigma$-admissible measure $\hat{\mu}$, it is obviously that the
$\hat{y}_{j}$’s are not in any $\delta$-neighborhood of $y_{j}$’s for
$\delta\leq\frac{d_{\min}}{2}$ (for $\delta>\frac{d_{\min}}{2}$ the intervals
in Definition 2.3 are overlapped). According to Definition 2.4, Theorem 2.4
implies $\mathcal{D}_{supp}^{+}>\frac{2e^{-1}}{\Omega}\
\Big{(}\frac{\sigma}{m_{\min}}\Big{)}^{\frac{1}{2n-1}}$. Thus we conclude that

$\frac{2e^{-1}}{\Omega}\
\Big{(}\frac{\sigma}{m_{\min}}\Big{)}^{\frac{1}{2n-1}}<\mathcal{D}_{supp}^{+}\leq\frac{5.88\pi
e}{\Omega}\ \Big{(}\frac{\sigma}{m_{\min}}\Big{)}^{\frac{1}{2n-1}}.$

To further demonstrate that the order
$O\left(\frac{1}{\Omega}\left(\frac{\sigma}{m_{\min}}\right)^{\frac{1}{2n-1}}\right)$
is essentially optimal for stable location reconstruction, we present an
example with a new distribution of the source locations as follows.

######  Proposition 2.1.

For given $0<\sigma<m_{\min}$ and integer $n\geq 2$, let

$\tau=\frac{0.2e^{-1}}{\Omega s^{\frac{2n+1}{2n-1}}}\
\Big{(}\frac{\sigma}{m_{\min}}\Big{)}^{\frac{1}{2n-1}}.$ (2.5)

Then there exist a positive measure $\mu=\sum_{j=1}^{n}a_{j}\delta_{y_{j}}$
with $n$ supports at
$\\{t_{j}=-\frac{sn-2}{2}\tau+\frac{(j-2)s}{2}\tau,j=2,4,\cdots,2n\\}$ and a
positive measure $\hat{\mu}=\sum_{j=1}^{n}\hat{a}_{j}\delta_{\hat{y}_{j}}$
with $n$ supports at
$\\{t_{j}=t_{4\lceil\frac{j+1}{4}\rceil-2}+(-1)^{\frac{j+1}{2}}\tau,j=1,3,5,\cdots,2n-1\\}$
such that

$||\mathcal{F}[\hat{\mu}]-\mathcal{F}[\mu]||_{\infty}<\sigma,\quad\min_{1\leq
j\leq n}|a_{j}|=m_{\min}.$

Note that the $n$ underlying sources in $\mu$ are spaced by

$s\tau=\frac{0.4e^{-1}}{\Omega s^{\frac{2}{2n-1}}}\
\Big{(}\frac{\sigma}{m_{\min}}\Big{)}^{\frac{1}{2n-1}}.$

Proposition 2.1 reveals that when the $n$ point sources are separated by
$\frac{c}{\Omega}\Big{(}\frac{\sigma}{m_{\min}}\Big{)}^{\frac{1}{2n-1}}$ for
some constant $c$, the recovered source locations from the $\sigma$-admissible
measures can be very unstable; see Figure 2.1.

Figure 2.1: An example of unstable location recovery.

######  Remark 2.1.

Note that all of our results hold for the case when the sources are supported
on a grid. Specifically, we consider the grid points
$t_{j}=j\Delta,j=1,\cdots,N,$ where $N$ and $\Delta$ are the number and
spacing of grid points, respectively, and assume the sources are supported on
the grid. Assume also that the grid spacing
$\Delta\leq\frac{e^{-1}}{\Omega}\left(\frac{\sigma}{m_{\min}}\right)^{\frac{1}{2n-1}}$
for fixed $n$ and $m_{\min}$. By Theorem 2.4, we can construct two positive
measures $\mu=\sum_{q=1}^{n}a_{q}\delta_{t_{j_{q}}}$ and
$\hat{\mu}=\sum_{q=1}^{n}\hat{a}_{q}\delta_{\hat{t}_{j_{q}}}$ supported on the
grid with completely different supports such that the difference of their
Fourier data is less than the noise level and the minimum separation of
sources is equal or less than
$\frac{2e^{-1}}{\Omega}\left(\frac{\sigma}{m_{\min}}\right)^{\frac{1}{2n-1}}$
with $\min_{q=1,\cdots,n}a_{q}=m_{\min}$.

######  Remark 2.2.

Note that our estimates for both the resolution limits in the number detection
and support recovery already improve the estimates in [26] for the case of
general sources.

###  2.1 Stability analysis of sparsity-promoting algorithms

Nowadays, sparsity-promoting algorithms are popular methods in image
processing, signal processing and many other fields. By our results for the
resolution limits, we can derive a sharp stability result for the $l_{0}$
minimization in the super-resolution of positive sources. We consider the
following $l_{0}$-minimization problem:

$\min_{\text{$\rho$ supported on $\mathcal{O}$, $\rho$ is a positive discrete
measure}}\left|\left|{\rho}\right|\right|_{0}\quad\text{subject
to}\quad|\mathcal{F}\rho(\omega)-\boldsymbol{\mathbf{Y}}(\omega)|<\sigma,\quad\omega\in[-\Omega,\Omega],$
(2.6)

where $||\rho||_{0}$ is the number of Dirac masses representing the discrete
measure $\rho$. As a corollary of Theorems 2.1 and 2.3, we have the following
theorem for its stability.

######  Theorem 2.5.

Let $n\geq 2$ and $\sigma\leq m_{\min}$. Let the measurement
$\boldsymbol{\mathbf{Y}}$ in (1.1) be generated by a positive $n$-sparse
measure $\mu=\sum_{j=1}^{n}a_{j}\delta_{y_{j}},y_{j}\in I(n,\Omega)$. Assume
that

$d_{\min}:=\min_{p\neq j}\left|y_{p}-y_{j}\right|\geq\frac{5.88\pi
e}{\Omega}\Big{(}\frac{\sigma}{m_{\min}}\Big{)}^{\frac{1}{2n-1}}.$ (2.7)

Let $\mathcal{O}$ in the minimization problem (2.6) be (or be included in)
$I(n,\Omega)$ , then the solution to (2.6) contains exactly $n$ point sources.
For any solution $\hat{\mu}=\sum_{j=1}^{n}\hat{a}_{j}\delta_{\hat{y}_{j}}$, it
is in a $\frac{d_{\min}}{2}$-neighborhood of $\mu$. Moreover, after reordering
the ${\hat{y}}_{j}$’s, we have

$\left|\hat{y}_{j}-y_{j}\right|\leq\frac{C(n)}{\Omega}SRF^{2n-2}\frac{\sigma}{m_{\min}},\quad
1\leq j\leq n,$ (2.8)

where $C(n)=n2^{4n-2}e^{2n}\pi^{-\frac{1}{2}}$.

Theorem 2.5 reveals that sparsity promoting over admissible solutions can
resolve the source locations to the resolution limit level. It provides an
insight that theoretically sparsity-promoting algorithms would have excellent
performance on the super-resolution of positive sources, which already have
been corroborated by [30, 29, 12]. Especially, under the separation condition
(2.7), any tractable sparsity-promoting algorithms (such as total variation
minimization algorithms [7]) rendering the sparsest solution could stably
reconstruct all the source locations.

##  3 Resolution limits for super-resolution in multi-dimensional spaces

In this section, combining the estimates in Section 2 and [25, 24], we present
our main results on the resolution limits to the super-resolution of positive
sources in multi-dimensional spaces. Let us first introduce the model setting.
We consider the source as the $n$-sparse positive measure

$\mu=\sum_{j=1}^{n}a_{j}\delta_{\boldsymbol{\mathbf{y}}_{j}},$

where $\delta$ denotes Dirac’s $\delta$-distribution in $\mathbb{R}^{k}$,
$\boldsymbol{\mathbf{y}}_{j}\in\mathbb{R}^{k},1\leq j\leq n$, represent the
locations of the point sources and $a_{j}>0,1\leq j\leq n$ are their
amplitudes. Denote by

$m_{\min}=\min_{j=1,\cdots,n}|a_{j}|,\quad d_{\min}=\min_{p\neq
j}||\boldsymbol{\mathbf{y}}_{p}-\boldsymbol{\mathbf{y}}_{j}||_{2}.$ (3.1)

The available measurement is the noisy Fourier data of $\mu$ in a bounded
region, that is,

$\mathbf{Y}(\boldsymbol{\mathbf{\omega}})=\mathcal{F}\mu(\boldsymbol{\mathbf{\omega}})+\mathbf{W}(\boldsymbol{\mathbf{\omega}})=\sum_{j=1}^{n}a_{j}e^{i\boldsymbol{\mathbf{y}}_{j}\cdot\boldsymbol{\mathbf{\omega}}}+\mathbf{W}(\boldsymbol{\mathbf{\omega}}),\
\boldsymbol{\mathbf{\omega}}\in\mathbb{R}^{k},$ (3.2)

where with slight abuse of notation $\mathcal{F}\mu$ denotes the Fourier
transform of $\mu$ in the $k$-dimensional space, $\Omega$ is the cut-off
frequency, and $\mathbf{W}$ is the noise. We assume that

$||\mathbf{W}(\boldsymbol{\mathbf{\omega}})||_{\infty}<\sigma,\
||\boldsymbol{\mathbf{\omega}}||_{2}\leq\Omega,$

where $\sigma$ is the noise level and
$\left|\left|{f(\boldsymbol{\mathbf{\omega}})}\right|\right|_{\infty}:=\max_{\boldsymbol{\mathbf{\omega}}\in\mathbb{R}^{k},||\boldsymbol{\mathbf{\omega}}||_{2}\leq\Omega}|f(\boldsymbol{\mathbf{\omega}})|$
in this section. We are interested in the resolution limit for resolving a
cluster of tightly-spaced point sources. Thus, we denote by

$B_{\delta}^{k}(\boldsymbol{\mathbf{x}}):=\Big{\\{}\mathbf{y}\ \Big{|}\
\mathbf{y}\in\mathbb{R}^{k},\
||\boldsymbol{\mathbf{y}}-\boldsymbol{\mathbf{x}}||_{2}<\delta\Big{\\}},$

and assume that $\boldsymbol{\mathbf{y}}_{j}\in
B_{\frac{(n-1)\pi}{2\Omega}}^{k}(\boldsymbol{\mathbf{0}}),j=1,\cdots,n$, or
equivalently $||\boldsymbol{\mathbf{y}}_{j}||_{2}<\frac{(n-1)\pi}{2\Omega}$.

We then define positive $\sigma$-admissible measures and computational
resolution limits in the $k$-dimensional space analogously to those in the
one-dimensional case.

######  Definition 3.1.

Given measurement $\mathbf{Y}$, we say that the positive measure
$\hat{\mu}=\sum_{j=1}^{m}\hat{a}_{j}\delta_{\mathbf{\hat{y}}_{j}},\
\mathbf{\hat{y}}_{j}\in\mathbb{R}^{k}$, is a positive $\sigma$-admissible
discrete measure of $\mathbf{Y}$ if

$||\mathcal{F}\hat{\mu}(\boldsymbol{\mathbf{\omega}})-\boldsymbol{\mathbf{Y}}(\boldsymbol{\mathbf{\omega}})||_{\infty}<\sigma,\
\text{for all}\ ||\boldsymbol{\mathbf{\omega}}||_{2}\leq\Omega,\
\boldsymbol{\mathbf{\omega}}\in\mathbb{R}^{k}.$

######  Definition 3.2.

The computational resolution limit to the number detection problem in
$k$-dimensional space is defined as the smallest nonnegative number
$\mathcal{D}_{k,num}^{+}$ such that for all positive $n$-sparse measures
$\sum_{j=1}^{n}a_{j}\delta_{\mathbf{y}_{j}},\boldsymbol{\mathbf{y}}_{j}\in
B_{\frac{(n-1)\pi}{2\Omega}}^{k}(\boldsymbol{\mathbf{0}})$ and the associated
measurement $\boldsymbol{\mathbf{Y}}$ in (3.2), if

$\min_{p\neq
j}||\mathbf{y}_{j}-\mathbf{y}_{p}||_{2}\geq\mathcal{D}_{k,num}^{+},$

then there does not exist any positive $\sigma$-admissible measure with less
than $n$ supports for $\mathbf{Y}$.

As a consequence of [25, Theorem 2.3], we have the following result for the
upper bound of the $\mathcal{D}_{k,num}^{+}$.

######  Theorem 3.1.

Let $n\geq 2$ and the measurement $\mathbf{Y}$ in (3.2) be generated by a
positive $n$-sparse measure
$\mu=\sum_{j=1}^{n}a_{j}\delta_{\mathbf{y}_{j}},\boldsymbol{\mathbf{y}}_{j}\in
B_{\frac{(n-1)\pi}{2\Omega}}^{k}(\boldsymbol{\mathbf{0}})$. There is a
constant $C_{num}(k,n)$ which has an explicit form such that if

$\min_{p\neq j,1\leq p,j\leq
n}\left|\left|{\mathbf{y}_{p}-\mathbf{y}_{j}}\right|\right|_{2}\geq\frac{C_{num}(k,n)}{\Omega}\Big{(}\frac{\sigma}{m_{\min}}\Big{)}^{\frac{1}{2n-2}}$
(3.3)

holds, then there do not exist any positive $\sigma$-admissible measures of
$\mathbf{Y}$ with less than $n$ supports.

We next show that the above upper bound is optimal in terms of the signal-to-
noise ratio.

######  Theorem 3.2.

For given $0<\sigma\leq m_{\min}$ and integer $n\geq 2$, there exist positive
measures $\mu=\sum_{j=1}^{n}a_{j}\delta_{\boldsymbol{\mathbf{y}}_{j}}$ with
$n$ supports, and
$\hat{\mu}=\sum_{j=1}^{n-1}\hat{a}_{j}\delta_{\mathbf{\hat{y}}_{j}}$ with
$(n-1)$ supports such that
$||\mathcal{F}[\hat{\mu}]-\mathcal{F}[\mu]||_{\infty}<\sigma$. Moreover,

$\min_{1\leq j\leq n}|a_{j}|=m_{\min},\quad\min_{p\neq
j}\left|\left|{\boldsymbol{\mathbf{y}}_{p}-\boldsymbol{\mathbf{y}}_{j}}\right|\right|_{2}=\frac{2e^{-1}}{\Omega}\Big{(}\frac{\sigma}{m_{\min}}\Big{)}^{\frac{1}{2n-2}}.$

###### Proof.

Consider $\gamma=\sum_{j=1}^{2n-1}a_{j}\delta_{\boldsymbol{\mathbf{t}}_{j}}$
with
$\boldsymbol{\mathbf{t}}_{1}=(-(n-1)\tau,0,\cdots,0),\boldsymbol{\mathbf{t}}_{2}=(-(n-2)\tau,0,\cdots,0),\cdots,\boldsymbol{\mathbf{t}}_{2n-1}=((n-1)\tau,0,\cdots,0)$
and
$\tau=\frac{e^{-1}}{\Omega}\Big{(}\frac{\sigma}{m_{\min}}\Big{)}^{\frac{1}{2n-2}}$.
For every
$\boldsymbol{\mathbf{\omega}}=(\omega_{1},\omega_{2},\cdots,\omega_{k})^{\top}$,

$\mathcal{F}\gamma(\boldsymbol{\mathbf{\omega}})=\sum_{j=1}^{2n-1}a_{j}e^{i\boldsymbol{\mathbf{t}}_{j}\cdot\boldsymbol{\mathbf{\omega}}}=\sum_{j=1}^{2n-1}a_{j}e^{i(-n+j)\tau\omega_{1}},|\omega_{1}|\leq\Omega.$

This reduces the estimation of
$\mathcal{F}\gamma(\boldsymbol{\mathbf{\omega}})$ to the one-dimensional case.
Combined with Theorem 2.2, there exist $a_{2j-1}>0,a_{2j}<0,1\leq j\leq
n,\min_{j=1,\cdots,n}|a_{2j-1}|=m_{\min}$, so that
$\left|\left|{\mathcal{F}\gamma(\boldsymbol{\mathbf{\omega}})}\right|\right|_{\infty}<\sigma$.
As a consequence,

$\mu=\sum_{j=1}^{n}a_{2j-1}\delta_{\boldsymbol{\mathbf{t}}_{2j-1}},\quad\hat{\mu}=\sum_{j=1}^{n-1}-a_{2j}\delta_{\boldsymbol{\mathbf{t}}_{2j}}$

satisfy all the conditions of the theorem. ∎

The above results indicate that

$\frac{C_{1,k}(n)}{\Omega}\Big{(}\frac{\sigma}{m_{\min}}\Big{)}^{\frac{1}{2n-2}}<\mathcal{D}_{k,num}^{+}\leq\frac{C_{2,k}(n)}{\Omega}\Big{(}\frac{\sigma}{m_{\min}}\Big{)}^{\frac{1}{2n-2}},$

with $C_{1,k}(n),C_{2,k}(n)$ being certain constants. An interesting open
problem is to improve these constants. Two of the authors of this paper have
made a progress in this direction [24].

To state the estimates for the resolution limits to the location recovery, we
introduce the following concepts which are analogue to those in the one-
dimensional case.

######  Definition 3.3.

Let $\mu=\sum_{j=1}^{n}a_{j}\delta_{\boldsymbol{\mathbf{y}}_{j}}$ be a
positive $n$-sparse discrete measure in $\mathbb{R}^{k}$ and let $\delta>0$ be
such that the $n$ balls $B_{\delta}^{k}(\boldsymbol{\mathbf{y}}_{j}),1\leq
j\leq n,$ are pairwise disjoint. We say that
$\hat{\mu}=\sum_{j=1}^{n}\hat{a}_{j}\delta_{\mathbf{\hat{y}}_{j}}$ is within
$\delta$-neighborhood of $\mu$ if each $\mathbf{\hat{y}}_{j}$ is contained in
one and only one of the $n$ balls
$B_{\delta}^{k}(\boldsymbol{\mathbf{y}}_{j}),1\leq j\leq n$.

######  Definition 3.4.

The computational resolution limit to the stable support recovery problem in
$k$-dimensional space is defined as the smallest non-negative number
$\mathcal{D}_{k,supp}^{+}$ such that for any positive $n$-sparse measure
$\mu=\sum_{j=1}^{n}a_{j}\delta_{\mathbf{y}_{j}},\boldsymbol{\mathbf{y}}_{j}\in
B_{\frac{(n-1)\pi}{2\Omega}}^{k}(\boldsymbol{\mathbf{0}})$ and the associated
measurement $\boldsymbol{\mathbf{Y}}$ in (3.2), if

$\min_{p\neq j,1\leq p,j\leq
n}\left|\left|{\mathbf{y}_{p}-\mathbf{y}_{j}}\right|\right|_{2}\geq\mathcal{D}_{k,supp}^{+},$

then there exists $\delta>0$ such that any $\sigma$-admissible measure of
$\mathbf{Y}$ with $n$ supports in
$B_{\frac{(n-1)\pi}{2\Omega}}^{k}(\mathbf{0})$ is within a
$\delta$-neighbourhood of $\mu$.

As a consequence of [25, Theorem 2.7], we have the following result on the
characterization of $\mathcal{D}_{k,supp}^{+}$.

######  Theorem 3.3.

Let $n\geq 2$. Let the measurement $\boldsymbol{\mathbf{Y}}$ in (3.2) be
generated by a positive $n$-sparse measure
$\mu=\sum_{j=1}^{n}a_{j}\delta_{\boldsymbol{\mathbf{y}}_{j}},\boldsymbol{\mathbf{y}}_{j}\in
B_{\frac{(n-1)\pi}{2\Omega}}^{k}(\boldsymbol{\mathbf{0}})$ in the
$k$-dimensional space. There is a constant $C_{supp}(k,n)$ which has an
explicit form such that if

$d_{\min}:=\min_{p\neq
j}\Big{|}\Big{|}\mathbf{y}_{p}-\mathbf{y}_{j}\Big{|}\Big{|}_{2}\geq\frac{C_{supp}(k,n)}{\Omega}\Big{(}\frac{\sigma}{m_{\min}}\Big{)}^{\frac{1}{2n-1}}$
(3.4)

holds, then for any
$\hat{\mu}=\sum_{j=1}^{n}\hat{a}_{j}\delta_{\mathbf{\hat{y}}_{j}},\mathbf{\hat{y}}_{j}\in
B_{\frac{(n-1)\pi}{2\Omega}}^{k}(\boldsymbol{\mathbf{0}})$ being a positive
$\sigma$-admissible measure of $\boldsymbol{\mathbf{Y}}$, $\hat{\mu}$ is
within the $\frac{d_{\min}}{2}$-neighborhood of $\mu$. Moreover, after
reordering the $\mathbf{\hat{y}}_{j}$’s, we have

$\Big{|}\Big{|}\mathbf{\hat{y}}_{j}-\mathbf{y}_{j}\Big{|}\Big{|}_{2}\leq\frac{C(k,n)}{\Omega}SRF^{2n-2}\frac{\sigma}{m_{\min}},\quad
1\leq j\leq n,$ (3.5)

where $SRF:=\frac{\pi}{\Omega}$ is the super-resolution factor and $C(k,n)$
has an explicit form.

Theorem 3.3 gives an upper bound for the computational resolution limit for
the stable support recovery in the $k$-dimensional space. This bound is
optimal in terms of the order of the signal-to-noise ratio, as is shown by the
theorem below.

######  Theorem 3.4.

For given $0<\sigma\leq m_{\min}$ and integer $n\geq 2$, let

$\tau=\frac{e^{-1}}{\Omega}\
\Big{(}\frac{\sigma}{m_{\min}}\Big{)}^{\frac{1}{2n-1}}.$ (3.6)

Then there exist a positive measure
$\mu=\sum_{j=1}^{n}a_{j}\delta_{\boldsymbol{\mathbf{y}}_{j}},\boldsymbol{\mathbf{y}}_{j}\in\mathbb{R}^{k},$
with $n$ supports at
$\\{(-(n-\frac{1}{2})\tau,0,\cdots,0),(-(n-\frac{5}{2})\tau,0,\cdots,0),\cdots,((n-\frac{3}{2})\tau,0,\cdots,0)\\}$
and a positive measure
$\hat{\mu}=\sum_{j=1}^{n}\hat{a}_{j}\delta_{\mathbf{\hat{y}}_{j}},\mathbf{\hat{y}}_{j}\in\mathbb{R}^{k},$
with $n$ supports at
$\\{(-(n-\frac{3}{2})\tau,0,\cdots,0),(-(n-\frac{7}{2})\tau,0,\cdots,0),\cdots,((n-\frac{1}{2})\tau,0,\cdots,0)\\}$
such that

$\left|\left|{\mathcal{F}[\hat{\mu}]-\mathcal{F}[\mu]}\right|\right|_{\infty}<\sigma,\quad\min_{1\leq
j\leq n}|a_{j}|=m_{\min}.$

###### Proof.

Similar to the discussions in the proof of Theorem 3.2, the problem can be
reduced to the one-dimensional case. Then leveraging Theorem 2.4 proves the
result. ∎

Theorem 3.4 provides a lower bound to the computational resolution limit
$\mathcal{D}_{k,supp}^{+}$. Combined with Theorem 3.3, it reveals that

$\frac{C_{3,k}(n)}{\Omega}\
\Big{(}\frac{\sigma}{m_{\min}}\Big{)}^{\frac{1}{2n-1}}<\mathcal{D}_{k,supp}^{+}\leq\frac{C_{4,k}(n)}{\Omega}\Big{(}\frac{\sigma}{m_{\min}}\Big{)}^{\frac{1}{2n-1}}$

for certain constants $C_{3,k}(n),C_{4,k}(n)$.

######  Remark 3.1.

Compared to the one-dimensional case in Section 2, the upper bounds of multi-
dimensional computational resolution limits for the number detection and
location recovery in the super-resolution of positive sources has the same
dependence on the signal-to-noise ratio and cutoff frequency. Moreover, their
dependence on the dimensionality are indicated by the constant factors in the
upper bound. We conjecture that the optimal constants may be independent of
the source number $n$. Note that the constant factors in the bounds have been
improved in [24] to nearly optimal for the two-dimensional case.

##  4 Proofs of main results

We first introduce some notation and lemmas that are used in the following
proofs. Set

$\phi_{s}(t)=\left(1,t,\cdots,t^{s}\right)^{\top}.$ (4.1)

We recall the Stirling formula that

$\sqrt{2\pi}n^{n+\frac{1}{2}}e^{-n}\leq n!\leq en^{n+\frac{1}{2}}e^{-n}.$
(4.2)

######  Lemma 4.1.

Let $t_{1},\cdots,t_{k}$ be $k$ different real numbers and let $t$ be a real
number. We have

$\left(D_{k}(k-1)^{-1}\phi_{k-1}(t)\right)_{j}=\Pi_{1\leq q\leq k,q\neq
j}\frac{t-t_{q}}{t_{j}-t_{q}},$

where $D_{k}(k-1):=\big{(}\phi_{k-1}(t_{1}),\cdots,\phi_{k-1}(t_{k})\big{)}$
with $\phi_{k-1}(\cdot)$ defined by (4.1).

###### Proof.

This is [26, Lemma 5]. For the reader’s convenience, we present a simple proof
here. We denote $\left(D_{k}(k-1)^{-1}\right)_{jq}=b_{jq}$. Observe that

$\left(D_{k}(k-1)^{-1}\phi_{k-1}(t)\right)_{j}=\sum_{q=1}^{k}b_{jq}t^{q-1}.$

We have

$\sum_{q=1}^{k}b_{jq}(t_{p})^{q-1}=\delta_{jp},\ \forall j,p=1,\cdots,k,$

where $\delta_{jp}$ is the Kronecker delta function. Then the polynomial
$P_{j}(x)=\sum_{q=1}^{k}b_{jq}x^{q-1}$ satisfies
$P_{j}(t_{1})=0,\cdots,P_{j}(t_{j-1})=0,P_{j}(t_{j})=1,P_{j}(t_{j+1})=0,\cdots,P_{j}(t_{k})=0$.
Therefore, it must be the Lagrange polynomial

$P_{j}(x)=\Pi_{1\leq q\leq k,q\neq j}\frac{x-t_{q}}{t_{j}-t_{q}}.$

It follows that

$\displaystyle\left(D_{k}(k-1)^{-1}\phi_{k-1}(t)\right)_{j}=\Pi_{1\leq q\leq
k,q\neq j}\frac{t-t_{q}}{t_{j}-t_{q}}.$

∎

###  4.1 Proof of Theorem 2.2

###### Proof.

Step 1. Let

$\tau=\frac{e^{-1}}{\Omega}\Big{(}\frac{\sigma}{m_{\min}}\Big{)}^{\frac{1}{2n-2}}$
(4.3)

and
$t_{1}=-(n-1)\tau,t_{2}=-(n-2)\tau,\cdots,t_{n}=0,t_{n+1}=\tau,\cdots,t_{2n-1}=(n-1)\tau$.
Consider the following system of linear equations:

$Aa=0,$ (4.4)

where $A=\big{(}\phi_{2n-3}(t_{1}),\cdots,\phi_{2n-3}(t_{2n-1})\big{)}$ with
$\phi_{2n-3}(\cdot)$ being defined by (4.1). Since $A$ is underdetermined,
there exists a nontrivial solution $a=(a_{1},\cdots,a_{2n-1})^{\top}$ to
(4.4). By the linear independence of the any $(2n-2)$ column vectors of $A$,
we can show that all $a_{j}$’s are nonzero. By a scaling of $a$, we can assume
that $a_{2n-1}>0$ and

$\min_{1\leq j\leq n}|a_{2j-1}|=m_{\min}.$ (4.5)

We define

$\mu=\sum_{j=1}^{n}a_{2j-1}\delta_{t_{2j-1}},\quad\hat{\mu}=\sum_{j=1}^{n-1}-a_{2j}\delta_{t_{2j}}.$

We shall show that the intensities in $\hat{\mu}$ and $\mu$ are all positive
and $||\mathcal{F}[\hat{\mu}]-\mathcal{F}[\mu]||_{\infty}<\sigma$ in the
subsequent steps.

Step 2. We first analyze the sign of each $a_{j},j=1,\cdots,2n-1,$ based on
$a_{2n-1}>0$. The equation (4.4) implies that

$-a_{2n-1}\phi_{2n-3}(t_{2n-1})=\big{(}\phi_{2n-3}(t_{1}),\cdots,\phi_{2n-3}(t_{2n-2})\big{)}(a_{1},\cdots,a_{2n-2})^{\top},$

and hence

$-a_{2n-1}\left(\phi_{2n-3}(t_{1}),\cdots,\phi_{2n-3}(t_{2n-2})\right)^{-1}\phi_{2n-3}(t_{2n-1})=(a_{1},\cdots,a_{2n-2})^{\top}.$

Together with Lemma 4.1, we have

$-a_{2n-1}\Pi_{1\leq q\leq 2n-2,q\neq
j}\frac{t_{2n-1}-t_{q}}{t_{j}-t_{q}}=a_{j},$ (4.6)

for $j=1,\cdots,2n-2$. Observe first that $\Pi_{1\leq q\leq 2n-2,q\neq
j}(t_{2n-1}-t_{q})$ is always positive for $1\leq j\leq 2n-2$. For $j=2n-2$,
since $a_{2n-1}>0$, $-a_{2n-1}\Pi_{1\leq q\leq 2n-2,q\neq
2n-2}(t_{2n-2}-t_{q})$ is negative in (4.6). Thus we have $a_{2n-2}<0$. In the
same fashion, we see that $a_{j}<0$ for even $j$ and $a_{j}>0$ for odd $j$.
Hence the intensities in $\hat{\mu}$ and $\mu$ are all positive.

Step 3. We demonstrate that
$||\mathcal{F}[\hat{\mu}]-\mathcal{F}[\mu]||_{\infty}<\sigma$. Observe that

$||\mathcal{F}[\hat{\mu}]-\mathcal{F}[\mu]||_{\infty}=\max_{x\in[-\Omega,\Omega]}|\mathcal{F}(\gamma)(x)|,$
(4.7)

where $\gamma=\sum_{j=1}^{2n-1}a_{j}\delta_{t_{j}}$ and

$\mathcal{F}[\gamma](x)=\sum_{j=1}^{2n-1}a_{j}e^{it_{j}x}=\sum_{j=1}^{2n-1}a_{j}\sum_{k=0}^{\infty}\frac{(it_{j}x)^{k}}{k!}=\sum_{k=0}^{\infty}Q_{k}(\gamma)\frac{(ix)^{k}}{k!}.$
(4.8)

Here, $Q_{k}(\gamma)=\sum_{j=1}^{2n-1}a_{j}t_{j}^{k}$. By (4.4), we have
$Q_{k}(\gamma)=0,k=0,\cdots,2n-3$. We next estimate $Q_{k}(\gamma)$ for
$k>2n-3$.

Step 4. We estimate $\sum_{j=1}^{2n-1}|a_{j}|$ first. We begin by ordering
$a_{j}$’s such that

$m_{\min}=|a_{j_{1}}|\leq|a_{j_{2}}|\leq\cdots\leq|a_{j_{2n-1}}|.$

Then (4.4) implies that

$a_{j_{1}}\phi_{2n-3}(t_{j_{1}})=\big{(}\phi_{2n-3}(t_{j_{2}}),\cdots,\phi_{2n-3}(t_{j_{2n-1}})\big{)}(-a_{j_{2}},\cdots,-a_{j_{2n-1}})^{\top},$

and hence

$a_{j_{1}}\left(\phi_{2n-3}(t_{j_{2}}),\cdots,\phi_{2n-3}(t_{j_{2n-1}})\right)^{-1}\phi_{2n-3}(t_{j_{1}})=(-a_{j_{2}},\cdots,-a_{j_{2n-1}})^{\top}.$

Together with Lemma 4.1, we have

$a_{j_{1}}\Pi_{2\leq q\leq
2n-2}\frac{t_{j_{1}}-t_{j_{q}}}{t_{j_{2n-1}}-t_{j_{q}}}=-a_{j_{2n-1}}.$

Further,

$\displaystyle\left|{a_{j_{2n-1}}}\right|=$
$\displaystyle\left|{a_{j_{1}}}\right|\Pi_{2\leq q\leq
2n-2}\frac{\left|{t_{j_{1}}-t_{j_{q}}}\right|}{\left|{t_{j_{2n-1}}-t_{j_{q}}}\right|}=\left|{a_{j_{1}}}\right|\Pi_{2\leq
q\leq
2n-2}\frac{\left|{t_{j_{1}}-t_{j_{q}}}\right|}{\left|{t_{j_{2n-1}}-t_{j_{q}}}\right|}\frac{\left|{t_{j_{1}}-t_{j_{2n-1}}}\right|}{\left|{t_{j_{2n-1}}-t_{j_{1}}}\right|}$
(4.9) $\displaystyle=$ $\displaystyle\left|{a_{j_{1}}}\right|\frac{\Pi_{2\leq
q\leq 2n-1}\left|{t_{j_{1}}-t_{j_{q}}}\right|}{\Pi_{1\leq q\leq
2n-2}\left|{t_{j_{2n-1}}-t_{j_{q}}}\right|}\leq\left|{a_{j_{1}}}\right|\frac{\max_{j_{1}=1,\cdots,2n-1}\Pi_{2\leq
q\leq
2n-1}\left|{t_{j_{1}}-t_{j_{q}}}\right|}{\min_{j_{2n-1}=1,\cdots,2n-1}\Pi_{1\leq
q\leq 2n-2}\left|{t_{j_{2n-1}}-t_{j_{q}}}\right|}.$

Thus, based on the distribution of $t_{j}$’s and (4.5), we have

$|a_{j_{2n-1}}|\leq\frac{(2n-2)!}{\left((n-1)!\right)^{2}}|a_{j_{1}}|\leq\frac{(2n-2)!}{\left((n-1)!\right)^{2}}m_{\min},$

and consequently,

$\sum_{j=1}^{2n-1}|a_{j}|=\sum_{q=1}^{2n-1}|a_{j_{q}}|\leq(2n-1)|a_{j_{2n-1}}|\leq\frac{(2n-1)!}{\left((n-1)!\right)^{2}}m_{\min}.$
(4.10)

It follows that for $k\geq 2n-2$,

$\displaystyle|Q_{k}(\gamma)|=$
$\displaystyle|\sum_{j=1}^{2n-1}a_{j}t_{j}^{k}|\leq\sum_{j=1}^{2n-1}|a_{j}|\big{(}(n-1)\tau\big{)}^{k}\leq\frac{(2n-1)!}{\left((n-1)!\right)^{2}}m_{\min}\big{(}(n-1)\tau\big{)}^{k}.$

Step 5. Using (4.8), we have

$\displaystyle\max_{x\in[-\Omega,\Omega]}\left|\mathcal{F}[\gamma](x)\right|\leq$
$\displaystyle\sum_{k\geq
2n-2}\frac{(2n-1)!}{\left((n-1)!\right)^{2}}m_{\min}\big{(}(n-1)\tau\big{)}^{k}\frac{\Omega^{k}}{k!}$
$\displaystyle=$
$\displaystyle\frac{(2n-1)!m_{\min}(n-1)^{2n-2}(\tau\Omega)^{2n-2}}{\left((n-1)!\right)^{2}(2n-2)!}\
\sum_{k=0}^{+\infty}\frac{(\tau\Omega)^{k}(2n-2)!(n-1)^{k}}{(k+2n-2)!}$
$\displaystyle<$
$\displaystyle\frac{(2n-1)m_{\min}(n-1)^{2n-2}(\tau\Omega)^{2n-2}}{\left((n-1)!\right)^{2}}\
\sum_{k=0}^{+\infty}\left(\frac{\tau\Omega}{2}\right)^{k}$ $\displaystyle\leq$
$\displaystyle\frac{(2n-1)m_{\min}(n-1)^{2n-2}(\tau\Omega)^{2n-2}}{\left((n-1)!\right)^{2}}\frac{1}{0.8}\quad\left(\text{by
(\ref{equ:numberlowerboundequ1}), $\frac{\tau\Omega}{2}\leq 0.2$}\right)$
$\displaystyle\leq$
$\displaystyle\frac{(2n-1)m_{\min}}{2\pi(n-1)}(e\tau\Omega)^{2n-2}\frac{1}{0.8}.\quad\Big{(}\text{by
(\ref{stirlingformula0})}\Big{)}$

Finally, using (4.3) and the inequality that
$\frac{(2n-1)}{2\pi(n-1)}\frac{1}{0.8}<1$, we obtain

$\max_{x\in[-\Omega,\Omega]}\left|\mathcal{F}[\gamma](x)\right|<\sigma.$

This completes the proof. ∎

###  4.2 Proof of Theorem 2.4

###### Proof.

Let
$t_{1}=-(n-\frac{1}{2})\tau,t_{2}=-(n-\frac{3}{2})\tau,\cdots,t_{n}=-\frac{\tau}{2},t_{n+1}=\frac{\tau}{2},\cdots,t_{2n}=(n-\frac{1}{2})\tau$.
Consider the following system of linear equations:

$Aa=0,$ (4.11)

where $A=\big{(}\phi_{2n-2}(t_{1}),\cdots,\phi_{2n-2}(t_{2n})\big{)}$ with
$\phi_{2n-2}(\cdot)$ being defined in (4.1). Since $A$ is underdetermined,
there exists a nontrivial solution $a=(a_{1},\cdots,a_{2n})^{\top}$. By the
linear independence of any $(2n-1)$ column vectors of $A$, all $a_{j}$’s are
nonzero. By a scaling of $a$, we can assume that $a_{2n}<0$ and

$\min_{1\leq j\leq n}|a_{2j-1}|=m_{\min}.$ (4.12)

We define

$\mu=\sum_{j=1}^{n}a_{2j-1}\delta_{t_{2j-1}},\quad\hat{\mu}=\sum_{j=1}^{n}-a_{2j}\delta_{t_{2j}}.$

Similar to Step 2 in the proof of Theorem 2.2, we can show that
$a_{2j-1}>0,j=1,\cdots,n,$ and $a_{2j}<0,j=1,\cdots,n$. Thus both $\hat{\mu}$
and $\mu$ are positive measures. Similar to Step 4 in the proof of Theorem
2.2, we can show that

$\sum_{j=1}^{2n}|a_{j}|\leq\frac{(2n)!}{n!(n-1)!}m_{\min}.$ (4.13)

We now prove that

$||\mathcal{F}[\hat{\mu}]-\mathcal{F}[\mu]||_{\infty}\leq\max_{x\in[-\Omega,\Omega]}|\mathcal{F}[\gamma](x)|<\sigma,$

where $\gamma=\sum_{j=1}^{2n}a_{j}\delta_{t_{j}}$. Indeed, (4.13) implies, for
$k\geq 2n-1$,

$\displaystyle|\sum_{j=1}^{2n}a_{j}t_{j}^{k}|\leq\sum_{j=1}^{2n}|a_{j}|((n-1/2)\tau)^{k}\leq\frac{(2n)!}{n!(n-1)!}m_{\min}\left((n-{1}/{2})\tau\right)^{k}.$

On the other hand, similar to expansion (4.8), we can expand
$\mathcal{F}[\gamma]$ and have

$\displaystyle Q_{k}(\gamma)=0,\ k=0,\cdots,2n-2\quad\text{and}\
|Q_{k}(\gamma)|\leq\frac{(2n)!}{n!(n-1)!}m_{\min}\left((n-{1}/{2})\tau\right)^{k},k\geq
2n-1.$

Therefore, for $|x|\leq\Omega$,

$\displaystyle\max_{x\in[-\Omega,\Omega]}\left|\mathcal{F}[\gamma](x)\right|\leq$
$\displaystyle\sum_{k\geq
2n-1}\frac{(2n)!}{n!(n-1)!}m_{\min}\left((n-{1}/{2})\tau\right)^{k}\frac{|x|^{k}}{k!}\leq\sum_{k\geq
2n-1}\frac{(2n)!}{n!(n-1)!}m_{\min}\left((n-{1}/{2})\tau\right)^{k}\frac{\Omega^{k}}{k!}$
$\displaystyle=$
$\displaystyle\frac{(2n)!m_{\min}(n-1/2)^{2n-1}(\tau\Omega)^{2n-1}}{n!(n-1)!(2n-1)!}\
\sum_{k=0}^{+\infty}\frac{(\tau\Omega)^{k}(2n-1)!(n-1/2)^{k}}{(k+2n-1)!}$
$\displaystyle<$
$\displaystyle\frac{2nm_{\min}(n-1/2)^{2n-1}(\tau\Omega)^{2n-1}}{n!(n-1)!}\
\sum_{k=0}^{+\infty}\left(\frac{\tau\Omega}{2}\right)^{k}$ $\displaystyle=$
$\displaystyle\frac{{2n}m_{\min}(n-1/2)^{2n-1}(\tau\Omega)^{2n-1}}{n!(n-1)!}\frac{1}{0.8}\quad\Big{(}\text{(\ref{supportlowerboundequ0})
implies $\frac{\tau\Omega}{2}\leq 0.2$}\Big{)}$ $\displaystyle\leq$
$\displaystyle\frac{nm_{\min}(n-1/2)^{2n-1}}{\pi
n^{n+\frac{1}{2}}(n-1)^{n-\frac{1}{2}}}(e\tau\Omega)^{2n-1}\frac{1}{0.8}\quad\Big{(}\text{by
(\ref{stirlingformula0})}\Big{)}$ $\displaystyle\leq$
$\displaystyle\frac{n}{\pi(n-1/2)}m_{\min}(e\tau\Omega)^{2n-1}\frac{1}{0.8}$
$\displaystyle<$ $\displaystyle\sigma.\quad\Big{(}\text{by
(\ref{supportlowerboundequ0}) and
$\frac{n}{\pi(n-1/2)}\frac{1}{0.8}<1$}\Big{)}$

It follows that $||\mathcal{F}[\hat{\mu}]-\mathcal{F}[\mu]||_{\infty}<\sigma$.
∎

###  4.3 Proof of Proposition 2.1

###### Proof.

Step 1. For $j\in\\{1,2,\cdots,2n\\}$, set
$t_{j}=-\frac{sn-2}{2}\tau+\frac{(j-2)s}{2}\tau$ if $j$ is even and
$t_{j}=t_{4\lceil\frac{j+1}{4}\rceil-2}+(-1)^{\frac{j+1}{2}}\tau$ otherwise.
Consider the following system of linear equations:

$Aa=0,$

where $A=\big{(}\phi_{2n-2}(t_{1}),\cdots,\phi_{2n-2}(t_{2n})\big{)}$ with
$\phi_{2n-2}(\cdot)$ defined in (4.1). Since $A$ is underdetermined, there
exists a nontrivial solution $a=(a_{1},\cdots,a_{2n})^{\top}$. Also, by the
linear independence of any $(2n-1)$ column vectors of A, we can show that all
$a_{j}$’s are nonzero. By a scaling of $a$, we can assume that $a_{2n}>0$ and

$\min_{1\leq j\leq n}|a_{2j}|=m_{\min}.$ (4.14)

We define

$\mu=\sum_{j=1}^{n}a_{2j}\delta_{t_{2j}},\quad\hat{\mu}=\sum_{j=1}^{n}-a_{2j-1}\delta_{t_{2j-1}}.$

Similar to Step 2 in the proof of Theorem 2.2, we can show that
$a_{2j-1}<0,j=1,\cdots,n,$ and $a_{2j}>0,j=1,\cdots,n$. Thus, both $\hat{\mu}$
and $\mu$ are positive measures.

Step 2. We now estimate $\sum_{j=1}^{2n}|a_{j}|$. Reorder $a_{j}$ such that

$m_{\min}=|a_{j_{1}}|\leq|a_{j_{2}}|\leq\cdots\leq|a_{j_{2n}}|.$

Similar to Step 4 in the proof of Theorem 2.2, we have

$a_{j_{1}}\Pi_{2\leq q\leq
2n-1}\frac{t_{j_{1}}-t_{j_{q}}}{t_{j_{2n}}-t_{j_{q}}}=-a_{j_{2n}}.$ (4.15)

We next estimate $\Pi_{2\leq q\leq
2n-1}\left|\frac{t_{j_{1}}-t_{j_{q}}}{t_{j_{2n}}-t_{j_{q}}}\right|$. Note that

$\begin{split}\Pi_{2\leq q\leq
2n-1}\frac{\left|t_{j_{1}}-t_{j_{q}}\right|}{\left|t_{j_{2n}}-t_{j_{q}}\right|}&=\bigg{(}\Pi_{2\leq
q\leq
2n-1}\frac{\left|t_{j_{1}}-t_{j_{q}}\right|}{\left|t_{j_{2n}}-t_{j_{q}}\right|}\bigg{)}\cdot\frac{\left|t_{j_{1}}-t_{j_{2n}}\right|}{\left|t_{j_{2n}}-t_{j_{1}}\right|}=\frac{\Pi_{2\leq
q\leq 2n}\left|t_{j_{1}}-t_{j_{q}}\right|}{\Pi_{1\leq q\leq
2n-1}\left|t_{j_{2n}}-t_{j_{q}}\right|}\\\
&\leq\frac{\max_{j\in\\{1,2,\dots,2n\\}}\Pi_{i\in\\{1,2,\dots,2n\\},i\neq
j}\left|t_{i}-t_{j}\right|}{\min_{j\in\\{1,2,\dots,2n\\}}\Pi_{i\in\\{1,2,\dots,2n\\},i\neq
j}\left|t_{i}-t_{j}\right|}.\end{split}$ (4.16)

We separate $\\{t_{j}\\}_{j=1,2,\dots,2n}$ into four classes:
$C_{1}=\\{t_{4j-2}\\}_{j=1}^{\lceil\frac{n}{2}\rceil},C_{2}=\\{t_{4j}\\}_{j=1}^{\lfloor\frac{n}{2}\rfloor},C_{3}=\\{t_{4j-3}\\}_{j=1}^{\lceil\frac{n}{2}\rceil},C_{4}=\\{t_{4j-1}\\}_{j=1}^{\lfloor\frac{n}{2}\rfloor}$;
See Figure 4.1 for an illustration. The points in each class are evenly-
spaced, by which we can estimate the right-hand side of (4.16).

Figure 4.1: Distribution of source locations.

Note that

$\begin{split}&\max_{j\in\\{1,2,\dots,2n\\}}\Pi_{p\in\\{1,2,\dots,2n\\},p\neq
j}|t_{p}-t_{j}|=\max_{k=1,2,3,4}\bigg{(}\max_{x\in
C_{k}}\Pi_{y\in\\{t_{1},t_{2}\dots,t_{2n}\\},y\neq x}|x-y|\bigg{)}\\\
\leq&\max_{k=1,2,3,4}\bigg{(}\max_{x\in C_{k}}\Pi_{p=1,2,3,4}\Pi_{y\in
C_{p},y\neq x}|x-y|\bigg{)}=:\max_{k=1,2,3,4}c^{\max}_{k},\end{split}$ (4.17)

and

$\begin{split}&\min_{j\in\\{1,2,\dots,2n\\}}\Pi_{p\in\\{1,2,\dots,2n\\},p\neq
j}|t_{p}-t_{j}|=\min_{k=1,2,3,4}\bigg{(}\min_{x\in
C_{k}}\Pi_{y\in\\{t_{1},t_{2}\dots,t_{2n}\\},y\neq x}|x-y|\bigg{)}\\\
\geq&\min_{k=1,2,3,4}\bigg{(}\min_{x\in C_{k}}\Pi_{p=1,2,3,4}\Pi_{y\in
C_{p},y\neq x}|x-y|\bigg{)}=:\min_{k=1,2,3,4}c^{\min}_{k}.\end{split}$ (4.18)

The estimates of $\max_{k=1,2,3,4}c^{\max}_{k}$ and
$\min_{k=1,2,3,4}c^{\min}_{k}$ are detailed in Lemmas A.3 and A.4 in Appendix
A. With the aid of them we control the left-hand side of (4.16) that

$\begin{split}&\quad\Pi_{2\leq q\leq
2n-1}\frac{|t_{j_{1}}-t_{j_{q}}|}{|t_{j_{2n}}-t_{j_{q}}|}\leq\frac{\tau^{2n-1}s^{2n-1}\left(2\lceil\frac{n}{2}\rceil\right)!\left(2\lceil\frac{n}{2}\rceil-1\right)!}{\tau^{2n-1}s^{2n-3}\cdot\bigg{(}(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1)!\bigg{)}^{4}}\leq\frac{s^{2}e^{11}}{\pi^{2}}(n+1)^{10}2^{2n-8},\end{split}$
(4.19)

where the last inequality is obtained by Lemma 4.2 in the following step.
Step 3.

######  Lemma 4.2.

For $n\geq 2$, we have

$\displaystyle\frac{\left(2\lceil\frac{n}{2}\rceil\right)!\left(2\lceil\frac{n}{2}\rceil-1\right)!}{\bigg{(}(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1)!\bigg{)}^{4}}\leq\frac{e^{11}}{\pi^{2}}(n+1)^{10}2^{2n-8}.$

###### Proof.

Recall the Stirling approximation of factorial, that is,

$\sqrt{2\pi}n^{n+\frac{1}{2}}e^{-n}\leq n!\leq en^{n+\frac{1}{2}}e^{-n}.$
(4.20)

For $n\leq 11$, the inequality can be checked by calculation. For $n>11$, we
have

$\displaystyle\frac{\left(2\lceil\frac{n}{2}\rceil\right)!\left(2\lceil\frac{n}{2}\rceil-1\right)!}{\bigg{(}(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1)!\bigg{)}^{4}}\leq\frac{e^{2-4\lceil\frac{n}{2}\rceil+1}(2\lceil\frac{n}{2}\rceil)^{2\lceil\frac{n}{2}\rceil+\frac{1}{2}}\cdot(2\lceil\frac{n}{2}\rceil-1)^{2\lceil\frac{n}{2}\rceil-\frac{1}{2}}}{(\sqrt{2\pi})^{4}(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1)^{4(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1)+2}e^{-4(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1)}}$
$\displaystyle\leq$
$\displaystyle\frac{1}{4\pi^{2}}\frac{e^{3-2n}}{e^{-4(2\cdot\frac{n}{4}-1)}}\cdot\frac{(2(\frac{n}{2}+\frac{1}{2}))^{2n+2}}{(2(\frac{n}{4}-\frac{3}{4})-1)^{4(2(\frac{n}{4}-\frac{3}{4})-1)+2}}=\frac{1}{4e\pi^{2}}\frac{(n+1)^{2n+2}}{(\frac{n}{2}-\frac{5}{2})^{2n-8}}$
$\displaystyle=$
$\displaystyle\frac{1}{4e\pi^{2}}(n+1)^{10}\left(2+\frac{6}{\frac{n}{2}-\frac{5}{2}}\right)^{2n-8}=\frac{1}{4e\pi^{2}}(n+1)^{10}2^{2n-8}\left(1+\frac{6}{n-5}\right)^{12\cdot\frac{n-5}{6}+2}$
$\displaystyle\leq$
$\displaystyle\frac{e^{11}}{4\pi^{2}}\left(1+\frac{6}{n-5}\right)^{2}(n+1)^{10}2^{2n-8}\leq\frac{e^{11}}{\pi^{2}}(n+1)^{10}2^{2n-8}.$

∎

Step 4. Thus, combined (4.15) and (4.19), we have

$\left|{a_{j_{2n}}}\right|\leq\frac{e^{11}s^{2}}{\pi^{2}}(n+1)^{10}2^{2n-8}\left|{a_{j_{1}}}\right|,$

and consequently,

$\sum_{j=1}^{2n}|a_{j}|\leq\sum_{q=1}^{2n}|a_{j_{q}}|\leq
2n\frac{e^{11}s^{2}}{\pi^{2}}(n+1)^{10}2^{2n-8}m_{\min}.$ (4.21)

It then follows that for $k\geq 2n-1$,

$\displaystyle\left|\sum_{j=1}^{2n-1}a_{j}t_{j}^{k}\right|\leq\sum_{j=1}^{2n-1}|a_{j}|\left(\frac{sn}{2}\tau\right)^{k}\leq$
$\displaystyle\frac{2n(n+1)^{10}e^{11}s^{2}}{\pi^{2}}2^{2n-8}m_{\min}\left(\frac{sn}{2}\tau\right)^{k}.$

Step 5. We now prove that

$||\mathcal{F}[\hat{\mu}]-\mathcal{F}[\mu]||_{\infty}\leq\max_{x\in[-\Omega,\Omega]}|\mathcal{F}[\gamma](x)|<\sigma,$

where $\gamma=\sum_{j=1}^{2n}a_{j}\delta_{t_{j}}$. On the other hand, similar
to expansion (4.8), we can expand $\mathcal{F}[\gamma]$ and have

$\displaystyle Q_{k}(\gamma)=0,\ k=0,\cdots,2n-2\quad\text{and}\
|Q_{k}(\gamma)|\leq\frac{2n(n+1)^{10}e^{11}s^{2}2^{2n-8}}{\pi^{2}}m_{\min}\left(\frac{sn}{2}\tau\right)^{k},\quad
k\geq 2n-1.$

Therefore, for $|x|\leq\Omega$ and $n\geq 6$, we have

$\displaystyle|\mathcal{F}[\gamma](x)|\leq$ $\displaystyle\sum_{k\geq
2n-1}\frac{2n(n+1)^{10}e^{11}s^{2}}{\pi^{2}}2^{2n-8}m_{\min}\left(\frac{sn}{2}\tau\right)^{k}\frac{|x|^{k}}{k!}$
$\displaystyle\leq$ $\displaystyle\sum_{k\geq
2n-1}\frac{2n(n+1)^{10}e^{11}s^{2}}{\pi^{2}}2^{2n-8}m_{\min}\left(\frac{sn}{2}\tau\right)^{k}\frac{\Omega^{k}}{k!}$
$\displaystyle\leq$
$\displaystyle\frac{2e^{11}}{\pi^{2}}\cdot\frac{s^{2}n(n+1)^{10}2^{2n-8}m_{\min}\cdot(\frac{sn\tau\Omega}{2})^{2n-1}}{(2n-1)!}\sum_{k=0}^{+\infty}\frac{(\frac{s\tau\Omega}{2})^{k}(2n-1)!n^{k}}{(k+2n-1)!}$
$\displaystyle<$
$\displaystyle\frac{e^{11}}{2^{6}\pi^{2}}\cdot\frac{(\tau\Omega)^{2n-1}s^{2n+1}m_{\min}n(n+1)^{10}n^{2n-1}}{(2n-1)!}\cdot\sum_{k=0}^{+\infty}\left(\frac{s\tau\Omega}{2}\right)^{k}$
$\displaystyle\leq$
$\displaystyle\frac{e^{11}}{2^{6}\pi^{2}}(\tau\Omega)^{2n-1}s^{2n+1}m_{\min}\frac{(n+1)^{10}n^{2n}e^{2n-1}}{\sqrt{2\pi}(2n-1)^{2n-\frac{1}{2}}}\sum_{k=0}^{+\infty}\left(\frac{s\tau\Omega}{2}\right)^{k}\quad\Big{(}\text{by
Stirling's formula (\ref{stirlingformula0})}\Big{)}$ $\displaystyle\leq$
$\displaystyle 38\cdot
0.2^{2n-1}\sigma\cdot\frac{n(n+1)^{10}}{\sqrt{2n-1}}\frac{n^{2n-1}}{(2n-1)^{2n-1}}\sum_{k=0}^{+\infty}\left(\frac{s\tau\Omega}{2}\right)^{k}\quad\Big{(}\text{by
separation condition (\ref{supportlowerboundequ1})}\Big{)}$ $\displaystyle=$
$\displaystyle 38\cdot
0.1^{2n-1}\sigma\cdot\frac{n(n+1)^{10}}{\sqrt{2n-1}}\left(\frac{n}{n-\frac{1}{2}}\right)^{2n-1}\frac{1}{1-0.04}\quad\Big{(}\text{(\ref{supportlowerboundequ1})
implies $\frac{s\tau\Omega}{2}\leq 0.04$}\Big{)}$ $\displaystyle\leq$
$\displaystyle 38e\cdot
0.1^{2n-1}\sigma\cdot\frac{n(n+1)^{10}}{\sqrt{2n-1}}\frac{1}{1-0.04}$
$\displaystyle<$ $\displaystyle\sigma\quad\left(\text{$38e\cdot
0.1^{2n-1}\cdot\frac{n(n+1)^{10}}{\sqrt{2n-1}}\frac{1}{1-0.04}<1$ for $n\geq
6$}\right).$

It then follows that
$||\mathcal{F}[\hat{\mu}]-\mathcal{F}[\mu]||_{\infty}<\sigma$.

Now consider the case when $2\leq n\leq 5$. By (4.19), we have

$\Pi_{2\leq q\leq
2n-1}\frac{|t_{j_{1}}-t_{j_{q}}|}{|t_{j_{2n}}-t_{j_{q}}|}\leq\frac{s^{2}\left(2\lceil\frac{n}{2}\rceil\right)!\left(2\lceil\frac{n}{2}\rceil-1\right)!}{\bigg{(}(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1)!\bigg{)}^{4}},$

and consequently,

$\sum_{j=1}^{2n}|a_{j}|\leq
2n\frac{s^{2}\left(2\lceil\frac{n}{2}\rceil\right)!\left(2\lceil\frac{n}{2}\rceil-1\right)!}{\bigg{(}(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1)!\bigg{)}^{4}}.$

By similar arguments as those for the case when $n\geq 6$, we can show that
for $2\leq n\leq 5$,

$|\mathcal{F}[\gamma](x)|<\sigma.$

∎

##  5 Phase transition in the number detection

In this section, employing the sweeping singular-value-thresholding number
detection algorithm introduced in [26], we verify the phase transition
phenomenon for the number detection in the super-resolution of positive
sources.

###  5.1 Review of the sweeping singular-value-thresholding number detection
algorithm

In [26], the authors proposed a number detection algorithm called sweeping
single-value-thresholding number detection algorithm. It determines the number
of sources by thresholding on the singular value of a Hankel matrix formulated
from the measurement data.

To be more specific, suppose the measurement is taken at $M$ evenly-spaced
points $\omega_{1}=-\Omega,\omega_{2},\cdots,\omega_{M}=\Omega$, that is,

$\mathbf{Y}(\omega_{j})=\mathcal{F}\mu(\omega_{j})+\mathbf{W}(\omega_{j}),\quad
j=1,\cdots,M.$

We choose a partial measurement at the sample points $z_{t}=\omega_{(t-1)r+1}$
for $t=1,\cdots,2s+1$, where $s\geq n$ and $r=(M-1)\mod 2s$. For ease of
exposition, assume $r=\frac{M-1}{2s}$. Then
$z_{t}=\omega_{(t-1)\frac{M-1}{2s}+1}=-\Omega+\frac{t-1}{s}\Omega$ (since
$\omega_{1}=-\Omega$, $\omega_{M}=\Omega$) and the partial measurement is

$\mathbf{Y}(z_{t})=\mathcal{F}\mu(z_{t})+\mathbf{W}(z_{t}),\quad 1\leq t\leq
2s+1.$

Assemble the following Hankel matrix by the measurements that

$\mathbf{H}(s)=\left(\begin{array}[]{cccc}\mathbf{Y}(-\Omega)&\mathbf{Y}(-\Omega+\frac{1}{s}\Omega)&\cdots&\mathbf{Y}(0)\\\
\mathbf{Y}(-\Omega+\frac{1}{s}\Omega)&\mathbf{Y}(-\Omega+\frac{2}{s}\Omega)&\cdots&\mathbf{Y}(\frac{1}{s}\Omega)\\\
\cdots&\cdots&\ddots&\cdots\\\
\mathbf{Y}(0)&\mathbf{Y}(\frac{1}{s}\Omega)&\cdots&\mathbf{Y}(\Omega)\end{array}\right).$
(5.1)

We observe that $\mathbf{H}(s)$ has the decomposition

$\mathbf{H}(s)=DAD^{\top}+\Delta,$

where $A=\text{diag}(e^{-iy_{1}\Omega}a_{1},\cdots,e^{-iy_{n}\Omega}a_{n})$
and
$D=\big{(}\phi_{s}(e^{iy_{1}\frac{\Omega}{s}}),\cdots,\phi_{s}(e^{iy_{n}\frac{\Omega}{s}})\big{)}$
with $\phi_{s}(\omega)$ being defined as $(1,\omega,\cdots,\omega^{s})^{\top}$
and

$\Delta=\left(\begin{array}[]{cccc}\mathbf{W}(-\Omega)&\mathbf{W}(-\Omega+\frac{1}{s}\Omega)&\cdots&\mathbf{W}(0)\\\
\mathbf{W}(-\Omega+\frac{1}{s}\Omega)&\mathbf{W}(-\Omega+\frac{2}{s}\Omega)&\cdots&\mathbf{W}(\frac{1}{s}\Omega)\\\
\vdots&\vdots&\ddots&\vdots\\\
\mathbf{W}(0)&\mathbf{W}(\frac{1}{s}\Omega)&\cdots&\mathbf{W}(\Omega)\end{array}\right).$

We denote the singular value decomposition of $\mathbf{H}(s)$ as

$\mathbf{H}(s)=\hat{U}\hat{\Sigma}\hat{U}^{*},$

where
$\hat{\Sigma}=\text{diag}(\hat{\sigma}_{1},\cdots,\hat{\sigma}_{n},\hat{\sigma}_{n+1},\cdots,\hat{\sigma}_{s+1})$
with the singular values $\hat{\sigma}_{j}$, $1\leq j\leq s+1$, ordered in a
decreasing manner. From [26], we have the following theorem for the threshold
to determine the source number.

######  Theorem 5.1.

Let $s\geq n$ and $\mu=\sum_{j=1}^{n}a_{j}\delta_{y_{j}}$ with $y_{j}\in
I(n,\Omega),1\leq j\leq n$. We have

$\hat{\sigma}_{j}\leq(s+1)\sigma,\quad j=n+1,\cdots,s+1.$ (5.2)

Moreover, if the following separation condition is satisfied

$\min_{p\neq j}|y_{p}-y_{j}|>\frac{\pi
s}{\Omega}\Big{(}\frac{2n(s+1)}{\zeta(n)^{2}}\frac{\sigma}{m_{\min}}\Big{)}^{\frac{1}{2n-2}},$
(5.3)

where $\zeta(n)=\left\\{\begin{array}[]{cc}(\frac{n-1}{2}!)^{2},&\text{$n$ is
odd,}\\\ (\frac{n}{2})!(\frac{k-2}{2})!,&\text{$n$ is
even,}\end{array}\right.$ then

$\hat{\sigma}_{n}>(s+1)\sigma.$ (5.4)

Based on this theorem, the threshold should be $(s+1)\sigma$ and the following
Algorithm 1 was proposed to detect the source number for fixed $s$.

Input: Number $s$, Noise level $\sigma$;

Input: measurement:
$\mathbf{Y}=(\mathbf{Y}(\omega_{1}),\cdots,\mathbf{Y}(\omega_{M}))^{\top}$;

1: $r=(M-1)\mod 2s$,
$\mathbf{Y}_{new}=(\mathbf{Y}(\omega_{1}),\mathbf{Y}(\omega_{r+1}),\cdots,\mathbf{Y}(\omega_{2sr+1}))^{\top}$;

2: Formulate the $(s+1)\times(s+1)$ Hankel matrix $\mathbf{H}(s)$ from
$\mathbf{Y}_{new}$, and compute the singular value of $\mathbf{H}(s)$ as
$\hat{\sigma}_{1},\cdots,\hat{\sigma}_{s+1}$ distributed in a decreasing
manner;

4: Determine $n$ by $\hat{\sigma}_{n}>(s+1)\sigma$ and
$\hat{\sigma}_{j}\leq(s+1)\sigma,j=n+1,\cdots,s+1$;

Return: $n$.

Algorithm 1 Singular-value-thresholding number detection algorithm

In Algorithm 1, the $s\geq n$ should be properly chosen to have a good
resolution. To address this issue, a sweeping strategy was utilized and the
following Algorithm 2 was proposed. It was shown in [26] that the Algorithm 2
achieves the optimal resolution order.

Input: Noise level $\sigma$, measurement:
$\mathbf{Y}=(\mathbf{Y}(\omega_{1}),\cdots,\mathbf{Y}(\omega_{M}))^{\top}$;

Input: $n_{max}=0$

for  _$s=1:\lfloor\frac{M-1}{2}\rfloor$_ do

Input $s,\sigma,\mathbf{Y}$ to Algorithm 1, save the output of Algorithm 1 as
$n_{recover}$;

if  _$n_{recover} >n_{max}$_ then

$n_{max}=n_{recover}$

Return $n_{max}$.

Algorithm 2 Sweeping singular-value-thresholding number detection algorithm

###  5.2 Phase transition

We know from Section 2 that the resolution limit to the number detection
problem in super-resolution of positive sources is bounded from below and
above by $\frac{C_{1}}{\Omega}(\frac{\sigma}{m_{\min}})^{\frac{1}{2n-2}}$ and
$\frac{C_{2}}{\Omega}(\frac{\sigma}{m_{\min}})^{\frac{1}{2n-2}}$, respectively
for some constants $C_{1},C_{2}$. This indeed implies a phase transition
phenomenon in the problem. Specifically, recall that the super-resolution
factor is $SRF=\frac{\pi}{d_{\min}\Omega}$ and the $\frac{m_{\min}}{\sigma}$
can be viewed as the signal-to-noise ratio $SNR$. Taking the logarithm of both
sides of the two bounds, we can conclude that the exact number detection is
guaranteed if

$\log(SNR)>(2n-2)\log(SRF)+(2n-2)\log\frac{C_{1}}{\pi},$

and may fail if

$\log(SNR)<(2n-2)\log(SRF)+(2n-2)\log\frac{C_{2}}{\pi}.$

As a consequence, we expect that in the parameter space of $\log SNR-\log
SRF$, there exist two lines both with slope $2n-2$ such that the number
detection is successful for cases above the first line and unsuccessful for
cases below the second. In the intermediate region between the two lines, the
number detection can be either successful or unsuccessful from case to case.
This is clearly demonstrated in the numerical experiments below.

We fix $\Omega=1$ and consider $n$ point sources randomly spaced in
$\left[-\frac{(n-1)\pi}{2},\frac{(n-1)\pi}{2}\right]$ with positive amplitudes
$a_{j}$’s. The noise level is $\sigma$ and the minimum separation distance
between sources is $d_{\min}$. We perform 10000 random experiments (the
randomness is in the choice of $(d_{\min},\sigma,y_{j},a_{j})$) to detect the
source number based on Algorithm 2. Figure 5.1 shows the results for $n=2,4,$
respectively. In each case, two lines of slope $2n-2$ strictly separate the
blue points (successful detection) and red points (unsuccessful detection) and
in-between is the phase transition region. It clearly elucidates the phase
transition phenomenon of Algorithm 2 and is consistent with our theory.

(a) detection success

(b) detection fail

(c) phase transition region

(d) detection success

(e) detection fail

(f) phase transition region

Figure 5.1: Plots of the successful and the unsuccessful number detection by
Algorithm 2 depending on the relation between $\log(SRF)$ and
$\log(\frac{m_{\min}}{\sigma})$. (a) illustrates that two positive point
source can be exactly detected if $\log(\frac{m_{\min}}{\sigma})$ is above a
line of slope $2$ in the parameter space. Conversely, for the same case, (b)
shows that the number detection fails if $\log(\frac{m_{\min}}{\sigma})$ falls
below another line of slope $2$. (c) highlights the phase transition region
which is bounded by the black slashes in (a) and (b). (d),(e) and (f)
illustrate parallel results for four positive point sources.

##  6 Phase transition in the location recovery

In this section, by the MUSIC algorithm we verify the phase transition
phenomenon for the location recovery in the super-resolution of positive
sources.

###  6.1 Review of the MUSIC algorithm

In this section we review the MUSIC algorithm. From the measurement
$\mathbf{Y}=(\mathbf{Y}(\omega_{1}),\mathbf{Y}(\omega_{2}),\cdots,\mathbf{Y}(\omega_{M}))^{\top}$
and $\hat{M}=\lfloor\frac{M-1}{2}\rfloor$, we assemble the
$(\hat{M}+1)\times(\hat{M}+1)$ Hankel matrix,

$\boldsymbol{\mathbf{H}}=\begin{pmatrix}\mathbf{Y}(\omega_{1})&\mathbf{Y}(\omega_{2})&\cdots&\mathbf{Y}(\omega_{\hat{M}})\\\
\mathbf{Y}(\omega_{2})&\mathbf{Y}(\omega_{3})&\cdots&\mathbf{Y}(\omega_{\hat{M}+1})\\\
\cdots&\cdots&\ddots&\cdots\\\
\mathbf{Y}(\omega_{\hat{M}})&\mathbf{Y}(\omega_{\hat{M}+1})&\cdots&\mathbf{Y}(\omega_{2\hat{M}+1})\end{pmatrix}.$
(6.1)

We perform the following singular value decomposition for
$\boldsymbol{\mathbf{H}}$,

$\boldsymbol{\mathbf{H}}=\hat{U}\hat{\Sigma}\hat{U}^{*}=[\hat{U}_{1}\quad\hat{U}_{2}]\text{diag}(\hat{\sigma}_{1},\hat{\sigma}_{2},\cdots,\hat{\sigma}_{n},\hat{\sigma}_{n+1},\cdots,\hat{\sigma}_{\hat{M}+1})[\hat{U}_{1}\quad\hat{U}_{2}]^{*},$

where
$\hat{U}_{1}=(\hat{U}(1),\cdots,\hat{U}(n)),\hat{U}_{2}=(\hat{U}(n+1),\cdots,\hat{U}(\hat{M}+1))$
with $n$ being the source number. Then we denote the orthogonal projection to
the space $\hat{U}_{2}$ by $\hat{P}_{2}x=\hat{U}_{2}(\hat{U}_{2}^{*}x)$. For a
test vector $\Phi(x)=(1,e^{ihx},\cdots,e^{i\hat{M}hx})^{\top}$ with $h$ being
the spacing parameter, we define the MUSIC imaging functional

$\displaystyle\hat{J}(x)=\frac{||\Phi(x)||_{2}}{||\hat{P}_{2}\Phi(x)||_{2}}=\frac{||\Phi(x)||_{2}}{||\hat{U}_{2}^{*}\Phi(x)||_{2}}.$

The local maximizers of $\hat{J}(x)$ indicate the locations of the point
sources. In practice, we test evenly spaced points in a specified interval and
plot the discrete imaging functional and then determine the source locations
by detecting the peaks. We present the peak selection algorithm as Algorithm 4
and summarize the MUSIC algorithm in Algorithm 3 below.

Input: Measurements:
$\mathbf{Y}=(\mathbf{Y}(\omega_{1}),\cdots,\mathbf{Y}(\omega_{M}))^{\top}$,
sampling distance $h$, source number $n$;

Input: Region of test points $[TS,TE]$ and spacing of test points $TPS$;

1: Let $\hat{M}=\lfloor\frac{M-1}{2}\rfloor$, formulate the
$(\hat{M}+1)\times(\hat{M}+1)$ Hankel matrix $\hat{X}$ from $\mathbf{Y}$;

2: Compute the singular vector of $\hat{X}$ as
$\hat{U}(1),\hat{U}(2),\cdots,\hat{U}(\hat{M}+1)$ and formulate the noise
space $\hat{U}_{2}=(\hat{U}(n+1),\cdots,\hat{U}(\hat{M}+1))$;

3: For test points $x$’s in $[TS,TE]$ evenly spaced by $TPS$, construct the
test vector $\Phi(x)=(1,e^{ihx},\cdots,e^{i\hat{M}hx})^{\top}$;

4: Plot the MUSIC imaging functional
$\hat{J}(x)=\frac{||\Phi(x)||_{2}}{||\hat{U}_{2}^{*}\Phi(x)||_{2}}$;

5: Select the peak locations $\hat{y}_{j}$’s in the $\hat{J}(x)$ by Algorithm
4;

Return $\hat{y}_{j}$’s.

Algorithm 3 MUSIC algorithm

Input: Image $IMG=(f(x_{1}),\cdots,f(x_{N}))$;

Input: Peak compare range $PCR$, differential compare range $DCR$,
differential compare threshold $DCT$;

1: Initialize the Local maximum points $LMP=[\ ]$, peak points $PP=[\ ]$;

2: Differentiate the image $IMG$ to get the
$DIMG=(f^{\prime}(x_{1}),\cdots,f^{\prime}(x_{N}))$;

3: for  _$j=1:N$_ do

if  _$f(x_{j})=\max(f(x_{j-PCR}),f(x_{j-PCR+1}),\cdots,f(x_{j+PCR}))$_ then

$LMP$ appends $x_{j}$;

4: for  _$x_{j}$ in $LMP$_ do

if  _
$\max(|f^{\prime}(x_{j-DCR})|,|f^{\prime}(x_{j-DCR+1})|,\cdots,|f^{\prime}(x_{j+DCR})|)\geq
DCT$ _ then

$PP$ appends $x_{j}$;

Return: $PP$.

Algorithm 4 Peak selection algorithm

###  6.2 Phase transition

The derived bounds for the resolution limit $\mathcal{D}_{supp}^{+}$ of the
location recovery in the super-resolution of positive sources implies a phase
transition in the problem. Taking the logarithm of both sides of the two
bounds, we can draw a conclusion that the location recovery is stable if

$\log(SNR)>(2n-1)\log(SRF)+(2n-1)\log\frac{C_{3}}{\pi},$

and may be unstable if

$\log(SNR)<(2n-1)\log(SRF)+(2n-1)\log\frac{C_{4}}{\pi},$

for certain constants $C_{3},C_{4}$. Similar to the number detection, we
expect that in the parameter space of $\log SNR-\log SRF$, there exist two
lines both with slope $2n-1$ such that the location recovery is stable for
cases above the first line and unstable for cases below the second. This phase
transition phenomenon has been demonstrated numerically using the Matrix
Pencil method, MUSIC and ESPRIT in [5, 22, 20, 21] for resolving general
sparse sources.

In what follows, we shall conduct numerical experiments to demonstrate the
phase transition phenomenon for the MUSIC algorithm in the super-resolution of
positive sources. For simplicity, we fix $\Omega=1$ and consider $n=2$ or $4$
positive point sources separated with minimum separation $d_{\min}$. We
perform $10000$ random experiments (the randomness is in the choice of
$(d_{\min},\sigma,y_{j},a_{j})$ to recover the source locations using
Algorithm 3. The recovery is deemed stable only if $n$ locations
$\hat{y}_{j}$’s are recovered and they are in a
$\frac{d_{\min}}{2}$-neighborhood of the ground truth; see Algorithm 5 for
details in a single experiment. As is shown in Figure 6.1, in each case, two
lines with slope $2n-1$ strictly separate the blue points (stable recoveries)
and red points (unstable recoveries), and in-between is the phase transition
region. This is exactly the predicted phase transition phenomenon by our
theory. It also demonstrates that the MUSIC can resolve the location of
positive point sources with optimal resolution order.

Input: Sources $\mu=\sum_{j=1}^{n}a_{j}\delta_{y_{j}}$, source number $n$;

Input: Measurements: $\mathbf{Y}$

Input source number $n$ and measurement $\boldsymbol{\mathbf{Y}}$ to Algorithm
3 and save the output as $\hat{y}_{1},\cdots,\hat{y}_{k}$, which are ordered
in an increasing manner;

if  _k==n_ then

Compute the reconstruction error for the source location $y_{j}$ that
$e_{j}:=|\hat{y}_{j}-y_{j}|$;

if  _$\max_{j=1,\cdots,n}e_{j} <\frac{\min_{p\neq j}|y_{p}-y_{j}|}{2}$_ then

Return Stable

else

Return Unstable

else

Return Unstable.

Algorithm 5 A single experiment

(a) recovery success

(b) recovery fail

(c) phase transition region

(d) recovery success

(e) recovery fail

(f) phase transition region

Figure 6.1: Plots of the stable and the unstable location recoveries by
Algorithm 3 in view of the relation between $\log(SRF)$ and
$\log(\frac{m_{\min}}{\sigma})$. (a) illustrates that the locations of two
positive point sources can be stably recovered if
$\log(\frac{m_{\min}}{\sigma})$ is above a line of slope $3$ in the parameter
space. Conversely, for the same case, (b) shows that the locations cannot be
stably recovered by MUSIC if $\log(\frac{m_{\min}}{\sigma})$ falls below
another line of slope $3$. (c) highlights the phase transition region which is
bounded by the black slashes in (a) and (b). (d),(e) and (f) illustrate
parallel results for four positive point sources.

##  7 Conclusions and future works

In this paper, we have introduced the resolution limit for respectively the
number detection and the location recovery in the super-resolution of positive
sources. We have quantitatively characterized the two limits by establishing
their sharp upper and lower bounds. We have also verified the phase transition
phenomena that predicted by our theory in the number detection and support
recovery problems.

Our new technique provides a way to analyze the resolving capability of the
super-resolution of positive sources. The applications of the technique
introduced here to other problems will be presented in a near future.

##  Appendix A Auxiliary lemmas

The following results can be easily proved.

######  Lemma A.1.

Let $n\in\mathbb{N}^{+}$ and $\tau>0$ and let
$\mathcal{C}=\\{j=1,2,\dots,n\\}$. Then

(1):

$\lceil\frac{n}{2}\rceil\in\arg\min_{z\in\mathcal{C}}\Pi_{x\in\mathcal{C},x\neq
z}|x-z|,$ (A.1)

and

$\min_{z\in\mathcal{C}}\Pi_{x\in\mathcal{C},x\neq
z}|x-z|=\left(\lceil\frac{n}{2}\rceil-1\right)!\left(\lfloor\frac{n}{2}\rfloor\right)!;$
(A.2)

(2):

$\arg\max_{z\in\mathcal{C}}\Pi_{x\in\mathcal{C},x\neq z}|x-z|=\\{1,n\\},$
(A.3)

and

$\max_{z\in\mathcal{C}}\Pi_{x\in\mathcal{C},x\neq z}|x-z|=(n-1)!.$ (A.4)

######  Lemma A.2.

Let $n\in\mathbb{N}^{+}$ and let $p,q\in\mathbb{R}$ be such that $p>q>0$. For
the following three sets of evenly spaced points
$\mathcal{C}_{1}:=\\{x_{j}=(j-1)p,j=1,\dots,n\\}$,
$\mathcal{C}_{2}:=\\{y_{j}=(j-1)p-q,j=1,\dots,n\\}$, and
$\mathcal{C}_{3}:=\\{y_{j}=(j-1)p-q,j=1,\dots,n+1\\}$, we have
(1):
$\arg\min_{z\in\mathcal{C}_{2}}\Pi_{j=1}^{n}|z-x_{j}|\subset\\{y_{\lfloor\frac{n}{2}\rfloor+1},y_{\lfloor\frac{n}{2}\rfloor+2}\\}$,
and

$\min_{z\in\mathcal{C}_{2}}\Pi_{i=1}^{n}|z-x_{i}|=\Pi_{j=0}^{\lceil\frac{n}{2}\rceil-1}\left(\min(p-q,q)+pj\right)\cdot\Pi_{j=0}^{\lfloor\frac{n}{2}\rfloor-1}\left(\max(p-q,q)+pj\right);$
(A.5)

(2):
$\arg\min_{z\in\mathcal{C}_{3}}\Pi_{j=1}^{n}|z-x_{j}|\subset\\{y_{\lfloor\frac{n}{2}\rfloor+1},y_{\lfloor\frac{n}{2}\rfloor+2}\\}$,
and

$\min_{z\in\mathcal{C}_{3}}\Pi_{j=1}^{n}|z-x_{j}|=\Pi_{j=0}^{\lceil\frac{n}{2}\rceil-1}\left(\min(p-q,q)+pj\right)\cdot\Pi_{j=0}^{\lfloor\frac{n}{2}\rfloor-1}\left(\max(p-q,q)+pj\right);$
(A.6)

(3): $y_{1}\in\arg\max_{z\in\mathcal{C}_{2}}\Pi_{j=1}^{n}|z-x_{j}|$, and

$\max_{z\in\mathcal{C}_{2}}\Pi_{j=1}^{n}|z-x_{j}|=\Pi_{j=0}^{n-1}\left(q+pj\right);$
(A.7)

(4):
$\arg\max_{z\in\mathcal{C}_{3}}\Pi_{j=1}^{n}|z-x_{j}|\subset\\{y_{1},y_{n+1}\\}$,
and

$\max_{z\in\mathcal{C}_{3}}\Pi_{i=j}^{n}|z-x_{j}|=\Pi_{j=0}^{n-1}\left(\max(p-q,q)+pj\right).$
(A.8)

###### Proof.

Cases (3) and (4) are obvious. For cases (1) and (2), we only need to prove
case (2). We verify firstly that for any integer $k$ with
$0<k<\lfloor\frac{n}{2}\rfloor+1$,

$\Pi^{n}_{j=1}|y_{k}-x_{j}|>\Pi^{n}_{j=1}|y_{k+1}-x_{j}|.$ (A.9)

This holds since

$\displaystyle\Pi^{n}_{j=1}|y_{k}-x_{j}|=\Pi^{k-1}_{j=1}|y_{k}-x_{j}|\cdot\Pi^{n-1}_{j=k}|y_{k}-x_{j}|\cdot|y_{k}-x_{n}|$

and

$\displaystyle\Pi^{n}_{j=1}|y_{k+1}-x_{j}|=|y_{k+1}-x_{1}|\cdot\Pi^{k}_{j=2}|y_{k+1}-x_{j}|\cdot\Pi^{n}_{j=k+1}|y_{k+1}-x_{j}|.$

As $\Pi^{k-1}_{j=1}|y_{k}-x_{j}|=\Pi^{k}_{j=2}|y_{k+1}-x_{j}|$,
$\Pi^{n-1}_{j=k}|y_{k}-x_{j}|=\Pi^{n}_{j=k+1}|y_{k+1}-x_{j}|$ and
$|y_{k}-x_{n}|\geq|y_{k+1}-x_{1}|$ due to the geometrical structure of
$\mathcal{C}_{1},\mathcal{C}_{3}$, we have (A.9). A similar argument gives
that for any integer $k$ with $\lfloor\frac{n}{2}\rfloor+2<k<n+2$,

$\Pi^{n}_{j=1}|y_{k}-x_{j}|>\Pi^{n}_{j=1}|y_{k-1}-x_{j}|.$ (A.10)

This proves that
$\arg\min_{z\in\mathcal{C}_{3}}\Pi_{j=1}^{n}|z-x_{j}|\subset\\{y_{\lfloor\frac{n}{2}\rfloor+1},y_{\lfloor\frac{n}{2}\rfloor+2}\\}$
and thus the minimum value can be checked directly. ∎

######  Lemma A.3.

For $c^{\max}_{j}$, $j=1,2,3,4,$ defined in (4.17), we have

$\max_{j=1,2,3,4}c^{\max}_{j}\leq\tau^{2n-1}s^{2n-1}\left(2\lceil\frac{n}{2}\rceil\right)!\left(2\lceil\frac{n}{2}\rceil-1\right)!.$

###### Proof.

We study $c^{\max}_{j},j=1,2,3,4,$ term by term. The definition of
$c^{\max}_{1}$ yields

$\displaystyle c_{1}^{\max}$ $\displaystyle=\max_{x\in
C_{1}}\Pi_{k=1,2,3,4}\Pi_{y\in C_{k},y\neq x}|x-y|$
$\displaystyle\leq\max_{x\in C_{1}}\Pi_{y\in C_{1},y\neq
x}|x-y|\cdot\max_{x\in C_{1}}\Pi_{y\in C_{2}}|x-y|\cdot\max_{x\in
C_{1}}\Pi_{y\in C_{3}}|x-y|\cdot\max_{x\in C_{1}}\Pi_{y\in C_{4}}|x-y|.$

Note that, by Lemmas A.1 and A.2, we have

$\displaystyle\max_{x\in C_{1}}\Pi_{y\in C_{1},y\neq x}|x-y|$
$\displaystyle\leq\tau^{\lceil\frac{n}{2}\rceil-1}\bigg{(}\Pi_{j=1}^{\lceil\frac{n}{2}\rceil-1}(2sj)\bigg{)}\qquad\left(\text{case
(2) in Lemma \ref{lem:produc-min-max-2}}\right)$
$\displaystyle\leq\tau^{\lceil\frac{n}{2}\rceil-1}s^{\lceil\frac{n}{2}\rceil-1}\left(2\lceil\frac{n}{2}\rceil-1\right)!!.$
$\displaystyle\max_{x\in C_{1}}\Pi_{y\in C_{2}}|x-y|$
$\displaystyle\leq\tau^{\lfloor\frac{n}{2}\rfloor}\bigg{(}\Pi^{\lfloor\frac{n}{2}\rfloor-1}_{j=0}(2sj+s)\bigg{)}\qquad\left(\text{cases
(3) or (4) in Lemma \ref{lem:product2}}\right)$
$\displaystyle\leq\tau^{\lfloor\frac{n}{2}\rfloor}s^{\lfloor\frac{n}{2}\rfloor}\left(2\lfloor\frac{n}{2}\rfloor-2\right)!!.$
$\displaystyle\max_{x\in C_{1}}\Pi_{y\in C_{3}}|x-y|$
$\displaystyle\leq\tau^{\lceil\frac{n}{2}\rceil}\left(\Pi_{j=0}^{\lceil\frac{n}{2}\rceil-1}(2sj+1)\right)\qquad\left(\text{case
(3) in Lemma \ref{lem:product2}}\right)$
$\displaystyle\leq\tau^{\lceil\frac{n}{2}\rceil}s^{\lceil\frac{n}{2}-1\rceil}\left(2\lceil\frac{n}{2}\rceil\right)!!.$
$\displaystyle\max_{x\in C_{1}}\Pi_{y\in C_{4}}|x-y|$
$\displaystyle\leq\tau^{\lfloor\frac{n}{2}\rfloor}\left(\Pi_{j=0}^{\lfloor\frac{n}{2}\rfloor-1}(2sj+2s-1)\right)\qquad\left(\text{cases
(3) or (4) in Lemma \ref{lem:product2}}\right)$
$\displaystyle\leq\tau^{\lfloor\frac{n}{2}\rfloor}s^{\lfloor\frac{n}{2}\rfloor}\left(2\lfloor\frac{n}{2}\rfloor-1\right)!!.$

Thus

$\displaystyle c_{1}^{\max}$
$\displaystyle\leq\tau^{2n-1}s^{2n-1}\left(2\lceil\frac{n}{2}\rceil-2\right)!!\left(2\lfloor\frac{n}{2}\rfloor-1\right)!!\left(2\lceil\frac{n}{2}\rceil-1\right)!!\left(2\lfloor\frac{n}{2}\rfloor\right)!!$
$\displaystyle=\tau^{2n-1}s^{2n-2}\left(2\lceil\frac{n}{2}\rceil-1\right)!\left(2\lfloor\frac{n}{2}\rfloor\right)!.$

Regarding $c^{\max}_{2}$, we have

$\displaystyle c_{2}^{\max}$ $\displaystyle=\max_{x\in
C_{2}}\Pi_{k=1,2,3,4}\Pi_{y\in C_{k},y\neq x}|x-y|$
$\displaystyle\leq\max_{x\in C_{2}}\Pi_{y\in C_{1}}|x-y|\cdot\max_{x\in
C_{2}}\Pi_{y\in C_{2},y\neq x}|x-y|\cdot\max_{x\in C_{2}}\Pi_{y\in
C_{3}}|x-y|\cdot\max_{x\in C_{2}}\Pi_{y\in C_{4}}|x-y|.$

Note that, by Lemmas A.1 and A.2, we have

$\displaystyle\max_{x\in C_{2}}\Pi_{y\in C_{1}}|x-y|$
$\displaystyle\leq\tau^{\lceil\frac{n}{2}\rceil}\bigg{(}\Pi_{j=0}^{\lceil\frac{n}{2}\rceil-1}(2sj+s)\bigg{)}\qquad\left(\text{cases
(3) in Lemma \ref{lem:product2}}\right)$
$\displaystyle\leq\tau^{\lceil\frac{n}{2}\rceil}s^{\lceil\frac{n}{2}\rceil}\left(2\lceil\frac{n}{2}\rceil-1\right)!!.$
$\displaystyle\max_{x\in C_{2}}\Pi_{y\in C_{2},y\neq x}|x-y|$
$\displaystyle\leq\tau^{\lfloor\frac{n}{2}\rfloor-1}\bigg{(}\Pi^{\lfloor\frac{n}{2}\rfloor-1}_{j=1}(2sj)\bigg{)}\qquad\left(\text{case
(2) in Lemma \ref{lem:produc-min-max-2}}\right)$
$\displaystyle\leq\tau^{\lfloor\frac{n}{2}\rfloor-1}s^{\lfloor\frac{n}{2}\rfloor-1}\left(2\lfloor\frac{n}{2}\rfloor-2\right)!!.$
$\displaystyle\max_{x\in C_{2}}\Pi_{y\in C_{3}}|x-y|$
$\displaystyle\leq\tau^{\lceil\frac{n}{2}\rceil}\left(\Pi_{j=0}^{\lceil\frac{n}{2}\rceil-1}(2sj+s+1)\right)\qquad\left(\text{case
(3) in Lemma \ref{lem:product2}}\right)$
$\displaystyle\leq\tau^{\lceil\frac{n}{2}\rceil}s^{\lceil\frac{n}{2}\rceil}\left(2\lceil\frac{n}{2}\rceil\right)!!.$
$\displaystyle\max_{x\in C_{2}}\Pi_{y\in C_{4}}|x-y|$
$\displaystyle\leq\tau^{\lfloor\frac{n}{2}\rfloor}\left(\Pi_{j=0}^{\lfloor\frac{n}{2}\rfloor-1}(2sj+s-1)\right)\qquad\left(\text{case
(3) in Lemma \ref{lem:product2}}\right)$
$\displaystyle\leq\tau^{\lfloor\frac{n}{2}\rfloor}s^{\lfloor\frac{n}{2}\rfloor}\left(2\lfloor\frac{n}{2}\rfloor-1\right)!!.$

Thus

$\displaystyle C_{2}^{\max}$
$\displaystyle\leq\tau^{2n-1}s^{2n-1}\left(2\lceil\frac{n}{2}\rceil-1\right)!!\left(2\lfloor\frac{n}{2}\rfloor-2\right)!!\left(2\lceil\frac{n}{2}\rceil\right)!!\left(2\lfloor\frac{n}{2}\rfloor-1\right)!!$
$\displaystyle=\tau^{2n-1}s^{2n-1}\left(2\lceil\frac{n}{2}\rceil\right)!\left(2\lfloor\frac{n}{2}\rfloor-1\right)!.$

As for $c^{\max}_{3}$, we have

$\displaystyle c_{3}^{\max}$ $\displaystyle=\max_{x\in
C_{3}}\Pi_{k=1,2,3,4}\Pi_{y\in C_{k},y\neq x}|x-y|$
$\displaystyle\leq\max_{x\in C_{3}}\Pi_{y\in C_{1}}|x-y|\cdot\max_{x\in
C_{3}}\Pi_{y\in C_{2}}|x-y|\cdot\max_{x\in C_{3},y\neq x}\Pi_{y\in
C_{3}}|x-y|\cdot\max_{x\in C_{3}}\Pi_{y\in C_{4}}|x-y|.$

Note that, by Lemmas A.1 and A.2, we obtain

$\displaystyle\max_{x\in C_{3}}\Pi_{y\in C_{1}}|x-y|$
$\displaystyle\leq\tau^{\lceil\frac{n}{2}\rceil}\bigg{(}\Pi_{j=0}^{\lceil\frac{n}{2}\rceil-1}(2sj+1)\bigg{)},\qquad\left(\text{case
(3) in Lemma \ref{lem:product2}}\right)$
$\displaystyle\leq\tau^{\lceil\frac{n}{2}\rceil}s^{\lceil\frac{n}{2}\rceil-1}\left(2\lceil\frac{n}{2}\rceil-1\right)!!.$
$\displaystyle\max_{x\in C_{3}}\Pi_{y\in C_{2}}|x-y|$
$\displaystyle\leq\tau^{\lfloor\frac{n}{2}\rfloor}\bigg{(}\Pi^{\lfloor\frac{n}{2}\rfloor-1}_{j=0}(2sj+s+1)\bigg{)},\qquad\left(\text{case
(3) or (4) in Lemma \ref{lem:product2}}\right)$ $\displaystyle\max_{x\in
C_{3}}\Pi_{y\in C_{3},y\neq x}|x-y|$
$\displaystyle\leq\tau^{\lceil\frac{n}{2}\rceil-1}\left(\Pi_{j=1}^{\lceil\frac{n}{2}\rceil-1}(2sj)\right),\qquad\left(\text{case
(2) in Lemma \ref{lem:produc-min-max-2}}\right)$
$\displaystyle\leq\tau^{\lceil\frac{n}{2}\rceil-1}s^{\lceil\frac{n}{2}\rceil-1}\left(2\lceil\frac{n}{2}\rceil-2\right)!!.$
$\displaystyle\max_{x\in C_{3}}\Pi_{y\in C_{4}}|x-y|$
$\displaystyle\leq\tau^{\lfloor\frac{n}{2}\rfloor}\left(\Pi_{j=0}^{\lfloor\frac{n}{2}\rfloor-1}(2sj+2s-2)\right).\qquad\left(\text{case
(3) or (4) in Lemma \ref{lem:product2}}\right)$

Thus

$\displaystyle C_{3}^{\max}$
$\displaystyle\leq\tau^{2n-1}s^{2\lceil\frac{n}{2}\rceil-2}\left(2\lceil\frac{n}{2}\rceil-1\right)!\cdot\left(\Pi_{j=0}^{\lfloor\frac{n}{2}\rfloor-1}(2sj+s+1)(2sj+2s-2)\right)$
$\displaystyle\leq\tau^{2n-1}s^{2\lceil\frac{n}{2}\rceil-2}\left(2\lceil\frac{n}{2}\rceil-1\right)!\cdot\left(\Pi_{j=0}^{\lfloor\frac{n}{2}\rfloor-1}(2sj+s)(2sj+2s)\right)$
$\displaystyle=\tau^{2n-1}s^{2n-3}\left(2\lceil\frac{n}{2}\rceil-1\right)!\left(2\lfloor\frac{n}{2}\rfloor\right)!.$

Finally, we study $c^{\max}_{4}$. We have

$\displaystyle\max_{x\in C_{4}}\Pi_{y\in C_{1}}|x-y|$
$\displaystyle\leq\tau^{\lceil\frac{n}{2}\rceil}(\Pi_{j=0}^{\lceil\frac{n}{2}\rceil-1}(2sj+1)),\qquad\left(\text{case
(3) in Lemma \ref{lem:product2}}\right)$
$\displaystyle\leq\tau^{\lceil\frac{n}{2}\rceil}s^{\lceil\frac{n}{2}\rceil-1}\bigg{(}2\lceil\frac{n}{2}\rceil-1\bigg{)}!!$
$\displaystyle\max_{x\in C_{4}}\Pi_{y\in C_{2}}|x-y|$
$\displaystyle\leq\tau^{\lfloor\frac{n}{2}\rfloor}(\Pi^{\lfloor\frac{n}{2}\rfloor-1}_{j=0}(2sj+s-1)),\qquad\left(\text{case
(3) in Lemma \ref{lem:product2}}\right)$
$\displaystyle\leq\tau^{\lfloor\frac{n}{2}\rfloor}s^{\lfloor\frac{n}{2}\rfloor}\bigg{(}2\lfloor\frac{n}{2}\rfloor\bigg{)}!!$
$\displaystyle\max_{x\in C_{4}}\Pi_{y\in C_{3}}|x-y|$
$\displaystyle\leq\tau^{\lceil\frac{n}{2}\rceil}(\Pi_{j=0}^{\lceil\frac{n}{2}\rceil-1}(2sj+2)),\qquad\left(\text{case
(3) in Lemma \ref{lem:product2}}\right)$
$\displaystyle\leq\tau^{\lceil\frac{n}{2}\rceil}s^{\lceil\frac{n}{2}\rceil}\bigg{(}2\lceil\frac{n}{2}\rceil-1\bigg{)}!!.$
$\displaystyle\max_{x\in C_{4}}\Pi_{y\in C_{4},y\neq x}|x-y|$
$\displaystyle\leq\tau^{\lfloor\frac{n}{2}\rfloor-1}(\Pi_{j=1}^{\lfloor\frac{n}{2}\rfloor-1}(2sj)).\qquad\left(\text{case
(2) in Lemma \ref{lem:produc-min-max-2}}\right)$
$\displaystyle\leq\tau^{\lfloor\frac{n}{2}\rfloor-1}s^{\lfloor\frac{n}{2}\rfloor-1}\bigg{(}2\lfloor\frac{n}{2}\rfloor-2\bigg{)}!!.$

Thus

$\displaystyle c_{4}^{\max}$
$\displaystyle\leq\tau^{2n-1}s^{2n-1}\bigg{(}2\lceil\frac{n}{2}\rceil-1\bigg{)}!!\cdot\bigg{(}2\lfloor\frac{n}{2}\rfloor\bigg{)}!!\cdot\bigg{(}2\lceil\frac{n}{2}\rceil-1\bigg{)}!!\cdot\bigg{(}2\lfloor\frac{n}{2}\rfloor-2\bigg{)}!!$
$\displaystyle\leq\tau^{2n-1}s^{2n-1}\bigg{(}2\lceil\frac{n}{2}\rceil\bigg{)}!\bigg{(}2\lceil\frac{n}{2}\rceil-1\bigg{)}!.$

By concluding above discussions, we have

$\max_{j=1,2,3,4}c_{j}^{\max}\leq\tau^{2n-1}s^{2n-1}\left(2\lceil\frac{n}{2}\rceil\right)!\left(2\lceil\frac{n}{2}\rceil-1\right)!.$

∎

######  Lemma A.4.

For $c^{\min}_{j}$, $j=1,2,3,4,$ defined in (4.18), we have

$\min_{j=1,2,3,4}c^{\min}_{j}\geq\tau^{2n-1}s^{2n-3}\cdot\bigg{(}(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1)!\bigg{)}^{4}.$

###### Proof.

We evaluate $c^{\min}_{k},k=1,2,3,4$. For $c^{\min}_{1}$,

$\displaystyle\qquad c^{\min}_{1}$ $\displaystyle=\min_{x\in
C_{1}}\Pi_{k=1,2,3,4}\Pi_{y\in C_{k},y\neq x}|x-y|$
$\displaystyle\geq\min_{x\in C_{1}}\Pi_{y\in C_{1},y\neq
x}|x-y|\cdot\min_{x\in C_{1}}\Pi_{y\in C_{2}}|x-y|\cdot\min_{x\in
C_{1}}\Pi_{y\in C_{3}}|x-y|\cdot\min_{x\in C_{1}}\Pi_{y\in C_{4}}|x-y|.$

By using Lemmas A.1 and A.2, we have

$\displaystyle\min_{x\in C_{1}}\Pi_{y\in C_{1}}|x-y|$
$\displaystyle=\tau^{\lceil\frac{n}{2}\rceil-1}\Pi^{\lceil\frac{\lceil\frac{n}{2}\rceil}{2}\rceil-1}_{j=1}(j\cdot
2s)\cdot\Pi^{\lfloor\frac{\lceil\frac{n}{2}\rceil}{2}\rfloor}_{j=1}(j\cdot
2s),\quad\left(\text{case (1) in Lemma \ref{lem:produc-min-max-2}}\right)$
$\displaystyle=\tau^{\lceil\frac{n}{2}\rceil-1}s^{\lceil\frac{n}{2}\rceil-1}\bigg{(}(2\lceil\frac{\lceil\frac{n}{2}\rceil}{2}\rceil-2)!!\cdot(2\lfloor\frac{\lceil\frac{n}{2}\rceil}{2}\rfloor)!!\bigg{)}$
$\displaystyle\geq\tau^{\lceil\frac{n}{2}\rceil-1}s^{\lceil\frac{n}{2}\rceil-1}\bigg{(}(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-2)!!\cdot(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor)!!\bigg{)}.$
$\displaystyle\min_{x\in C_{1}}\Pi_{y\in C_{2},y\neq x}|x-y|$
$\displaystyle=\tau^{\lfloor\frac{n}{2}\rfloor}\Pi_{j=0}^{\lceil\frac{\lfloor\frac{n}{2}\rfloor}{2}\rceil-1}\left(s+2sj\right)\cdot\Pi_{j=0}^{\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1}\left(s+2sj\right),\quad\left(\text{case
(1) or (2) in Lemma \ref{lem:product2}}\right)$
$\displaystyle=\tau^{\lfloor\frac{n}{2}\rfloor}s^{\lfloor\frac{n}{2}\rfloor}\bigg{(}(2\lceil\frac{\lfloor\frac{n}{2}\rfloor}{2}\rceil-1)!!\cdot(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1)!!\bigg{)}$
$\displaystyle\geq\tau^{\lfloor\frac{n}{2}\rfloor}s^{\lfloor\frac{n}{2}\rfloor}\bigg{(}(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1)!!\cdot(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1)!!\bigg{)}.$

Furthermore,

$\displaystyle\min_{x\in C_{1}}\Pi_{y\in C_{3}}|x-y|$
$\displaystyle=\tau^{\lceil\frac{n}{2}\rceil}\Pi_{j=0}^{\lceil\frac{\lceil\frac{n}{2}\rceil}{2}\rceil-1}\left(1+2sj\right)\cdot\Pi_{k=0}^{\lfloor\frac{\lceil\frac{n}{2}\rceil}{2}\rfloor-1}\left(2s-1+2sk\right)\quad\left(\text{case
(1) in Lemma \ref{lem:product2}}\right)$
$\displaystyle\geq\tau^{\lceil\frac{n}{2}\rceil}\Pi_{j=1}^{\lceil\frac{\lceil\frac{n}{2}\rceil}{2}\rceil-1}\left(2sj\right)\cdot\Pi_{k=0}^{\lfloor\frac{\lceil\frac{n}{2}\rceil}{2}\rfloor-1}\left(s+2sk\right)$
$\displaystyle=\tau^{\lceil\frac{n}{2}\rceil}s^{\lceil\frac{n}{2}\rceil-1}\bigg{(}(2\lceil\frac{\lceil\frac{n}{2}\rceil}{2}\rceil-2)!!\cdot(2\lfloor\frac{\lceil\frac{n}{2}\rceil}{2}\rfloor-1)!!\bigg{)}$
$\displaystyle\geq\tau^{\lceil\frac{n}{2}\rceil}s^{\lceil\frac{n}{2}\rceil-1}\bigg{(}(2\lfloor\frac{\lceil\frac{n}{2}\rceil}{2}\rfloor-2)!!\cdot(2\lfloor\frac{\lceil\frac{n}{2}\rceil}{2}\rfloor-1)!!\bigg{)}$
$\displaystyle\geq\tau^{\lfloor\frac{n}{2}\rfloor}s^{\lfloor\frac{n}{2}\rfloor-1}\cdot\left(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1\right)!.$
$\displaystyle\min_{x\in C_{1}}\Pi_{y\in C_{4}}|x-y|$
$\displaystyle=\tau^{\lfloor\frac{n}{2}\rfloor}\Pi_{j=0}^{\lceil\frac{\lfloor\frac{n}{2}\rfloor}{2}\rceil-1}\left(1+2sj\right)\cdot\Pi_{k=0}^{\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1}\left(2s-1+2sk\right)\quad\left(\text{case
(1) or (2) in Lemma \ref{lem:product2}}\right)$
$\displaystyle\geq\tau^{\lfloor\frac{n}{2}\rfloor}\Pi_{j=1}^{\lceil\frac{\lfloor\frac{n}{2}\rfloor}{2}\rceil-1}\left(2sj\right)\cdot\Pi_{k=0}^{\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1}\left(s+2sk\right)$
$\displaystyle=\tau^{\lfloor\frac{n}{2}\rfloor}s^{\lfloor\frac{n}{2}\rfloor-1}\bigg{(}(2\lceil\frac{\lfloor\frac{n}{2}\rfloor}{2}\rceil-2)!!\cdot(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1)!!\bigg{)}$
$\displaystyle\geq\tau^{\lfloor\frac{n}{2}\rfloor}s^{\lfloor\frac{n}{2}\rfloor-1}\left(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1\right)!.$

By combining estimates in the above four cases, it follows that

$c_{1}^{\min}\geq\tau^{2n-1}s^{2n-3}\left(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor\right)!\left(\left(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1\right)!\right)^{3}.$

Regarding $c^{\min}_{2}$, we have

$\displaystyle\qquad c^{\min}_{2}$ $\displaystyle=\min_{x\in
C_{2}}\Pi_{k=1,2,3,4}\Pi_{y\in C_{k},y\neq x}|x-y|$
$\displaystyle\geq\min_{x\in C_{2}}\Pi_{y\in C_{1}}|x-y|\cdot\min_{x\in
C_{2}}\Pi_{y\in C_{2},y\neq x}|x-y|\cdot\min_{x\in C_{2}}\Pi_{y\in
C_{3}}|x-y|\cdot\min_{x\in C_{2}}\Pi_{y\in C_{4}}|x-y|.$

Note that by Lemmas A.1 and A.2 we have

$\displaystyle\min_{x\in C_{2}}\Pi_{y\in C_{1}}|x-y|$
$\displaystyle=\tau^{\lceil\frac{n}{2}\rceil}\Pi_{j=0}^{\lceil\frac{\lceil\frac{n}{2}\rceil}{2}\rceil-1}\left(s+2sj\right)\cdot\Pi_{j=0}^{\lfloor\frac{\lceil\frac{n}{2}\rceil}{2}\rfloor-1}\left(s+2sj\right)\qquad\left(\text{case
(1) or (2) in Lemma \ref{lem:product2}}\right)$
$\displaystyle=\tau^{\lceil\frac{n}{2}\rceil}s^{\lceil\frac{n}{2}\rceil}\bigg{(}(2\lceil\frac{\lceil\frac{n}{2}\rceil}{2}\rceil-1)!!\cdot(2\lfloor\frac{\lceil\frac{n}{2}\rceil}{2}\rfloor-1)!!\bigg{)}$
$\displaystyle\geq\tau^{\lceil\frac{n}{2}\rceil}s^{\lceil\frac{n}{2}\rceil}\bigg{(}(2\lceil\frac{\lfloor\frac{n}{2}\rfloor}{2}\rceil-1)!!\cdot(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1)!!\bigg{)}.$
$\displaystyle\min_{x\in C_{2}}\Pi_{y\in C_{2},y\neq x}|x-y|$
$\displaystyle=\tau^{\lfloor\frac{n}{2}\rfloor-1}\Pi^{\lceil\frac{\lfloor\frac{n}{2}\rfloor}{2}\rceil-1}_{j=1}(j\cdot
2s)\cdot\Pi^{\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor}_{j=1}(j\cdot
2s)\qquad\left(\text{case (1) in Lemma \ref{lem:produc-min-max-2}}\right)$
$\displaystyle=\tau^{\lfloor\frac{n}{2}\rfloor-1}s^{\lfloor\frac{n}{2}\rfloor-1}\bigg{(}(2\lceil\frac{\lfloor\frac{n}{2}\rfloor}{2}\rceil-2)!!\cdot(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor)!!\bigg{)}$
$\displaystyle\geq\tau^{\lfloor\frac{n}{2}\rfloor-1}s^{\lfloor\frac{n}{2}\rfloor-1}\bigg{(}(2\lceil\frac{\lfloor\frac{n}{2}\rfloor}{2}\rceil-2)!!\cdot(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor)!!\bigg{)}.$
$\displaystyle\min_{x\in C_{2}}\Pi_{y\in C_{3}}|x-y|$
$\displaystyle=\tau^{\lceil\frac{n}{2}\rceil}\Pi_{j=0}^{\lceil\frac{\lceil\frac{n}{2}\rceil}{2}\rceil-1}\left(s-1+2sj\right)\cdot\Pi_{k=0}^{\lfloor\frac{\lceil\frac{n}{2}\rceil}{2}\rfloor-1}\left(s+1+2sk\right)\qquad\left(\text{case
(1) or (2) in Lemma \ref{lem:product2}}\right)$
$\displaystyle\geq\tau^{\lceil\frac{n}{2}\rceil}\Pi_{j=1}^{\lceil\frac{\lceil\frac{n}{2}\rceil}{2}\rceil-1}\left(2sj\right)\cdot\Pi_{k=0}^{\lfloor\frac{\lceil\frac{n}{2}\rceil}{2}\rfloor-1}\left(s+2sk\right)$
$\displaystyle=\tau^{\lceil\frac{n}{2}\rceil}s^{\lceil\frac{n}{2}\rceil-1}\bigg{(}(2\lceil\frac{\lceil\frac{n}{2}\rceil}{2}\rceil-2)!!\cdot(2\lfloor\frac{\lceil\frac{n}{2}\rceil}{2}\rfloor-1)!!\bigg{)}$
$\displaystyle\geq\tau^{\lceil\frac{n}{2}\rceil}s^{\lceil\frac{n}{2}\rceil-1}\bigg{(}(2\lfloor\frac{\lceil\frac{n}{2}\rceil}{2}\rfloor-2)!!\cdot(2\lfloor\frac{\lceil\frac{n}{2}\rceil}{2}\rfloor-1)!!\bigg{)}$
$\displaystyle=\tau^{\lceil\frac{n}{2}\rceil}s^{\lceil\frac{n}{2}\rceil-1}(2\lfloor\frac{\lceil\frac{n}{2}\rceil}{2}\rfloor-1)!.$
$\displaystyle\min_{x\in C_{2}}\Pi_{y\in C_{4}}|x-y|$
$\displaystyle=\tau^{\lfloor\frac{n}{2}\rfloor}\Pi_{j=0}^{\lceil\frac{\lfloor\frac{n}{2}\rfloor}{2}\rceil-1}\left(s-1+2sj\right)\cdot\Pi_{k=0}^{\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1}\left(s+1+2sk\right)\qquad\left(\text{case
(1) in Lemma \ref{lem:product2}}\right)$
$\displaystyle\geq\tau^{\lfloor\frac{n}{2}\rfloor}\Pi_{j=1}^{\lceil\frac{\lfloor\frac{n}{2}\rfloor}{2}\rceil-1}\left(2sj\right)\cdot\Pi_{k=0}^{\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1}\left(s+2sk\right)$
$\displaystyle=\tau^{\lfloor\frac{n}{2}\rfloor}s^{\lfloor\frac{n}{2}\rfloor-1}\bigg{(}(2\lceil\frac{\lfloor\frac{n}{2}\rfloor}{2}\rceil-2)!!\cdot(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1)!!\bigg{)}$
$\displaystyle\geq\tau^{\lfloor\frac{n}{2}\rfloor}s^{\lfloor\frac{n}{2}\rfloor-1}\bigg{(}(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-2)!!\cdot(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1)!!\bigg{)}$
$\displaystyle=\tau^{\lfloor\frac{n}{2}\rfloor}s^{\lfloor\frac{n}{2}\rfloor-1}(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1)!.$

Thus,

$\displaystyle
c^{\min}_{2}\geq\tau^{2n-1}s^{2n-3}\cdot\bigg{(}(2\lceil\frac{\lfloor\frac{n}{2}\rfloor}{2}\rceil-1)!!\cdot(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1)!!\bigg{)}\cdot\bigg{(}(2\lceil\frac{\lfloor\frac{n}{2}\rfloor}{2}\rceil-2)!!\cdot(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor)!!\bigg{)}\cdot(2\lfloor\frac{\lceil\frac{n}{2}\rceil}{2}\rfloor-1)!\cdot(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1)!$
$\displaystyle=\tau^{2n-1}s^{2n-3}\cdot(2\lceil\frac{\lfloor\frac{n}{2}\rfloor}{2}\rceil-1)!\cdot(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor)!\cdot(2\lfloor\frac{\lceil\frac{n}{2}\rceil}{2}\rfloor-1)!\cdot(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1)!$
$\displaystyle\geq\tau^{2n-1}s^{2n-3}\cdot(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor)!\cdot\bigg{(}(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1)!\bigg{)}^{3}.$

We then turn to estimate $c_{3}^{\min}$. We have that

$\displaystyle\qquad c^{\min}_{3}$ $\displaystyle=\min_{x\in
C_{3}}\Pi_{k=1,2,3,4}\Pi_{y\in C_{k},y\neq x}|x-y|$
$\displaystyle\geq\min_{x\in C_{3}}\Pi_{y\in C_{1}}|x-y|\cdot\min_{x\in
C_{3}}\Pi_{y\in C_{2}}|x-y|\cdot\min_{x\in C_{3}}\Pi_{y\in C_{3},y\neq
x}|x-y|\cdot\min_{x\in C_{3}}\Pi_{y\in C_{4}}|x-y|.$

By Lemmas A.1 and A.2, it follows that we

$\displaystyle\min_{x\in C_{3}}\Pi_{y\in C_{1}}|x-y|$
$\displaystyle=\tau^{\lceil\frac{n}{2}\rceil}\Pi_{j=0}^{\lceil\frac{\lceil\frac{n}{2}\rceil}{2}\rceil-1}\left(1+2sj\right)\cdot\Pi_{j=0}^{\lfloor\frac{\lceil\frac{n}{2}\rceil}{2}\rfloor-1}\left(2s-1+2sj\right)\qquad\left(\text{case
(1) or (2) in Lemma \ref{lem:produc-min-max-2}}\right)$
$\displaystyle\geq\tau^{\lceil\frac{n}{2}\rceil}\Pi_{j=1}^{\lceil\frac{\lceil\frac{n}{2}\rceil}{2}\rceil-1}\left(2sj\right)\cdot\Pi_{j=0}^{\lfloor\frac{\lceil\frac{n}{2}\rceil}{2}\rfloor-1}\left(s+2sj\right)$
$\displaystyle=\tau^{\lceil\frac{n}{2}\rceil}s^{\lceil\frac{n}{2}\rceil-1}\bigg{(}(2\lceil\frac{\lceil\frac{n}{2}\rceil}{2}\rceil-2)!!\cdot(2\lfloor\frac{\lceil\frac{n}{2}\rceil}{2}\rfloor-1)!!\bigg{)}$
$\displaystyle\geq\tau^{\lceil\frac{n}{2}\rceil}s^{\lceil\frac{n}{2}\rceil-1}\bigg{(}(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-2)!!\cdot(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1)!!\bigg{)}$
$\displaystyle=\tau^{\lceil\frac{n}{2}\rceil}s^{\lceil\frac{n}{2}\rceil-1}(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1)!.$
$\displaystyle\min_{x\in C_{3}}\Pi_{y\in C_{2}}|x-y|$
$\displaystyle=\tau^{\lfloor\frac{n}{2}\rfloor}\Pi_{j=0}^{\lceil\frac{\lfloor\frac{n}{2}\rfloor}{2}\rceil-1}\left(s-1+2sj\right)\cdot\Pi_{k=0}^{\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1}\left(s+1+2sk\right)\qquad\left(\text{case
(1) in Lemma \ref{lem:produc-min-max-2}}\right)$
$\displaystyle=\tau^{\lfloor\frac{n}{2}\rfloor}\bigg{(}s^{\lfloor\frac{n}{2}\rfloor}\Pi_{j=0}^{\lceil\frac{\lfloor\frac{n}{2}\rfloor}{2}\rceil-1}\left(\frac{s-1}{s}+2j\right)\cdot\Pi_{j=0}^{\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1}\left(\frac{s+1}{s}+2j\right)\bigg{)}$
$\displaystyle\geq\tau^{\lfloor\frac{n}{2}\rfloor}\bigg{(}s^{\lfloor\frac{n}{2}\rfloor}\cdot\frac{1}{2}\cdot\Pi_{j=1}^{\lceil\frac{\lfloor\frac{n}{2}\rfloor}{2}\rceil-1}\left(2j\right)\cdot\Pi_{j=0}^{\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1}\left(1+2j\right)\bigg{)}$
$\displaystyle=\frac{1}{2}\tau^{\lfloor\frac{n}{2}\rfloor}s^{\lfloor\frac{n}{2}\rfloor}\bigg{(}\Pi_{j=1}^{\lceil\frac{\lfloor\frac{n}{2}\rfloor}{2}\rceil-1}\left(2j\right)\cdot\Pi_{j=0}^{\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1}\left(1+2j\right)\bigg{)}$
$\displaystyle=\frac{1}{2}\tau^{\lfloor\frac{n}{2}\rfloor}s^{\lfloor\frac{n}{2}\rfloor}\bigg{(}(2\lceil\frac{\lfloor\frac{n}{2}\rfloor}{2}\rceil-2)!!\cdot(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1)!!\bigg{)}$
$\displaystyle\geq\frac{1}{2}\tau^{\lfloor\frac{n}{2}\rfloor}s^{\lfloor\frac{n}{2}\rfloor}\bigg{(}(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-2)!!\cdot(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1)!!\bigg{)}$
$\displaystyle\geq\frac{1}{2}\tau^{\lfloor\frac{n}{2}\rfloor}s^{\lfloor\frac{n}{2}\rfloor}(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1)!.$
$\displaystyle\min_{x\in C_{3}}\Pi_{y\in C_{3},y\neq x}|x-y|$
$\displaystyle=\tau^{\lceil\frac{n}{2}\rceil-1}\Pi^{\lceil\frac{\lceil\frac{n}{2}\rceil}{2}\rceil-1}_{j=1}(j\cdot
2s)\cdot\Pi^{\lfloor\frac{\lceil\frac{n}{2}\rceil}{2}\rfloor}_{j=1}(j\cdot
2s)\qquad\left(\text{case (1) in Lemma \ref{lem:product2}}\right)$
$\displaystyle=\tau^{\lceil\frac{n}{2}\rceil-1}s^{\lceil\frac{n}{2}\rceil-1}\bigg{(}(2\lceil\frac{\lceil\frac{n}{2}\rceil}{2}\rceil-2)!!\cdot(2\lfloor\frac{\lceil\frac{n}{2}\rceil}{2}\rfloor)!!\bigg{)}$
$\displaystyle\geq\tau^{\lceil\frac{n}{2}\rceil-1}s^{\lceil\frac{n}{2}\rceil-1}\bigg{(}(2\lfloor\frac{\lceil\frac{n}{2}\rceil}{2}\rfloor-2)!!\cdot(2\lfloor\frac{\lceil\frac{n}{2}\rceil}{2}\rfloor-1)!!\bigg{)}$
$\displaystyle=\tau^{\lceil\frac{n}{2}\rceil-1}s^{\lceil\frac{n}{2}\rceil-1}(2\lfloor\frac{\lceil\frac{n}{2}\rceil}{2}\rfloor-1)!.$
$\displaystyle\min_{x\in C_{3}}\Pi_{y\in C_{4}}|x-y|$
$\displaystyle=\tau^{\lfloor\frac{n}{2}\rfloor}\Pi_{j=0}^{\lceil\frac{\lfloor\frac{n}{2}\rfloor}{2}\rceil-1}\left(2+2sj\right)\cdot\Pi_{k=0}^{\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1}\left(2s-2+2sk\right)\qquad\left(\text{case
(1) or (2) in Lemma \ref{lem:product2}}\right)$ $\displaystyle\geq
2\tau^{\lfloor\frac{n}{2}\rfloor}\Pi_{j=1}^{\lceil\frac{\lfloor\frac{n}{2}\rfloor}{2}\rceil-1}\left(2sj\right)\cdot\Pi_{k=0}^{\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1}\left(s+2sk\right)$
$\displaystyle=2\tau^{\lfloor\frac{n}{2}\rfloor}s^{\lfloor\frac{n}{2}\rfloor-1}\bigg{(}(2\lceil\frac{\lfloor\frac{n}{2}\rfloor}{2}\rceil-2)!!\cdot(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1)!!\bigg{)}$
$\displaystyle\geq
2\tau^{\lfloor\frac{n}{2}\rfloor}s^{\lfloor\frac{n}{2}\rfloor-1}\bigg{(}(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-2)!!\cdot(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1)!!\bigg{)}$
$\displaystyle=2\tau^{\lfloor\frac{n}{2}\rfloor}s^{\lfloor\frac{n}{2}\rfloor-1}(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1)!.$

Thus,

$\displaystyle c^{\min}_{3}$
$\displaystyle\geq\cdot\tau^{2n-1}s^{2n-3}\cdot(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1)!\cdot(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1)!\cdot(2\lfloor\frac{\lceil\frac{n}{2}\rceil}{2}\rfloor-1)!\cdot(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1)!$
$\displaystyle\geq\tau^{2n-1}s^{2n-3}\cdot\bigg{(}(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1)!\bigg{)}^{4}$

Finally, regarding $c^{\min}_{4}$, we write

$\displaystyle\qquad c^{\min}_{4}$ $\displaystyle=\min_{x\in
C_{4}}\Pi_{k=1,2,3,4}\Pi_{y\in C_{k},y\neq x}|x-y|$
$\displaystyle\geq\min_{x\in C_{4}}\Pi_{y\in C_{1}}|x-y|\cdot\min_{x\in
C_{4}}\Pi_{y\in C_{2}}|x-y|\cdot\min_{x\in C_{4}}\Pi_{y\in
C_{3}}|x-y|\cdot\min_{x\in C_{4}}\Pi_{y\in C_{4},y\neq x}|x-y|.$

Note that, by Lemmas A.1 and A.2, we obtain

$\displaystyle\min_{x\in C_{4}}\Pi_{y\in C_{1}}|x-y|$
$\displaystyle=\tau^{\lceil\frac{n}{2}\rceil}\Pi_{j=0}^{\lceil\frac{\lceil\frac{n}{2}\rceil}{2}\rceil-1}\left(1+2sj\right)\cdot\Pi_{j=0}^{\lfloor\frac{\lceil\frac{n}{2}\rceil}{2}\rfloor-1}\left(2s-1+2sj\right)\qquad\left(\text{case
(1) in Lemma \ref{lem:produc-min-max-2}}\right)$
$\displaystyle\geq\tau^{\lceil\frac{n}{2}\rceil}\Pi_{j=1}^{\lceil\frac{\lceil\frac{n}{2}\rceil}{2}\rceil-1}\left(2sj\right)\cdot\Pi_{j=0}^{\lfloor\frac{\lceil\frac{n}{2}\rceil}{2}\rfloor-1}\left(s+2sj\right)$
$\displaystyle=\tau^{\lceil\frac{n}{2}\rceil}s^{\lceil\frac{n}{2}\rceil-1}\bigg{(}(2\lceil\frac{\lceil\frac{n}{2}\rceil}{2}\rceil-2)!!\cdot(2\lfloor\frac{\lceil\frac{n}{2}\rceil}{2}\rfloor-1)!!\bigg{)}$
$\displaystyle\geq\tau^{\lceil\frac{n}{2}\rceil}s^{\lceil\frac{n}{2}\rceil-1}\bigg{(}(2\lfloor\frac{\lceil\frac{n}{2}\rceil}{2}\rfloor-2)!!\cdot(2\lfloor\frac{\lceil\frac{n}{2}\rceil}{2}\rfloor-1)!!\bigg{)}$
$\displaystyle=\tau^{\lceil\frac{n}{2}\rceil}s^{\lceil\frac{n}{2}\rceil-1}(2\lfloor\frac{\lceil\frac{n}{2}\rceil}{2}\rfloor-1)!.$
$\displaystyle\min_{x\in C_{4}}\Pi_{y\in C_{2}}|x-y|$
$\displaystyle=\tau^{\lfloor\frac{n}{2}\rfloor}\Pi_{j=0}^{\lceil\frac{\lfloor\frac{n}{2}\rfloor}{2}\rceil-1}\left(s-1+2sj\right)\cdot\Pi_{k=0}^{\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1}\left(s+1+2sk\right)\qquad\left(\text{case
(1) in Lemma \ref{lem:produc-min-max-2}}\right)$
$\displaystyle=\tau^{\lfloor\frac{n}{2}\rfloor}\bigg{(}s^{\lfloor\frac{n}{2}\rfloor}\Pi_{j=0}^{\lceil\frac{\lfloor\frac{n}{2}\rfloor}{2}\rceil-1}\left(\frac{s-1}{s}+2j\right)\cdot\Pi_{j=0}^{\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1}\left(\frac{s+1}{s}+2j\right)\bigg{)}$
$\displaystyle\geq\tau^{\lfloor\frac{n}{2}\rfloor}\bigg{(}s^{\lfloor\frac{n}{2}\rfloor}\cdot\frac{1}{2}\cdot\Pi_{j=1}^{\lceil\frac{\lfloor\frac{n}{2}\rfloor}{2}\rceil-1}\left(2j\right)\cdot\Pi_{j=0}^{\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1}\left(1+2j\right)\bigg{)}$
$\displaystyle=\frac{1}{2}\tau^{\lfloor\frac{n}{2}\rfloor}s^{\lfloor\frac{n}{2}\rfloor}\bigg{(}(2\lceil\frac{\lfloor\frac{n}{2}\rfloor}{2}\rceil-2)!!\cdot(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1)!!\bigg{)}$
$\displaystyle\geq\frac{1}{2}\tau^{\lfloor\frac{n}{2}\rfloor}s^{\lfloor\frac{n}{2}\rfloor}\bigg{(}(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-2)!!\cdot(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1)!!\bigg{)}$
$\displaystyle=\frac{1}{2}\tau^{\lfloor\frac{n}{2}\rfloor}s^{\lfloor\frac{n}{2}\rfloor}(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1)!.$
$\displaystyle\min_{x\in C_{4}}\Pi_{y\in C_{3}}|x-y|$
$\displaystyle=\tau^{\lceil\frac{n}{2}\rceil}\Pi_{j=0}^{\lceil\frac{\lceil\frac{n}{2}\rceil}{2}\rceil-1}\left(2+2sj\right)\cdot\Pi_{k=0}^{\lfloor\frac{\lceil\frac{n}{2}\rceil}{2}\rfloor-1}\left(2s-2+2sk\right)\qquad\left(\text{case
(1) in Lemma \ref{lem:produc-min-max-2}}\right)$ $\displaystyle\geq
2\tau^{\lceil\frac{n}{2}\rceil}\Pi_{j=1}^{\lceil\frac{\lceil\frac{n}{2}\rceil}{2}\rceil-1}\left(2sj\right)\cdot\Pi_{k=0}^{\lfloor\frac{\lceil\frac{n}{2}\rceil}{2}\rfloor-1}\left(s+2sk\right)$
$\displaystyle=2\tau^{\lceil\frac{n}{2}\rceil}s^{\lceil\frac{n}{2}\rceil-1}\bigg{(}(2\lceil\frac{\lceil\frac{n}{2}\rceil}{2}\rceil-2)!!\cdot(2\lfloor\frac{\lceil\frac{n}{2}\rceil}{2}\rfloor-1)!!\bigg{)}$
$\displaystyle\geq
2\tau^{\lceil\frac{n}{2}\rceil}s^{\lceil\frac{n}{2}\rceil-1}\bigg{(}(2\lfloor\frac{\lceil\frac{n}{2}\rceil}{2}\rfloor-2)!!\cdot(2\lfloor\frac{\lceil\frac{n}{2}\rceil}{2}\rfloor-1)!!\bigg{)}$
$\displaystyle=2\tau^{\lceil\frac{n}{2}\rceil}s^{\lceil\frac{n}{2}\rceil-1}(2\lfloor\frac{\lceil\frac{n}{2}\rceil}{2}\rfloor-1)!.$
$\displaystyle\min_{x\in C_{4}}\Pi_{y\in C_{4},y\neq x}|x-y|$
$\displaystyle=\tau^{\lfloor\frac{n}{2}\rfloor-1}\Pi^{\lceil\frac{\lfloor\frac{n}{2}\rfloor}{2}\rceil-1}_{j=1}(j\cdot
2s)\cdot\Pi^{\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor}_{j=1}(j\cdot
2s)\qquad\left(\text{case (1) in Lemma \ref{lem:product2}}\right)$
$\displaystyle=\tau^{\lfloor\frac{n}{2}\rfloor-1}s^{\lfloor\frac{n}{2}\rfloor-1}\bigg{(}(2\lceil\frac{\lfloor\frac{n}{2}\rfloor}{2}\rceil-2)!!\cdot(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor)!!\bigg{)}$
$\displaystyle\geq\tau^{\lfloor\frac{n}{2}\rfloor-1}s^{\lfloor\frac{n}{2}\rfloor-1}\bigg{(}(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-2)!!\cdot(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1)!!\bigg{)}$
$\displaystyle=\tau^{\lfloor\frac{n}{2}\rfloor-1}s^{\lfloor\frac{n}{2}\rfloor-1}(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1)!.$

Thus,

$\displaystyle c^{\min}_{4}$
$\displaystyle\geq\tau^{2n-1}s^{2n-3}\cdot(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1)!\cdot(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1)!\cdot(2\lfloor\frac{\lceil\frac{n}{2}\rceil}{2}\rfloor-1)!\cdot(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1)!$
$\displaystyle\geq\tau^{2n-1}s^{2n-3}\cdot\bigg{(}(2\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor-1)!\bigg{)}^{4}.$

Summarizing all claims above finishes the proof. ∎

## References

  * [1] Ernst Abbe.  Beiträge zur theorie des mikroskops und der mikroskopischen wahrnehmung.  Archiv für mikroskopische Anatomie, 9(1):413–468, 1873.
  * [2] Andrey Akinshin, Dmitry kov, and Yosef Yomdin.  Accuracy of spike-train fourier reconstruction for colliding nodes.  In 2015 International Conference on Sampling Theory and Applications (SampTA), pages 617–621. IEEE, 2015.
  * [3] Jean-Marc Azais, Yohann De Castro, and Fabrice Gamboa.  Spike detection from inaccurate samplings.  Applied and Computational Harmonic Analysis, 38(2):177–195, 2015\.
  * [4] 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.
  * [5] Dmitry Batenkov, Gil Goldman, and Yosef Yomdin.  Super-resolution of near-colliding point sources.  Information and Inference: A Journal of the IMA, 05 2020.  iaaa005.
  * [6] Badri Narayan Bhaskar, Gongguo Tang, and Benjamin Recht.  Atomic norm denoising with applications to line spectral estimation.  IEEE Transactions on Signal Processing, 61(23):5987–5999, 2013\.
  * [7] Emmanuel J. Candès and Carlos Fernandez-Granda.  Towards a mathematical theory of super-resolution.  Communications on Pure and Applied Mathematics, 67(6):906–956, 2014\.
  * [8] Sitan Chen and Ankur Moitra.  Algorithmic foundations for the diffraction limit.  Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 490–503, 2021.
  * [9] Henri Clergeot, Sara Tressens, and Abdelaziz Ouamri.  Performance of high resolution frequencies estimation methods compared to the cramer-rao bounds.  IEEE transactions on acoustics, speech, and signal processing, 37(11):1703–1720, 1989.
  * [10] Maxime Ferreira Da Costa and Yuejie Chi.  On the stable resolution limit of total variation regularization for spike deconvolution.  IEEE Transactions on Information Theory, 66(11):7237–7252, 2020\.
  * [11] Laurent Demanet and Nam Nguyen.  The recoverability limit for superresolution via sparsity.  arXiv preprint arXiv:1502.01385, 2015.
  * [12] Quentin Denoyelle, Vincent Duval, and Gabriel Peyré.  Support recovery for sparse super-resolution of positive measures.  Journal of Fourier Analysis and Applications, 23(5):1153–1194, 2017\.
  * [13] David L. Donoho.  Superresolution via sparsity constraints.  SIAM journal on mathematical analysis, 23(5):1309–1331, 1992.
  * [14] David L Donoho, Iain M Johnstone, Jeffrey C Hoch, and Alan S Stern.  Maximum entropy and the nearly black object.  Journal of the Royal Statistical Society: Series B (Methodological), 54(1):41–67, 1992.
  * [15] Vincent Duval and Gabriel Peyré.  Exact support recovery for sparse spikes deconvolution.  Foundations of Computational Mathematics, 15(5):1315–1355, 2015\.
  * [16] J-J Fuchs.  Sparsity and uniqueness for some specific under-determined linear systems.  In Proceedings.(ICASSP’05). IEEE International Conference on Acoustics, Speech, and Signal Processing, 2005., volume 5, pages v–729. IEEE, 2005.
  * [17] C Helstrom.  The detection and resolution of optical signals.  IEEE Transactions on Information Theory, 10(4):275–287, 1964.
  * [18] Yingbo Hua and Tapan K. Sarkar.  Matrix pencil method for estimating parameters of exponentially damped/undamped sinusoids in noise.  IEEE Transactions on Acoustics, Speech, and Signal Processing, 38(5):814–824, 1990.
  * [19] Qiuwei Li and Gongguo Tang.  Approximate support recovery of atomic line spectral estimation: A tale of resolution and precision.  Applied and Computational Harmonic Analysis, 2018.
  * [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] Wenjing Liao and Albert C. Fannjiang.  MUSIC for single-snapshot spectral estimation: Stability and super-resolution.  Applied and Computational Harmonic Analysis, 40(1):33–67, 2016\.
  * [23] Ping Liu.  Mathematical Theory of Computational Resolution Limit and Efficient Fast Algorithms for Super-Resolution.  Hong Kong University of Science and Technology (Hong Kong), 2021.
  * [24] Ping Liu and Habib Ammari.  Nearly optimal resolution estimate for the two-dimensional super-resolution and a new algorithm for direction of arrival estimation with uniform rectangular array.  arXiv preprint arXiv:2205.07115, 2022.
  * [25] Ping Liu and Hai Zhang.  A mathematical theory of computational resolution limit in multi-dimensional spaces.  Inverse Problems, 37(10):104001, 2021.
  * [26] Ping Liu and Hai Zhang.  A theory of computational resolution limit for line spectral estimation.  IEEE Transactions on Information Theory, 67(7):4812–4827, 2021\.
  * [27] Ping Liu and Hai Zhang.  A mathematical theory of computational resolution limit in one dimension.  Applied and Computational Harmonic Analysis, 56:402–446, 2022.
  * [28] Ankur Moitra.  Super-resolution, extremal functions and the condition number of vandermonde matrices.  In Proceedings of the Forty-seventh Annual ACM Symposium on Theory of Computing, STOC ’15, pages 821–830, 2015.
  * [29] Veniamin I Morgenshtern.  Super-resolution of positive sources on an arbitrarily fine grid.  J. Fourier Anal. Appl., 28(1):Paper No. 4., 2021.
  * [30] Veniamin I. Morgenshtern and Emmanuel J. Candes.  Super-resolution of positive sources: The discrete setup.  SIAM Journal on Imaging Sciences, 9(1):412–444, 2016.
  * [31] Clarice. Poon and Gabriel. Peyré.  Multidimensional sparse super-resolution.  SIAM Journal on Mathematical Analysis, 51(1):1–44, 2019.
  * [32] R. Prony.  Essai expérimental et analytique.  J. de l’ Ecole Polytechnique (Paris), 1(2):24–76, 1795.
  * [33] Lord Rayleigh.  Xxxi. investigations in optics, with special reference to the spectroscope.  The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, 8(49):261–274, 1879.
  * [34] Richard Roy and Thomas Kailath.  ESPRIT-estimation of signal parameters via rotational invariance techniques.  IEEE Transactions on acoustics, speech, and signal processing, 37(7):984–995, 1989.
  * [35] Ralph Schmidt.  Multiple emitter location and signal parameter estimation.  IEEE transactions on antennas and propagation, 34(3):276–280, 1986\.
  * [36] Arthur Schuster.  An introduction to the theory of optics.  E. Arnold, 1904.
  * [37] Morteza Shahram and Peyman Milanfar.  Imaging below the diffraction limit: a statistical analysis.  IEEE Transactions on image processing, 13(5):677–689, 2004.
  * [38] Morteza Shahram and Peyman Milanfar.  On the resolvability of sinusoids with nearby frequencies in the presence of noise.  IEEE Transactions on Signal Processing, 53(7):2579–2588, 2005.
  * [39] Carroll Mason Sparrow.  On spectroscopic resolving power.  The Astrophysical Journal, 44:76, 1916.
  * [40] Petre Stoica and Arye Nehorai.  MUSIC, maximum likelihood, and Cramer-Rao bound.  IEEE Transactions on Acoustics, speech, and signal processing, 37(5):720–741, 1989.
  * [41] Petre Stoica and Torsten Soderstrom.  Statistical analysis of music and subspace rotation estimates of sinusoidal frequencies.  IEEE Transactions on Signal Processing, 39(8):1836–1847, 1991.
  * [42] Gongguo Tang.  Resolution limits for atomic decompositions via markov-bernstein type inequalities.  In 2015 International Conference on Sampling Theory and Applications (SampTA), pages 548–552. IEEE, 2015.
  * [43] Gongguo Tang, Badri Narayan Bhaskar, and Benjamin Recht.  Near minimax line spectral estimation.  IEEE Transactions on Information Theory, 61(1):499–512, 2014.
  * [44] Gongguo Tang, Badri Narayan Bhaskar, Parikshit Shah, and Benjamin Recht.  Compressed sensing off the grid.  IEEE transactions on information theory, 59(11):7465–7490, 2013\.
  * [45] Harald Volkmann.  Ernst abbe and his work.  Applied optics, 5(11):1720–1731, 1966.