# The dual approach to non-negative super-resolution:
perturbation analysis

Stéphane Chrétien  Laboratoire ERIC, Université Lyon 2, Bron, France  National
Physical Laboratory, Teddington, UK  Alan Turing Institute, London, UK  Andrew
Thompson  National Physical Laboratory, Teddington, UK  Bogdan Toader
Cambridge Advanced Imaging Centre, University of Cambridge, UK

###### Abstract

We study the problem of super-resolution, where we recover the locations and
weights of non-negative point sources from a few samples of their convolution
with a Gaussian kernel. It has been shown that exact recovery is possible by
minimising the total variation norm of the measure, and a practical way of
achieve this is by solving the dual problem. In this paper, we study the
stability of solutions with respect to the solutions dual problem, both in the
case of exact measurements and in the case of measurements with additive
noise. In particular, we establish a relationship between perturbations in the
dual variable and perturbations in the primal variable around the optimiser
and a similar relationship between perturbations in the dual variable around
the optimiser and the magnitude of the additive noise in the measurements. Our
analysis is based on a quantitative version of the implicit function theorem.

##  1 Problem setup

In the study of non-negative super-resolution, the aim is to estimate a signal
$x$ which consists of a number of point sources with unknown locations and
non-negative magnitudes, from only a few measurements of the convolution of
$x$ with a known convolution kernel $\phi$. This is a problem that arises in a
number of applications, for example fluorescence microscopy [1], astronomy [2]
or ultrasound imaging [3]. In such applications, the measurement device has a
limited resolution and cannot distinguish between distinct point sources that
are close to each other in the input signal $x$. This is often modelled as a
deconvolution problem with a Gaussian kernel.

Specifically, let $x$ be a non-negative measure on $I=[0,1]$ consisting of $k$
unknown non-negative point sources:

$x=\sum_{i=1}^{k}a_{i}\delta_{t_{i}},$

with $a_{i}>0$, for all $i=1,\ldots,k$, and let $y_{j}$ be the possibly noisy
measurements obtained by sampling the convolution of $x$ with a known kernel
$\phi$ at locations $s_{j}$:

$y_{j}=\int_{I}\phi(t-s_{j})x(\operatorname{d\\!}t)+w_{j}=\sum_{i=1}^{k}a_{i}\phi(t_{i}-s_{j})+w_{j},$
(1)

for all $j=1,\ldots,m$ or, in vector notation:

$y=\sum_{i=1}^{k}a_{i}\Phi(t_{i})+w,$ (2)

where

$\displaystyle y$ $\displaystyle=[y_{1},\ldots,y_{m}]^{T},$ (3)
$\displaystyle\Phi(t)$
$\displaystyle=[\phi(t-s_{1}),\ldots,\phi(t-s_{m})]^{T},$ (4) $\displaystyle
w$ $\displaystyle=[w_{1},\ldots,w_{m}]^{T}.$ (5)

Of particular interest is the case of the Gaussian kernel:

$\phi(t)=e^{-t^{2}/\sigma^{2}},$ (6)

where $\sigma$ is assumed to be known to the practitioner.

In the setting where the measurements $y$ are exact, namely when $w=0$, the
signal $x$ can be recovered by solving the following problem:

$\min_{x\geq 0}\|x\|_{TV}\quad\text{subject to}\quad
y=\int_{I}\Phi(t)x(\operatorname{d\\!}t),$ (7)

where $\|\cdot\|_{TV}$ is the Total Variation (TV) norm for Radon measures
defined as

$\displaystyle\|x\|_{\mathrm{TV}}$
$\displaystyle=\sup\left\\{\int\psi\mathrm{d}x;\quad\psi\in
C(I),\|\psi\|_{\infty}\leqslant 1\right\\}.$ (8)

When additive measurement noise is present, the signal $x$ can be recovered as
the solution to

$\min_{x\geq
0}\left\|y-\int_{I}\Phi(t)x(\operatorname{d\\!}t)\right\|_{1}\quad\text{such
that}\quad\|x\|_{TV}\leq\Pi.$ (9)

Opting for an $\ell_{1}$-type fidelity term is a reasonable choice in a robust
estimation framework, as discussed in e.g. [4].

In the context of problems (7) and (9), in this manuscript we give bounds on
the errors in the source locations $\\{t_{i}\\}_{i=1}^{k}$ and weights
$\\{a_{i}\\}_{i=1}^{k}$ as a function of the errors in the dual variable when
solving the dual problem, which we then extend to the case when the
measurements are corrupted by additive noise, where we give an exact
dependence of the error in the dual variable on the level of noise.

The problem of super-resolution has been studied extensively in the literature
since the seminal paper [5], which addressed the case of complex amplitudes.
Since the original contributions of Candès and Fernandez-Granda, there have
been numerous follow-up results such as the ones by Schiebinger et al. [6],
Duval and Peyré [7], Denoyelle et al. [8], Bendory et al. [9], Azaïs et al.
[10] and many others. For instance, the authors of [6] consider the noiseless
setting by taking real-valued samples of $y$ with a more general choice of
$\phi$ (such as a Gaussian) and also assume $x$ to be non-negative as in the
present work. Their proposed approach again involves TV norm minimization with
linear constraints. Bendory et al. [9] consider $\phi$ to be Gaussian or
Cauchy, do not place sign assumptions on $x$, and also analyze the TV norm
minimization with linear fidelity constraints for estimating $x$ from
noiseless samples of $y$.

###  1.1 Main goals of our study

A standard way to approach problem (7) is by considering its dual:

$\max_{\lambda\in\mathbb{R}^{m}}\;y^{T}\lambda\quad\text{subject
to}\quad\lambda^{T}\Phi(t)\leq 1\quad\forall t\in I,$ (10)

which is a finite-dimensional problem with infinitely many constraints, known
as a semi-infinite program (SIP). One of the main motivations for the study of
the dual problem stems from the fact that this dual problem is finite (and
even sometimes low) dimensional and as such, is amenable to efficient
optimisation algorithms such as exchange methods [11] or sequential quadratic
programming [12]. Moreover, the constraints $\lambda^{T}\Phi(t)\leq 1,\forall
t\in I$ can be handled using an exact penalty approach, i.e. can be
reformulated as

$\min_{\lambda\in\mathbb{R}^{m}}-y^{T}\lambda+\Pi\cdot\max\left\\{\sup_{s}\left(\lambda^{T}\Phi(s)-1\right),0\right\\},$
(11)

thus making the problem amenable to non-smooth optimisation algorithms such as
bundle methods [13, 14]. To illustrate the use of such methods for solving the
dual problem, we present the result of an experiment in which we use the level
bundle method [13] to solve a continuous sparse inverse problem of the kind
introduced in this section. Here a signal (consisting of five spikes with
locations $\\{0.2,0.4,0.6,0.7,0.75\\}$ each with amplitude $1$) is convolved
with a Gaussian kernel $\phi(t)=e^{-t^{2}/\sigma^{2}}$ with $\sigma=0.1$ and
sampled at $15$ equispaced points on $[0,1]$. The dual problem is solved using
the level bundle method, and the spike locations are identified from the
global maximisers of the dual certificate obtained. Figure 1(a) displays the
recovered solution using the level bundle method along with the corresponding
dual certificate, showing that the method is able to recover the signal to
high accuracy even though the minimum separation is somewhat small ($0.05$).
Figure 1(b) shows the speed of convergence in terms of the decrease in the
optimality gap (the model gap - see Appendix B). We observe linear convergence
in practice.

Figure 1: (a) Solution and dual certificate obtained using the level bundle
method. (b) Decrease in optimality gap with iteration number.

The dual approach has nevertheless a drawback. It is indeed not yet clear how
errors in the solution of the dual problem impact primal solution recovery.
Providing a quantitative analysis of the recovery error as a function of the
error in the dual solution is the main goal of the present work. In addition,
we extend the analysis to the noisy setting, where we give the explicit
dependence of the error of the dual solution on potential additive noise in
the measurements.

###  1.2 Our contributions

In this paper, we restrict our study to the case of Gaussian kernels. Our main
results are the following

  * •

In the setting of exact measurements, we provide bounds on how far the
estimated locations $t_{k}$ and magnitudes $a_{k}$ are from their true values
as the dual variable $\lambda$ is perturbed from its optimal value
$\lambda^{*}$ when $x$ is recovered by solving the dual problem (10). These
bounds are given in Theorems 2 and 3. These give us an insight into the size
of the error in the locations and magnitudes when we apply an optimisation
algorithm to the dual of the super-resolution problem.

  * •

In the setting of measurements corrupted by additive noise, we leverage the
perturbation bounds obtained for the noiseless case in order to study the
impact of additive noise in the observations, when the signal is recovered by
solving the alternative problem (9). For this purpose, we make precise links
between the dual solutions to (9) and (10). Our main result for this noisy
setup is Theorem 4, where we give an explicit bound on the impact of noise on
the estimation of the dual solution to (10). This makes again the case for the
study of (10) under perturbation.

While the bounds given in these theorems apply only to the case when the
convolution kernel is Gaussian, the same techniques can be applied to obtain
perturbation bounds for other kernels, with a few differences in the way some
sums in the proofs are bounded, which would would be specific to the kernel
used.

###  1.3 Comparison with previous work

####  1.3.1 Alternative formulations for the noiseless setting

For the particular case of non-negative $x$, Boyd et al. [15] proposed an
improved Frank-Wolfe algorithm in the primal. In certain instances, for e.g.,
with Fourier samples (such as in [5, 16]), the dual, which is a SIP, can also
be reformulated as a semi-definite program (SDP). From a practical point of
view, SDP is notoriously slow for even moderately large number of variables.
The algorithm of [15] is a first order scheme with potential local correction
steps, and is practically more viable.

As already mentioned, the main reason we advocate for using the dual problem
(10) is that exact penalty can be used in order to reformulate the dual
problem as a non-smooth minimisation problem for which methods such as bundle
methods [13], [17] are efficient in practice. To the best of our knowledge,
there is no analysis of the impact of obtaining approximate solutions of the
dual on the quality of the recovered locations.

####  1.3.2 The penalised least squares approach

The approach adopted in [7, 8] is to solve a least-squares-type minimization
procedure with a TV norm based penalty term (also referred to as the Beurling
LASSO (for example [18])) for recovering $x$ from samples of $y$. The approach
in [19] considers a natural finite approximation on the grid to the continuous
problem, and studies the limiting behaviour as the grid becomes finer; see
also [20]. These works develop a perturbation analysis which is different from
ours since it applies to specific types of perturbations of a different
problem ($\ell_{2}$ vs. $\ell_{1}$ type fidelity terms), and do not provide
precise quantitative dependencies with respect to all the parameters of the
problem.

####  1.3.3 The Prony/Matrix Pencil approach

Another efficient approach is the one of [21] based on the original work of
Hua and Sarkar [22] using a Matrix Pencil approach, and recently extended to
the multi-kernel setting in [23]. Perturbation analysis of the Matrix Pencil
approach is provided in [21]; see also [23] for a more detailed exposition of
these results with the correct order of dependencies. The reason we develop an
analysis of the dual problem (10) here is that it easily extends to the
multidimensional setting as well, at least for small dimensions. In contrast,
the Matrix Pencil method, although very efficient in one dimension, becomes
much more involved in several dimensions [24].

###  1.4 Plan of the paper

We start by presenting the noise-free perturbation results related to problem
(10) in Section 2, followed by the perturbation results in the setting when
the measurements are corrupted by noise in Section 3. The proofs of our
results are given in Section 4 and we show numerical experiments to verify the
validity of our results in practice in Section 5. Lastly, we conclude the
paper in Section 6.

##  2 Bound on the error as $\lambda$ is perturbed – the noise-free case

In this section we present our first main results, namely two theorems that
give bounds on the perturbations around the source locations $t_{i}$ and the
magnitudes $a_{i}$ respectively, as the dual variable is perturbed away from
the optimiser $\lambda^{*}$, when the convolution kernel is a Gaussian with
known width $\sigma$ as defined in (6).

Before we discuss these results, we define the concept of a dual certificate,
which plays an important role throughout this paper.

######  Definition 1.

(Dual certificate) Consider a solution $\lambda^{*}$ of the dual problem (10)
or (24). Then a dual certificate is a function of the form

$q(t)=\sum_{j=1}^{m}\lambda_{j}^{*}\phi(t-s_{j})={\lambda^{*}}^{T}\Phi(t),$
(12)

which satisfies the conditions:

$\displaystyle q(t_{i})=1,\quad\forall i=1,\ldots,k,$ (13) $\displaystyle
q(t)<1,\quad\forall t\neq t_{i},\forall i=1,\ldots,k.$ (14)

