# Multivariate Super-Resolution without Separation

Bakytzhan Kurmanbek  Department of Mathematics, The University of British
Columbia, 1984 Mathematics Rd, Vancouver, BC V6T 1Z2  Elina Robeva  Department
of Mathematics, The University of British Columbia, 1984 Mathematics Rd,
Vancouver, BC V6T 1Z2

###### Abstract

In this paper we study the high-dimensional super-resolution imaging problem.
Here we are given an image of a number of point sources of light whose
locations and intensities are unknown. The image is pixelized and is blurred
by a known point-spread function arising from the imaging device. We encode
the unknown point sources and their intensities via a nonnegative measure and
we propose a convex optimization program to find it. Assuming the device’s
point-spread function is componentwise decomposable, we show that the optimal
solution is the true measure in the noiseless case, and it approximates the
true measure well in the noisy case with respect to the generalized
Wasserstein distance. Our main assumption is that the components of the point-
spread function form a Tchebychev system ($T$-system) in the noiseless case
and a $T^{*}$-system in the noisy case, mild conditions that are satisfied by
Gaussian point-spread functions. Our work is a generalization to all
dimensions of the work Eftekhari, Bendory Tang (2021) where the same analysis
is carried out in 2 dimensions. We resolve an open problem posed in
Schiebinger . (2018) in the case when the point-spread function decomposes.

††footnotetext: 2020 Mathematics Subject Classification: 65K10, 15A30

Keywords. Super-resolution, Tchebychev systems, Generalized-Wasserstein
distance, Exact solutions, Bounds for a recovery error

##  1 Introduction

In the super-resolution imaging problem we are given the output of an imaging
device depicting often very small or very distant objects. As a result, we
observe a pixelized, blurred, and noisy image, and we aim to recover the true
picture by removing the blur and increasing the resolution. Solving this
problem is essential in many applied sciences such as neuroscience Betzig .
(2006); Hess . (2006); Rust . (2006); Ekanadham . (2011); Evanko (2009); Tur .
(2011), geophysics Khaidukov . (2004), and astronomy Puschmann Kneer (2005).
Knowing the blurring (point-spread) function is usually crucial in achieving
accurate results.

Due to the complexity of the super-resolution imaging problem it is difficult
to distinguish point sources of light that are very close to one another. As a
result many of the existing methods can be proved to work only under a minimum
separation condition between the point sources of light even as the amount of
noise approaches zero Bendory . (2016); Candès Fernandez-Granda (2014);
Morgenshtern Candès (2015).

It was first shown in the 1-dimensional case Schiebinger . (2018) that if no
noise is present, then no minimum separation condition is required provided
that the point-spread function satisfies a Tchebychev system Karlin Studden
(1966) condition. This work was simplified and extended to the noisy case in
Eftekhari, Tanner . (2021), and then to the 2-dimensional and possibly noisy
case in Eftekhari, Bendory Tang (2021). In the present paper we generalize
these results to the case of any dimension both with or without noise.

A lot of the theoretical work on super-resolution imaging uses concepts and
techniques from compressed sensing Donoho (2006); Candès . (2006); Candés Tao
(2005), by minimizing total variation over measures Candès Fernandez-Granda
(2014); Tang . (2013); Fyhn . (2013); Demanet . (2013); Duval Peyré (2015);
Denoyelle . (2017); Azais . (2015); Bendory . (2016). In this manuscript,
assuming that we have $K$ source points in the exact image, we show that
$(2K+1)^{d}$ observations are enough to recover the image. In the noiseless
case, we recover the image exactly, and in the noisy case, we provide an error
bound in Generalized-Wasserstein distance.

### Mathematical setup

Let $\mu$ be a Borel measure supported on $\mathbb{I}^{d}=[0,1]^{d}$. This
measure will represent the true image that we are trying to reconstruct. Given
an image represented by the measure $\mu$, an imaging device with (a known)
point-spread function $\Psi:\mathbb{R}^{d}\to\mathbb{R}$ convolves each
individual point source of light with the point-spread function $\Psi$
resulting in a new image which, at a point $(x_{1},\ldots,x_{d})$ equals (up
to a noise term)

$\int_{\mathbb{I}^{d}}\Psi(x_{1}-t_{1},\ldots,x_{d}-t_{d})\mu[\text{d}(t_{1},\ldots,t_{d})].$

We will later assume that $\mu$ is a sparse measure, i.e.,
$\mu=\sum_{k=1}^{K}a_{k}\delta_{\theta_{k}}$, where
$\theta_{k}=(t_{1}^{(k)},\ldots,t_{d}^{(k)})\in\mathbb{R}^{d}$ are the point
source locations, and $a_{k}>0$ are their intensities. In this case, the
observed image at a point $(x_{1},\ldots,x_{d})$ equals

$\sum_{k=1}^{K}a_{k}\Psi(x_{1}-t_{1}^{(k)},\ldots,x_{d}-t_{d}^{(k)}).$

We will also assume that the point-spread function $\Psi$ lies in the tensor
product model, i.e.,

$\Psi(\xi_{1},\cdots,\xi_{d})=\psi^{(1)}(\xi_{1})\cdots\psi^{(d)}(\xi_{d}),$
(1.1)

where $\psi^{(1)},\ldots,\psi^{(d)}$ are continuous real-valued functions on
$\mathbb{I}$.

This is a widely used model in imaging as noted in Eftekhari, Bendory Tang
(2021) which studies the 2-dimensional case and assumes the 2-dimensional
point-spread function satisfies (1.1). It is also often the case that the
functions $\psi^{(j)}$ are copies of a function $\psi$.

Suppose that the image we observe is of size $M\times\cdots\times M$ ($d$
times) with coordinates $\\{y_{i_{1},\cdots,i_{d}}\\}_{i_{j}=1}^{M}$ measured
on an $M\times\cdots\times M$ ($d$ times) grid
$\\{x_{1}^{(1)},\ldots,x_{M}^{(1)}\\}\times\cdots\times\\{x_{1}^{(d)},\ldots,x_{M}^{(d)}\\}$,
which can be thought of as consisting of the pixels. Then,

$y_{i_{1},\cdots,i_{d}}\approx\int_{\mathbb{I}^{d}}\psi^{(1)}(x_{i_{1}}^{(1)}-t_{1})\cdots\psi^{(d)}(x_{i_{d}}^{(d)}-t_{d})\mu[\text{d}(t_{1},\cdots,t_{d})],$
(1.2)

where we have noted the possibility of noise being present. For notational
convenience, we denote

$\psi^{(i)}_{m}(t_{i})=\psi^{(i)}(x^{(i)}_{m_{i}}-t_{i})$

for every $i\in[d]$ and $m\in[M]$. More specifically, we will assume that

$\sum_{i_{1},\cdots,i_{d}=1}^{M}\Big{|}y_{i_{1},\cdots,i_{d}}-\int_{\mathbb{I}^{d}}\psi^{(1)}_{i_{1}}(t_{1})\cdots\psi^{(d)}_{i_{d}}(t_{d})\mu[\text{d}(t_{1},\cdots,t_{d})]\Big{|}^{2}\leq\delta^{2}$
(1.3)

where $\delta\geq 0$ reflects an additive noise model.

We may rewrite (1.3) more compactly as

$\Big{\|}y-\int_{\mathbb{I}^{d}}\psi^{(1)}_{[M]}(t_{1})\otimes\cdots\otimes\psi^{(d)}_{[M]}(t_{d})\mu[\text{d}(t_{1},\cdots,t_{d})]\Big{\|}_{F}\leq\delta$
(1.4)

where $\|\cdot\|_{F}$ stands for the Frobenious norm (of a tensor), and
$\psi^{(j)}_{[M]}(t_{j})=(\psi^{(j)}_{1}(t_{j}),\ldots,\psi^{(j)}_{M}(t_{j}))^{T}$.

### Summary of results

To recover $\mu$, we propose to use the convex feasibility program

Find a nonnegative Borel measure $\mu$ on $\mathbb{I}^{d}$ such that

$\Big{\|}y-\int_{\mathbb{I}^{d}}\psi^{(1)}_{[M]}(t_{1})\otimes\cdots\otimes\psi^{(d)}_{[M]}(t_{d})\mu[\text{d}(t_{1},\cdots,t_{d})]\Big{\|}_{F}\leq\delta^{\prime}$
(1.5)

for some $\delta^{\prime}\geq\delta$. Note that this program is grid-free and
has no regularity other than the non-negativity of the Borel measure compared
to other methods where the measure’s total variation is assumed to be constant
Candès Fernandez-Granda (2014); Tang . (2013); Fyhn . (2013). The dual program
to the program (1.5) can be used to find the unknown point sources and their
amplitudes. When there is no noise, i.e., $\delta^{\prime}=0$, we show that
the solution of (1.5) is exact and unique under certain conditions for the
component functions of the point spread function. In the presence of noise,
i.e. $\delta>0$, we show that the solution of program (1.5) well approximates
the true measure, by showing an upper bound for the recovery error.

We generalize the main results obtained in Eftekhari, Bendory Tang (2021) from
2 to higher dimensions. We address the noiseless case in Section 2. We show in
Theorem 2.2 that if the true measure $\mu$ consists of $K$ point sources, then
the unique solution of program (1.5) is the true measure $\mu$. Here we assume
that the translates of the component-wise functions $\psi^{(j)}$ form
Tchebychev systems and that $M\geq 2K+1$, where our observations
$y\in(\mathbb{R}^{M})^{\bigotimes d}$. Moreover, no minimum separation between
the point sources is required, and, therefore, program (1.5) recovers correct
solution no matter how close to each other the point sources may be.

We address the noisy case in Section 3. We assume the true measure is an
arbitrary measure $\mu$ supported on $\mathbb{I}^{d}$ and the noise level is
$\delta>0$. Theorem 3.7 then shows that if the translates of the component-
wise functions form $T^{*}$-systems, and given enough observations, the
solution of program (1.5) well-approximates the true image measure in
Generalized-Wasserstein distance. We use two auxiliary Lemmas 3.8 and 3.9,
which utilize the existence of dual certificates $Q$ and $Q^{0}$, to bound the
errors away from the support and near the support. The existence of such dual
certificates shown in Propositions 3.11 and 3.12 is a generalization to all
dimensions of Propositions 21 and 22 in Eftekhari, Bendory Tang (2021) which
address this problem in 2 dimensions. We give an upper bound on the recovery
error in terms of the noise level and the minimum separation between the
points sources (see Theorem 3.7).