The idea of dual certificate is common in the super-resolution literature, and
we know that the global maximisers of $q(t)$ correspond to the source
locations $\\{t_{i}\\}_{i=1}^{k}$ (see, for example [5, 6, 25], Once these are
found, amplitudes $\\{a_{i}\\}_{i=1}^{k}$ are obtained by solving a linear
system.

We are now ready to discuss the perturbation results in the noise-free
setting. In the following theorem, we consider the dual (10) of (7) and
quantify how the source locations given by the global maximisers of the dual
certificate formed by the dual solution $\lambda^{*}$ are affected by
perturbations of $\lambda^{*}$. The proof is given in Section 4.1.

######  Theorem 2.

(Dependence of $|t-t^{*}|$ on $\|\lambda-\lambda^{*}\|_{2}$) Let
$\lambda^{*}\in\mathbb{R}^{m}$ be a solution of the dual program (10) with
$\phi$ Gaussian as given in (6) such that the the dual certificate $q(s)$
defined in (12) satisfies conditions (13) and (14), $\lambda$ a perturbation
of $\lambda^{*}$ in a ball of radius $\delta_{\lambda}$ and $t$ an arbitrary
local maximiser of $q_{\lambda}(s)=\sum_{j=1}^{m}\lambda_{j}\phi(s-s_{j})$ so
that for $\lambda=\lambda^{*}$, the corresponding local maximiser $t^{*}$ is a
true source location in $x$. Let $R=\frac{\|\lambda^{*}\|_{2}}{\sigma}$ and
$c\approx 3.9036$ a universal constant. If the radius $\delta_{\lambda}$ is
bounded by

$\delta_{\lambda}\leq\frac{|q^{\prime\prime}(t^{*})|^{2}\sigma^{3}\sqrt{e}}{4\sqrt{2}\left(2+cR\right)m},$
(15)

then

$|t-t^{*}|\leq C_{t^{*}}\|\lambda-\lambda^{*}\|_{2},$ (16)

where

$\displaystyle C_{t^{*}}$
$\displaystyle=\frac{1}{4+cR}\left[1+\frac{2\sqrt{2m}(2+cR)}{|q^{\prime\prime}(t^{*})|\sqrt{e}}\right].$
(17)

One of the main conclusions which can be drawn from this result is that the
primal spike location error is controlled in $l_{\infty}$, but degrades as a
function of the number of measurements in the order of $\sqrt{m}$.
Alternatively, we can write (16) in terms of the $\ell_{2}$ norm of the error
between the vector of true source locations $\mathbf{t^{*}}$ and the perturbed
source locations $\mathbf{\tilde{t}}$:

$\|\mathbf{\tilde{t}}-\mathbf{t^{*}}\|_{2}\leq\sqrt{k}C_{t^{*}}\|\lambda-\lambda^{*}\|_{2}.$

Of crucial importance is the curvature of the dual certificate at the true
solution: the flatter the certificate, the worse the estimation error. Our
theorem also gives important information about the accuracy in the dual
variable required to guarantee our upper bound on the error of recovery. This
accuracy is of the inverse order of the number of measurements, which is quite
a stringent constraint. Both the $m$ and the $\sqrt{m}$ factors are a
consequence of the way we bound sums of shifted copies of the kernel, namely
$\sum_{j=1}^{m}\phi(t-s_{j})\leq m\max_{t\in\mathbb{R}}\phi(t)$. Given the
fast decay of the Gaussian, it is clear that this is not a tight bound.
However, any bound would reflect the density of samples close to each source
location.

We will now give a result regarding the perturbation of the magnitudes $a_{i}$
when $\lambda^{*}$ is perturbed. Let $\Phi$ be the matrix whose entries are
defined as

$\Phi_{ij}=\phi(t_{j}-s_{i}),$ (19)

and $\mathbf{t^{*}}$ and $\mathbf{a^{*}}$ the vectors of source locations and
weights:

$\displaystyle\mathbf{t^{*}}=[t_{1},\ldots,t_{k}]^{T},\quad\quad\mathbf{a^{*}}=[a_{1},\ldots,a_{k}]^{T}.$

When we solve (10) exactly, we obtain the source locations by finding the
global maximisers of $q(s)$. Then, the vector of weights $\mathbf{a^{*}}$ is
found by solving the system

$\Phi\mathbf{a}=\mathbf{y}.$

When the source locations are perturbed, we denote the resulting perturbed
data matrix by:

$\tilde{\Phi}=\Phi+E,$ (20)

and we calculate the vector of perturbed weights $\tilde{\mathbf{a}}$ as the
solution of the least squares problem

$\min_{\mathbf{a}}\|\tilde{\Phi}\mathbf{a}-\mathbf{y}\|_{2}.$ (21)

The following theorem, proved in Section 4.2, gives a bound on the error
$\|\mathbf{a^{*}}-\tilde{\mathbf{a}}\|_{2}$ between the vector of true weights
$\mathbf{a^{*}}$ and the vector of weights $\tilde{\mathbf{a}}$ obtained by
solving the least squares problem (21) with the perturbed matrix
$\tilde{\Phi}$, as a function of the error
$\|\tilde{\mathbf{t}}-\mathbf{t^{*}}\|_{2}$ between the perturbed source
locations $\tilde{\mathbf{t}}$ and the true source locations $\mathbf{t^{*}}$.

######  Theorem 3.

(Dependence of $\|\mathbf{\tilde{a}}-\mathbf{a^{*}}\|_{2}$ on
$\|\mathbf{\tilde{t}}-\mathbf{t^{*}}\|_{2}$) Let $\mathbf{t^{*}}\in[0,1]^{k}$
be the vector of true source locations, $\tilde{\mathbf{t}}\in[0,1]^{k}$ the
perturbed source locations, and $\sigma_{\max}(\Phi)$, $\sigma_{\min}(\Phi)$
the largest and respectively smallest singular values of the matrix $\Phi$
defined in (19), such that:

$\|\mathbf{\tilde{t}}-\mathbf{t^{*}}\|_{2}<\frac{\sigma^{2}\sigma_{\max}(\Phi)}{4e^{4/\sigma^{2}}\sqrt{m}}\left(\sqrt{1+\frac{\sigma_{\min}^{2}(\Phi)}{\sigma_{\max}^{2}(\Phi)}}-1\right).$
(22)

Then the error between the true weights $\mathbf{a^{*}}$ and the perturbed
weights $\tilde{\mathbf{a}}$ obtained by solving problem (21) is bounded by:

$\|\mathbf{\tilde{a}}-\mathbf{a^{*}}\|_{2}\leq
C_{a^{*}}\|\tilde{\mathbf{t}}-\mathbf{t^{*}}\|_{2}+O(\|\tilde{\mathbf{t}}-\mathbf{t^{*}}\|_{2}^{2}),$
(23)

where

$C_{a^{*}}=\frac{4e^{\frac{4}{\sigma^{2}}}\sqrt{m}\|\mathbf{a^{*}}\|_{2}}{\sigma^{2}\sigma_{\min}(\Phi)}.$

Note that we write the $O(\|\tilde{\mathbf{t}}-\mathbf{t^{*}}\|_{2}^{2})$ term
in the bound above in order to simplify the presentation of the result. We
can, however, calculate the constants corresponding to the higher order terms
in the bound by using the inequality (115) in the proof of Theorem 3 in
Section 4.2. For example, the constant in the second order term is equal to
$C_{a^{*}}^{2}/\|\mathbf{a^{*}}\|_{2}\left[1+2\sigma^{2}_{\max}(\Phi)/\sigma^{2}_{\min}(\Phi)\right]$.

##  3 Bound on $\|\lambda-\lambda^{*}\|_{2}$ in terms of the noise $w$

In this section we assume that the measurements are corrupted by additive
noise and we give a result where we bound the perturbation in the dual
variable $\lambda$ around the minimiser $\lambda^{*}$ as a function of the
noise $w$ in the measurements. Specifically, the noisy measurements are
defined as in (1):

$y_{j}=\int_{I}\phi_{j}(t)x(\operatorname{d\\!}t)+w_{j}=\sum_{i=1}^{k}a_{i}\phi_{j}(t_{i})+w_{j},$

for $w_{j}\neq 0$ and $j=1,\ldots,m$.

The aim is to estimate how the source locations $\\{t_{i}\\}_{i=1}^{k}$ and
weights $\\{a_{i}\\}_{i=1}^{k}$ are affected by the additive noise $w$ in the
measurements around the solution of the problem. In the previous section we
have established how the source locations and weights are perturbed around
their true values as the dual variable $\lambda$ is perturbed around its
optimal value $\lambda^{*}$. In the noisy setting, we want to establish a
precise quantitative relationship between the perturbations of $\lambda$
around $\lambda^{*}$ and the magnitude of the noise.

Before we state the main result, which gives a relationship of this kind,
first we need to describe the exact mathematical setting under which the
result holds. Then we introduce the function $\bar{F}$ in (35) to which we
apply the implicit function theorem, whose Jacobian is crucial for this
result.

In order to account for noise in the measurements, we consider a slightly
modified version of the dual problem (10). To be specific, we use an
additional box constraint on the dual variable $\lambda$ and obtain the dual
problem:

$\displaystyle\max_{\lambda\in\mathbb{R}^{m}}y^{T}\lambda\quad$
$\displaystyle\text{such that}\quad\lambda^{T}\Phi(t)\leq 1,\quad\forall t\in
I,$ $\displaystyle\quad\quad\text{and}\quad\|\lambda\|_{\infty}\leq\tau,$ (24)

Looking at the specific formulation of the primal problem that (24) is the
dual of, namely (9), we can see that it takes measurement noise into account
by doing $\ell_{1}$ minimisation of the error instead of requiring the
measurements to be satisfied exactly.

To motivate the exact form of the function $\bar{F}$ in (35) to which we apply
the implicit function theorem to obtain the perturbation result from Theorem
4, consider the exact penalty formulation of (24):

$\min_{\lambda\in\mathbb{R}^{m}}\Psi_{\Pi}(\lambda)\quad\text{such
that}\quad\|\lambda\|_{\infty}\leq\tau,$ (25)

where

$\Psi_{\Pi}(\lambda)=-y^{T}\lambda+\Pi\cdot\max\left\\{\sup_{s}\left(\sum_{j=1}^{m}\lambda_{j}\phi(s-s_{j})-1\right),0\right\\}.$
(26)

For a large enough value of $\Pi$, a solution to (25) which satisfies the
constraints in (24) is also a solution of (24) (see, for example, Section 1.2
in [17]). This is a non-smooth optimisation problem and its solution can be
found by using any method that relies on calculating subgradients, for example
the level method [13].

A subgradient of $\Psi_{\Pi}(\lambda)$ has the form:

$\partial\Psi_{\Pi}=\begin{cases}-y+\Pi\sum_{i=1}^{k^{\prime}}\nu_{i}g(s_{i}^{*}),\quad(\nu_{1}+\ldots+\nu_{k^{\prime}}=1)&\quad\text{
if }\quad\sup_{s}\sum_{j=1}^{m}\lambda_{j}\phi(s-s_{j})>1,\\\
-y+\Pi\sum_{i=1}^{k^{\prime}}\nu_{i}g(s_{i}^{*}),\quad(\nu_{1}+\ldots+\nu_{k^{\prime}}\leq
1)&\quad\text{ if }\quad\sup_{s}\sum_{j=1}^{m}\lambda_{j}\phi(s-s_{j})=1,\\\
-y,&\quad\text{ if
}\quad\sup_{s}\sum_{j=1}^{m}\lambda_{j}\phi(s-s_{j})<1,\end{cases}$ (27)

where $\\{s_{i}^{*}\\}_{i=1}^{k^{\prime}}$ are the global maximisers of the
function $\sum_{j=1}^{m}\lambda_{j}\phi(s-s_{j})$, the vectors $g(s)$ are of
the form $g(s)=[\phi(s-s_{1}),\ldots,\phi(s-s_{m})]^{T}$ and $\nu_{i}\geq 0$
for all $i=1,\ldots,k^{\prime}$. Note that here we apply the formula for the
subgradient of the $\max$ function and for the $\sup$ function (see for
example [17]). The coefficients in the convex combination from the formula for
the subgradient of the $\max$ function with zero account for the case when
$\nu_{1}+\ldots+\nu_{k^{\prime}}<1$111 More specifically, both functions in
the $\max$ attain their maximum, so we have that
$\partial\Psi_{\pi}=-y+\Pi\left[\alpha_{1}\partial\sup_{s}\left(\sum_{j=1}^{m}\lambda_{j}\phi(s-s_{j})-1\right)+\alpha_{2}\partial
0\right]$, with $\alpha_{1},\alpha_{2}>0$ and $\alpha_{1}+\alpha_{2}=1$, and
therefore
$\partial\Psi_{\pi}=-y+\Pi\sum_{i=1}^{k^{\prime}}\alpha_{1}\nu_{i}^{\prime}g(s_{i}^{*})$,
with $\nu_{1}^{\prime}+\ldots+\nu_{k^{\prime}}^{\prime}=1$ and
$0\leq\alpha_{1}\leq 1$. .

As in the noise-free setting, we assume here that the dual solution
$\lambda^{*}$ forms a dual certificate, namely the function $q(s)$ as defined
in (12) satisfies conditions (13) and (14). Then, the subdifferential at
$\lambda^{*}$ has the form:

$\partial\Psi_{\Pi}(\lambda^{*})=-y+\Pi\sum_{i=1}^{k}\nu_{i}g(t_{i}),$ (28)

where $\\{t_{i}\\}_{i=1}^{k}$ are the source locations, so the optimality
condition for (25):

$0\in\partial\Psi_{\Pi}(\lambda^{*}),$ (29)

is equivalent to:

$y=\Pi\sum_{i=1}^{k}\nu_{i}g(t_{i}),$ (30)

for some $\nu_{1},\ldots,\nu_{k}\geq 0$ with $\nu_{1}+\ldots+\nu_{k}\leq 1$
and for $w=0$. Note that, given the definition of $y$ from (1), the optimality
condition (30) is satisfied for

$\displaystyle\nu_{i}$ $\displaystyle=\frac{a_{i}}{\Pi},\quad\forall
i=1,\ldots,k,$ (31) $\displaystyle w_{j}$ $\displaystyle=0,\quad\forall
j=1,\ldots,m,$ (32)

where in order to satisfy $\nu_{1}+\ldots+\nu_{k}\leq 1$, we need $\Pi$ such
that:

$\Pi\geq a_{1}+\ldots+a_{i},$ (33)

which is the same as the constraint in (9).

Motivated by the above reasoning, we now want to apply the quantitative
implicit function theorem, as given in [26], to a function $F$ of the form:

$F([\lambda,\nu]^{T},w)=\sum_{i=1}^{k}a_{i}\Phi(t_{i}^{*})-\sum_{i=1}^{k}\nu_{i}\Phi(t(\lambda))+w,$
(34)

where we know that $F([\lambda^{*},a]^{T},0)=0$. For the sake of simplicity,
we include the parameter $\Pi$ in the coefficients $\nu_{i}$, so in the second
sum in $F$ each $\nu_{i}$ actually corresponds to $\Pi\nu_{i}$, and
$\nu_{1}+\ldots+\nu_{k}\leq\Pi$ rather than $\nu_{1}+\ldots+\nu_{k}\leq 1$.

However, note that $F\mathrel{\mathop{\mathchar
58\relax}}\mathbb{R}^{m+k}\times\mathbb{R}^{m}\to\mathbb{R}^{m}$ and in order
to apply the implicit function theorem to obtain the dependence of the first
argument of $F$ as a function of the second argument, we need the first
argument to be in $\mathbb{R}^{m}$.

To solve this issue, we first reduce the system by dropping $m-2k$ rows above.
The $2k$ rows which are not dropped depend on the conditions that must be met
in order for the conditions in the implicit function theorem to be satisfied,
and intuitively these correspond to the samples that contain the most
information, for example the two samples that are the closest to each source.
This leads to the function $F\mathrel{\mathop{\mathchar
58\relax}}\mathbb{R}^{m+k}\times\mathbb{R}^{2k}\to\mathbb{R}^{2k}$. The next
step is to we set $m-k$ components of $\lambda$ to the boundary of the box
constraint $\|\lambda\|_{\infty}\leq\tau$. This is justified by the fact that
the system $F([\lambda^{*},a]^{T},0)=0$ of $2k$ equations and $m+k$ unknowns
$[\lambda^{*},a]^{T}$ is underdetermined, and therefore solving it involves
setting $m-k$ of the unknowns to arbitrary values. In practice, this is
achieved by tuning the box constraint in such a way that the largest
components of $\lambda$ are set to $\tau$ or $-\tau$. More specifically, we
keep $k$ values of $\lambda$ which correspond to a subset of the $2k$ samples
which have not been dropped. This finally leads to the function which we will
denote by $\bar{F}$:

$\bar{F}\mathrel{\mathop{\mathchar
58\relax}}\mathbb{R}^{2k}\times\mathbb{R}^{2k}\to\mathbb{R}^{2k},\quad\bar{F}([\bar{\lambda},\nu]^{T},\bar{w})=\sum_{i=1}^{k}a_{i}\bar{\Phi}(t_{i}^{*})-\sum_{i=1}^{k}\nu_{i}\bar{\Phi}(t(\lambda))+\bar{w},$
(35)

where $\bar{\lambda}\in\mathbb{R}^{k}$ contains only the entries of $\lambda$
which are not fixed and $\bar{w}\in\mathbb{R}^{2k}$,
$\bar{\Phi}(t)\in\mathbb{R}^{2k}$ are the vectors with the entries from $w$
and $\Phi(t)$ respectively corresponding to the equations which have not been
dropped. Given the definition of $\bar{F}$ in (35), we can now state the main
result of this section, proved in Section 4.3.

######  Theorem 4.

(Dependence of $\|\lambda-\lambda^{*}\|_{2}$ on the noise $w$) Let
$\lambda^{*}$ be the solution to the dual problem (24) with $w=0$. Given the
function $\bar{F}$ defined in (35), let $J^{*}$ be its Jacobian with respect
to the first variable, evaluated at $([\bar{\lambda}^{*},a]^{T},0)$ and
$\sigma_{\min}(J^{*})$ its smallest singular value. We also assume that the
solution $\lambda^{*}$ forms a dual certificate, namely the function $q(t)$
defined in (12) satisfies conditions (13) and (14). If $J^{*}$ is invertible
and $\|\bar{w}\|_{2}\leq\delta_{w}$, then:

$\left\|\bar{\lambda}-\bar{\lambda}^{*}\right\|_{2}\leq
C_{\lambda^{*}}\cdot\left\|\bar{w}\right\|_{2},$ (36)

where

$\displaystyle C_{\lambda^{*}}=\frac{2}{\sigma_{\min}(J^{*})},$ (37)
$\displaystyle\delta_{w}=\frac{\sigma_{\min}(J^{*})^{2}}{4P(m,k,\sigma,\Pi,\tau,C_{t^{*}})},$
(38)

and

$\displaystyle P($ $\displaystyle
m,k,\sigma,\Pi,\tau,C_{t^{*}})=\sqrt{2}k\Bigg{[}\frac{1}{\sigma^{2}}\left(2\sqrt{k}C_{t^{*}}^{2}\Pi+4kC_{t^{*}}\bar{\Delta}_{2}\tau\Pi\right)$
$\displaystyle+\frac{1}{\sigma}\left(\frac{\sqrt{2k}C_{t^{*}}}{\sqrt{e}}+4\sqrt{k}C_{t^{*}}^{2}\Pi+\frac{2\sqrt{2}\bar{\Delta}_{2}\Pi}{\sqrt{e}}+8kC_{t^{*}}\bar{\Delta}_{2}\tau\Pi+\frac{\sqrt{2k}\bar{\Delta}_{2}\Pi}{\sqrt{e}}+\sqrt{\frac{2}{e}}C_{t^{*}}\right)\Bigg{]},$

where $C_{t^{*}}$ is given in (17) in Theorem 2 and $\bar{\Delta}_{2}$ is
given in (163) in the proof of Lemma 8.

The theorem above makes explicit the dependence of the perturbation in the
dual variable $\bar{\lambda}$ around the solution $\bar{\lambda^{*}}$ on the
additive noise $\bar{w}$ in the measurement vector $\bar{y}$. This is a linear
relation where the constant depends on the specific configuration of the
problem we are solving, namely the locations and weights of the sources, and
width of the Gaussian and the sampling locations. The theorem also gives an
upper bound on the magnitude of the noise where this result holds as a
function of the same parameters.

Moreover, under the assumption that $\Pi,C_{t^{*}},\tau\geq 1$, we can write
the order of $P$ as:

$P\approx\frac{k\sqrt{k}\Pi
C_{t^{*}}}{\sigma^{2}}\left(C_{t^{*}}+\sqrt{k}\bar{\Delta}_{2}\tau\right),$
(39)

which gives us a clearer idea of the main parameters that affect the magnitude
of the noise for which our perturbation results hold.

One observation we want to make is that, while the above result only applies
to a subset of the entries in $\lambda$ and $w$, which entries are selected is
not arbitrary. The choice of the entries in $\lambda$ and $w$ reflects which
samples $s_{j}$ contain the most information, and therefore which noise
entries in $w$ affect the solution to the optimisation problem the most. More
specifically, in order for the Jacobian $J^{*}$ to be invertible, we are led
to select the samples (and therefore $\lambda$ and $w$ entries) that satisfy
this condition the best, namely the ones that are the closest to the source
locations. We discuss this aspect in more detail in Section 3.1.

Lastly, note that the results in Section 2 and Section 3 refer to different
optimisation problems: the duals (10) and (24) of problems (7) and (9)
respectively. However, the proofs of our perturbation results rely on the
property that the dual solution $\lambda$ forms a dual certificate, the global
maximisers of which give the locations of the point sources in the input
signal $x$, with the additional bound on $\lambda$ from (24) being used in the
proof of Theorem 4. Moreover, since our analysis is independent of the exact
formulation of the primal problems, we can conclude that the results from both
Section 2 and Section 3 apply to the problem of super-resolution in the noisy
setting, namely they give bounds of the perturbations of the source locations
and weights as a consequence of noise in the measurements.

###  3.1 Discussion

One of the conditions in Theorem 4 is that the Jacobian $J^{*}$ is invertible.
While we do not provide a rigorous analysis of the conditions in which this is
satisfied, in this section we discuss in more detail what the condition
requires and give further motivation for why it is true in a reasonable
scenario. Specifically, we assume that the samples that are used for
calculating the Jacobian are the closest samples to the sources (for each
source location, we select the two samples that are the closest to it), so the
rows in the system given by $\bar{F}$ in (35) correspond to these samples.
Consequently, the entries in $\lambda$ and the entries in the noise vector $w$
also correspond to the same samples.

Recall that $J^{*}$ is the Jacobian of the function $\bar{F}$ from (35) with
respect to the first argument. The entries in $J^{*}$ are:

$\displaystyle\partial_{\lambda_{l}}F([\lambda,\nu]^{T},w)\Bigr{|}_{\begin{subarray}{c}\lambda=\lambda^{*}\\\
\nu=a\\\ w=0\end{subarray}}$
$\displaystyle=-\sum_{i=1}^{k}a_{i}\phi^{\prime}(t_{i}^{*}-s_{j})\partial_{\lambda_{l}}t_{i}(\lambda^{*})$
(40)
$\displaystyle=\sum_{i=1}^{k}\frac{a_{i}\phi^{\prime}(t_{i}^{*}-s_{j})\phi^{\prime}(t_{i}^{*}-s_{l})}{q^{\prime\prime}(t_{i}^{*})},$
(41)

for $l=1,\ldots,k$, $j=1,\ldots,2k$ and

$\partial_{\nu_{l}}F([\lambda,\nu]^{T},w)\Bigr{|}_{\begin{subarray}{c}\lambda=\lambda^{*}\\\
\nu=a\\\ w=0\end{subarray}}=-\phi(t_{l}^{*}-s_{j}),$ (42)

for $l=1,\ldots,k$, $j=1,\ldots,2k$, where in the first equality we used (52)
with (56) and (57) plugged in, so the result holds under the conditions in
Theorem 2, namely for $\lambda$ with
$\|\lambda-\lambda^{*}\|_{2}\leq\delta_{\lambda}$, where $\delta_{\lambda}$ is
given in (15).

Writing $J^{*}$ as

$J^{*}=[J_{\lambda}J_{\nu}],$ (43)

where the entries in the blocks $J_{\lambda}$ and $J_{\nu}$ are given by (41)
and (42) respectively, we have that:

$J_{\lambda}=\sum_{i=1}^{k}\frac{a_{i}}{q^{\prime\prime}(t_{i}^{*})}\Phi^{\prime}(t_{i}^{*})\Phi^{\prime}(t_{i}^{*})^{T},$
(44)

and

$J_{\nu}=-[\Phi(t_{1}^{*})\ldots\Phi(t_{k}^{*})],$ (45)

where

$\displaystyle\Phi(t)=[\phi(t-s_{1}),\ldots,\phi(t-s_{2k})]^{T},$ (46)
$\displaystyle\Phi^{\prime}(t)=[\phi^{\prime}(t-s_{1}),\ldots,\phi^{\prime}(t-s_{2k})]^{T}.$
(47)

Note that $rank(J_{\nu})=k$ by the T-systems property of the Gaussian
(assuming that the $t_{1}\leq\ldots\leq t_{k}$ and $s_{1}\leq\ldots s_{2k}$)
and in order for the matrix $J^{*}$ to be invertible we need $rank(J^{*})=2k$,
as it is a square matrix with $2k$ columns. By rewriting the columns of
$J_{\lambda}$, we have that:

$\displaystyle
J^{*}=\left[\sum_{i=1}^{k}\frac{a_{i}\phi^{\prime}(t_{i}^{*}-s_{1})}{q^{\prime\prime}(t_{i}^{*})}\Phi^{\prime}(t_{i}^{*})\quad\ldots\quad\sum_{i=1}^{k}\frac{a_{i}\phi^{\prime}(t_{i}^{*}-s_{k})}{q^{\prime\prime}(t_{i}^{*})}\Phi^{\prime}(t_{i}^{*})\quad-\Phi(t_{1}^{*})\quad\ldots\quad-\Phi(t_{k}^{*})\right],$
(48)

and by taking its determinant and using the multi-linearity property of the
determinant with respect to its columns, we have that:

$\displaystyle\det(J^{*})$ $\displaystyle=(-1)^{k}\frac{a_{1}\ldots
a_{k}}{q^{\prime\prime}(t_{1}^{*})\ldots q^{\prime\prime}(t_{k}^{*})}$
$\displaystyle\cdot\sum_{l=1}^{k!}\left(\prod_{i=1}^{k}\phi^{\prime}(P_{l}(t_{i}^{*})-s_{i})\right)\left|P_{l}(\Phi^{\prime}(t_{1}^{*}))\quad\ldots\quad
P_{l}(\Phi^{\prime}(t_{k}^{*}))\quad\Phi(t_{1}^{*})\quad\ldots\quad\Phi(t_{k}^{*})\right|,$
(49)

where $P_{l}$ for $l=1,\ldots,k!$ are the permutations of $k$ elements. Note
that when we expand the determinant, the terms in the final sum are
determinants with all the possible combinations of the vectors in each sum,
which results in many determinants having repeated columns, so they are equal
to zero. The only non-zero determinants in the resulting sum are the ones
where the first $k$ columns are the vectors
$\\{\Phi^{\prime}(t_{i}^{*})\\}_{i=1}^{k}$ and their permutations, multiplied
by the corresponding constants. We now order the columns of the determinant:

$\displaystyle\det(J^{*})$ $\displaystyle=(-1)^{k}\frac{a_{1}\ldots
a_{k}}{q^{\prime\prime}(t_{1}^{*})\ldots q^{\prime\prime}(t_{k}^{*})}$
$\displaystyle\qquad\qquad\sum_{l=1}^{k!}sign(P_{i})\left(\prod_{i=1}^{k}\phi^{\prime}(P_{l}(t_{i}^{*})-s_{i})\right)\left|\Phi(t_{1}^{*})\quad\Phi^{\prime}(t_{1}^{*})\quad\ldots\quad\Phi(t_{k}^{*})\quad\Phi^{\prime}(t_{k}^{*})\right|,$
$\displaystyle=(-1)^{k}\frac{a_{1}\ldots
a_{k}}{q^{\prime\prime}(t_{1}^{*})\ldots
q^{\prime\prime}(t_{k}^{*})}\left|\Phi(t_{1}^{*})\quad\Phi^{\prime}(t_{1}^{*})\quad\ldots\quad\Phi(t_{k}^{*})\quad\Phi^{\prime}(t_{k}^{*})\right|$
$\displaystyle\qquad\qquad\sum_{l=1}^{k!}sign(P_{l})\left(\prod_{i=1}^{k}\phi^{\prime}(P_{l}(t_{i}^{*})-s_{i})\right),$
(50)

where by $sign(P_{i})$ we denote the sign of the determinant corresponding to
the permutation $P_{i}$ after reordering the columns as above. Because of the
extended T-system property of the Gaussian function [27], the determinant
above is strictly positive. The dominant term in the sum is the one
corresponding to the identity permutation, where for each $i=1,\ldots,k$, the
sample $s_{i}$ is the closest sample to the source location $t_{i}^{*}$. As
the samples get further, the terms of the sum approach zero. This can be
expressed in more quantitatively by imposing explicit conditions on the
distances between the closest samples and the sources, the separation of
sources and the separation of samples, as done, for example, in [25].

##  4 Proofs

In this section we present the proofs of the theorems from Sections 2 and 3.

###  4.1 Proof of Theorem 2 (Dependence of $|t-t^{*}|$ on
$\|\lambda-\lambda^{*}\|_{2}$)

Let $t^{*}$ be an arbitrary local maximiser of the function $q(t)$ in (12), so
$t^{*}$ is also a source location, and $\lambda^{*}$ the solution to (10). The
key step in this proof is applying a quantitative version of the implicit
function theorem [26] to the function:

$F(t,\lambda)=\sum_{j=1}^{m}\lambda_{j}\phi^{\prime}(t-s_{j}),$ (51)

where $F(t^{*},\lambda^{*})=0$ because $t^{*}$ is a maximizer of $q(s)$ in
(12). The theorem allows us to express $t$ as a function $t(\lambda)$ of
$\lambda$ with:

$\partial_{\lambda}t(\lambda)=-\left[\partial_{t}F(t(\lambda),\lambda)\right]^{-1}\partial_{\lambda}F(t(\lambda),\lambda),$
(52)

for $t$ in a ball of radius $\delta_{0}$ around $t^{*}$ and for $\lambda$ in a
ball of radius $\delta_{1}\leq\delta_{0}$ around $\lambda^{*}$, where
$\delta_{0}$ is chosen such that

$\sup_{(t,\lambda)\in
V_{\delta}}\left\|I-\left[\partial_{t}F(t^{*},\lambda^{*})\right]^{-1}\partial_{t}F(t,\lambda)\right\|\leq\frac{1}{2},$
(53)

where
$V_{\delta}=\left\\{(t,\lambda)\in\mathbb{R}^{m+1}\mathrel{\mathop{\mathchar
58\relax}}|t-t^{*}|\leq\delta_{0},\|\lambda-\lambda^{*}\|\leq\delta_{0}\right\\}$
and $\delta_{1}$ is given by

$\delta_{1}=(2M_{t}B_{\lambda})^{-1}\delta_{0},$ (54)

where

$\displaystyle B_{\lambda}$ $\displaystyle=\sup_{(t,\lambda)\in
V_{\delta}}\|\partial_{\lambda}F(t,\lambda)\|_{2},$ $\displaystyle M_{t}$
$\displaystyle=\left\|\partial_{t}F(t^{*},\lambda^{*})^{-1}\right\|_{2}.$

The following two lemmas, proved in Sections 4.1.1 and 4.1.2 respectively,
give us values of $\delta_{0}$ and $\delta_{1}$ that define balls around
$t^{*}$ and $\lambda^{*}$ respectively which are included in the balls
required by the quantitative implicit function theorem with radii defined in
(53) and (54).

######  Lemma 5.

(Radius of ball around $t^{*}$) The condition (53) is satisfied if

$\delta_{0}=\frac{\sigma^{2}|q^{\prime\prime}(t^{*})|}{\sqrt{m}\left(4+2c\cdot\frac{\|\lambda^{*}\|_{2}}{\sigma}\right)}.$
(55)

######  Lemma 6.

(Radius of ball around $\lambda^{*}$) For $\delta_{0}$ from Lemma 55 and
$\delta_{1}$ from condition (54), the following choice of $\delta_{\lambda}$:

$\delta_{\lambda}=\frac{\sigma\sqrt{e}|q^{\prime\prime}(t^{*})|}{2\sqrt{2m}}\cdot\delta_{0}$

satisfies $\delta_{\lambda}<\delta_{1}$.

Given the definition of the function $F$ in (51), we have that

$\displaystyle\partial_{t}F(t,\lambda)$
$\displaystyle=\sum_{j=1}^{m}\lambda_{j}\phi^{\prime\prime}(t-s_{j}),$ (56)
$\displaystyle\partial_{\lambda}F(t,\lambda)$
$\displaystyle=[\phi^{\prime}(t-s_{1}),\quad\ldots\quad,\phi^{\prime}(t-s_{m})]^{T}.$
(57)

By applying Taylor expansion to $t(\lambda)$ around $\lambda^{*}$ in the
region defined by $\delta_{0}$ and $\delta_{\lambda}$, we have that

$t(\lambda)=t(\lambda^{*})+\left<\lambda-\lambda^{*},\partial_{\lambda}t(\lambda_{\delta})\right>,$

for some $\lambda_{\delta}$ on the line segment determined by $\lambda^{*}$
and $\lambda$, so

$\displaystyle\left|t(\lambda)-t(\lambda^{*})\right|$
$\displaystyle\leq\left\|\lambda-\lambda^{*}\right\|_{2}\cdot\left\|\partial_{\lambda}t(\lambda_{\delta})\right\|_{2}$
$\displaystyle\leq\frac{\delta_{0}}{\sum_{j=1}^{m}{\lambda_{\delta}}_{j}\phi^{\prime\prime}(t(\lambda_{\delta})-s_{j})}\cdot\left\|\left[\phi^{\prime}(t(\lambda_{\delta})-s_{1}),\quad\ldots\quad,\phi^{\prime}(t(\lambda_{\delta})-s_{m})\right]\right\|_{2},$
(58)

where in the last inequality we used that
$\|\lambda-\lambda^{*}\|\leq\delta_{0}$ and (52). We now need to bound the
terms in (58) for the Gaussian kernel $\phi(t)=e^{-t^{2}/\sigma^{2}}$. First,
we rewrite the last inequality as

$\displaystyle|t(\lambda)-t(\lambda^{*})|$
$\displaystyle\sum_{j=1}^{m}({\lambda_{\delta}}_{j}+\lambda_{j}^{*}-\lambda_{j}^{*})\phi^{\prime\prime}(t(\lambda_{\delta})-s_{j})$
$\displaystyle\leq\delta_{0}\cdot\left\|\left[\phi^{\prime}(t(\lambda_{\delta})-s_{1}),\quad\ldots\quad,\phi^{\prime}(t(\lambda_{\delta})-s_{m})\right]\right\|_{2},$
(59)

we apply the reverse triangle inequality in the sum on the left hand side:

$\displaystyle|t(\lambda)-t(\lambda^{*})|$
$\displaystyle\left[-\left|\sum_{j=1}^{m}({\lambda_{\delta}}_{j}-\lambda_{j}^{*})\phi^{\prime\prime}(t(\lambda_{\delta})-s_{j})\right|+\left|\sum_{j=1}^{m}\lambda_{j}^{*}\phi^{\prime\prime}(t(\lambda_{\delta})-s_{j})\right|\right]$
$\displaystyle\leq\delta_{0}\cdot\left\|\left[\phi^{\prime}(t(\lambda_{\delta})-s_{j})\right]_{j=1}^{m}\right\|_{2}$
(60)

and then we apply the Cauchy-Schwartz inequality to the first sum on the left
hand side above to obtain:

$\displaystyle|t(\lambda)-t(\lambda^{*})|$
$\displaystyle\left[-\left\|\lambda_{\delta}-\lambda^{*}\right\|_{2}\cdot\left\|\left[\phi^{\prime\prime}(t(\lambda_{\delta})-s_{j})\right]_{j=1}^{m}\right\|_{2}+\left|\sum_{j=1}^{m}\lambda_{j}^{*}\phi^{\prime\prime}(t(\lambda_{\delta})-s_{j})\right|\right]$
$\displaystyle\leq\delta_{0}\cdot\left\|\left[\phi^{\prime}(t(\lambda_{\delta})-s_{j})\right]_{j=1}^{m}\right\|_{2}.$
(61)

To simplify the notation, we write $\delta_{t}=|t(\lambda)-t(\lambda^{*})|$
and

$\displaystyle A$
$\displaystyle=\left\|\left[\phi^{\prime\prime}(t(\lambda_{\delta})-s_{j})\right]_{j=1}^{m}\right\|_{2},$
(62) $\displaystyle B$
$\displaystyle=\left|\sum_{j=1}^{m}\lambda_{j}^{*}\phi^{\prime\prime}(t(\lambda_{\delta})-s_{j})\right|,$
(63) $\displaystyle C$
$\displaystyle=\left\|\left[\phi^{\prime}(t(\lambda_{\delta})-s_{j})\right]_{j=1}^{m}\right\|_{2},$
(64)

and by using222 Since $\|\lambda-\lambda^{*}\|\leq\delta_{0}$ and
$\lambda_{\delta}$ is on the line segment between $\lambda^{*}$ and $\lambda$,
then $\lambda_{\delta}$ is in the ball centred at $\lambda^{*}$ with radius
$\delta_{0}$.  $\|\lambda_{\delta}-\lambda^{*}\|_{2}\leq\delta_{0}$, we have
that:

$\delta_{t}(-\delta_{0}A+B)\leq\delta_{0}C,$ (65)

which can be further re-written as:

$\delta_{t}\leq\frac{C+\delta_{t}A}{B}\cdot\delta_{0}.$ (66)

The aim now is to obtain a bound on $\delta_{t}$ as a function of $\delta_{0}$
and the parameters of the problem. Therefore, we need to lower bound $B$ and
upper bound $C+\delta_{t}A$.

#### Bounding A,B,C

We start with $B$, for which we want to calculate a lower bound. First, we
Taylor expand each term of the sum around $t(\lambda^{*})-s_{j}$ as follows:

$\displaystyle B$
$\displaystyle=\left|\sum_{j=1}^{m}\lambda_{j}^{*}\phi^{\prime\prime}(t(\lambda^{*})-s_{j}+t(\lambda_{\delta})-t(\lambda^{*}))\right|$
$\displaystyle=\left|\sum_{j=1}^{m}\lambda_{j}^{*}\phi^{\prime\prime}(t(\lambda^{*})-s_{j})+\left(t(\lambda_{\delta})-t(\lambda^{*})\right)\sum_{j=1}^{m}\lambda_{j}^{*}\phi^{\prime\prime\prime}(\xi_{j})\right|$
(67)
$\displaystyle\geq\left|\sum_{j=1}^{m}\lambda_{j}^{*}\phi^{\prime\prime}(t(\lambda^{*})-s_{j})\right|-\left|t(\lambda_{\delta})-t(\lambda^{*})\right|\left|\sum_{j=1}^{m}\lambda_{j}^{*}\phi^{\prime\prime\prime}(\xi_{j})\right|,$
(68)

where
$\xi_{j}\in\left[t(\lambda^{*})-s_{j}-|t(\lambda_{\delta})-t(\lambda^{*})|,\quad
t(\lambda^{*})-s_{j}+|t(\lambda_{\delta})-t(\lambda^{*})|\right]$ for
$j=1,\ldots,m$, and on the last line we used the reverse triangle inequality.
We calculate an upper bound of the last sum in the previous equation as
follows:

$\displaystyle\left|\sum_{j=1}^{m}\lambda_{j}^{*}\phi^{\prime\prime\prime}(\xi_{j})\right|$
$\displaystyle\leq\left\|\lambda^{*}\right\|_{2}\cdot\left\|\left[\phi^{\prime\prime\prime}(\xi_{j})\right]_{j=1}^{m}\right\|_{2},\quad\quad\text{by
Cauchy-Schwartz,}$ (69)
$\displaystyle\leq\frac{c\|\lambda^{*}\|_{2}\sqrt{m}}{\sigma^{3}},$ (70)

where in the last line we used the maximum value of
$\phi^{\prime\prime\prime}(t)$ and $c$ is a constant.333
$\max_{t\in\mathbb{R}}\phi^{\prime}(t)=\frac{\sqrt{2}}{\sigma\sqrt{e}},\max_{t\in\mathbb{R}}\phi^{\prime\prime}(t)=\frac{2}{\sigma^{2}},\max_{t\in\mathbb{R}}\phi^{\prime\prime\prime}(t)=\frac{c}{\sigma^{3}},\text{
where }c=\frac{4\sqrt{9-3\sqrt{6}}}{e^{\frac{3-\sqrt{6}}{2}}}\approx 3.9036.$

Finally, by using the $\delta_{0}$ from Lemma 55 as a bound on
$|t(\lambda_{\delta})-t(\lambda^{*})|$ and (70), we obtain:

$B\geq|q^{\prime\prime}(t^{*})|\left[1-\frac{c\|\lambda^{*}\|_{2}}{4\sigma+2c\|\lambda^{*}\|_{2}}\right].$
(71)

Note that the last fraction above is subunitary, so the bound is indeed
positive.

Lastly, we upper bound $C+\delta_{t}A$. We bound both $A$ and $C$ using the
upper bounds on $\phi^{\prime}$ and $\phi^{\prime\prime}$ given in footnote 3
and obtain:

$\displaystyle A$ $\displaystyle\leq\frac{2\sqrt{m}}{\sigma^{2}},$ (72)
$\displaystyle C$ $\displaystyle\leq\frac{\sqrt{2m}}{\sigma\sqrt{e}},$ (73)

and for $\delta_{t}$ we use the bound (55). Putting (55), (71), (72) and (73)
together, we obtain:

$\left|t(\lambda)-t(\lambda^{*})\right|\leq
C_{t^{*}}\cdot\left\|\lambda-\lambda^{*}\right\|_{2},$ (74)

where

$C_{t^{*}}=\frac{2\sqrt{2m}\left(2\sigma+c\|\lambda^{*}\|_{2}\right)}{|q^{\prime\prime}(t^{*})|\sigma\sqrt{e}\left(4\sigma+c\|\lambda^{*}\|_{2}\right)}+\frac{2\sigma}{4\sigma+F\|\lambda^{*}\|_{2}},$
(75)

which can also be written in the form in (17) in Theorem 2.