The $T$-system and $T^{*}$-system assumptions have already been shown to hold
for translated copies of Gaussian functions Eftekhari, Bendory Tang (2021);
Eftekhari, Tanner . (2021). Therefore, all of our results hold for Gaussian
point spread functions that satisfy the decomposability criterion (1.1).

The proofs of all theorems, lemmas, and propositions can be found in the
appendices.

##  2 The noiseless case

Let $\mu$ be a nonnegative atomic measure

$\mu=\sum_{k=1}^{K}a_{k}\delta_{\theta_{k}},\;\;\;a_{k}>0$

with $K\geq 1$ impulses located at
$\Theta=\\{\theta_{k}\\}_{k=1}^{K}\subset\text{interior}(\mathbb{I}^{d})$ with
positive amplitudes $\\{a_{k}\\}_{k=1}^{K}$, where
$\theta_{k}=(t_{1}^{(k)},\ldots,t_{d}^{(k)})\in\mathbb{R}^{d}$. Consider the
case where there is no imaging noise ($\delta=0$). In this case, we collect
noise-free measurements

$y=\int_{\mathbb{I}^{d}}\psi^{(1)}_{[M]}(t_{1})\cdots\psi^{(d)}_{[M]}(t_{d})\mu[\text{d}(t_{1},\cdots,t_{d})]\in(\mathbb{R}^{M})^{\bigotimes
d}.$

To understand when solving program (1.5) with $\delta^{\prime}=0$ successfully
recovers the true measure $\mu$, recall the concept of a T-system Karlin
Studden (1966):

######  Definition 2.1.

Several real-valued and continuous functions $\\{\phi_{j}\\}_{j=1}^{m}$ form a
Tchebychev system (or T-system) on the interval $\mathbb{I}$ if the $m\times
m$ matrix $[\phi_{j}(\tau_{i})]_{i,j=1}^{m}$ is nonsingular for any increasing
sequence $\\{\tau_{i}\\}_{i=1}^{m}\subset\mathbb{I}$.

Many sets of functions, such as the monomials $1,t,t^{2},\ldots,t^{m-1}$ as
well as shifted translates of Gaussian functions, are known to form $T$
systems. Given a $T$-system $\\{\phi_{m}\\}_{m=1}^{M}$, any linear combination
of the elements $\sum_{i=1}^{m}b_{i}\phi_{i}$ is often called a "polynomial",
and, like real polynomials of degree $m-1$, it has at most $m-1$ zeros on the
real line. We will use some of the properties of $T$-systems to form a dual
polynomial certificate for our program (1.5), which will be a linear
combination of shiften copies of the point-spread function. The dual
polynomial certificate will be the unique solution of the dual program to
(1.5) and will correspond to the unique solution to the original program
(1.5). The construction of a dual certificate is a classical technique used in
compressed sensing Candès . (2006); Fuchs (2005).

######  Theorem 2.2 (Noiseless measurements).

Let $\mu$ be a $K$-sparse nonnegative measure supported on
interior$(\mathbb{I}^{d})$. Let also $M\geq 2K+1$, and suppose that the
functions $\\{\psi^{(i)}_{m_{i}}\\}_{m_{i}=1}^{M}$ form a T-system on
$\mathbb{I}$ for every $i=1,\ldots,d$. Lastly, consider the image
$y\in(\mathbb{R}^{M})^{\bigotimes d}$ of the measure $\mu$ in (1.4) with noise
level $\delta=0$. Then, $\mu$ is the unique solution of program (1.5) with
$\delta^{\prime}=0$.

In other words, given at least $(2K+1)^{d}$ samples from an image consisting
of $K$ point sources, program (1.5) recovers the $K$ point sources exactly.
Here, we require the component-wise functions
$\\{\psi^{(i)}_{m_{i}}\\}_{m_{i}=1}^{M}$ to form a $T$-system for every
$i=1,...,d$. Lemmas 2.3 and 2.4 below establish Theorem 2.2. Their proofs are
located in Appendices A and B, respectively.

######  Lemma 2.3 (Uniqueness of the measure).

Let $\mu$ be a $K$-sparse nonnegative atomic measure supported on
$\Theta\subset interior(\mathbb{I}^{d})$. Then, $\mu$ is the unique solution
of program (1.5) with $\delta^{\prime}=0$ if

  * •

the $M^{d}\times K$ matrix
$[\psi^{(1)}_{i_{1}}(t^{(k)}_{1})\cdots\psi^{(d)}_{i_{d}}(t^{(k)}_{d})]_{i_{1},\cdots,i_{d},k=1}^{i_{1},\cdots,i_{d}=M,k=K}$
has full rank, and

  * •

there exist real coefficients
$\\{b_{i_{1},\cdots,i_{d}}\\}_{i_{1},\cdots,i_{d}=1}^{M}$ and a polynomial

$Q(t_{1},\cdots,t_{d})=\sum_{i_{1},\cdots,i_{d}=1}^{M}b_{i_{1},\cdots,i_{d}}\psi^{(1)}_{i_{1}}(t_{1})\cdots\psi^{(d)}_{i_{d}}(t_{d})$

such that $Q$ is nonnegative on $interior(\mathbb{I}^{d})$ and vanishes only
on $\Theta$.

Our next lemma establishes the second one of the above conditions, namely the
existence of a dual polynomial certificate for our program.

######  Lemma 2.4 (Existence of a dual polynomial certificate).

Let $\mu$ be a $K$-sparse non-negative atomic measure supported on
interior$(\mathbb{I}^{d})$. For $M\geq 2K+1$, suppose that
$\\{\psi^{(i)}_{m_{i}}\\}_{m_{i}=1}^{M}$ form a T-system on $\mathbb{I}$ for
$i=1,...,d$. Then the dual certificate $Q$ in Lemma 2.3 exists.

Combining these two lemmas, we see that the true sparse measure $\mu$ is the
unique solution to our optimization problem, which proves Theorem 2.2.

##  3 The noisy case

In this section, we present our generalized results for the noisy case. Since
the measure in this case, might not be atomic, we use atomic measures to
approximate both true measure and the solution of program (1.5). We use the
Generalized-Wasserstein distance for the recovery error. Before stating the
main Theorem 3.7, we introduce several necessary concepts.

######  Definition 3.1 (Separation).

For an atomic measure $\mu$ supported on
$\Theta=\\{\theta_{k}\\}_{k=1}^{K}=\\{(t_{k}^{(1)},\ldots,t_{k}^{(d)})\\})_{k=1}^{K}$,
let sep$(\mu)$ denote the minimum separation between all impulses in $\mu$ and
the boundary of $\mathbb{I}^{d}$. That is, $sep(\mu)$, is the largest number
$v$ such that

$v\leq|t_{k}^{(i)}-t_{l}^{(i)}|,\;\forall\;k\neq l;\;k,l\in[K],i\in[d]$
$\displaystyle
v\leq|t_{k}^{(i)}-0|,\;\;\;v\leq|t_{k}^{(i)}-1|\;\forall\;i\in[d],k\in[K].$

We call a measure $\mu$, which satisfies $sep(\mu)=\epsilon$, an
$\epsilon$-separated measure. This means that all point sources are separated
from each other and the boundary by at least $\epsilon$.

In Figure 1, the separation of the atomic measure $\mu$ supported at two
points (points $A$ and $B$) is

$\displaystyle sep(\mu)=\min\\{$ $\displaystyle
t^{(1)}_{A},t^{(2)}_{A},t^{(3)}_{A},t^{(1)}_{B},t^{(2)}_{B},t^{(3)}_{B},$
$\displaystyle
1-t^{(1)}_{A},1-t^{(2)}_{A},1-t^{(3)}_{A},1-t^{(1)}_{B},1-t^{(2)}_{B},1-t^{(3)}_{B}$
$\displaystyle|t^{(1)}_{A}-t^{(1)}_{B}|,|t^{(2)}_{A}-t^{(2)}_{B}|,|t^{(3)}_{A}-t^{(3)}_{B}|\\}$

Figure 1: Separation in 3-D

Next, we introduce the Generalized-Wasserstein distance Piccoli Rossi (2014),
a natural notion of distance between measures that has been widely used in the
optimal transport literature. We first recall the total variation (TV) norm
and Wasserstein distance Villani (2008). The total variation norm of a measure
$\mu$ supported on $\mathbb{I}^{d}$ is
$\|\mu\|_{TV}=\int_{\mathbb{I}^{d}}|\mu(\text{d}\theta)|$. It is similar to
the $l_{1}$ norm for measures in finite dimensions. Wasserstein distance is
defined for two non-negative measures $\mu_{1}$ and $\mu_{2}$, supported on
$\mathbb{I}^{d}$, as

$d_{W}(\mu_{1},\mu_{2})=\inf\int_{\mathbb{I}^{d}\times\mathbb{I}^{d}}\|\tau_{1}-\tau_{2}\|_{1}\gamma(\text{d}\tau_{1},\text{d}\tau_{2})$
(3.1)

where the infimum is over every non-negative measure $\gamma$ on
$\mathbb{I}^{d}\times\mathbb{I}^{d}$ that produces $\mu_{1}$ and $\mu_{2}$ as
marginals, i.e.,

$\mu_{1}(A_{1})=\int_{A_{1}\times\mathbb{I}^{d}}\gamma(\text{d}\tau_{1},\text{d}\tau_{2}),\;\;\;\;\mu_{2}(A_{2})=\int_{\mathbb{I}^{d}\times
A_{2}}\gamma(\text{d}\tau_{1},\text{d}\tau_{2})$ (3.2)

for all measurable sets $A_{1},A_{2}\subseteq\mathbb{I}^{d}$. To find the
Wasserstein distance between $\mu_{1}$ and $\mu_{2}$, we require that the
total variation norms of the two measures are equal, i.e.,
$\|\mu_{1}\|_{TV}=\|\mu_{2}\|$. However, this might might not be the case if
$\mu_{1}$ is the true image measure and $\mu_{2}$ is the measure recovered by
(1.5). Therefore, similar to Eftekhari, Bendory Tang (2021), we use the
Generalized-Wasserstein distance between measures with unequal total
variation.

######  Definition 3.2 (Generalized-Wasserstein distance).

For two non-negative measures $\mu_{1}$ and $\mu_{2}$, supported on
$\mathbb{I}^{d}$, the Generalized-Wasserstein distance between $\mu_{1}$ and
$\mu_{2}$ is defined as