####  4.1.1 Proof of Lemma 55 (Radius $\delta_{0}$ of the ball around $t^{*}$)

Let us now find the radius $\delta_{0}$ which satisfies (53). Using (56), the
expression inside the $\sup$ in (53) is

$E=\left|1-\frac{\sum_{j=1}^{m}\lambda_{j}\phi^{\prime\prime}(t-s_{j})}{\sum_{j=1}^{m}\lambda_{j}^{*}\phi^{\prime\prime}(t^{*}-s_{j})}\right|=\frac{\left|\sum_{j=1}^{m}\lambda_{j}^{*}\phi^{\prime\prime}(t^{*}-s_{j})-\lambda_{j}\phi^{\prime\prime}(t-s_{j})\right|}{\left|\sum_{j=1}^{m}\lambda_{j}^{*}\phi^{\prime\prime}(t^{*}-s_{j})\right|.}$
(76)

By denoting each term in the sum in the numerator in the last equation above
by $T_{j}$ and then adding and subtracting $\lambda_{j}^{*}$ and $t^{*}$, we
obtain:

$\displaystyle T_{j}$
$\displaystyle=\lambda_{j}^{*}\phi^{\prime\prime}(t^{*}-s_{j})-(\lambda_{j}-\lambda_{j}^{*})\phi^{\prime\prime}(t-s_{j})-\lambda_{j}^{*}\phi^{\prime\prime}(t^{*}-s_{j}+t-t^{*})$
$\displaystyle=-(\lambda_{j}-\lambda_{j}^{*})\phi^{\prime\prime}(t-s_{j})-\lambda_{j}^{*}(t-t^{*})\phi^{\prime\prime\prime}(\xi_{j}),$
(77)

for some $\xi_{j}\in\left[t^{*}-s_{j}-|t-t^{*}|,t^{*}-s_{j}+|t-t^{*}|\right]$.
Then:

$\displaystyle E$
$\displaystyle\leq\frac{\left|\sum_{j=1}^{m}(\lambda_{j}-\lambda_{j}^{*})\phi^{\prime\prime}(t-s_{j})\right|+\left|\sum_{j=1}^{m}\lambda_{j}^{*}(t-t^{*})\phi^{\prime\prime\prime}(\xi_{j})\right|}{\left|\sum_{j=1}^{m}\lambda_{j}^{*}\phi^{\prime\prime}(t^{*}-s_{j})\right|}$
$\displaystyle\leq\frac{\left\|\lambda-\lambda^{*}\right\|_{2}\left\|\left[\phi^{\prime\prime}(t-s_{j})\right]_{j=1}^{m}\right\|_{2}+\left|t-t^{*}\right|\left|\sum_{j=1}^{m}\lambda_{j}^{*}\phi^{\prime\prime\prime}(\xi_{j})\right|}{\left|\sum_{j=1}^{m}\lambda_{j}^{*}\phi^{\prime\prime}(t^{*}-s_{j})\right|}=E^{\prime}$
(78)

We now have that

$\displaystyle\sup_{(t,\lambda)\in V_{\delta_{0}}}E$
$\displaystyle\leq\sup_{\begin{subarray}{c}|t-t^{*}|\leq\delta_{0},\\\
\|\lambda-\lambda^{*}\|\leq\delta_{0}\end{subarray}}E^{\prime}$ (79)
$\displaystyle\leq\delta_{0}\cdot\frac{\left\|\left[\phi^{\prime\prime}(t-s_{j})\right]_{j=1}^{m}\right\|_{2}+\left|\sum_{j=1}^{m}\lambda_{j}^{*}\phi^{\prime\prime\prime}(\xi_{j})\right|}{\left|\sum_{j=1}^{m}\lambda_{j}^{*}\phi^{\prime\prime}(t^{*}-s_{j})\right|}.$
(80)

We now further upper bound the fraction on the last line of the previous
equation. The terms in the numerator are bounded by taking the maxima of the
functions $\phi^{\prime\prime}$ and $\phi^{\prime\prime\prime}$ from footnote
3 respectively:

$\left\|\left[\phi^{\prime\prime}(t-s_{j})\right]_{j=1}^{m}\right\|_{2}=\sqrt{\sum_{j=1}^{m}\phi^{\prime\prime}(t-s_{j})^{2}}\leq\sqrt{m\cdot\max_{j}|\phi^{\prime\prime}(t-s_{j})|^{2}}\leq\frac{2\sqrt{m}}{\sigma^{2}}$
(81)

and

$\displaystyle\left|\sum_{j=1}^{m}\lambda_{j}^{*}\phi^{\prime\prime\prime}(\xi_{j})\right|$
$\displaystyle\leq\|\lambda^{*}\|_{2}\left\|\left[\phi^{\prime\prime\prime}(\xi_{j})\right]_{j=1}^{m}\right\|_{2}\quad\quad\text{by
Cauchy-Schwartz}$ (82)
$\displaystyle=\|\lambda^{*}\|_{2}\sqrt{\sum_{j=1}^{m}\phi^{\prime\prime\prime}(\xi_{j})^{2}}$
(83)
$\displaystyle\leq\|\lambda^{*}\|_{2}\max_{j}|\phi^{\prime\prime\prime}(\xi_{j})|\sqrt{m}$
(84) $\displaystyle=c\cdot\frac{\|\lambda^{*}\|_{2}\sqrt{m}}{\sigma^{3}},$
(85)

where $c=\frac{4\sqrt{9-3\sqrt{6}}}{e^{\frac{3-\sqrt{6}}{2}}}\approx 3.9036$.
By writing

$q(t)=\sum_{j=1}^{m}\lambda_{j}^{*}\phi(t-s_{j})$ (86)

and using the above bounds, we have that

$\sup_{(t,\lambda)\in
V_{\delta_{0}}}E\leq\delta_{0}\cdot\frac{\frac{2\sqrt{m}}{\sigma^{2}}+c\cdot\frac{\|\lambda^{*}\|_{2}\sqrt{m}}{\sigma^{3}}}{\left|q^{\prime\prime}(t^{*})\right|}$
(87)

Finally, in order to satisfy condition (53), we need to impose the condition
that the right hand side of (87) is less than or equal to $\frac{1}{2}$. We
select $\delta_{0}$ to be the largest value that satisfies this, so:

$|t-t^{*}|\leq\delta_{0}=\frac{\left|q^{\prime\prime}(t^{*})\right|}{\frac{4\sqrt{m}}{\sigma^{2}}+2c\cdot\frac{\|\lambda^{*}\|_{2}\sqrt{m}}{\sigma^{3}}}=\frac{\sigma^{2}|q^{\prime\prime}(t^{*})|}{\sqrt{m}\left(4+2c\cdot\frac{\|\lambda^{*}\|_{2}}{\sigma}\right)}.$
(88)

####  4.1.2 Proof of Lemma 6 (Radius $\delta_{\lambda}$ of the ball around
$\lambda^{*}$)

The radius $\delta_{\lambda}$ of the perturbation of $\lambda^{*}$ is given
by:

$\delta_{\lambda}=(2M_{t}B_{\lambda})^{-1}\delta_{0},$ (89)

where

$\displaystyle B_{\lambda}$ $\displaystyle=\sup_{(t,\lambda)\in
V_{\delta}}\|\partial_{\lambda}F(t,\lambda)\|_{2},$ (90) $\displaystyle M_{t}$
$\displaystyle=\left\|\partial_{t}F(t^{*},\lambda^{*})^{-1}\right\|_{2}.$ (91)

For $B_{\lambda}$, we have:

$\displaystyle\|\partial_{\lambda}F(t,\lambda)\|_{2}=\sqrt{\sum_{j=1}^{m}\phi^{\prime}(t-s_{j})^{2}}\leq\frac{\sqrt{2m}}{\sigma\sqrt{e}},$
(92)

where we have used the global maximum of the first derivative of the Gaussian
from footnote 3, so by taking $\sup$ on both sides in the last equation, we
obtain:

$B_{\lambda}\leq\frac{\sqrt{2m}}{\sigma\sqrt{e}}.$ (93)

Note that here we do not use any assumptions on the locations of the sources
$t_{i}$ and the samples $s_{j}$. If we did, we would be able to obtain a
tighter bound than by only using the absolute maximum of the function.

For $M_{t}$, note that we have

$M_{t}=|q^{\prime\prime}(t^{*})|^{-1},$ (94)

where $q(t)$ is defined in (86), so

$(2M_{t}B_{\lambda})^{-1}\delta_{0}\geq\frac{\sigma\sqrt{e}|q^{\prime\prime}(t^{*})|}{2\sqrt{2m}}\cdot\delta_{0},$
(95)

We then take $\delta_{\lambda}$ to be equal to the lower bound in the equation
above:

$\delta_{\lambda}=\frac{\sigma\sqrt{e}|q^{\prime\prime}(t^{*})|}{2\sqrt{2m}}\cdot\delta_{0},$
(96)

and, after substituting our choice of $\delta_{0}$ from (55), we obtain the
radius (15) in Theorem 2.

###  4.2 Proof of Theorem 3 (Dependence of
$\|\mathbf{\tilde{a}}-\mathbf{a^{*}}\|_{2}$ on
$\|\mathbf{\tilde{t}}-\mathbf{t^{*}}\|_{2}$)

We apply equation (4.2) in [28], with $e=0$ (the noise in the observations),
and obtain

$\mathbf{\tilde{a}}=\mathbf{a^{*}}-\Phi^{\dagger}E\mathbf{a^{*}}-F^{T}E\mathbf{a^{*}},$
(97)

where $\Phi^{\dagger}=(\Phi^{T}\Phi)^{-1}\Phi^{T}$ is the pseudo-inverse of
$\Phi$ and $F=O(E)$ is the perturbation of the $\Phi^{\dagger}$ due to the
perturbation $E$ of $\Phi$, namely

$\tilde{\Phi}^{\dagger}=\Phi^{\dagger}+F^{T}.$

In order to obtain an explicit expression for $F$, we write
$\tilde{\Phi}^{\dagger}$:

$\displaystyle\tilde{\Phi}^{\dagger}$
$\displaystyle=(\tilde{\Phi}^{T}\tilde{\Phi})^{-1}\tilde{\Phi}^{T}$
$\displaystyle=\left[(\Phi+E)^{T}(\Phi+E)\right]^{-1}(\Phi+E)^{T}\quad\quad\text{by
}\eqref{eq:phi tilde def}$
$\displaystyle=(\Phi^{T}\Phi+\Delta)^{-1}(\Phi^{T}+E^{T}),$ (98)

where

$\Delta=E^{T}\Phi+\Phi^{T}E+E^{T}E\in\mathbb{R}^{k\times k}.$ (99)

In order to compute the first factor in (98), consider the QR decomposition of
$\Phi$:

$\Phi=QR,\quad\text{where}\quad Q\in\mathbb{R}^{m\times k}\quad\text{and}\quad
R\in\mathbb{R}^{k\times k},$ (100)

with $Q^{T}Q=I_{k}$ $R$ upper triangular. We have that:

$\displaystyle\Phi^{\dagger}$ $\displaystyle=R^{-1}Q^{T},$ (101)
$\displaystyle\Phi^{T}\Phi$ $\displaystyle=R^{T}R.$ (102)

We then write the first factor in (98) as

$\displaystyle(\Phi^{T}\Phi+\Delta)^{-1}$ $\displaystyle=(R^{T}R+\Delta)^{-1}$
$\displaystyle=\left[R^{T}\left(I+R^{-T}\Delta R^{-1}\right)R\right]^{-1}$
$\displaystyle=R^{-1}\left[I+\sum_{l=1}^{\infty}(-1)^{l}\left(R^{-T}\Delta
R^{-1}\right)^{l}\right]R^{-T}$ $\displaystyle=(R^{T}R)^{-1}+S_{\Phi}$
$\displaystyle=(\Phi^{T}\Phi)^{-1}+S_{\Phi},$ (103)

where

$S_{\Phi}=R^{-1}\left[\sum_{l=1}^{\infty}(-1)^{l}\left(R^{-T}\Delta
R^{-1}\right)^{l}\right]R^{-T}\in\mathbb{R}^{k\times k},$ (104)

and in the second inequality in (103) we applied the Neumann series expansion
to the matrix $I-R^{-T}\Delta R^{-1}$, which converges if

$\|-R^{-T}\Delta R^{-1}\|_{2}<1.$ (105)

We will return to condition (105) at the end of this section. We now
substitute (103) in (98), giving

$\displaystyle\tilde{\Phi}^{\dagger}$
$\displaystyle=\left[(\Phi^{T}\Phi)^{-1}+S_{\Phi}\right](\Phi^{T}+E^{T})$
$\displaystyle=\Phi^{\dagger}+(\Phi^{T}\Phi)^{-1}E^{T}+S_{\Phi}\Phi^{T}+S_{\Phi}E^{T},$

so we have that

$F^{T}=(\Phi^{T}\Phi)^{-1}E^{T}+S_{\Phi}\Phi^{T}+S_{\Phi}E^{T},$ (106)

which is indeed $O(E)$, since $S_{\Phi}=O(\Delta)$ and $\Delta=O(E)$. We next
upper bound $\|S_{\Phi}\|_{2}$. Firstly, note that, because
$\Phi^{\dagger}=\left(QR^{-1}\right)^{T}$, we have that:444 To see the second
equality in (108), for a matrix $Q\in\mathbb{R}^{m\times k}$ with $Q^{T}Q=I$
and any matrix $A\in\mathbb{R}^{k\times k}$ we have that
$\|QA\|_{2}=\sup_{\|v\|_{2}=1}\|QAv\|_{2}=\sup_{\|v\|_{2}=1}\|Av\|_{2}=\|A\|_{2},$
since  $\|QAv\|_{2}^{2}=v^{T}A^{T}Q^{T}QAv=v^{T}A^{T}Av=\|Av\|_{2}^{2}.$ (107)

$\displaystyle\|\Phi^{\dagger}\|_{2}=\|QR^{-1}\|_{2}=\|R^{-1}\|_{2}.$ (108)

Then, by using (108), norm submultiplicativity and triangle inequality, from
(104) we have

$\|S_{\Phi}\|_{2}\leq\|\Phi^{\dagger}\|^{2}_{2}\sum_{l=1}^{\infty}\|\Phi^{\dagger}\|^{2l}_{2}\|\Delta\|^{l}_{2}.$
(109)

Now let $D$ be an upper bound on $\|\Delta\|_{2}$, obtained by applying the
triangle inequality in (99), so that

$\|\Delta\|_{2}\leq D=2\|E\|_{2}\|\Phi\|_{2}+\|E\|^{2}_{2}.$ (110)

Then, from (109) we have

$\displaystyle\|S_{\Phi}\|_{2}$
$\displaystyle\leq\|\Phi^{\dagger}\|^{2}_{2}\sum_{l=1}^{\infty}\|\Phi^{\dagger}\|^{2l}_{2}D^{l}$
$\displaystyle=\|\Phi^{\dagger}\|^{2}_{2}\left(\frac{1}{1-D\|\Phi^{\dagger}\|^{2}_{2}}-1\right)=\frac{D\|\Phi^{\dagger}\|^{4}_{2}}{1-D\|\Phi^{\dagger}\|^{2}_{2}},$
(111)

where the series converges if $D\|\Phi^{\dagger}\|_{2}^{2}<1$, in which case
the denominator in the last fraction above is positive. We return to this
condition at the end of the section. We also know that555 Using the SVD
$\Phi=U\Sigma V^{T}$, we have
$\Phi^{\dagger}=(\Phi^{T}\Phi)^{-1}\Phi^{T}=(V\Sigma^{2}V^{T})^{-1}V\Sigma
U^{T}=V\Sigma^{-1}U^{T}$, so the conclusion follows.

$\|\Phi^{\dagger}\|_{2}=\frac{1}{\sigma_{\min}(\Phi)}.$ (112)

By applying triangle inequality in (106) and then using (111) and the fact
that
$\|(\Phi^{T}\Phi)^{-1}\|_{2}=1/\sigma_{\min}^{2}(\Phi)=\|\Phi^{\dagger}\|_{2}^{2}$
(from (112)), we obtain

$\|F\|_{2}\leq\|E\|_{2}\|\Phi^{\dagger}\|_{2}^{2}+\frac{D\|\Phi^{\dagger}\|^{4}_{2}}{1-D\|\Phi^{\dagger}\|^{2}_{2}}\left(\|\Phi\|_{2}+\|E\|_{2}\right),$
(113)

where $D$ is given in (110). It remains to establish an upper bound on
$\|E\|_{F}$, and consequently on $\|E\|_{2}$. The following lemma gives us
such a bound.

######  Lemma 7.

(Upper bound on $\|E\|_{F})$ Let $E=\tilde{\Phi}-\Phi$ for $\Phi$ and
$\tilde{\Phi}$ as defined in (19) and (20) respectively for
$t_{j},\tilde{t}_{j}\in[0,1]$ for $j=1,\ldots,k$. Then:

$\|E\|_{F}\leq\frac{4e^{\frac{4}{\sigma^{2}}}\sqrt{m}}{\sigma^{2}}\|\mathbf{\tilde{t}}-\mathbf{t^{*}}\|_{2}.$
(114)

By using triangle inequality and norm submultiplicativity in (97), and then
substituting (113) and (114), we obtain

$\displaystyle\|\mathbf{a^{*}}-\mathbf{\tilde{a}}\|_{2}$
$\displaystyle\leq\|E\|_{2}\|\Phi^{\dagger}\|_{2}\|\mathbf{a^{*}}\|_{2}+\|E\|_{2}^{2}\|\Phi^{\dagger}\|_{2}^{2}\|\mathbf{a^{*}}\|_{2}$
$\displaystyle\qquad+\frac{\|E\|_{2}D\|\Phi^{\dagger}\|_{2}^{4}}{1-D\|\Phi^{\dagger}\|_{2}^{2}}(\|\Phi\|_{2}+\|E\|_{2})\|\mathbf{a^{*}}\|_{2}$
$\displaystyle\leq\frac{4e^{\frac{4}{\sigma^{2}}}\sqrt{m}\|\mathbf{a^{*}}\|_{2}}{\sigma^{2}\sigma_{\min}(\Phi)}\|\mathbf{\tilde{t}}-\mathbf{t^{*}}\|_{2}+O(\|\mathbf{\tilde{t}}-\mathbf{t^{*}}\|_{2}^{2}),$
(115)

which is the bound given in Theorem 3. Note that because
$\|E\|_{2}=O(\|\tilde{\mathbf{t}}-\mathbf{t^{*}}\|_{2})$ (see (114)), the
first term is the only term that is
$O(\|\tilde{\mathbf{t}}-\mathbf{t^{*}}\|_{2})$ in the first inequality above,
so the other terms are included in the
$O(\|\tilde{\mathbf{t}}-\mathbf{t^{*}}\|_{2}^{2})$ term at the end.

Lastly, we return to condition (105), which must be satisfied in order for the
bound above to hold. By using norm submultiplicativity and the bound on
$\|\Delta\|_{2}$ from (110), we obtain

$\|{\Phi^{\dagger}}^{T}\Delta\Phi^{\dagger}\|_{2}\leq\|\Phi^{\dagger}\|^{2}_{2}\|E\|^{2}_{2}+2\|\Phi\|_{2}\|\Phi^{\dagger}\|^{2}_{2}\|E\|_{2}$
(116)

and by requiring that the right hand side above is less than one, we obtain a
quadratic constraint on $\|E\|_{2}$, satisfied if

$\|E\|_{2}<\sigma_{\max}(\Phi)\left(\sqrt{1+\frac{\sigma^{2}_{\min}(\Phi)}{\sigma^{2}_{\max}(\Phi)}}-1\right).$

By using the bound on $\|E\|_{2}$ from (114), the above holds if (22) holds.
Note that by imposing this, we also ensure that the condition for the series
in (111) to converge holds, since $D\|\Phi^{\dagger}\|_{2}^{2}$ is equal to
the right hand side of (116).

####  4.2.1 Proof of Lemma 114 (Bound of $\|E\|_{F}$)

Since $E=\tilde{\Phi}-\Phi$, for $\tilde{t}_{j}$ being a perturbation of
$t_{j}$, we have that

$|E_{ij}|=\left|e^{-\frac{(s_{i}-\tilde{t}_{j})^{2}}{\sigma^{2}}}-e^{-\frac{(s_{i}-t_{j})^{2}}{\sigma^{2}}}\right|=e^{-\frac{(s_{i}-t_{j})^{2}}{\sigma^{2}}}\left|e^{\frac{1}{\sigma^{2}}\left[(s_{i}-t_{j})^{2}-(s_{i}-\tilde{t}_{j})^{2}\right]}-1\right|.$

Then the exponent can be written as

$\left|\frac{1}{\sigma^{2}}\left[(s_{i}-t_{j})^{2}-(s_{i}-\tilde{t}_{j})^{2}\right]\right|=\left|\frac{1}{\sigma^{2}}\left[2s_{i}(\tilde{t}_{j}-t_{j})+(t_{j}+\tilde{t}_{j})(t_{j}-\tilde{t}_{j})\right]\right|\leq\frac{4|\tilde{t}_{j}-t_{j}|}{\sigma^{2}},$

where we used that $s_{i},\tilde{t}_{j},t_{j}\in[0,1]$, so

$e^{-\frac{4}{\sigma^{2}}|\tilde{t}_{j}-t_{j}|}\leq
e^{\frac{1}{\sigma^{2}}\left[(s_{i}-t_{j})^{2}-(s_{i}-\tilde{t}_{j})^{2}\right]}\leq
e^{\frac{4}{\sigma^{2}}{|\tilde{t}_{j}-t_{j}|}},$

which implies that

$\displaystyle|E_{ij}|$
$\displaystyle\leq\left|e^{\frac{1}{\sigma^{2}}\left[(s_{i}-t_{j})^{2}-(s_{i}-\tilde{t}_{j})^{2}\right]}-1\right|$
$\displaystyle\leq\max\left\\{1-e^{-\frac{4}{\sigma^{2}}|\tilde{t}_{j}-t_{j}|},e^{\frac{4}{\sigma^{2}}|\tilde{t}_{j}-t_{j}|}-1\right\\}$
$\displaystyle=e^{\frac{4}{\sigma^{2}}|\tilde{t}_{j}-t_{j}|}-1$
$\displaystyle=\frac{4}{\sigma^{2}}|\tilde{t}_{j}-t_{j}|\cdot e^{\xi},$

for some
$\xi\in\left[-\frac{4}{\sigma^{2}}|\tilde{t}_{j}-t_{j}|,\frac{4}{\sigma^{2}}|\tilde{t}_{j}-t_{j}|\right]$
and where in the first inequality we have used that
$e^{-\frac{(s_{i}-t_{j})^{2}}{\sigma^{2}}}\leq 1$. Then

$\displaystyle|E_{ij}|$
$\displaystyle\leq\frac{4}{\sigma^{2}}|\tilde{t}_{j}-t_{j}|\cdot
e^{\frac{4}{\sigma^{2}}|\tilde{t}_{j}-t_{j}|}\leq\frac{4e^{\frac{4}{\sigma^{2}}}}{\sigma^{2}}|\tilde{t}_{j}-t_{j}|,$

where the last inequality holds if $\tilde{t}_{j},t_{j}\in[0,1]$. We can
therefore conclude that

$\displaystyle\|E\|_{2}\leq\|E\|_{F}$
$\displaystyle\leq\sqrt{\sum_{i=1}^{m}\sum_{j=1}^{k}\left(\frac{4e^{\frac{4}{\sigma^{2}}}}{\sigma^{2}}\right)^{2}|\tilde{t}_{j}-t_{j}|^{2}}$
$\displaystyle=\frac{4e^{\frac{4}{\sigma^{2}}}\sqrt{m}}{\sigma^{2}}\|\mathbf{\tilde{t}}-\mathbf{t^{*}}\|_{2},$
(117)

provided that $\tilde{t}_{j},t_{j}\in[0,1]$ for all $j=1,\ldots,k$.

###  4.3 Proof of Theorem 4 (Dependence of $\|\lambda-\lambda^{*}\|_{2}$ on
the noise $w$)

We apply the quantitative implicit function theorem to the function $\bar{F}$
defined in (35). However, in order to simplify the notation, we use
$F,\lambda,w$ instead of $\bar{F},\bar{\lambda},\bar{w}$ respectively
throughout this proof. The partial derivatives of $F$ are:

$\displaystyle\partial_{\lambda_{l}}F_{j}$
$\displaystyle=-\sum_{i=1}^{k}\nu_{i}\phi^{\prime}(t_{i}(\lambda)-s_{j})\partial_{\lambda_{l}}t_{i}(\lambda)\quad
l=1,\ldots,k,\quad j=1,\ldots,2k,$ (118)
$\displaystyle\partial_{\nu_{l}}F_{j}$
$\displaystyle=-\phi(t_{l}(\lambda)-s_{j}),\quad l=1,\ldots,k,\quad
j=1,\ldots,2k,$ (119) $\displaystyle\partial_{w_{l}}F_{j}$
$\displaystyle=\begin{cases}1,\quad\text{if}\quad l=j,\\\
0,\quad\text{otherwise},\end{cases}\quad l,j=1,\ldots,2k.$ (120)

Let $\gamma=[\lambda,\nu]^{T}$ and $\gamma^{*}=[\lambda^{*},a]^{T}$, so that
we can write $F([\lambda,\nu]^{T},w)$ as $F(\gamma,w)$ and
$F(\gamma^{*},0)=0$. In order to apply the implicit function theorem, the
following conditions must be satisfied:

  1. 1.

$\partial_{\gamma}F(\gamma^{*},0)$ is invertible,

  2. 2.

We choose the radius $\delta_{\gamma}$ of the ball $V_{\delta_{\gamma}}$
around $\gamma$ where the result of the quantitative implicit function theorem
holds:

$\sup_{(\gamma,w)\in
V_{\delta_{\gamma}}}\left\|I-\left[\partial_{\gamma}F(\gamma^{*},0)\right]^{-1}\partial_{\gamma}F(\gamma,w)\right\|_{2}\leq\frac{1}{2},$
(121)

  3. 3.

The radius $\delta_{w}$ of the ball around $w^{*}=0$ that contains $w$ is:

$\delta_{w}=(2M_{w}B_{\delta_{\gamma}})^{-1}\delta_{\gamma},$ (122)

where

$\displaystyle B_{\delta_{\gamma}}$ $\displaystyle=\sup_{(\gamma,w)\in
V_{\delta_{\gamma}}}\|\partial_{w}F(\gamma,w)\|_{2},$ (123) $\displaystyle
M_{w}$ $\displaystyle=\|\partial_{\gamma}F(\gamma^{*},0)^{-1}\|_{2}.$ (124)

The first condition is also one of the conditions in the theorem, and it has
been discussed in Section 3.1. We now need to establish the two radii for the
balls of the perturbations.

#### Perturbation radii

Before proceeding to calculating the radii of the balls where the implicit
function theorem holds, we need to state the following lemma, which allows us
to write the Jacobian of $F$ with respect to the first variable as a sum of
the Jacobian evaluated at $(\gamma^{*},w^{*})=([\lambda^{*},a]^{T},0)$ and a
perturbation matrix, whose norm is bounded explicitly. The proof of Lemma 8 is
given in Section 4.3.2.

######  Lemma 8.

(Bound on the perturbation of the Jacobian of $F$) Let $J(\lambda,\nu,w)$ be
the Jacobian of $F(\gamma,w)$ with respect to $\gamma=[\lambda,\nu]^{T}$ and
$\delta_{\gamma}$ an upper bound on the perturbation of
$\gamma^{*}=[\lambda^{*},a]^{T}$, namely:

$\left\|\begin{bmatrix}\lambda-\lambda^{*}\\\
\nu-a\end{bmatrix}\right\|_{2}\leq\delta_{\gamma}.$

Then:

$J(\lambda,\nu,w)=J(\lambda^{*},a,0)+E,$ (125)

with

$\|E\|_{F}\leq P(k,\sigma,\Pi,\tau,C_{t^{*}})\cdot\delta_{\gamma},$ (126)

where:

$\displaystyle P(k,\sigma,\Pi,$
$\displaystyle\tau,C_{t^{*}})=\sqrt{2}k\Bigg{[}\frac{1}{\sigma^{2}}\left(2\sqrt{k}C_{t^{*}}^{2}\Pi+4kC_{t^{*}}\bar{\Delta}_{2}\tau\Pi+2C_{t^{*}}\right)$
$\displaystyle+\frac{1}{\sigma}\left(\frac{\sqrt{2k}C_{t^{*}}}{\sqrt{e}}+4\sqrt{k}C_{t^{*}}^{2}\Pi+\frac{2\sqrt{2}\bar{\Delta}_{2}\Pi}{\sqrt{e}}+8kC_{t^{*}}\bar{\Delta}_{2}\tau\Pi+\frac{\sqrt{2k}\bar{\Delta}_{2}\Pi}{\sqrt{e}}\right)\Bigg{]},$
(127)

for $\|\lambda-\lambda^{*}\|\leq\delta_{\lambda}$, where $\delta_{\lambda}$
and $C_{t^{*}}$ are given in (15) and (17) respectively in Theorem 2 and
$\bar{\Delta}_{2}$ is given in (163) in the proof.

We can now use Lemma 8 to write

$\partial_{\gamma}F(\gamma,w)=\partial_{\gamma}F(\gamma^{*},0)+E,$ (128)

then

$\displaystyle
I-\left[\partial_{\gamma}F(\gamma^{*},0)\right]^{-1}\partial_{\gamma}F(\gamma,w)$
$\displaystyle=I-\left[\partial_{\gamma}F(\gamma^{*},0)\right]^{-1}\left[\partial_{\gamma}F(\gamma^{*},0)+E\right]$
$\displaystyle=-\left[\partial_{\gamma}F(\gamma^{*},0)\right]^{-1}E,$ (129)

so

$\displaystyle\left\|I-\left[\partial_{\gamma}F(\gamma^{*},0)\right]^{-1}\partial_{\gamma}F(\gamma,w)\right\|_{2}$
$\displaystyle\leq\left\|\left[\partial_{\gamma}F(\gamma^{*},0)\right]^{-1}\right\|_{2}\cdot\|E\|_{F}$
$\displaystyle\leq\frac{\|E\|_{F}}{\sigma_{\min}(\partial_{\gamma}F(\gamma^{*},0))}$
$\displaystyle\leq\frac{P(k,\sigma,\Pi,\tau,C_{t^{*}})}{\sigma_{\min}(\partial_{\gamma}F(\gamma^{*},0))}\cdot\delta_{\gamma},$
(130)

where $P\cdot\delta_{\gamma}$ is the upper bound on $\|E\|_{F}$ given in
(127).

Therefore, from the condition that the right-hand side of the last inequality
is less than or equal to $\frac{1}{2}$, we choose the radius $\delta_{\gamma}$
to be:

$\delta_{\gamma}=\frac{\sigma_{\min}(\partial_{\gamma}F(\gamma^{*},0))}{2P(k,\sigma,\Pi,\tau,C_{t^{*}})}.$
(131)

Using (120), we have that

$B_{\delta_{\gamma}}=1.$ (132)

Then

$M_{w}=\frac{1}{\sigma_{\min}(\partial_{\gamma}F(\gamma^{*},0))},$ (133)

so, using (131), we obtain

$\delta_{w}=\frac{\sigma_{\min}(\partial_{\gamma}F(\gamma^{*},0))^{2}}{4P(k,\sigma,\Pi,\tau,C_{t^{*}})}.$
(134)

#### Applying the quantitative implicit function theorem

Having calculated the radii where the quantitative implicit function theorem
holds, we apply it to obtain:

$\partial_{w}g(w)=-\left[\partial_{1}F(g(w),w)\right]^{-1},$ (135)

where $\partial_{1}$ is the partial derivative with respect with the first
argument and $g(w)$ gives the dependence of $[\lambda,\nu]^{T}$ on $w$.
Specifically, we write:

$\displaystyle\lambda_{i}(w)=g_{i}(w)\quad\text{ for }\quad i=1,\ldots,k,$
(136) $\displaystyle\nu_{i}(w)=g_{k+i}(w)\quad\text{ for }\quad i=1,\ldots,k.$
(137)

Let $J(\lambda,\nu,w)=\partial_{1}F([\lambda,\nu]^{T},w)$, where
$\lambda=\lambda(w)$ and $\nu=\nu(w)$ by (136) and (137). Lemma 8 gives

$J(\lambda,\nu,w)=J(\lambda^{*},a,0)+E,$ (138)

so $E$ is the perturbation of $J(\lambda^{*},a,0)$ due to perturbed
$\lambda,\nu,w$ and a bound on $\|E\|_{F}$ is given in the lemma.

We will now use the following result, proved in Section 4.3.1, which enables
us to make use of the upper bound on the norm of the perturbation given by
Lemma 8 in order to lower bound the smallest singular value of $J$.

######  Lemma 9.

Let $J\in\mathbb{R}^{m\times n}$. If $J=A+E$, then

$\sigma_{\min}(J)\geq\sigma_{\min}(A)-\|E\|_{F}.$

By applying Lemma 9, we have that:

$\displaystyle\frac{1}{\sigma_{\min}(J(\lambda,\nu,w))}$
$\displaystyle\leq\frac{1}{\sigma_{\min}(J(\lambda^{*},a,0))-\|E\|_{F}}=\frac{1}{\sigma_{\min}(J(\lambda^{*},a,0))\left(1-\frac{\|E\|_{F}}{\sigma_{\min}(J(\lambda^{*},a,0))}\right)}$
$\displaystyle\leq\frac{1}{\sigma_{\min}(J(\lambda^{*},a,0))}\cdot\left(1+\frac{2\|E\|_{F}}{\sigma_{\min}(J(\lambda^{*},a,0))}\right),$
(139)

for

$\frac{\|E\|_{F}}{\sigma_{\min}(J(\lambda^{*},a,0))}\leq\frac{1}{2},$ (140)

where we used the fact that $(1-x)^{-1}\leq 1+2x$ for $x\in[0,\frac{1}{2}]$.
Note that the condition above is the same as the condition that the right hand
side of (130) is less than or equal to $\frac{1}{2}$, which is satisfied for
our choice of $\delta_{\gamma}$ and $\delta_{w}$.

From (135) and (139), we have that:

$\displaystyle\|\partial_{w}g(w)\|_{2}$
$\displaystyle=\frac{1}{\sigma_{\min}(J(\lambda^{*},a,0)+E)}$
$\displaystyle\leq\frac{1}{\sigma_{\min}(J(\lambda^{*},a,0))}\left(1+\frac{2}{\sigma_{\min}(J(\lambda^{*},a,0))}\cdot\|E\|_{F}\right)$
$\displaystyle\leq\frac{2}{\sigma_{\min}(J(\lambda^{*},a,0))},$ (141)

where $\|E\|_{F}$ is upper bounded in (127) and $w$, $\lambda$ and $\nu$
satisfy

$\|w\|_{2}\leq\delta_{w},\quad\|\lambda-\lambda^{*}\|_{2}\leq\leavevmode\nobreak\
\delta_{\gamma},\quad\|\nu-a\|_{2}\leq\delta_{\gamma}.$

The first-order Taylor expansion of $g(w)$ around $w=0$ is:

$g(w)=g(0)+\partial_{w}g(w_{\delta})^{T}w,$ (142)

for some $w_{\delta}$ on the segment between the zero vector and $w$. Noting
that $g(w)$ is our notation for the vector:

$g(w)=\begin{bmatrix}\lambda(w)\\\ \nu(w)\end{bmatrix},$ (143)

with $\lambda(0)=\lambda^{*}$ and $\nu(0)=a$, from (142) we have that:

$\displaystyle\left\|\begin{bmatrix}\lambda(w)-\lambda^{*}\\\
\nu(w)-a\end{bmatrix}\right\|_{2}$
$\displaystyle=\left\|\partial_{w}g(w_{\delta})^{T}w\right\|_{2}$
$\displaystyle\leq\|\partial_{w}g(w_{\delta})\|_{2}\cdot\|w\|_{2},$ (144)

for $w$, $\lambda$ and $\nu$ such that

$\|w\|_{2}\leq\delta_{w},\quad\|\lambda-\lambda^{*}\|_{2}\leq\delta_{\gamma},\quad\|\nu-a\|_{2}\leq\delta_{\gamma},$

where we use the bound from (141).

####  4.3.1 Proof of Lemma 9

We have that

$\displaystyle\sigma(J)$
$\displaystyle=\min_{\|v\|_{2}=1}\max_{\|u\|_{2}=1}u^{T}(A+E)v$
$\displaystyle\geq\min_{\|v\|_{2}=1}\max_{\|u\|_{2}=1}u^{T}Av-\max_{\|v\|_{2}=1}\max_{\|u\|_{2}=1}u^{T}Ev$
$\displaystyle\geq\sigma_{\min}(A)-\|E\|_{F}.$