$d_{GW}(\mu_{1},\mu_{2})=\inf(\|\mu_{1}-z_{1}\|_{TV}+d_{W}(z_{1},z_{2})+\|\mu_{2}-z_{2}\|_{TV}).$
(3.3)

where the infimum is over pairs of non-negative Borel measures $z_{1}$ and
$z_{2}$ supported on $\mathbb{I}^{d}$ such that
$\|z_{1}\|_{TV}=\|z_{2}\|_{TV}$.

We use the Generalized-Wasserstein distance $d_{GW}(\mu,\hat{\mu})$ to bound
the distance between $\mu$ and $\hat{\mu}$ in Theorem 3.7, where $\mu$ is the
true measure and $\hat{\mu}$ is the solution to the program (1.5). In bounding
this quantity, we approximate the true measure by a sparse and well-separated
atomic measure.

######  Definition 3.3 (Residual).

For a non-negative measure $\mu$ supported on $\mathbb{I}^{d}$, an integer
$K$, and $\epsilon\in(0,1/2]$, we define the residual

$R(\mu,K,\epsilon):=d_{GW}(\mu,\mu_{K,\epsilon})=\min d_{GW}(\mu,\nu)$ (3.4)

where the minimum above is taken over all non-negative $K$-sparse and
$\epsilon$-separated measures $\nu$ supported on interior($\mathbb{I}^{d}$).

In other words, $R(\mu,K,\epsilon)$ can be thought of as the mismatch between
the true measure $\mu$ and the closest well-separated sparse measure
$\mu_{K,\varepsilon}$. The existence of the minimum in the above definition is
explained in Eftekhari, Bendory Tang (2021).

In addition, we will impose a natural smoothness condition on the imaging
apparatus, namely, L-Lipschitz-continuity.

######  Definition 3.4 (Smoothness).

The imaging apparatus $\Psi(\theta)$ is a L-Lipschitz-continuous if