####  4.3.2 Proof of Lemma 8 (Bound on the perturbation of the Jacobian of
$F$)

Let $J(\lambda,\nu,w)=\partial_{1}F([\lambda,\nu]^{T},w)$, where
$\lambda=\lambda(w)$ and $\nu=\nu(w)$ by (136) and (137), and we want to write
$J$ in the form

$J(\lambda,\nu,w)=J(\lambda^{*},a,0)+E$ (145)

i.e. $E$ is the perturbation of $J(\lambda^{*},a,0)$ due to perturbed
$\lambda,\nu,w$. In order to apply Lemma 9, we need an upper bound on
$\|E\|_{F}$, so we need to upper bound each entry of $E$. Let

$J=\left[J_{1}J_{2}\right],$ (146)

where $J_{1}$ corresponds to the terms (118) and $J_{2}$ to the terms (119)
and

$E=\left[E_{1}E_{2}\right]$ (147)

the corresponding perturbation terms.

### Entries in $J_{1}$

For $i=1,\ldots,k$ and $j=1,\ldots,2k$:

$\displaystyle J_{1_{j,i}}$
$\displaystyle=-\sum_{p=1}^{k}(\nu_{p}-a_{p}+a_{p})\phi^{\prime}(t_{p}(\lambda)-t_{p}^{*}+t_{p}^{*}-s_{j})\partial_{\lambda_{i}}t_{p}(\lambda)$
$\displaystyle=-\sum_{p=1}^{k}\partial_{\lambda_{i}}t_{p}(\lambda)\left[a_{p}\phi^{\prime}(t_{p}^{*}-s_{j}+t_{p}(\lambda)-t_{p}^{*})+(\nu_{p}-a_{p})\phi^{\prime}(t_{p}^{*}-s_{j}+t_{p}(\lambda)-t_{p}^{*})\right]$
$\displaystyle=-\sum_{p=1}^{k}\partial_{\lambda_{i}}t_{p}(\lambda)\big{[}a_{p}\phi^{\prime}(t_{p}^{*}-s_{j})+a_{p}(t_{p}(\lambda)-t_{p}^{*})\phi^{\prime\prime}(\xi_{j,p})+(\nu_{p}-a_{p})\phi^{\prime}(t_{p}^{*}-s_{j})$
$\displaystyle\quad+(\nu_{p}-a_{p})(t_{p}(\lambda)-t_{p}^{*})\phi^{\prime\prime}(\xi_{j,p})\big{]}$
$\displaystyle=-\sum_{p=1}^{k}\partial_{\lambda_{i}}t_{p}(\lambda)\left(a_{p}\phi^{\prime}(t_{p}^{*}-s_{j})+\Delta_{1_{j,p}}\right),$
(148)

where

$\Delta_{1_{j,p}}=a_{p}(t_{p}(\lambda)-t_{p}^{*})\phi^{\prime\prime}(\xi_{j,p})+(\nu_{p}-a_{p})\phi^{\prime}(t_{p}^{*}-s_{j})+(\nu_{p}-a_{p})(t_{p}(\lambda)-t_{p}^{*})\phi^{\prime\prime}(\xi_{j,p}),$
(149)

for some
$\xi_{j,p}\in[t_{p}^{*}-s_{j}-|t_{p}-t_{p}^{*}|,t_{p}^{*}-s_{j}+|t_{p}-t_{p}^{*}|]$.
The factor involving the partial derivative in (148) has the same form as (52)
so in order to bound it we write the Taylor expansion of (52) around
$\lambda^{*}$:

$\partial_{\lambda}t_{p}(\lambda)=\partial_{\lambda}t_{p}(\lambda^{*})+\partial^{2}_{\lambda\lambda}t_{p}(\lambda_{\delta})\left(\lambda-\lambda^{*}\right),$
(150)

for some $\lambda_{\delta}$ on the segment between $\lambda$ and
$\lambda^{*}$. By using (52) with (56) and (57), the entry $i,l$ in the
Hessian matrix $H=\partial^{2}_{\lambda\lambda}t_{p}(\lambda_{\delta})$ is

$\left(H^{T}\right)_{i,l}=\frac{F_{i,l}(\lambda)}{\left[\sum_{j=1}^{m}\lambda_{j}\phi^{\prime\prime}(t_{p}(\lambda)-s_{j})\right]^{2}},$
(151)

for $i,l=1,\ldots,k$, where

$\displaystyle F_{i,l}(\lambda)=$
$\displaystyle-\phi^{\prime\prime}(t_{p}(\lambda)-s_{i})\partial_{\lambda_{l}}t_{p}(\lambda)\sum_{j=1}^{m}\lambda_{j}\phi^{\prime\prime}(t_{p}(\lambda)-s_{j})$
$\displaystyle+\phi^{\prime}(t_{p}(\lambda)-s_{i})\left(\sum_{j=1}^{m}\lambda_{j}\phi^{\prime\prime\prime}(t_{p}(\lambda)-s_{j})\partial_{\lambda_{l}}t_{p}(\lambda)+\phi^{\prime\prime}(t_{p}(\lambda)-s_{l})\right).$
(152)

Note that in the denominator (151) we use all $m$ entries of $\lambda$ and
samples due to how we defined the function from (52), and the same is true for
the sums in (152). From (150) and (152), we then write:

$\partial_{\lambda_{i}}t_{p}(\lambda)=\partial_{\lambda_{i}}t_{p}(\lambda^{*})+\Delta_{2_{i,p}},$
(153)

where

$\Delta_{2_{i,p}}=\sum_{l=1}^{k}\frac{(\lambda_{l}-\lambda^{*}_{l})F_{i,l}(\lambda_{\delta})}{\left[\sum_{j=1}^{m}\lambda_{j}\phi^{\prime\prime}(t_{p}(\lambda_{\delta})-s_{j})\right]^{2}}.$
(154)

Note that $l$ goes up to $k$ because we only work with $k$ entries in
$\lambda$. Therefore, we have that:

$J_{1_{j,i}}=-\sum_{p=1}^{k}\left(\partial_{\lambda_{i}}t_{p}(\lambda^{*})+\Delta_{2_{i,p}}\right)\left(a_{p}\phi^{\prime}(t_{p}^{*}-s_{j})+\Delta_{1_{j,p}}\right),$
(155)

where

$\displaystyle\Delta_{1_{j,p}}$
$\displaystyle=O(|t_{p}-t_{p}^{*}|+|\nu_{p}-a_{p}|),$ (156)
$\displaystyle\Delta_{2_{i,p}}$
$\displaystyle=O(\|\lambda-\lambda^{*}\|_{2}),$ (157)

for $i=1,\ldots,k$, $j=1,\ldots,2k$ and $p=1,\ldots,k$. The next step now is
to upper bound $|\Delta_{1_{j,p}}|$ and $|\Delta_{2_{i,p}}|$.

#### Bounding $\Delta_{1_{j,p}}$

By the triangle inequality, we have that:

$\displaystyle|\Delta_{1_{j,p}}|$
$\displaystyle\leq|a_{p}||t_{p}(\lambda)-t_{p}^{*}||\phi^{\prime\prime}(\xi_{j,p})|+|\nu_{p}-a_{p}||\phi^{\prime}(t_{p}^{*}-s_{j})|+|\nu_{p}-a_{p}||t_{p}(\lambda)-t_{p}^{*}||\phi^{\prime\prime}(\xi_{j,p})|$
$\displaystyle\leq|a_{p}||t_{p}(\lambda)-t_{p}^{*}|\frac{2}{\sigma^{2}}+|\nu_{p}-a_{p}|\frac{\sqrt{2}}{\sqrt{e}\sigma}+|\nu_{p}-a_{p}||t_{p}(\lambda)-t_{p}^{*}|\frac{2}{\sigma^{2}}=\mathrel{\mathop{\mathchar
58\relax}}\bar{\Delta}_{1_{p}},$ (158)

for $j=1,\ldots,2k$ and $p=1,\ldots,k$, where we have used the maxima of the
Gaussian and its derivatives given in footnote 3.

#### Bounding $\Delta_{2_{i,p}}$

By applying the Cauchy-Schwartz inequality, we have that:

$\displaystyle|\Delta_{2_{i,p}}|$
$\displaystyle\leq\frac{1}{\left|\sum_{j=1}^{m}\lambda_{j}\phi^{\prime\prime}(t_{p}(\lambda_{\delta})-s_{j})\right|^{2}}\cdot\left\|\begin{bmatrix}F_{i,1}(\lambda_{\delta})\\\
\vdots\\\
F_{i,k}(\lambda_{\delta})\end{bmatrix}\right\|_{2}\cdot\|\lambda-\lambda^{*}\|2$
(159)

We now bound $|F_{i,l}|$ for $i,l=1,\ldots,k$:

$\displaystyle|F_{i,l}(\lambda_{\delta})|$
$\displaystyle\leq|\phi^{\prime\prime}(t_{p}(\lambda_{\delta})-s_{i})|\left|\partial_{\lambda_{l}}t_{p}(\lambda_{\delta})\right|\left|\sum_{j=1}^{m}\lambda_{j}\phi^{\prime\prime}(t_{p}(\lambda_{\delta})-s_{j})\right|$
$\displaystyle\qquad+|\phi^{\prime}(t_{p}(\lambda_{\delta})-s_{i})|\left(\left|\partial_{\lambda_{l}}t_{p}(\lambda_{\delta})\right|\left|\sum_{j=1}^{m}\lambda_{j}\phi^{\prime\prime\prime}(t_{p}(\lambda_{\delta})-s_{j})\right|+|\phi^{\prime\prime}(t_{p}(\lambda_{\delta})-s_{l})|\right)$
$\displaystyle\leq\frac{2C_{t^{*}}}{\sigma^{2}}\|\lambda_{\delta}\|_{2}\cdot\left\|\left[\phi^{\prime\prime}(t_{p}(\lambda_{\delta})-s_{j})\right]_{j=1}^{m}\right\|_{2}$
$\displaystyle\qquad+\frac{\sqrt{2}}{\sqrt{e}\sigma}\left(C_{t^{*}}\|\lambda_{\delta}\|_{2}\cdot\left\|\left[\phi^{\prime\prime\prime}(t_{p}(\lambda_{\delta})-s_{j})\right]_{j=1}^{m}\right\|_{2}+\frac{2}{\sigma^{2}}\right)$
$\displaystyle\leq\frac{2C_{t^{*}}}{\sigma^{2}}\|\lambda_{\delta}\|_{2}\cdot\frac{2\sqrt{m}}{\sigma^{2}}+\frac{\sqrt{2}}{\sqrt{e}\sigma}\left(C_{t^{*}}\|\lambda_{\delta}\|_{2}\cdot\frac{c\sqrt{m}}{\sigma^{3}}+\frac{2}{\sigma^{2}}\right),$
(160)

where we used the Cauchy-Schwartz inequality, the bounds in footnote 3 and
$C_{t^{*}}$ from (17). Therefore, the above inequality holds for
$\lambda_{\delta}\in\mathcal{B}(\lambda^{*},\delta_{\lambda})$ with
$\delta_{\lambda}$ from (15).

The final bound on $|F_{i,l}|$ is

$|F_{i,l}|\leq\frac{c_{2}C_{t^{*}}\sqrt{m}\|\lambda_{\delta}\|_{2}}{\sigma^{4}}+\frac{2\sqrt{2}}{\sqrt{e}\sigma^{3}},$
(161)

where $c_{2}=4+\frac{c\sqrt{2}}{\sqrt{e}}\approx 7.3484$, for
$i,l=1,\ldots,k$.

The next step is to obtain a lower bound on the denominator in (159). By
adding and subtracting $\lambda_{j}^{*}$ to $\lambda_{j}$ and applying the
reverse triangle inequality, we obtain:

$\displaystyle\left|\sum_{j=1}^{m}\lambda_{j}\phi^{\prime\prime}(t_{p}(\lambda)-s_{j})\right|$
$\displaystyle\geq
B^{\prime}-\left|\sum_{j=1}^{m}(\lambda_{j}-\lambda_{j}^{*})\phi^{\prime\prime}(t_{p}(\lambda)-s_{j})\right|$
$\displaystyle\geq
B^{\prime}-\frac{2\sqrt{m}\|\lambda-\lambda^{*}\|_{2}}{\sigma^{2}},$ (162)

where $B^{\prime}$ has the same form as $B$ in (63), except that we evaluate
it at a different $t(\lambda_{\delta})$ and possibly a subset of the entries
in $\lambda^{*}$, and then we apply Cauchy-Schwartz inequality and the bound
in footnote 3. For $B^{\prime}$, the bound in (71) is valid. By combining
(159), (161) and (162), we obtain the final bound on $|\Delta_{2_{i,p}}|$:

$|\Delta_{2_{i,p}}|\leq\bar{\Delta}_{2}\cdot\|\lambda-\lambda^{*}\|_{2}$ (163)

for $i=1,\ldots,k$ and $p=1,\ldots,k$, where

$\bar{\Delta}_{2}=\frac{\left(c_{2}C_{t}\sqrt{m}\|\lambda_{\delta}\|_{2}+\frac{2\sqrt{2}}{\sqrt{e}}\sigma\right)\sqrt{k}}{\left(\sigma^{2}B^{\prime}-2\sqrt{m}\|\lambda-\lambda^{*}\|_{2}\right)^{2}}.$
(164)

Therefore, from (155) and by using the definitions of $\bar{\Delta}_{1_{p}}$
and $\bar{\Delta}_{2}$ from (158) and (163) respectively, we have that:

$\displaystyle|E_{1_{j,i}}|$
$\displaystyle=\left|\sum_{p=1}^{k}\partial_{\lambda_{i}}t_{p}(\lambda^{*})\Delta_{1_{j,p}}+a_{p}\phi^{\prime}(t_{p}^{*}-s_{j})\Delta_{2_{i,p}}+\Delta_{1_{j,p}}\Delta_{2_{i,p}}\right|$
$\displaystyle\leq
C_{t}\sum_{p=1}^{k}\bar{\Delta}_{1_{p}}+\|\lambda-\lambda^{*}\|_{2}\bar{\Delta}_{2}\|a\|_{2}\cdot\left\|\left[\phi^{\prime}(t_{p}^{*}-s_{j})\right]_{p=1}^{k}\right\|_{2}+\|\lambda-\lambda^{*}\|_{2}\bar{\Delta}_{2}\sum_{p=1}^{k}\bar{\Delta}_{1_{p}}$
$\displaystyle\leq(C_{t}+\|\lambda-\lambda^{*}\|_{2}\bar{\Delta}_{2})\Big{(}\frac{2}{\sigma^{2}}\|a\|_{2}\|t(\lambda)-t^{*}\|_{2}+\frac{\sqrt{2}}{\sqrt{e}\sigma}\|\nu-a\|_{1}$
$\displaystyle\quad+\frac{2}{\sigma}\|\nu-a\|_{2}\|t(\lambda)-t^{*}\|_{2}\Big{)}+\frac{\sqrt{2k}}{\sqrt{e}\sigma}\|a\|_{2}\bar{\Delta}_{2}$
$\displaystyle\leq(C_{t}+\|\lambda-\lambda^{*}\|_{2}\bar{\Delta}_{2})\Big{(}\frac{2\sqrt{k}C_{t^{*}}}{\sigma^{2}}\|a\|_{2}\|\lambda-\lambda^{*}\|_{2}+\frac{\sqrt{2}}{\sqrt{e}\sigma}\|\nu-a\|_{1}$
$\displaystyle\quad+\frac{2\sqrt{k}C_{t^{*}}}{\sigma}\|\nu-a\|_{2}\|\lambda-\lambda^{*}\|_{2}\Big{)}+\frac{\sqrt{2k}}{\sqrt{e}\sigma}\|a\|_{2}\|\lambda-\lambda^{*}\|_{2}\bar{\Delta}_{2}=\mathrel{\mathop{\mathchar
58\relax}}\bar{E}_{1}$ (165)

for $i=1,\ldots,k$ and $j=1,\ldots,2k$.

### Entries in $J_{2}$

By adding and subtracting $t_{j}^{*}$ then taking a Taylor expansion like
before, we obtain:

$\displaystyle J_{2_{j,i}}$
$\displaystyle=-\phi(t_{i}^{*}-s_{j}+t_{i}(\lambda)-t_{i}^{*})$
$\displaystyle=-\phi(t_{i}^{*}-s_{j})-(t_{i}(\lambda)-t_{i}^{*})\phi^{\prime}(\xi_{j})$
$\displaystyle=-\phi(t_{i}^{*}-s_{j})-E_{2_{i,j}},$ (166)

for some
$\xi_{j}\in[t_{i}^{*}-s_{j}-|t_{i}(\lambda)-t_{i}^{*}|,t_{i}^{*}-s_{j}+|t_{i}(\lambda)-t_{i}^{*}|]$
and $E_{2_{j,i}}$ is the perturbation term. Then:

$|E_{2_{j,i}}|\leq|t_{i}(\lambda)-t_{i}^{*}|\cdot\frac{\sqrt{2}}{\sigma\sqrt{e}},$
(167)

for $i=1,\ldots,k$ and $j=1,\ldots,2k$.

### Putting everything together

We have that

$\displaystyle\|E\|_{F}$
$\displaystyle=\sqrt{\sum_{i=1}^{k}\sum_{j=1}^{2k}E_{1_{j,i}}^{2}+\sum_{i=1}^{k}\sum_{j=1}^{2k}E_{2_{j,i}}^{2}}$
$\displaystyle\leq\sqrt{2k^{2}\bar{E}_{1}^{2}+\frac{4k}{\sigma^{2}e}\sum_{i=1}^{k}|t_{i}(\lambda)-t_{i}^{*}|^{2}}$
$\displaystyle\leq
k\bar{E}_{1}\sqrt{2}+\frac{2\sqrt{k}}{\sigma\sqrt{e}}\|t(\lambda)-t^{*}\|_{2}$
$\displaystyle\leq
k\bar{E}_{1}\sqrt{2}+\frac{2C_{t^{*}}k}{\sigma\sqrt{e}}\|\lambda-\lambda^{*}\|_{2},$
(168)

where we have used the bounds on the entries of $E_{1}$ and $E_{2}$ from (165)
and (167) and Theorem 2, so this result holds for
$\lambda\in\mathcal{B}(\lambda^{*},\delta_{\lambda})$ for $\delta_{\lambda}$
defined in the theorem. Finally, by substituting the expression of
$\bar{E}_{1}$ from (165), we obtain:

$\displaystyle\|E\|_{F}$
$\displaystyle\leq\sqrt{2}k\Bigg{[}\bigg{(}C_{t^{*}}+\|\lambda-\lambda^{*}\|_{2}\bar{\Delta}_{2}\bigg{)}\bigg{(}\frac{2C_{t^{*}}\sqrt{k}}{\sigma^{2}}\|a\|_{2}\|\lambda-\lambda^{*}\|_{2}$
$\displaystyle+\frac{\sqrt{2}}{\sqrt{e}\sigma}\|\nu-a\|_{1}+\frac{2C_{t^{*}}\sqrt{k}}{\sigma}\|\nu-a\|_{2}\|\lambda-\lambda^{*}\|_{2}\bigg{)}+\frac{\sqrt{2k}}{\sqrt{e}\sigma}\|a\|_{2}\|\lambda-\lambda^{*}\|_{2}\bar{\Delta}_{2}\Bigg{]}$
$\displaystyle+\frac{2C_{t^{*}}k}{\sigma\sqrt{e}}\|\lambda-\lambda^{*}\|_{2}.$
(169)

Let $\delta_{\gamma}$ be a bound on the perturbation:

$\left\|\begin{bmatrix}\lambda-\lambda^{*}\\\
\nu-a\end{bmatrix}\right\|_{2}\leq\delta_{\gamma},$ (170)

and therefore:

$\|\lambda-\lambda^{*}\|_{2}\leq\delta_{\gamma}\qquad\text{and}\qquad\|\nu-a\|_{2}\leq\delta_{\gamma}.$
(171)

We also have that:

$\displaystyle\|\nu-a\|_{2}$
$\displaystyle\leq\|\nu-a\|_{1}\leq\|\nu\|_{1}+\|a\|_{1}\leq 2\Pi,$ (172)

where we used that $\nu_{1}+\ldots+\nu_{k}\leq\Pi$ and the fact that
$x=\sum_{p=1}^{k}a_{p}\delta_{t_{p}}$ is the solution to (9), so it satisfies
$\|x\|_{TV}=\|a\|_{1}\leq\Pi$.

Similarly, we have that:

$\displaystyle\|\lambda-\lambda^{*}\|_{2}$
$\displaystyle\leq\|\lambda\|_{2}+\|\lambda^{*}\|_{2}\leq\sqrt{k}\|\lambda\|_{\infty}+\sqrt{k}\|\lambda^{*}\|_{\infty}$
$\displaystyle\leq 2\sqrt{k}\tau,$ (173)

since both $\lambda$ and $\lambda^{*}$ satisfy the constraint in (24). In
order to write the bound (169) as $P\cdot\delta_{\gamma}$, we expand the
parentheses and use the following bounds:

$\displaystyle\|\lambda-\lambda^{*}\|_{2}\|\nu-a\|_{1}\leq
2\Pi\cdot\delta_{\gamma}$ (174)
$\displaystyle\|\lambda-\lambda^{*}\|_{2}^{2}\|\nu-a\|_{2}\leq
4\sqrt{k}\tau\Pi\cdot\delta_{\gamma}$ (175)
$\displaystyle\|\lambda-\lambda^{*}\|_{2}\|\nu-a\|_{2}\leq
2\Pi\cdot\delta_{\gamma}$ (176)

to obtain:

$\displaystyle\|E\|_{F}$
$\displaystyle\leq\sqrt{2}k\bigg{(}\frac{2\sqrt{k}C_{t^{*}}^{2}\Pi}{\sigma^{2}}+\frac{\sqrt{2k}C_{t^{*}}}{\sqrt{e}\sigma}+\frac{4\sqrt{k}C_{t^{*}}^{2}\Pi}{\sigma}$
$\displaystyle+\frac{4kC_{t^{*}}\bar{\Delta}_{2}\tau\Pi}{\sigma^{2}}+\frac{2\sqrt{2}\bar{\Delta}_{2}\Pi}{\sqrt{e}\sigma}+\frac{8kC_{t^{*}}\bar{\Delta}_{2}\tau\Pi}{\sigma}+\frac{\sqrt{2k}\bar{\Delta}_{2}\Pi}{\sqrt{e}\sigma}$
$\displaystyle+\frac{\sqrt{2}C_{t^{*}}}{\sigma\sqrt{e}}\bigg{)}\cdot\delta_{\gamma},$
(177)

which we rearrange based on $\sigma$ to obtain $\|E\|_{F}\leq
P(k,\sigma,\Pi,\tau,C_{t^{*}})\cdot\delta_{\gamma}$, where:

$\displaystyle P(k,\sigma,\Pi,\tau,$ $\displaystyle
C_{t^{*}})=\sqrt{2}k\Bigg{[}\frac{1}{\sigma^{2}}\left(2\sqrt{k}C_{t^{*}}^{2}\Pi+4kC_{t^{*}}\bar{\Delta}_{2}\tau\Pi\right)$
$\displaystyle+\frac{1}{\sigma}\left(\frac{\sqrt{2k}C_{t^{*}}}{\sqrt{e}}+4\sqrt{k}C_{t^{*}}^{2}\Pi+\frac{2\sqrt{2}\bar{\Delta}_{2}\Pi}{\sqrt{e}}+8kC_{t^{*}}\bar{\Delta}_{2}\tau\Pi+\frac{\sqrt{2k}\bar{\Delta}_{2}\Pi}{\sqrt{e}}+\sqrt{\frac{2}{e}}C_{t^{*}}\right)\Bigg{]},$

which is the final bound in (127).

##  5 Numerical experiments

In this section, we present numerical experiments which verify the bounds
given by our main results, Theorem 2, Theorem 3 and Theorem 4. To do this, we
take an example of a source and sample configuration and a Gaussian kernel for
a given $\sigma$ and solve the exact penalty formulation (25) of the dual
problem (24) using the level method [13], given in Appendix B. We introduce
inaccuracies in $\lambda$ by stopping the algorithm early and show how these
perturbations affect the source locations and weights. Next, we add noise to
the measurements to show how $\lambda$ is affected. We are, therefore, able to
compare the ratios of the perturbations obtained numerically with the
constants in the theorems to show the validity of our results in practice. The
specific details are discussed in the next subsections.

#### Setup

We place three sources at locations $t_{i}^{*}\in T=\\{0.25,0.63,0.889\\}$
with weights $a_{i}^{*}\leavevmode\nobreak\ \in\leavevmode\nobreak\
\\{0.8,0.5,0.9\\}$ and $m=21$ equispaced samples in $[0,1]$, with a Gaussian
kernel $\phi(t)=e^{-t^{2}/\sigma^{2}}$ with $\sigma=0.07$. We show this
configuration in Figure 2.

Figure 2: The source-sample configuration used for numerical experiments in
the current section.

#### Effect of $\lambda^{*}$ perturbations on $t^{*}$

We then solve the dual problem (24) in the exact penalty formulation (25) with
box constraint parameter $\tau=10^{5}$ and penalty parameter $\Pi=100$ and run
it for $P=500$ iterations. This gives an accuracy in the source locations of
$|t_{i}-t^{*}_{i}|\leq 10^{-8}$ for $t^{*}_{i}\in T$.

While it is possible to optimise the parameters $\tau$, $\Pi$ and $P$ in order
to obtain better accuracy in the source locations $t_{i}$ and weights $a_{i}$,
it is not the aim of this section. Note that Theorem 2 gives the result (16)
in the form

$|t_{i}-t^{*}_{i}|\leq C_{t^{*}}\|\lambda-\lambda^{*}\|_{2},$

where $t^{*}_{i}\in T$ is an arbitrary true source location, $\lambda^{*}$ is
the solution to the dual problem (24)666Note that the analysis of the dual
problem (10) from Section 2 applies to the dual problem (24) considered in
Section 3 as well, as the only difference difference between (10) and (24) is
a box constraint on $\lambda$. and $t$ is obtained by perturbing $t^{*}$ as a
consequence of the perturbation $\lambda^{*}$ in $\lambda$.

One way of showing that a relationship of the type of (16) holds in practice
is to plot the ratio
$\frac{|t^{(p)}_{i}-t_{i}^{*}|}{\|\lambda^{(p)}-\lambda^{*}\|_{2}}$, for
$p=p_{0},\ldots,P$ and $i=1,\ldots,k$, where $P$ is the number of iterations
the level method is run for, $p$ is the index of each iteration and
$t^{(p)}_{i}$ and $\lambda^{(p)}$ are the values of $t_{i}$ and $\lambda$
obtained at iteration $p$, where $p_{0}\geq 1$ is large enough so that
$\|\lambda^{(p)}-\lambda^{*}\|_{2}$ satisfies the condition in Theorem 2. The
level method computes the value $\lambda^{(p)}$ after $p$ iterations and
$\\{t^{(p)}_{i}\\}_{i=1}^{k}$ are obtained by calculating the global maxima of
the dual certificate
$q^{(p)}(s)=\sum_{j=1}^{m}\lambda_{j}^{(p)}\phi(s-s_{j})$. Since we know the
true value of $t^{*}_{i}$, we can find $t_{i}^{(p)}$ by running a local
optimisation algorithm with $t_{i}^{*}$ as the initial condition. For a large
enough value of $p$, this will give an accurate value of $t_{i}^{(p)}$ and we
can, therefore, calculate $|t_{i}^{(p)}-t_{i}^{*}|$ for each
$p=p_{0},\ldots,P$ and $t_{i}^{*}\in T$. Then we check that:

$\frac{|t_{i}^{(p)}-t_{i}^{*}|}{\|\lambda^{(p)}-\lambda^{*}\|_{2}}\leq
C_{t^{*}},$ (178)

for $p=p_{0},\ldots,P$ and $i=1,\ldots,k$. One issue is that the true value of
$\lambda^{*}$ is not known. The best estimate we have is
$\lambda_{best}^{*}=\lambda^{(P)}$, namely the value of $\lambda^{*}$ given by
the level method after $P$ iterations. Therefore, the result of Theorem 2
cannot be verified directly in practice, but must be adapted to take into
account this inaccuracy. For $i=1,\ldots,k$, we have that:

$\displaystyle|t_{i}^{(p)}-t_{i}^{*}|$ $\displaystyle\leq
C_{t^{*}}\|\lambda^{(p)}-\lambda^{*}\|_{2}$ $\displaystyle\leq
C_{t^{*}}\left(\|\lambda^{(p)}-\lambda^{*}_{best}\|_{2}+\|\lambda^{*}_{best}-\lambda^{*}\|_{2}\right),$
(179)

and so

$\displaystyle\frac{|t_{i}^{(p)}-t_{i}^{*}|}{\|\lambda^{(p)}-\lambda^{*}_{best}\|_{2}}$
$\displaystyle\leq
C_{t^{*}}\left(1+\frac{\|\lambda^{*}_{best}-\lambda^{*}\|_{2}}{\|\lambda^{(p)}-\lambda^{*}_{best}\|_{2}}\right).$
(180)

For fixed $P$, which in the experiments in this section is $P=500$,
$\|\lambda^{*}_{best}-\lambda^{*}\|_{2}$ above is fixed and as $p$ approaches
$P$, we have that $\|\lambda^{(p)}-\lambda^{*}_{best}\|_{2}\to 0$, and
therefore the right hand side above goes to infinity. This is not a problem
for our results, as it is not relevant how the ratio
$\frac{|t_{i}^{(p)}-t_{i}^{*}|}{\|\lambda^{(p)}-\lambda^{*}_{best}\|_{2}}$
behaves for
$\|\lambda^{(p)}-\lambda^{*}_{best}\|_{2}\leq\|\lambda^{*}_{best}-\lambda^{*}\|_{2}$.

We can then find a range for $p$ where
$\frac{\|\lambda^{*}_{best}-\lambda^{*}\|_{2}}{\|\lambda^{(p)}-\lambda^{*}_{best}\|_{2}}\leq
1$ and where we can see that

$\displaystyle\frac{|t_{i}^{(p)}-t_{i}^{*}|}{\|\lambda^{(p)}-\lambda^{*}_{best}\|_{2}}$
$\displaystyle\leq 2C_{t^{*}}.$ (181)

In Figure 3, we plot
$\frac{|t_{i}^{(p)}-t_{i}^{*}|}{\|\lambda^{(p)}-\lambda^{*}_{best}\|_{2}}$ for
$p=20,\ldots,270$, where we see that the ratio is less than $C_{t^{*}}$.
Specifically, in the left hand side panels (a), (c) and (e), we show the
errors $\|t_{i}^{(p)}-t_{i}^{*}\|$ and
$\|\lambda^{(p)}-\lambda_{best}^{*}\|_{2}$ for each $i\in\\{1,2,3\\}$
respectively at each iteration $p$ for $p=20,\ldots,270$ and
$\lambda_{best}^{*}=\lambda^{(P)}$ at $P=500$. In the right hand side panels
(b), (d) and (f), we show the ratio
$\frac{\|t_{i}^{(p)}-t_{i}^{*}\|}{\|\lambda^{(p)}-\lambda_{best}^{*}\|_{2}}$
and the constant $C_{t^{*}}$ from Theorem 2.

(a)

(b)

(c)

(d)

(e)

(f)

Figure 3: The result of Theorem 2 for $T=\\{0.25,0.63,0.888\\}$, $\sigma=0.07$
and $m=21$. In panels (a), (c) and (e) we show how $|t_{i}^{(p)}-t_{i}^{*}|$
and $\|\lambda^{(p)}-\lambda^{(p)}_{best}\|_{2}$ change at each iteration
$p=20,\ldots,270$ of the level method for $t_{1}$, $t_{2}$ and $t_{3}$
respectively, while in panels (b), (d) and (f) we show their ratio and
$C_{t^{*}}$ given by Theorem 2.

#### Effect of $t^{*}$ perturbations on $a^{*}$

In the case of Theorem 3, it is more straightforward to check the ratio of the
errors, since we know the true values of the source locations and weights,
which we denote by $t^{*}=[t_{1}^{*},\ldots,t_{k}^{*}]^{T}$ and
$a^{*}=[a_{1}^{*},\ldots,a_{k}^{*}]^{T}$ respectively. The error bound (23)
given by the theorem is of the form:

$\|a-a^{*}\|_{2}\leq
C_{a^{*}}\|t-t^{*}\|_{2}+\mathcal{O}(\|t-t^{*}\|_{2}^{2}),$

where $t$ is the perturbed vector $t^{*}$ and $a$ is the perturbed vector
$a^{*}$ as a consequence of perturbing $t^{*}$. For the values
$t^{(p)}_{i},i\in\\{1,2,3\\}$, obtained after $p$ iterations of the level
method, we now solve the least squares problem
$argmin_{\hat{a}}\|\Phi^{(p)}\hat{a}-y\|_{2}$ with the entries in the data
matrix $\Phi^{(p)}$ given by $\Phi^{(p)}_{j,i}=\phi(t^{(p)}_{i}-s_{j})$ to
find the corresponding perturbed weights $a^{(p)}_{i}$ for $i\in\\{1,2,3\\}$.
Then, according to Theorem 3, we have that:

$\frac{\|a^{(p)}-a^{*}\|_{2}}{\|t^{(p)}-t^{*}\|_{2}}\leq
C_{a^{*}}+\mathcal{O}(\|t^{(p)}-t^{*}\|_{2}).$ (182)

In Figure 4, panel (a), we show $\|a^{(p)}-a^{*}\|_{2}$ and
$\|t^{(p)}-t^{*}\|_{2}$ in the same setting as in Figure 3, for iterations
$p=20,\ldots,270$, and in panel (b) we see the ratio
$\frac{\|a^{(p)}-a^{*}\|_{2}}{\|t^{(p)}-t^{*}\|_{2}}$.

We do not plot the value of $C_{a^{*}}$, as it is of the order of $10^{5}$,
and therefore (182) holds.

(a)

(b)

Figure 4:  Plots of $\|a^{(p)}-a^{*}\|_{2}$ and $\|t^{(p)}-t^{*}\|_{2}$ (panel
(a)) and their ratio (panel (b)) for $p=20,\ldots,270$, in the setup described
at the beginning of this section.

#### Effect of the noise $w$ on $\lambda^{*}$ and $t^{*}$

As in the case of Theorem 2, where we rely on a best approximation
$\lambda^{*}_{best}$ of $\lambda^{*}$ for the numerical experiments, a similar
approach is required to check the validity of the results of Theorem 4 in
practice. Theorem 4 gives the bound (36) in the form:

$\|\lambda^{*}_{w}-\lambda^{*}\|_{2}\leq C_{\lambda^{*}}\cdot\|w\|_{2},$

where $\lambda^{*}$ is the true solution of the dual problem (24) and
$\lambda^{*}_{w}$ is the solution to the same problem with $y$ perturbed by
the noise $w$.

As it is not possible to know exactly the values of $\lambda^{*}$ and
$\lambda^{*}_{w}$, let $\lambda^{*}_{best}=\lambda^{(P)}$ be the value of
$\lambda$ given by the level method after $P$ iterations when $y$ is exact and
$\lambda_{best}$ be the value of $\lambda$ returned by the level method after
$P$ iterations when $y$ is corrupted by the additive noise $w$. Then we can
reformulate the bound (36) in terms of $\lambda^{*}_{best}$ and
$\lambda_{best}$:

$\displaystyle\|\lambda_{best}-\lambda^{*}_{best}\|_{2}$
$\displaystyle=\|\lambda_{best}-\lambda^{*}_{best}+\lambda^{*}-\lambda^{*}+\lambda^{*}_{w}-\lambda^{*}_{w}\|_{2}$
$\displaystyle\leq\|\lambda_{best}-\lambda^{*}_{w}\|_{2}+\|\lambda^{*}-\lambda^{*}_{w}\|_{2}+\|\lambda^{*}-\lambda^{*}_{best}\|_{2}$
$\displaystyle\leq\|\lambda_{best}-\lambda^{*}_{w}\|_{2}+C_{\lambda^{*}}\|w\|_{2}+\|\lambda^{*}-\lambda^{*}_{best}\|_{2},$
(183)

so

$\frac{\|\lambda_{best}-\lambda^{*}_{best}\|_{2}}{\|w\|_{2}}\leq
C_{\lambda^{*}}+\frac{\|\lambda_{best}-\lambda^{*}_{w}\|_{2}+\|\lambda^{*}-\lambda^{*}_{best}\|_{2}}{\|w\|_{2}}.$
(184)