$\Big{\|}\int_{\mathbb{I}^{d}}\Psi(\theta)(\mu_{1}(\text{d}\theta)-\mu_{2}(\text{d}\theta)\Big{\|}_{F}\leq
L\cdot d_{GW}(\mu_{1},\mu_{2})$ (3.5)

for every pair of measures $\mu_{1},\mu_{2}$ supported on $\mathbb{I}^{d}$.

Finally, following Eftekhari, Bendory Tang (2021) and Eftekhari, Tanner .
(2021) we also need to generalize the concept of a $T$-system so that we can
use it in the noisy case. Firstly, we introduce admissible sequences, which
are sequences of ordered indexed numbers from $\mathbb{I}$ with specific
properties. The limits of these numbers (except constants) approach at most
$K$ different numbers in $\mathbb{I}$, and each limiting number has an even
multiplicity, except for exactly one.

######  Definition 3.5 (Admissible sequence).

For a pair of integers $K$ and $M$ obeying $M\geq 2K+1$, we say that
$\\{\\{\tau_{k}^{n}\\}_{k=0}^{M}\\}_{n\geq 1}\subset\mathbb{I}$ is a
$(K,\epsilon)$-admissible sequence if:

  * •

$\tau^{n}_{0}=0$ and $\tau_{M}^{n}=1$ for every $n$

  * •

As $n\to\infty$, the increasing sequence
$\\{\\{\tau_{k}^{n}\\}_{k=1}^{M-1}\\}$ converges (element-wise) to an
$\epsilon$-separated finite subset of $\mathbb{I}$ with at most $K$ distinct
points, where every element has an even multiplicity, except one element that
appears only once.

Figure 2: Figure from "Stable super-resolution of images: theoretical study"
by Eftekhari, Bendory Tang, 2021, Information and Inference: A Journal of the
IMA, 10 (1), p. 169

Recall that $T$-systems are defined for all increasing sequences in
$\mathbb{I}$. In contrast, $T^{*}$-systems are defined for all admissible
sequences, requiring that the determinant of the matrix evaluated at
subsequences of an admissible sequence is positive and all of the minors of
this matrix along a row converge to zero at the same rate.

######  Definition 3.6 ($T^{*}$-system).

For an integer $K$ and an even integer $M$ obeying $M\geq 2K+2$, the real-
valued functions $\\{\phi_{m}\\}_{m=1}^{M}$ form a $T^{*}_{K,\epsilon}$-system
if for every $(K,\epsilon)$-admissible sequence
$\\{\\{\tau_{k}^{n}\\}_{k=0}^{M}\\}_{n\geq 1}$:

  * •

The determinant of the $(M+1)\times(M+1)$ matrix
$[\phi_{m}(\tau^{n}_{k})]_{k,m=0}^{M}$ is positive for all sufficiently large
$n$.

  * •

All minors along the $l$th row of the above matrix
$[\phi_{m}(\tau^{n}_{k})]_{k,m=0}^{M}$ approach zero at the same rate when
$n\to\infty$. Here, $l$ is the index of the element of the limit sequence that
appears only once.

We now mention the following important properties of $T^{*}$-systems:

  * •

A $T^{*}_{K,\epsilon}$-system on $\mathbb{I}$ is also a
$T^{*}_{K^{\prime},\epsilon}$-system for every integer $K^{\prime}\leq K$,
because every $(K^{\prime},\epsilon)$-admissible sequence is also a
$(K,\epsilon)$-admissible sequence.

  * •

If $\\{\phi_{m}\\}_{m=1}^{M}$ form a $T^{*}_{K,\epsilon}$-system on
$\mathbb{I}$, then so do the scaled functions $\\{c_{m}\phi_{m}\\}_{m=1}^{M}$
for any positive constants $\\{c_{m}\\}_{m=1}^{M}$.

In the following theorem, we introduce our main result, which generalizes
Theorem 11 from Eftekhari, Bendory Tang (2021) to higher dimensions. Theorem
3.7 gives an upper bound for the recovery error in terms of the noise level
$\delta\geq 0$ and the separation $\epsilon\in(0,1/2]$.

######  Theorem 3.7 (Noisy measurements).

Consider a non-negative measure $\mu$ supported on $\mathbb{I}^{d}$, a noise
level $\delta\geq 0$, and the image $y\in(\mathbb{R}^{M})^{\bigotimes d}$
obtained from $\mu$ as in (1.2) and (1.4). Assume further that the imaging
apparatus is $L$-Lipschitz continuous in the sense of (3.5).

For an integer $K$ and $\epsilon\in(0,1/2]$, let $\mu_{K,\epsilon}$ be a
$K$-sparse and $\epsilon$-separated non-negative measure supported on
$\mathbb{I}^{d}$ that approximates $\mu$ with residual $R(\mu,K,\epsilon)$.
Let
$\Theta=\\{\theta_{k}\\}_{k=1}^{K}=\\{(t^{(1)}_{k},...,t^{(d)}_{k})\\}_{k=1}^{K}\subset\mathbb{I}^{d}$
denote the support of $\mu_{K,\epsilon}$, and set
$T_{\Omega_{i}}:=\\{t^{(i)}_{k}\\}_{k\in\Omega_{i}\subseteq[K]}$ for each
$i\in[d]$.

If $\hat{\mu}$ is the solution of program (1.5), with
$\delta^{\prime}\geq(1+L\cdot R(\mu,K,\epsilon))\delta$, then

$d_{GW}(\mu,\hat{\mu})\leq c_{1}\delta+c_{2}(\epsilon)+c_{3}R(\mu,K,\epsilon)$
(3.6)

where $d_{GW}$ is a Generalized-Wasserstein metric (3.1), above
$c_{1},c_{2}(\epsilon),c_{3}$ are specified in the proof, and they depend on
the measure $\mu$, the separation $\epsilon$ and the measurement functions
$\\{\psi_{m}\\}_{m=1}^{M}$.

The error bound (3.6) holds if $M\geq 2K+2$ and

  1. 1.

$\\{\psi^{(i)}_{m_{i}}\\}_{m_{i}=1}^{M}$ forms a T-system on $\mathbb{I}$ for
$i\in[d]$,

  2. 2.

$\\{F_{T_{\Omega_{i}}}\\}\cup\\{\psi^{(i)}_{m_{i}}\\}_{m_{i}=1}^{M}$ forms a
$T^{*}$-system on $\mathbb{I}$ for every $\Omega_{i}\subseteq[K]$ and
$i\in[d]$,

  3. 3.

$\\{F^{\pm}_{t^{(i)}_{k}}\\}\cup\\{\psi^{(i)}_{m_{i}}\\}_{m_{i}=1}^{M}$ forms
a $T^{*}$-system on $\mathbb{I}$ for every $k\in[K]$ and $i\in[d-1]$,

  4. 4.

$\\{F^{+}_{t^{(d)}_{k}}\\}\cup\\{\psi^{(i)}_{m_{i}}\\}_{m_{i}=1}^{M}$ forms a
$T^{*}$-system on $\mathbb{I}$ for every $k\in[K]$ and $i\in[d]$,

where the functions $F_{T_{\Omega_{i}}},F_{t_{k}^{(d)}}^{+}$, and
$F_{t_{k}^{(d)}}^{\pm}$ are defined below.

For a finite set of distinct points $T^{\prime}\subset\mathbb{I}$ and
$\epsilon\in(0,sep(T^{\prime})]$, we define the function
$F_{T^{\prime}}:\mathbb{I}\rightarrow\mathbb{R}$ as

$F_{T^{\prime}}(t):=\begin{cases}0,\;\text{when there exists}\;t^{\prime}\in
T^{\prime}\;\text{such that}\;t\in t^{\prime}_{\epsilon}\\\
1,\;\text{elsewhere on}\;\mathbb{I},\end{cases}$ (3.7)

where $t^{\prime}_{\epsilon}=\\{t\in\mathbb{I}:|t-t^{\prime}|\leq\epsilon\\}$
is the $\epsilon$-neighborhood of $t^{\prime}$. For $t^{\prime}\in\mathbb{I}$
and $\epsilon\in(0,1/2]$, we define the functions
$F^{\pm}_{t^{\prime}},F^{+}_{t^{\prime}}:\mathbb{I}\rightarrow\mathbb{R}$ as

$F^{\pm}_{t^{\prime}}(t):=\begin{cases}\pm 1,\;\text{when}\;t\in
t^{\prime}_{\epsilon}\\\ 0,\;\text{elsewhere
on}\;\mathbb{I}\end{cases}\;\;\text{and}\;\;\;\;F^{+}_{t^{\prime}}(t):=\begin{cases}1,\;\text{when}\;t\in
t^{\prime}_{\epsilon}\\\ 0,\;\text{elsewhere on}\;\mathbb{I}.\end{cases}$

Outline of the proof of Theorem 3.7. In the proof of Theorem 3.7, we use
Lemmas 3.8 and 3.9 and Propositions 3.10, 3.11 and 3.12. The first two lemmas
are concerned with bounding the error $h=\hat{\mu}-\mu_{K,\epsilon}$ around
and away from the support, where $\hat{\mu}$ and $\mu_{K,\epsilon}$ are the
solution of the program (1.5) and the approximation of the true measure of the
image, respectively. The above mentioned lemmas require the existence of
particular dual certificates. Propositions 3.11 and 3.12 guarantee the
existence of such dual certificates under some of the conditions required in
Theorem 3.7. The results presented in Propositions 3.11 and 3.12 are
generalizaitons to the high-dimensional case of their 2-dimensional versions
in Eftekhari, Bendory Tang (2021). Proposition 3.10 combines the results from
Lemmas 3.8 and 3.9, and finds the error bound for
$d_{GW}(\mu_{K,\epsilon},\hat{\mu})$.

We use the following notation throughout the paper. For a positive $\epsilon$
and $T^{(i)}=\\{t_{k}^{(i)}\\}_{k=1}^{K}\subset\mathbb{I}$, let us define the
neighborhoods

$\displaystyle
t_{k,\epsilon}^{(i)}=\\{t\in\mathbb{I}:\;|t-t^{(i)}_{k}|\leq\epsilon\\}\subset\mathbb{I},$
$T^{(i)}_{\epsilon}=\bigcup_{k=1}^{K}t^{(i)}_{k,\epsilon}.$

Also, let

$\theta_{k,\epsilon}:=t^{(1)}_{k,\epsilon}\times...\times
t^{(d)}_{k,\epsilon}=\\{\theta\in\mathbb{I}^{d}:\|\theta-\theta_{k}\|_{\infty}\leq\epsilon\\}\subset\mathbb{I}^{d},$
$\Theta_{\epsilon}:=\bigcup_{k=1}^{K}\theta_{k,\epsilon}\subseteq
T^{(1)}_{\epsilon}\times...\times T^{(d)}_{\epsilon}.$

######  Lemma 3.8 (Error away from the support).

Let $\hat{\mu}$ be the solution to program (1.5) with
$\delta^{\prime}\geq\delta$ and set $h:=\hat{\mu}-\mu_{K,\epsilon}$ to be the
error. Fix a positive scalar $\bar{g}$. Suppose that there exist real
coefficients $\\{b_{m_{1},\cdots,m_{d}}\\}_{m_{1},\cdots,m_{d}=1}^{M}$ and a
polynomial

$Q(\theta)=Q(t^{(1)},\cdots,t^{(d)})=\sum_{m_{1},\cdots,m_{d}=1}^{M}b_{m_{1},\cdots,m_{d}}\psi^{(1)}_{m_{1}}(t^{(1)})\cdots\psi^{(d)}_{m_{d}}(t^{(d)})$

such that

$Q(\theta)\geq G(\theta)=\begin{cases}0,\;\text{when there
exists}\;k\in[K]\;\text{such that}\;\theta\in\theta_{k,\epsilon},\\\
\bar{g},\;\text{elsewhere in}\;interior(\mathbb{I}^{d}),\end{cases}$ (3.8)

where equality holds when $\theta\in\Theta=\\{\theta_{k}\\}_{k=1}^{K}$. Then,

$\int_{\Theta_{\epsilon}^{C}}h(d\theta)\leq
2\|b\|_{F}\delta^{\prime}/\bar{g},$

where $b\in(\mathbb{R}^{M})^{\bigotimes d}$ is the tensor with entries
$\\{b_{m_{1},\cdots,m_{d}}\\}_{m_{1},\cdots,m_{d}=1}^{M}$.

Assuming a dual certificate $Q$ exists, Lemma 3.8 bounds the error away from
the support. The proof is stated in Appendix C, and uses the triangle and
Cauchy-Schwartz inequalities. In the next lemma, we estimate the error near
the support.

######  Lemma 3.9 (Error near the support).

Let $\hat{\mu}$ be the solution to program (1.5) with
$\delta^{\prime}\geq\delta$ and set $h:=\hat{\mu}-\mu_{K,\epsilon}$ to be the
error. For $\alpha\in[0,1]$, suppose that there exist real coefficients
$\\{b^{0}_{m_{1},\cdots,m_{d}}\\}_{m_{1},\cdots,m_{d}=1}^{M}$ and a polynomial

$Q^{0}(\theta)=Q^{0}(t^{(1)},\cdots,t^{(d)})=\sum_{m_{1},\cdots,m_{d}=1}^{M}b^{0}_{m_{1},\cdots,m_{d}}\psi^{(1)}_{m_{1}}(t^{(1)})\cdots\psi^{(d)}_{m_{d}}(t^{(d)})$

such that

$Q^{0}(\theta)\geq G^{0}(\theta):=\begin{cases}1,&\text{when there
exists}\;k\in[K]\;\text{such
that}\;\theta\in\theta_{k,\epsilon}\;\text{and}\;\int_{\theta_{k,\epsilon}}h(d\theta)>0\\\
-1,&\text{when there exists}\;k\in[K]\;\text{such
that}\;\theta\in\theta_{k,\epsilon}\;\text{and}\;\int_{\theta_{k,\epsilon}}h(d\theta)\leq
0\\\ -1+\alpha,&\text{when there exists}\;k\in[K]\;\text{such
that}\;\theta=\theta_{k,\epsilon}\;\text{and}\;\int_{\theta_{k,\epsilon}}h(d\theta)\leq
0\\\ -1,&\text{elsewhere in}\;interior(\mathbb{I}^{d})\end{cases}$ (3.9)

where equality holds when $\theta\in\Theta$. Then,

$\sum_{k=1}^{K}\Big{|}\int_{\theta_{k,\epsilon}}h(d\theta)\Big{|}\leq\alpha\|\mu_{K,\epsilon}\|_{TV}+2\Big{(}\|b^{0}\|_{F}+\frac{\|b\|_{F}}{\bar{g}}\Big{)}\delta^{\prime}$
(3.10)

where $b^{0}\in(\mathbb{R}^{M})^{\bigotimes d}$ is the tensor with entries
$\\{b^{0}_{m_{1},\cdots,m_{d}}\\}_{m_{1},\cdots,m_{d}=1}^{M}$.

Assuming a dual certificate $Q^{0}$ exists, Lemma 3.9 bounds the error near
the support, and together with Lemma 3.8, it is used to bound the Generalized-
Wasserstein distance between the solution of program (1.5) and the
approximation $\mu_{K,\varepsilon}$ of the exact measure with a $K$-sparse and
$\epsilon$-separated atomic measure supported on $\mathbb{I}^{d}$.

If the dual certificates $Q$ and $Q^{0}$ exist, then inequality (3.11) below
holds. The proof in the 1-dimensional case is presented in Lemma 18 of
Eftekhari, Tanner . (2021), and we here extended it to higher dimensions.

######  Proposition 3.10 (Error in Wasserstein metric).

Suppose the dual certificates $Q$ and $Q^{0}$ in Lemmas (3.8) and (3.9) exist.
Then,

$d_{GW}(\mu_{K,\epsilon},\hat{\mu})\leq\Big{(}\frac{8\|b\|_{F}}{\bar{g}}+6\|b^{0}\|_{F}\Big{)}\delta^{\prime}+(\epsilon+3\alpha)\|\mu_{K,\epsilon}\|_{TV}.$
(3.11)

In the next two propositions, we show the existence of dual certificates $Q$
and $Q^{0}$ under some mild conditions. These results generalize similar
propositions from Eftekhari, Tanner . (2021); Eftekhari, Bendory Tang (2021)
to the higher-dimensional case. The detailed proofs of Propositions 3.11 and
3.12 can be found in Appendices E and F, respectively.

######  Proposition 3.11 (Dual certificate for error away from support).

Suppose that $\\{\psi^{(i)}_{m_{i}}\\}_{m_{i}=1}^{M}$ form a T-system on
$\mathbb{I}$ for $i\in[d]$ with $M\geq 2K+2$. For every partition
$\pi=\\{\Omega_{1},\ldots,\Omega_{d}\\}$ of $[K]$, suppose also that all
$\\{F^{(i)}_{T_{\Omega_{i}}}\\}\cup\\{\psi^{(i)}_{m}\\}_{m=1}^{M}$ are
$T^{*}_{K,\epsilon}$-systems on $\mathbb{I}$ for each $i\in[d]$. Then the dual
certificate $Q$, as specified in Lemma 3.8, exists with

$\bar{g}=(d-1)d^{K-2}.$

######  Proposition 3.12 (Dual certificate for error near support).

For $M\geq 2K+2$, suppose that $\\{\psi^{(i)}_{m}\\}_{m=1}^{M}$ form a
T-system on $\mathbb{I}$. Suppose also that all
$\\{F^{\pm}_{t^{(j)}_{k}}\\}\cup\\{\psi^{(i)}_{m}\\}_{m=1}^{M}$ are
$T^{*}_{K,\epsilon}$-systems on $\mathbb{I}$ for each $1\leq j\leq d-1$.
Additionally, $\\{F^{+}_{t^{(d)}_{k}}\\}\cup\\{\psi^{(i)}_{m}\\}_{m=1}^{M}$
also form $T^{*}_{K,\epsilon}$-systems on $\mathbb{I}$. Then the dual
certificate $Q^{0}$, as specified in Lemma 3.9 , exists with

$\alpha=\alpha(\epsilon)=1+(-1)^{d-1}/q^{\pi_{*}}_{max}(\epsilon),$

where $q^{\pi_{*}}_{max}(\epsilon)$ is defined in the proof.

##  4 Discussion

In this paper we have shown that program (1.5) solves the super-resolution
imaging problem in any dimension, assuming that the point-spread function
factorizes, and that translates of each of the factors satisfy a number of
$T$-system and $T^{*}$-system conditions. Our work extends Eftekhari, Bendory
Tang (2021) from the 2-dimensional to the $d$-dimensional case. We show that
if there is no measurement noise, then, one can recover the true locations of
the point-sources regardless of how close they are to each other, and, if
there is noise, then the quality of the estimate will depend on the separation
of the point-sources through the noise level.

We wish to remark that here we show that the output of a certain convex
program (1.5) is the desired true image, but we do not provide an algorithm
for solving this program. In practice, as noted in Eftekhari, Tanner . (2021),
one may want to minimize a certain objective function, such as the total
variation of the unknown measure $\mu$. There already exist algorithms for
solving such programs, for example, see Boyd . (2017).

Of course, one of the main open questions that remain is whether our results
can extend to the case when the point-spread function does not factorize.
Solving this problem may require developing a high-dimensional analog of
$T$-systems, which are currently only defined for functions in one variable.
Perhaps a simpler start is to consider point-spread functions that factorize
after a suitable rotation is applied – this is at least true for all Gaussian
point-spread functions.

## Acknowledgements

We wish to thank Geoffrey Schiebinger and Jean-Baptiste Seby for helpful
discussions at the beginning stages of this project. ER was supported by an
NSERC Discovery Grant (DGECR-2020-00338).

## References

  * Azais . (2015) azais2015spikeAzais, JM., De Castro, Y. Gamboa, F.  2015\.  Spike detection from inaccurate samplings Spike detection from inaccurate samplings.  Applied and Computational Harmonic Analysis382177–195.
  * Bendory . (2016) bendory2016robustBendory, T., Dekel, S. Feuer, A.  2016\.  Robust recovery of stream of pulses using convex optimization Robust recovery of stream of pulses using convex optimization.  Journal of mathematical analysis and applications4422511–536.
  * Betzig . (2006) betzig2006imagingBetzig, E., Patterson, GH., Sougrat, R., Lindwasser, OW., Olenych, S., Bonifacino, JS.Hess, HF.  2006\.  Imaging intracellular fluorescent proteins at nanometer resolution Imaging intracellular fluorescent proteins at nanometer resolution.  science31357931642–1645.
  * Boyd . (2017) boyd2017Boyd, N., Schiebinger, G. Recht, B.  2017\.  The alternating descent conditional gradient method for sparse inverse problems The alternating descent conditional gradient method for sparse inverse problems.  SIAM Journal on Optimization272616–639.
  * Candès Fernandez-Granda (2014) candes2014towardsCandès, EJ. Fernandez-Granda, C.  2014\.  Towards a mathematical theory of super-resolution Towards a mathematical theory of super-resolution.  Communications on pure and applied Mathematics676906–956.
  * Candès . (2006) candes2006robustCandès, EJ., Romberg, J. Tao, T.  2006\.  Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information.  IEEE Transactions on information theory522489–509.
  * Candés Tao (2005) candes2005decodingCandés, EJ. Tao, T.  2005\.  Decoding by linear programming Decoding by linear programming.  IEEE transactions on information theory51124203–4215.
  * Demanet . (2013) demanet2013superDemanet, L., Needell, D. Nguyen, N.  2013\.  Super-resolution via superset selection and pruning Super-resolution via superset selection and pruning.  arXiv preprint arXiv:1302.6288.
  * Denoyelle . (2017) denoyelle2017supportDenoyelle, Q., Duval, V. Peyré, G.  2017\.  Support recovery for sparse super-resolution of positive measures Support recovery for sparse super-resolution of positive measures.  Journal of Fourier Analysis and Applications2351153–1194.
  * Donoho (2006) donoho2006compressedDonoho, DL.  2006\.  Compressed sensing Compressed sensing.  IEEE Transactions on information theory5241289–1306.
  * Duval Peyré (2015) duval2015exactDuval, V. Peyré, G.  2015\.  Exact support recovery for sparse spikes deconvolution Exact support recovery for sparse spikes deconvolution.  Foundations of Computational Mathematics1551315–1355.
  * Eftekhari, Bendory Tang (2021) eftekhari2021stableEftekhari, A., Bendory, T. Tang, G.  2021\.  Stable super-resolution of images: theoretical study Stable super-resolution of images: theoretical study.  Information and Inference: A Journal of the IMA101161–193.
  * Eftekhari, Tanner . (2021) eftekhari2021sparseEftekhari, A., Tanner, J., Thompson, A., Toader, B. Tyagi, H.  2021\.  Sparse non-negative super-resolution — simplified and stabilised Sparse non-negative super-resolution — simplified and stabilised.  Applied and Computational Harmonic Analysis50216–280.
  * Ekanadham . (2011) ekanadham2011blindEkanadham, C., Tranchina, D. Simoncelli, E.  2011\.  A blind sparse deconvolution method for neural spike identification A blind sparse deconvolution method for neural spike identification.  Advances in Neural Information Processing Systems24.
  * Evanko (2009) evanko2009primerEvanko, D.  2009\.  Primer: fluorescence imaging under the diffraction limit Primer: fluorescence imaging under the diffraction limit.  Nature methods6119–20.
  * Fuchs (2005) fuchs2005sparsityFuchs, JJ.  2005\.  Sparsity and uniqueness for some specific under-determined linear systems Sparsity and uniqueness for some specific under-determined linear systems.  Proceedings.(ICASSP’05). IEEE International Conference on Acoustics, Speech, and Signal Processing, 2005. Proceedings.(icassp’05). ieee international conference on acoustics, speech, and signal processing, 2005\. ( 5, v–729).
  * Fyhn . (2013) fyhn2013spectralFyhn, K., Dadkhahi, H. Duarte, MF.  2013\.  Spectral compressive sensing with polar interpolation Spectral compressive sensing with polar interpolation.  2013 IEEE International Conference on Acoustics, Speech and Signal Processing 2013 ieee international conference on acoustics, speech and signal processing ( 6225–6229).
  * Hess . (2006) hess2006ultraHess, ST., Girirajan, TP. Mason, MD.  2006\.  Ultra-high resolution imaging by fluorescence photoactivation localization microscopy Ultra-high resolution imaging by fluorescence photoactivation localization microscopy.  Biophysical journal91114258–4272.
  * Karlin Studden (1966) karlin1966tchebycheffKarlin, S. Studden, WJ.  1966\.  Tchebycheff systems: With applications in analysis and statistics Tchebycheff systems: With applications in analysis and statistics ( 15).  Wiley.
  * Khaidukov . (2004) khaidukov2004diffractionKhaidukov, V., Landa, E. Moser, TJ.  2004\.  Diffraction imaging by focusing-defocusing: An outlook on seismic superresolution Diffraction imaging by focusing-defocusing: An outlook on seismic superresolution.  Geophysics6961478–1490.
  * Morgenshtern Candès (2015) morgenstern2015stableMorgenshtern, V. Candès, E.  2015\.  Stable super-resolution of positive sources: the discrete setup Stable super-resolution of positive sources: the discrete setup.  arXiv:1504.00717.
  * Piccoli Rossi (2014) piccoli2014generalizedPiccoli, B. Rossi, F.  2014\.  Generalized Wasserstein distance and its application to transport equations with source Generalized wasserstein distance and its application to transport equations with source.  Archive for Rational Mechanics and Analysis2111335–358.
  * Puschmann Kneer (2005) puschmann2005superPuschmann, KG. Kneer, F.  2005\.  On super-resolution in astronomical imaging On super-resolution in astronomical imaging.  Astronomy & Astrophysics4361373–378.
  * Rust . (2006) rust2006subRust, MJ., Bates, M. Zhuang, X.  2006\.  Sub-diffraction-limit imaging by stochastic optical reconstruction microscopy (STORM) Sub-diffraction-limit imaging by stochastic optical reconstruction microscopy (storm).  Nature methods310793–796.
  * Schiebinger . (2018) schiebinger2018superresolutionSchiebinger, G., Robeva, E. Recht, B.  2018\.  Superresolution without separation Superresolution without separation.  Information and Inference: A Journal of the IMA711–30.
  * Tang . (2013) tang2013compressedTang, G., Bhaskar, BN., Shah, P. Recht, B.  2013\.  Compressed sensing off the grid Compressed sensing off the grid.  IEEE transactions on information theory59117465–7490.
  * Tur . (2011) tur2011innovationTur, R., Eldar, YC. Friedman, Z.  2011\.  Innovation rate sampling of pulse streams with application to ultrasound imaging Innovation rate sampling of pulse streams with application to ultrasound imaging.  IEEE Transactions on Signal Processing5941827–1842.
  * Villani (2008) villani2008optimalVillani, C.  2008\.  Optimal transport, old and new. Notes for the 2005 Saint-Flour summer school Optimal transport, old and new. notes for the 2005 saint-flour summer school.  Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer3.

##  Appendix A Proof of Lemma 2.3

Clearly, the true measure $\mu=\sum_{k=1}^{K}a_{k}\delta_{\theta_{k}}$ is a
solution of (1.5). Suppose that there is another measure $\hat{\mu}$ that
solves (1.5). Then, by (1.5) we necessarily have

$\int_{\mathbb{I}^{d}}\Psi_{i_{1},\cdots,i_{d}}\text{d}\mu=\int_{\mathbb{I}^{d}}\Psi_{i_{1},\cdots,i_{d}}\text{d}\hat{\mu}$

for all $i_{1},...,i_{d}\in[M]$. Therefore, summing both sides over
$i_{1},...,i_{d}$ with coefficients $b_{i_{1},...,i_{d}}$, we get that

$\int_{\mathbb{I}^{d}}Q\text{d}\mu=\int_{\mathbb{I}^{d}}Q\text{d}\hat{\mu}$

But note that $Q=0$ on $\Theta$, therefore,

$\int_{\mathbb{I}^{d}\setminus\Theta}Q\text{d}\mu=\int_{\mathbb{I}^{d}\setminus\Theta}Q\text{d}\hat{\mu}$

But $\mu=0$ on $\mathbb{I}^{d}\setminus\Theta$, and $Q>0$ on
$\mathbb{I}^{d}\setminus\Theta$. Therefore, $\hat{\mu}=0$ on
$\mathbb{I}^{d}\setminus\Theta$.

##  Appendix B Proof of Lemma 2.4

The following lemma has been stated in Eftekhari, Tanner . (2021) in Lemma 15,
and proved in Karlin Studden (1966) in Theorem 5.1.

######  Lemma B.1 (Univariate polynomial of a T-system).

Consider a set $T^{\prime}\subset\mathbb{I}$ of size $K^{\prime}$. With $M\geq
2K^{\prime}+1$, suppose that $\\{\phi_{m}\\}_{m=1}^{M}$ form a T-system on
$\mathbb{I}$. Then, there exist coefficients $\\{b_{m}\\}_{m=1}^{M}$ such that
the polynomial $q_{T^{\prime}}=\sum_{m=1}^{M}b_{m}\phi_{m}$ is non-negative on
$\mathbb{I}$ and vanishes only on $T^{\prime}$.

Consider any partition $\pi$ of $[K]$ into $d$ parts,
$\Omega_{1},...,\Omega_{d}\subset[K]$, and we denote throughout of this paper

$T_{\Omega_{1}}=\\{t^{(1)}_{k}\\}_{k\in\Omega_{1}},\cdots,T_{\Omega_{d}}=\\{t^{(d)}_{k}\\}_{k\in\Omega_{d}}.$
(B.1)

By assumption $\\{\psi^{(i)}_{m_{i}}\\}_{m_{i}=1}^{M}$ forms a T-system for
each $i=1,...,d$, so by Lemma B.1, there exist polynomials
$q_{T_{\Omega_{1}}},\cdots,q_{T_{\Omega_{d}}}$ that are nonnegative on
$\mathbb{I}$ and vanish only on $T_{\Omega_{1}},\cdots,T_{\Omega_{d}}$
respectively.

Let us form a polynomial

$Q(\theta)=Q(t^{(1)},\cdots,t^{(d)})=\sum_{\text{all
partitions}\;\pi\;\text{of}\;[K]}q_{T_{\Omega_{1}}}(t^{(1)})\cdot...\cdot
q_{T_{\Omega_{d}}}(t^{(d)}),$

where the sum is all over partitions of $[K]$. Obviously, $Q$ is a nonnegative
on $\mathbb{I}^{d}$, because each summand is nonnegative. Now, let’s verify
$Q$ vanishes at $\Theta$. Take $\theta_{k}=(t^{(1)}_{k},\cdots,t^{(d)}_{k})$,
then since $k$ always belongs to one of partitions, each summand would be zero
at $\theta_{k}$.

When $\theta\in\Theta^{C}$, then consider

  1. 1.

For
$\theta=(t^{(1)},...,t^{(d)})\in(T^{(1)}_{\epsilon})^{C}\times\cdots\times(T^{(d)}_{\epsilon})^{C}\subseteq\Theta^{C}_{\epsilon}$,
it holds

$q_{T_{\Omega_{1}}}(t^{(1)})\cdot...\cdot q_{T_{\Omega_{d}}}(t^{(d)})>0$

for every partition, by summing up over all partitions, it immediately follows

$Q(\theta)>0$

  2. 2.

For
$\theta\in\Theta^{C}_{\epsilon}\setminus\Big{(}(T^{(1)}_{\epsilon})^{C}\times\cdots\times(T^{(d)}_{\epsilon})^{C}\Big{)}$.
We will consider two cases

    1. (a)

Since the order of indexes doesn’t matter, assume that there exist
$k_{1},...,k_{l}\in[K]$, might all equal to each other with $l<d$, such that
$\theta\in t^{(1)}_{k_{1},\epsilon}\times\cdots\times
t^{(l)}_{k_{l},\epsilon}\times t^{(l+1)}\times\cdots t^{(d)}$. There exist a
partition $\pi^{*}$ such that the first $l$ elements of it
$\Omega^{*}_{1},...,\Omega^{*}_{l}$ doesn’t contain any of these numbers
$\\{k_{1},...,k_{l}\\}$, so for this partition

$q_{T_{\Omega^{*}_{1}}}(t^{(1)})\cdot...\cdot
q_{T_{\Omega^{*}_{d}}}(t^{(d)})>0.$

Therefore,

$Q(\theta)>0$

    2. (b)

The case when $l=d$, which means there exist $k_{1},...,k_{d}\in[K]$, not all
equal to each other, such that $\theta\in
t^{(1)}_{k_{1},\epsilon}\times\cdots\times t^{(d)}_{k_{d},\epsilon}$. Consider
a partition $\pi^{*}$ such that $\Omega^{*}_{i}$ doesn’t contain $k_{i}$, so

$q_{T_{\Omega^{*}_{1}}}(t^{(1)})\cdot...\cdot
q_{T_{\Omega^{*}_{d}}}(t^{(d)})>0$

And, we have

$Q(\theta)>0.$

In conclusion, $Q(\theta)$ is everywhere positive except it vanishes only on
$\Theta$.

##  Appendix C Proof of Lemma 3.8

By feasibility of both $\hat{\mu}$ and $\mu_{K,\epsilon}$ for the Program,
applying the triangle inequality, we get

$\Big{\|}\int_{\mathbb{I}^{d}}\Psi(\theta)h(\text{d}\theta)\Big{\|}_{F}\leq
2\delta^{\prime}$

Now, using the existence of the dual certificate

$\displaystyle\bar{g}\int_{\Theta^{C}_{\epsilon}}h(\text{d}\theta)$
$\displaystyle\leq\int_{\Theta^{C}_{\epsilon}}G(\theta)h(\text{d}\theta)\;\;(\text{since}\;h\;\text{is
nonnegative on}\;\Theta^{C}_{\epsilon})$
$\displaystyle=\int_{\Theta^{C}_{\epsilon}}G(\theta)h(\text{d}\theta)+\sum_{k=1}^{K}\int_{\theta_{k,\epsilon}}G(\theta)h(\text{d}\theta)$
$\displaystyle=\int_{\mathbb{I}^{d}}G(\theta)h(\text{d}\theta)$
$\displaystyle\leq\sum_{m_{1},\cdots,m_{d}=1}^{M}b_{m_{1},\cdots,m_{d}}\int_{\mathbb{I}^{d}}\psi^{(1)}_{m_{1}}(t^{(1)})\cdots\psi^{(d)}_{m_{d}}(t^{(d)})h(\text{d}t^{(1)},\cdots,\text{d}t^{(d)})\;\;\text{(by
\eqref{eq:er_away})}$
$\displaystyle=\Big{\langle}b,\int_{\mathbb{I}^{d}}\Psi(\theta)h(\text{d}\theta)\Big{\rangle}$
$\displaystyle\leq\|b\|_{F}\Big{\|}\int_{\mathbb{I}^{d}}\Psi(\theta)h(\text{d}\theta)\Big{\|}_{F}\;\;(\text{Cauchy-
Schwarz inequality})$ $\displaystyle\leq 2\|b\|_{F}\delta^{\prime}$

where $b\in(\mathbb{R}^{M})^{\bigotimes d}$.

##  Appendix D Proof of Lemma 3.9

The existence of the dual certificate $Q^{0}$ allows us to write that

$\displaystyle\sum_{k=1}^{K}\Big{|}\int_{\theta_{k,\epsilon}}h(\text{d}\theta)\Big{|}$
$\displaystyle=$
$\displaystyle=\sum_{k=1}^{K}\int_{\theta_{k,\epsilon}}s_{k}h(\text{d}\theta)\;\;\;\;\Big{(}s_{k}:=sign\Big{(}\int_{\theta_{k,\epsilon}}h(\text{d}\theta)\Big{)}\Big{)}$
$\displaystyle=\sum_{k=1}^{K}\int_{\theta_{k,\epsilon}}(s_{k}-Q^{0}(\theta))h(\text{d}\theta)+\sum_{k=1}^{K}\int_{\theta_{k,\epsilon}}Q^{0}(\theta)h(\text{d}\theta)$
$\displaystyle=\sum_{k=1}^{K}\int_{\theta_{k,\epsilon}}(s_{k}-Q^{0}(\theta))h(\text{d}\theta)+\int_{\mathbb{I}^{d}}Q^{0}(\theta)h(\text{d}\theta)-\int_{\Theta^{C}_{\epsilon}}Q^{0}(\theta)h(\text{d}\theta)$
$\displaystyle=\sum_{s_{k}=1}\int_{\theta_{k,\epsilon}}(1-Q^{0}(\theta))h(\text{d}\theta)+\sum_{s_{k}=-1}\int_{\theta_{k,\epsilon}}(-1-Q^{0}(\theta))h(\text{d}\theta)$
$\displaystyle\;\;\;\;\;\;\;\;\;\;+\int_{\mathbb{I}^{d}}Q^{0}(\theta)h(\text{d}\theta)-\int_{\Theta^{C}_{\epsilon}}Q^{0}(\theta)h(\text{d}\theta)$
$\displaystyle=\sum_{s_{k}=1}\int_{\theta_{k,\epsilon}}(1-Q^{0}(\theta))h(\text{d}\theta)+\sum_{s_{k}=-1}\int_{\theta_{k,\epsilon}\setminus\theta_{k}}(-1-Q^{0}(\theta))h(\text{d}\theta)$
$\displaystyle+\sum_{s_{k}=-1}\int_{\theta_{k}}(-1+\alpha-Q^{0}(\theta))h(\text{d}\theta)-\alpha\sum_{s_{k}=-1}\int_{\theta_{k}}h(\text{d}\theta)+\int_{\mathbb{I}^{d}}Q^{0}(\theta)h(\text{d}\theta)-\int_{\Theta^{C}_{\epsilon}}Q^{0}(\theta)h(\text{d}\theta)$
$\displaystyle\leq-\alpha\sum_{s_{k}=-1}\int_{\theta_{k}}h(\text{d}\theta)+\int_{\mathbb{I}^{d}}Q^{0}(\theta)h(\text{d}\theta)+\int_{\Theta^{C}_{\epsilon}}h(\text{d}\theta)\;\;\;\;(\text{by
\eqref{eq:0.2} })$
$\displaystyle\leq-\alpha\sum_{s_{k}=-1}\int_{\theta_{k}}h(\text{d}\theta)+\int_{\mathbb{I}^{d}}Q^{0}(\theta)h(\text{d}\theta)+2\|b\|_{F}\delta^{\prime}/\bar{g}\;\;\;\;(\text{by
previous lemma})$
$\displaystyle\leq\alpha\sum_{s_{k}=-1}\int_{\theta_{k}}\mu_{K,\epsilon}(\text{d}\theta)+\int_{\mathbb{I}^{d}}Q^{0}(\theta)h(\text{d}\theta)+2\|b\|_{F}\delta^{\prime}/\bar{g}\;\;\;\;(\text{since}\;h:=\hat{\mu}-\mu_{K,\epsilon}\;\text{and}\;\hat{\mu}\geq
0)$
$\displaystyle=\alpha\sum_{s_{k}=-1}\sum_{k=1}^{K}\int_{\theta_{k}}a_{k}(\text{d}\theta)+\int_{\mathbb{I}^{d}}Q^{0}(\theta)h(\text{d}\theta)+2\|b\|_{F}\delta^{\prime}/\bar{g}\;\;\;\;(\text{since}\;\mu_{K,\epsilon}=\sum_{k=1}^{K}a_{k}\delta_{\theta_{k}})$
$\displaystyle\leq\alpha\|\mu_{K,\epsilon}\|_{TV}+\int_{\mathbb{I}^{d}}Q^{0}(\theta)h(\text{d}\theta)+2\|b\|_{F}\delta^{\prime}/\bar{g}$
$\displaystyle=\alpha\|\mu_{K,\epsilon}\|_{TV}+\Big{\langle}b^{0},\int_{\mathbb{I}^{d}}\Psi(\theta)h(\text{d}\theta)\Big{\rangle}+2\|b\|_{F}\delta^{\prime}/\bar{g}$
$\displaystyle\leq\alpha\|\mu_{K,\epsilon}\|_{TV}+\|b^{0}\|_{F}\cdot
2\delta^{\prime}+2\|b\|_{F}\delta^{\prime}/\bar{g}\;\;\;\;(\text{by Cauchy-
Schwarz and ineq. from prev. lemma})$

Above the tensor $b^{0}\in(\mathbb{R}^{M})^{\bigotimes d}$ formed by
coefficients of dual certificate $Q^{0}$.

##  Appendix E Proof of Proposition 3.11

In the proof of proposition we will use the lemma about $T^{*}$-systems; see
Eftekhari, Tanner . (2021), Proposition 19 for proof details.

######  Lemma E.1 (Univariate polynomial of a $T^{*}$-system).

Consider a finite set $T^{\prime}\subset\mathbb{I}$ of size no longer than
$K$. For $M\geq 2K+2$, suppose that $\\{\phi_{m}\\}_{m=1}^{M}$ form a T-system
on $\mathbb{I}$. Consider also $F^{\prime}:\mathbb{R}\rightarrow\mathbb{R}$
and suppose that $\\{F^{\prime}\\}\cup\\{\phi_{m}\\}_{m=1}^{M}$ form a
$T^{*}_{K,\epsilon}$-system on $\mathbb{I}$. Then there exist real
coefficients $\\{b_{m}\\}_{m=1}^{M}$ and a continuous polynomial
$q_{T^{\prime}}=\sum_{m=1}^{M}b_{m}\phi_{m}$ such that $q_{T^{\prime}}\geq
F^{\prime}$ with equality holding on $T^{\prime}$.

Consider any partition $\pi=\\{\Omega_{1},...,\Omega_{d}\\}$ of $[K]$ and
define $T_{\Omega_{i}}$ in the sense of (B.1). By assumption,
$\\{F_{T_{\Omega_{i}}}\\}\cup\\{\psi^{(i)}_{m_{i}}\\}_{m_{i}=1}^{M}$ form a
$T^{*}_{K,\epsilon}$-system on $\mathbb{I}$ for each $i\in[d]$. Therefore, by
above lemma, there exist polynomials $q_{T_{\Omega_{i}}}$ for each $i\in[d]$
such that

$q_{T_{\Omega_{i}}}\geq F_{T_{\Omega_{i}}}$

with equality holding on $T_{\Omega_{i}}$.

Consider the polynomial

$Q(\theta)=Q(t^{(1)},\cdots,t^{(d)})=\sum_{all\;partitions\;\pi\;of[K]}q_{T_{\Omega_{1}}}(t^{(1)})\cdots
q_{T_{\Omega_{d}}}(t^{(d)})$

where the sum is over all partitions of $[K]$. We next show that $Q$ is the
desired dual certificate.

For every $\theta\in\theta_{k,\epsilon}$, it holds that

$\displaystyle
Q(\theta)=\sum_{all\;partitions\;\pi\;of[K]}q_{T_{\Omega_{1}}}(t^{(1)})\cdots
q_{T_{\Omega_{d}}}(t^{(d)})\geq\sum_{all\;partitions\;\pi\;of[K]}F_{T_{\Omega_{1}}}(t^{(1)})\cdots
F_{T_{\Omega_{d}}}(t^{(d)})=0$

because we know for sure that every partition has a set $\Omega_{j}$ which
contains $k$, that means $F_{T_{\Omega_{j}}}(t^{(j)})=0$. And, equality
achieves exactly at $\Theta$.

On the other hand, consider $\theta\in\Theta^{C}_{\epsilon}$.

  1. 1.

For
$\theta=(t^{(1)},...,t^{(d)})\in(T^{(1)}_{\epsilon})^{C}\times\cdots\times(T^{(d)}_{\epsilon})^{C}\subseteq\Theta^{C}_{\epsilon}$,
it holds

$q_{T_{\Omega_{1}}}(t^{(1)})\cdots q_{T_{\Omega_{d}}}(t^{(d)})\geq 1$

for every partition, by summing up over all partitions, it immediately follows

$Q(\theta)\geq d^{K}$

  2. 2.

For
$\theta\in\Theta^{C}_{\epsilon}\setminus\Big{(}(T^{(1)}_{\epsilon})^{C}\times\cdots\times(T^{(d)}_{\epsilon})^{C}\Big{)}$.
We will consider two cases

    1. (a)

Since the order of indexes doesn’t matter, assume that there exist
$k_{1},...,k_{l}\in[K]$, might all equal to each other with $l<d$, such that
$\theta\in t^{(1)}_{k_{1},\epsilon}\times\cdots\times
t^{(l)}_{k_{l},\epsilon}\times t^{(l+1)}\times\cdots t^{(d)}$. Suppose among
these $\\{k_{1},...,k_{l}\\}$ indexes, there are only $p$ different numbers,
and WLOG, we can take

$\displaystyle k_{1}=\cdots=k_{a_{1}}$ $\displaystyle
k_{a_{1}+1}=\cdots=k_{a_{1}+a_{2}}$ $\displaystyle\;\;\;\;\;\vdots$
$\displaystyle k_{a_{1}+\cdots+a_{p-1}+1}=\cdots=k_{a_{1}+\cdots+a_{p}}$

with $a_{1}+\cdots+a_{p}=l$, where each $a_{i}\geq 1$. Using this notation, we
can write

$\displaystyle Q(\theta)=$
$\displaystyle\sum_{\pi}q_{T_{\Omega_{1}}}(t^{(1)})\cdot...\cdot
q_{T_{\Omega_{a_{1}}}}(t^{(a_{1})})\cdot
q_{T_{\Omega_{a_{1}+1}}}(t^{(a_{1}+1)})\cdot...\cdot
q_{T_{\Omega_{a_{1}+a_{2}}}}(t^{(a_{1}+a_{2})})\cdot$ $\displaystyle...\cdot
q_{T_{\Omega_{a_{1}+\cdots+a_{p-1}+1}}}(t^{(a_{1}+\cdots+a_{p-1}+1)})\cdot...\cdot
q_{T_{\Omega_{a_{1}+\cdots+a_{p}}}}(t^{(a_{1}+\cdots+a_{p})})\cdot
q_{T_{\Omega_{l+1}}}(t^{(l+1)})\cdot...\cdot q_{T_{\Omega_{d}}}(t^{(d)})$

This polynomial is not zero only when the first $a_{1}$ components of $\theta$
are not in $\Omega_{1},...,\Omega_{a_{1}}$, and the second $a_{2}$ components
are not in $\Omega_{a_{1}+1},...,\Omega_{a_{1}+a_{2}}$, and so on, then all
the components starting from $t^{(l+1)}$ can be in any place, therefore

$Q(\theta)\geq(d-a_{1})\cdot\cdots\cdot(d-a_{p})d^{K-p}$

with $a_{1}+...+a_{p}=l$, $l\geq 1,\;a_{i}\geq 1,\;p\geq 1$.

Using Lemma E.2, we know that for each $1\leq l\leq d-1$, we have
$Q(\theta)\geq(d-l)d^{K-1}$, and it achieves its minimum when $l=d-1$, so

$Q(\theta)\geq d^{K-1}$

    2. (b)

The case when $l=d$, which means there exist $k_{1},...,k_{d}\in[K]$, not all
equal to each other, such that $\theta\in
t^{(1)}_{k_{1},\epsilon}\times\cdots\times t^{(d)}_{k_{d},\epsilon}$.
Repeating the same steps as above, we obtain a minimization problem

$Q(\theta)\geq(d-a_{1})\cdot\cdots\cdot(d-a_{p})d^{K-p}$

with $a_{1}+\cdots+a_{p}=d$, where $a_{i}\geq 1$ and $p\geq 2$.
When $p=2$, consider a function $P(x)=(d-x)(d-(d-x))=(d-x)x$, which is concave
down, and achieves it’s minimum at endpoints $x=1$, $P(1)=d-1$, so
$Q(\theta)\geq(d-1)d^{K-2}$
So for $l=d$, using Lemma E.3

$Q(\theta)\geq(d-1)d^{K-2}$

Comparing the lower bounds in all above cases, we see that

$Q(\theta)\geq(d-1)d^{K-2}$

for all $d$.

######  Lemma E.2.

For a fixed $l$, with $l<d$, the following

$(d-l)d^{p-1}\leq(d-a_{1})\cdot...\cdot(d-a_{p})$

is true for any partition of $l$, i.e., $a_{1}+\cdots+a_{p}=l$, $l\geq
1,\;p\geq 1,\;a_{i}\geq 1$.

###### Proof.

We proceed by induction on $l$. The base case is trivial, $l=1$, we have
$p=1$, so $(d-1)\leq(d-1)$. Suppose we proved for $l=n-1$ for some $n$, so we
have

$(d-n+1)d^{p-1}\leq(d-a_{1})\cdot...\cdot(d-a_{p})$

for any partition of $n-1$, i.e., $a_{1}+\cdots+a_{p}=n-1,\;p\geq
1,\;a_{i}\geq 1$.
Now, let’s prove for $l=n$ case, and consider any partition of $n$, say
$b_{1}+\cdots+b_{q}=n$, then $\\{b_{1},...,b_{q}\\}$ belongs to one of these
forms

  * •

If there exists $1\in\\{b_{1},...,b_{q}\\}$, then WLOG,
$b_{1}+\cdots+b_{q-1}=n-1$ is a partition of $n-1$, so

$(d-n)d^{q-1}\leq(d-n+1)(d-1)d^{q-2}\leq(d-b_{1})\cdot...\cdot(d-b_{q-1})(d-1)=(d-b_{1})\cdot...\cdot(d-b_{q})$

  * •

If $1\notin\\{b_{1},...,b_{q}\\}$, then $(b_{1}-1)+\cdots+b_{q}=n-1$ is a
partition of $n-1$

$\displaystyle(d-n)d^{q-1}$
$\displaystyle=(d-n+1)d^{q-1}-d^{q-1}\leq(d-b_{1}+1)\cdot...\cdot(d-b_{q})-d^{q-1}=$
$\displaystyle=(d-b_{1})\cdot...\cdot(d-b_{q})+(d-b_{2})\cdot...\cdot(d-b_{q})-d^{q-1}\leq(d-b_{1})\cdot...\cdot(d-b_{q})$

due to the last difference is negative.

This finishes our proof. ∎

######  Lemma E.3.

For any partition of $d$ such that $a_{1}+\cdots+a_{p}=d$, where $p\geq 3$ and
$a_{i}\geq 1$, the following is satisfied

$(d-a_{1})\cdot...\cdot(d-a_{p})d^{K-p}\geq(d-1)d^{K-2}$

###### Proof.

The above inequality is equivalent to

$(d-a_{1})\cdot...\cdot(d-a_{p})\geq(d-1)d^{p-2}$

Let’s notice that for any positive $a,b\geq 1$, we have $(d-a)(d-b)\geq
d(d-(a+b))$, and applying it many times, we get

$\displaystyle(d-a_{1})\cdot...\cdot(d-a_{p})$ $\displaystyle\geq
d(d-(a_{1}+a_{2}))(d-a_{3})\cdot...\cdot(d-a_{p})\geq$ $\displaystyle...\geq
d^{p-2}(d-(a_{1}+\cdots+a_{p-1}))(d-a_{p})=d^{p-2}a_{p}(d-a_{p})\geq(d-1)d^{p-2}$

The last inequality came from $p=2$ case. ∎

##  Appendix F Proof of Proposition 3.12

The proof is based on Lemma E.1, let us now fix an arbitrary sign pattern
$\pi\in\\{\pm 1\\}_{k=1}^{K}$. For every $k\in[K]$, by assumption
$\\{F^{+}_{t^{(d)}_{k}}\\}\cup\\{\psi^{(i)}_{m_{i}}\\}_{m_{i}=1}^{M}$ form a
$T^{*}$-system, therefore, there exists a polynomial
$q^{\pi_{k}}_{t^{(d)}_{k}}$ such that

$\displaystyle
q^{\pi_{k}}_{t^{(d)}_{k}}\geq\begin{cases}F^{+}_{t^{(d)}_{k}}\;\text{when}\;\pi_{k}=1\\\
\epsilon^{d-1}F^{+}_{t^{(d)}_{k}}\;\text{when}\;\pi_{k}=-1\end{cases}$

for every $t^{(d)}_{k}\in\mathbb{I}$, with equality holding on
$T^{(d)}=\\{t^{(d)}_{k}\\}_{k=1}^{K}$. When the sign pattern $\pi$ contains at
least one negative sign, we define for future use the normalized maximum

$q^{\pi}_{\max}(\epsilon):=\epsilon^{-(d-1)}\max_{\pi_{k}=-1}\max_{t^{(d)}\in\mathbb{I}}q^{\pi_{k}}_{t^{(d)}_{k}}$

where the inner maximum above is indeed achieved in view of the continuity of
$q^{\pi_{k}}_{t^{(d)}_{k}}$ and the compactness of $\mathbb{I}$. Note that
$q^{\pi}_{\max}(\epsilon)\geq 1$ for every $\epsilon>0$. When $\epsilon=0$, we
choose the trivial polynomial $q^{\pi_{k}}_{t^{(d)}_{k}}=\epsilon=0$ for every
$k$ such that $\pi_{k}=-1$, and thus let’s take it as

$q^{\pi}_{\max}(0)=1.$

Likewise, for every $k\in[K]$,
$\\{F^{\pm}_{t^{(j)}_{k}}\\}\cup\\{\psi^{(j)}_{m_{j}}\\}_{m_{j}=1}^{M}$ form a
$T^{*}$-system on $\mathbb{I}$ by assumption. Therefore, for every $k\in[K]$
there exists a polynomial $q^{\pi_{k}}_{t^{(j)}_{k}}$ such that

$\displaystyle
q^{\pi_{k}}_{t^{(j)}_{k}}\geq\begin{cases}F^{\pi_{k}}_{t^{(j)}_{k}}\;&\text{when}\;\pi_{k}=1\\\
\frac{F^{\pi_{k}}_{t^{(j)}_{k}}}{\epsilon
q^{\pi}_{\max}(\epsilon)}\;&\text{when}\;\pi_{k}=-1\end{cases}$

for every $t^{(j)}_{k}$ with equality holding on
$\\{t^{(j)}_{k}\\}_{k=1}^{K}$. Now, we observe that

$\displaystyle q^{\pi_{k}}_{t^{(1)}_{k}}\cdot...\cdot
q^{\pi_{k}}_{t^{(d-1)}_{k}}\cdot
q^{\pi_{k}}_{t^{(d)}_{k}}\geq\begin{cases}\pi_{k}\;&\text{when}\;\theta\in\theta_{k,\epsilon}\\\
\frac{(-1)^{d-1}}{q^{\pi}_{\max}(\epsilon)}\;&\text{when}\;\theta=\theta_{k}\;\text{and}\;\pi_{k}=-1\\\
-1\;&\text{elsewhere in}\;\mathbb{I}^{d}\end{cases}$

with equality holding at least on $\Theta$. Let us now consider the polynomial

$\displaystyle
Q^{\pi}(\theta):=\sum_{k\in[K]}q^{\pi_{k}}_{t^{(1)}_{k}}(t^{(1)})\cdot...\cdot
q^{\pi_{k}}_{t^{(d-1)}_{k}}(t^{(d-1)})q_{t^{(d)}_{k}}(t^{(d)})$

We establish that for the appropriate choice of the sign pattern $\pi$,
$Q^{\pi}$ is indeed the desired dual certificate prescribed in Lemma 3.9.More
specifically, let $\pi^{*}$ denote the sign pattern specified by the error
measure $h$ in (3.9), then the dual certificate exists with

$\alpha(\epsilon)=1+\frac{(-1)^{d-1}}{q^{\pi^{*}}_{\max}(\epsilon)}$

This completes the proof.

##  Appendix G Proof of Theorem 3.7

Using the $L$-Lipschitz property of the imaging apparatus and using the
triangle inequality, we can write

$\displaystyle\Big{\|}y-\int_{\mathbb{I}^{d}}\Psi(\theta)\mu_{K,\epsilon}(\text{d}\theta)\Big{\|}_{F}$
$\displaystyle\leq\Big{\|}y-\int_{\mathbb{I}^{d}}\Psi(\theta)\mu(\text{d}\theta)\Big{\|}_{F}+\Big{\|}\int_{\mathbb{I}^{d}}\Psi(\theta)(\mu(\text{d}\theta)-\mu_{K,\epsilon}(\text{d}\theta))\Big{\|}_{F}$
$\displaystyle\leq\delta+L\cdot d_{GW}(\mu,\mu_{K,\epsilon})$
$\displaystyle=\delta+L\cdot R(\mu,K,\epsilon):=\delta^{\prime}$

We can think that $\hat{\mu}$ is a solution of rogram (1.5) with
$\delta^{\prime}$ as an estimation of $\mu_{K,\epsilon}$. And since we
constructed appropriate dual certificates in Propositions 3.11 and 3.12, we
can use the results to bound the the generalized Wasserstein metric error
between the true measure and the solution of program (1.5).

$\displaystyle d_{GW}(\mu,\hat{\mu})$ $\displaystyle\leq
d_{GW}(\mu,\mu_{K,\epsilon})+d_{GW}(\mu_{K,\epsilon},\hat{\mu})\;\;(\text{triangle
inequality})$ $\displaystyle\leq
R(\mu,K,\epsilon)+\Big{(}\frac{8\|b\|_{F}}{\bar{g}}+6\|b^{0}\|_{F}\Big{)}\delta^{\prime}+(\epsilon+3\alpha(\epsilon))\|\mu_{K,\epsilon}\|_{TV}\;\;\text{(Proposition
\ref{prop:0})}$
$\displaystyle=R(\mu,K,\epsilon)+\Big{(}\frac{8\|b\|_{F}}{\bar{g}}+6\|b^{0}\|_{F}\Big{)}(\delta+L\cdot
R(\mu,K,\epsilon))+(\epsilon+3\alpha(\epsilon))\|\mu_{K,\epsilon}\|_{TV}$
$\displaystyle=\Big{(}\frac{8\|b\|_{F}}{\bar{g}}+6\|b^{0}\|_{F}\Big{)}\delta+\Big{(}\frac{8L\|b\|_{F}}{\bar{g}}+6L\|b^{0}\|_{F}+1\Big{)}R(\mu,K,\epsilon)+(\epsilon+3\alpha(\epsilon))\|\mu_{K,\epsilon}\|_{TV}$
$\displaystyle=\Big{(}\frac{8}{d-1}d^{2-K}\|b\|_{F}+6\|b^{0}\|_{F}\Big{)}\delta+\Big{(}\frac{8L}{d-1}d^{2-K}\|b\|_{F}+6L\|b^{0}\|_{F}+1\Big{)}R(\mu,K,\epsilon)$
$\displaystyle\;\;\;\;+(\epsilon+3\alpha(\epsilon))\|\mu_{K,\epsilon}\|_{TV}$

Next, we relate $\|\mu_{K,\epsilon}\|_{TV}$ to $\|\mu\|_{TV}$. So,

$\displaystyle\|\mu_{K,\epsilon}\|_{TV}$
$\displaystyle=d_{GW}(\mu_{K\epsilon},0)$ $\displaystyle\leq
d_{GW}(\mu_{K,\epsilon},\mu)+d_{GW}(\mu,0)\;\;\text{triangle inequality}$
$\displaystyle=d_{GW}(\mu_{K,\epsilon},\mu)+\|\mu\|_{TV}$ $\displaystyle\leq
d_{GW}(\mu,0)+\|\mu\|_{TV}$ $\displaystyle=2\|\mu\|_{TV}$

So, combining the two above results, we get

$\displaystyle c_{1}$
$\displaystyle=\frac{8}{d-1}d^{2-K}\|b\|_{F}+6\|b^{0}\|_{F}$ $\displaystyle
c_{2}(\epsilon)$ $\displaystyle=(2\epsilon+6\alpha(\epsilon))\|\mu\|_{TV}$
$\displaystyle c_{3}$
$\displaystyle=\frac{8L}{d-1}d^{2-K}\|b\|_{F}+6L\|b^{0}\|_{F}+1$