As before, we plot
$\frac{\|\lambda_{best}-\lambda^{*}_{best}\|_{2}}{\|w\|_{2}}$, where
$\lambda^{*}_{best}$ is the solution we obtain by solving the dual problem
(24) in its exact penalty formulation using the level method with $P=100$
iterations and $\lambda_{best}$ is the ‘noisy’ solution, which is obtained by
solving the problem with $P=100$ iterations when $y$ is corrupted by additive
noise $w$. We repeat this for different magnitudes of the noise $w$, which we
increase gradually as follows. For each component $y_{j}$ of $y$, we add a
sample $X_{j}$ from the standard uniform distribution $U(0,1)$, multiplied by
a coefficient $w_{c}$:

$y_{{noisy}_{j}}=y_{j}+w_{c}\cdot X_{j}.$ (185)

We repeat this for different values of the coefficient $w_{c}$ from the set:

$\displaystyle w_{c}\in\\{$ $\displaystyle 0.000002,0.000004,\ldots,0.00001,$
$\displaystyle 0.00002,0.00004,\ldots,0.0001,$ $\displaystyle
0.0002,0.0004,\ldots,0.001,$ $\displaystyle 0.002,0.003,\ldots,0.01,$
$\displaystyle 0.02,0.03,\ldots,0.1\\}.$ (186)

Therefore, in Figure 5 we show the basic setup described at the beginning of
this section. Panel (a) shows $\|\lambda_{best}-\lambda_{best}^{*}\|_{2}$
against the norm of the noise $\|w\|_{2}$, and in order to check that the
algorithm actually converges to a useful $\lambda_{best}^{*}$, we also plot
plot $\|t_{best}-t^{*}\|_{2}$ against $\|w\|_{2}$ in panel (b), since we know
the true value $t^{*}$. Then, in panel (c) we plot the ratio
$\frac{\|\lambda_{best}-\lambda_{best}^{*}\|_{2}}{\|w\|_{2}}$ and
$C_{\lambda^{*}}$ as given by Theorem 4, where we see that the ratio is
smaller than the constant, as the theorem states. In the same plot, we also
show the ratio $\frac{\|t_{best}-t^{*}\|_{2}}{\|w\|_{2}}$ and we see that it
does not grow as the magnitude of the noise increases.

We end this section by mentioning that in these experiments we only take into
account $2k$ entries of $\lambda$ and $w$, corresponding to the $2k$ samples
that are the closest to the $k$ sources, as described in Section 3, for which
Theorem 4 holds. However, in Figure 6 we show the same plot where we calculate
the errors using the full vectors $\lambda_{best},\lambda_{best}^{*}$ and $w$
and we see that the ratio of the two norms follows a similar pattern.

(a)

(b)

(c)

Figure 5: Plots of $\|\lambda_{best}-\lambda^{*}_{best}\|_{2}$ (panel(a)),
$\|t_{best}-t\|_{2}$ (panel (b)) and their ratio to the noise $\|w\|_{2}$
(panel(c)) for $\|w\|_{2}$ in a range as given in (185) and (186), in the
setting described at the beginning of this section. Figure 6:
$\frac{\|\lambda_{best}-\lambda^{*}_{best}\|_{2}}{\|w\|_{2}}$ and
$\frac{\|t_{best}-t\|_{2}}{\|w\|_{2}}$ for $\|w\|_{2}$ in a range as given in
(185) and (186) in the setting described at the beginning of this section.
Here, instead of selecting only $2k$ entries of $\lambda$ and $w$ as described
in Section 3, we calculate the errors using all the components of the vectors.

##  6 Conclusion

In this paper, we proved primal stability in the non-negative super-resolution
problem, when addressed via convex duality. The main ingredient in our
analysis is a quantitative version of the implicit function theorem, a
folklore result in the theory of dynamical systems community.

In the noise-free setting, our results provide quantitative bounds in terms of
the number of measurements for the accuracy of the primal solution with
respect to the convex dual problem solution in an $\ell_{\infty}$ error bound
on the primal spike locations and an $\ell_{2}$ error bound on the spike
weights. In the case when the measurements are corrupted by additive noise, we
have proved a similar result for how the dual variable is perturbed as a
function of the magnitude of the noise.

## Acknowledgements

This work was done while BT was affiliated to the Mathematical Institute,
University of Oxford, UK. This publication is based on work supported by the
EPSRC Centre For Doctoral Training in Industrially Focused Mathematical
Modelling (EP/L015803/1) in collaboration with the National Physical
Laboratory and by the Alan Turing Institute under the EPSRC grant EP/N510129/1
and the Turing Seed Funding grant SF019.

## References

  * [1] Eric Betzig, George H. Patterson, Rachid Sougrat, O. Wolf Lindwasser, Scott Olenych, Juan S. Bonifacino, Michael W. Davidson, Jennifer Lippincott-Schwartz, and Harald F. Hess.  Imaging intracellular fluorescent proteins at nanometer resolution.  Science, 313(5793):1642–1645, 2006.
  * [2] Klaus G. Puschmann and Franz Kneer.  On super-resolution in astronomical imaging.  Astronomy & Astrophysics, 436(1):373–378, 2005.
  * [3] Ronen Tur, Yonina C. Eldar, and Zvi Friedman.  Innovation rate sampling of pulse streams with application to ultrasound imaging.  IEEE Transactions on Signal Processing, 59(4):1827–1842, 2011.
  * [4] Federico Pierucci, Zaid Harchaoui, and Jérôme Malick.  A smoothing approach for composite conditional gradient with nonsmooth loss.  Research report, RR-8662, INRIA Grenoble, 2014.
  * [5] 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\.
  * [6] Geoffrey Schiebinger, Elina Robeva, and Benjamin Recht.  Superresolution without separation.  Information and Inference: A Journal of the IMA, 7(1):1–30, 2018\.
  * [7] Vincent Duval and Gabriel Peyré.  Exact support recovery for sparse spikes deconvolution.  Foundations of Computational Mathematics, 15:1315–1355, 2015.
  * [8] 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\.
  * [9] Tamir Bendory, Shai Dekel, and Arie Feuer.  Robust recovery of stream of pulses using convex optimization.  Journal of Mathematical Analysis and Applications, 442(2):511–536, 2016.
  * [10] Jean-Marc Azais, Yohann De Castro, and Fabrice Gamboa.  Spike detection from inaccurate samplings.  Applied and Computational Harmonic Analysis, 38(2):177–195, 2015\.
  * [11] Armin Eftekhari and Andrew Thompson.  Sparse inverse problems over measures: Equivalence of the conditional gradient and exchange methods.  SIAM Journal on Optimization, 29(2):1329–1349, 2019.
  * [12] Marco A. López and Georg Still.  Semi-infinite programming.  European Journal of Operational Research, 180(2):491–518, 2007\.
  * [13] Yurii Nesterov.  Introductory Lectures on Convex Optimization: A Basic Course.  Springer Publishing Company, 2014.
  * [14] Zhenan Fan, Yifan Sun, and Michael P. Friedlander.  Bundle methods for dual atomic pursuit.  arXiv preprint arXiv:1910.13650, 2019.
  * [15] Nicholas Boyd, Geoffrey Schiebinger, and Benjamin Recht.  The alternating descent conditional gradient method for sparse inverse problems.  SIAM Journal on Optimization, 27(2):616–639, 2017.
  * [16] Emmanuel J. Candès and Carlos Fernandez-Granda.  Super-resolution from noisy data.  Journal of Fourier Analysis and Applications, 19(6):1229–1254, 2013\.
  * [17] Jean-Baptiste Hiriart-Urruty and Claude Lemarechal.  Convex Analysis and Minimization Algorithms, Volume I: Algorithms.  Springer-Verlag, Berlin, 2nd edition, 1996.
  * [18] Yohann De Castro and Fabrice Gamboa.  Exact reconstruction using Beurling minimal extrapolation.  Journal of Mathematical Analysis and applications, 395(1):336–354, 2012.
  * [19] Vincent Duval and Gabriel Peyré.  Sparse regularization on thin grids I: the Lasso.  Inverse Problems, 33(5), 2017.
  * [20] Vincent Duval and Gabriel Peyré.  Sparse spikes super-resolution on thin grids II: the continuous basis pursuit.  Inverse Problems, 33(9), 2017.
  * [21] Ankur Moitra.  Super-resolution, extremal functions and the condition number of Vandermonde matrices.  In Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC 2015), 2015.
  * [22] 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.
  * [23] Stephane Chretien and Hemant Tyagi.  Multi-kernel unmixing and super-resolution using the Modified Matrix Pencil method.  Journal of Fourier Analysis and Applications, 26(1), 2020.
  * [24] Cédric Josz, Jean Bernard Lasserre, and Bernard Mourrain.  Sparse polynomial interpolation: sparse recovery, super-resolution, or Prony?  Advances in Computational Mathematics, 45(3):1401–1437, 2019.
  * [25] Armin Eftekhari, Jared Tanner, Andrew Thompson, Bogdan Toader, and Hemant Tyagi.  Sparse non-negative super-resolution – simplified and stabilised.  To appear in Applied and Computational Harmonic Analysis, arXiv:1804.01490, 2019.
  * [26] Carlangelo Liverani.  Implicit function theorem (a quantitative version).  Retrieved January 13, 2019, from https://www.mat.uniroma2.it/~liverani/SysDyn15/app1.pdf.
  * [27] Samuel Karlin and William J. Studden.  Tchebycheff systems: with applications in analysis and statistics.  Pure and applied mathematics. Interscience Publishers, 1966.
  * [28] G. W. Stewart.  Perturbation theory and least squares with errors in the variables.  In Contemporary Mathematics 112: Statistical Analysis of Measurement Error Models and Applications, pages 171–181. American Mathematical Society, 1990.

##  Appendix A Duality in the noisy case

In this section, we show the duality of the following problems:

$\min_{x\geq
0}\left\|y-\int\Phi(t)x(\operatorname{d\\!}t)\right\|_{1}\quad\text{subject
to}\quad\|x\|_{TV}\leq\Pi,$

which is given in (9), and

$\max_{\begin{subarray}{c}\beta>0\\\
\lambda\in\mathbb{R}^{m}\end{subarray}}\beta\left(\lambda^{T}y-\Pi\right)\quad\text{subject
to}\quad\lambda^{T}\Phi(t)\leq 1,\quad\forall
t\in[0,1]\quad\text{and}\quad\|\lambda\|_{\infty}\leq 1/\beta,$ (187)

which is a more general version of the dual problem (24). We start from the
primal problem (9) by introducing a new variable
$z=\int\Phi(t)x(\operatorname{d\\!}t)$:

$\displaystyle\min_{\begin{subarray}{c}x\geq 0\\\
z\in\mathbb{R}^{m}\end{subarray}}\left\|z-y\right\|_{1}\quad\text{subject
to}\quad$ $\displaystyle z=\int\Phi(t)x(\operatorname{d\\!}t),$
$\displaystyle\|x\|_{TV}\leq\Pi,$ (188)

and then we write the Lagrangian:

$\displaystyle
L(x,z,\beta,\lambda)=\|z-y\|_{1}+\lambda^{T}\left(z-\int\Phi(t)x(\operatorname{d\\!}t)\right)+\beta\left(\|x\|_{TV}-\Pi\right),$
(189)

so the Lagrangian dual problem is:

$\displaystyle\max_{\begin{subarray}{c}\beta\geq 0\\\
\lambda\in\mathbb{R}^{m}\end{subarray}}$
$\displaystyle\min_{\begin{subarray}{c}x\geq 0\\\
z\in\mathbb{R}^{m}\end{subarray}}L(x,z,\beta,\lambda)=$
$\displaystyle=\max_{\begin{subarray}{c}\beta\geq 0\\\
\lambda\in\mathbb{R}^{m}\end{subarray}}\min_{\begin{subarray}{c}x\geq 0\\\
z\in\mathbb{R}^{m}\end{subarray}}\left[\|z-y\|_{1}+\lambda^{T}z+\int\left(\beta-\lambda^{T}\Phi(t)\right)x(\operatorname{d\\!}t)\right]-\beta\Pi$
$\displaystyle=\max_{\begin{subarray}{c}\beta\geq 0\\\
\lambda\in\mathbb{R}^{m}\end{subarray}}\min_{\begin{subarray}{c}x\geq 0\\\
w\in\mathbb{R}^{m}\end{subarray}}\left[\|w\|_{1}+\lambda^{T}w+\int\left(\beta-\lambda^{T}\Phi(t)\right)x(\operatorname{d\\!}t)\right]+\lambda^{T}y-\beta\Pi,$
(190)

where in the last equality we make the substitution $w=z-y$.

The integral on the right hand side is equal to $-\infty$ if there exists
$t_{0}\in[0,1]$ such that $\lambda^{T}\Phi(t_{0})>\beta$, as we can set
$x=\infty\cdot\delta_{t_{0}}$. Therefore, we impose the condition that
$\lambda^{T}\Phi(t)\leq\beta$ for all $t\in[0,1]$, in which case the integral
is equal to zero by taking $x$ to be zero wherever the integrand is non-zero,
and the dual becomes:

$\displaystyle\max_{\begin{subarray}{c}\beta\geq 0\\\
\lambda\in\mathbb{R}^{m}\end{subarray}}\min_{w\in\mathbb{R}^{m}}\left(\|w\|_{1}+\lambda^{T}w\right)+\lambda^{T}y-\beta\Pi\quad\text{subject
to}\quad\lambda^{T}\Phi(t)\leq\beta,\quad\forall t\in[0,1].$ (191)

which can be rewritten as:

$\displaystyle\max_{\begin{subarray}{c}\beta\geq 0\\\
\lambda\in\mathbb{R}^{m}\end{subarray}}\max_{w\in\mathbb{R}^{m}}\left(-\lambda^{T}w-\|w\|_{1}\right)+\lambda^{T}y-\beta\Pi\quad\text{subject
to}\quad\lambda^{T}\Phi(t)\leq\beta,\quad\forall t\in[0,1].$ (192)

and note that for $f(w)=\|w\|_{1}$:

$f^{*}(\lambda)=\max_{w}\left(\lambda^{T}w-\|w\|_{1}\right)=\begin{cases}0,&\text{if}\quad\|\lambda\|_{\infty}\leq
1,\\\ \infty,&\text{otherwise},\end{cases}$ (193)

is its conjugate [17]. Therefore, we impose the condition that
$\|\lambda\|_{\infty}\leq 1$ and the dual becomes:

$\displaystyle\max_{\begin{subarray}{c}\beta\geq 0\\\
\lambda\in\mathbb{R}^{m}\end{subarray}}\lambda^{T}y-\beta\Pi\quad\text{subject
to}\quad\lambda^{T}\Phi(t)\leq\beta,\quad\forall
t\in[0,1]\quad\text{and}\quad\|\lambda\|_{\infty}\leq 1.$ (194)

We then make the substitution $\lambda^{\prime}=\lambda/\beta$ (for $\beta>0$)
to obtain:

$\displaystyle\max_{\begin{subarray}{c}\beta>0\\\
\lambda^{\prime}\in\mathbb{R}^{m}\end{subarray}}\beta\left(\lambda^{\prime
T}y-\Pi\right)\quad\text{subject to}\quad\lambda^{\prime T}\Phi(t)\leq
1,\quad\forall t\in[0,1]\quad\text{and}\quad\|\lambda^{\prime}\|_{\infty}\leq
1/\beta,$ (195)

which is the problem (187).

Note that if we fix $\beta$ and solve for $\lambda^{\prime}$, given that we
are interested in the value of $\lambda^{\prime}$ rather than the value of the
objective function, the problem above becomes:

$\displaystyle\operatorname*{\arg\\!\max}_{\lambda^{\prime}\in\mathbb{R}^{m}}\lambda^{\prime
T}y\quad\text{subject to}\quad\lambda^{\prime T}\Phi(t)\leq 1,\quad\forall
t\in[0,1]\quad\text{and}\quad\|\lambda^{\prime}\|_{\infty}\leq 1/\beta,$ (196)

which is the problem (24) that we consider in Section 3.

##  Appendix B The level bundle method

In this section, we describe the level bundle method [13] applied to (25) for
which experiments were presented in Section 1.1 and Section 5. The algorithm
progressively builds up a polyhedral model of the objective function from a
‘bundle’ of subgradients at each iteration. The algorithm proceeds by
projecting iterates onto a level set of the model, an approach which is known
to improve robustness in comparison with the standard cutting planes
subgradient method (Kelley’s method). A statement of the algorithm is given in
Algorithm 1.

Input: Kernel function $\Phi\mathrel{\mathop{\mathchar
58\relax}}I\rightarrow\mathbb{R}^{m}$, measurements $y\in\mathbb{R}^{m}$,
sample locations $\\{s_{j}\\}_{j\in\\{1,\ldots,m\\}}\in I$, penalty parameter
$\Pi>0$, level set parameter $\alpha\in(0,1)$ and number of iterations $L$.

Initialize: $l=1$.

While $l\leq L$ , do

  1. 1.

Compute a subgradient as

$t^{l}\in\arg\sup_{s\in I}\displaystyle(\lambda^{l-1})^{T}\Phi(s),$
$g^{l}=\left\\{\begin{array}[]{ll}-y+\Pi\left[(\lambda^{l-1})^{T}\Phi(t^{l})-1\right],&(\lambda^{l-1})^{T}\Phi(t^{l})\geq
1\\\ -y,&(\lambda^{l-1})^{T}\Phi(t^{l})<1\end{array}\right.$

  2. 2.

Build the polyhedral model

$\widehat{\Psi}^{l}_{\Pi}(\lambda)=\max_{r=1,\ldots,l}\Psi_{\Pi}(\lambda^{r-1})+(g^{r})^{T}(\lambda-\lambda^{r-1}).$

  3. 3.

Compute $\nu^{l}=\displaystyle\inf_{\lambda}\widehat{\Psi}_{\Pi}^{l}(\lambda)$
and $\mu^{l}=\displaystyle\min_{r=1,\ldots,l}\Psi_{\Pi}(\lambda^{r})$.

  4. 4.

Project onto the level set as
$\lambda^{l}=\mathcal{P}_{\mathcal{L}_{\alpha}^{l}}(\lambda^{l-1})$ where
$\mathcal{L}_{\alpha}^{l}=\\{\lambda\mathrel{\mathop{\mathchar
58\relax}}\widehat{\Psi}_{\Pi}(\lambda)\leq\alpha\mu^{l}+(1-\alpha)\nu^{l}\\}$.

  5. 5.

$l=l+1$.

Output: $\lambda^{L}\in\mathbb{R}^{m}$.

Algorithm 1 Level bundle method for solving Program (25).

In the experiments shown in Section 1.1, $\Pi$ was chosen to be
$2\|\bf{a^{\ast}}\|_{1}$ and the level set parameter $\alpha$ was taken to be
$1/4$.