2.1. The forward map and the model class

In the following, we introduce the main assumptions and setup. Let $\mathscr{X}$ , $\mathscr{Y}$ and $\mathscr{Z}$ be non-empty sets. Furthermore, consider subsets $\mathscr{M}_1 \subset \mathscr{X}$ and $\mathscr{E}\subset \mathscr{Z}$ , referred to as the model class and the noise class, respectively. As outlined in the introduction, we consider inverse problems with a given forward map $F \colon \mathscr{M}_1\times \mathscr{E} \to \mathscr{M}_2^{\kern0.5pt\mathscr{E}} \subset \mathscr{Y}$ , with

\begin{equation*} \mathscr{M}_2^{\kern0.5pt\mathscr{E}} = F(\mathscr{M}_1\times \mathscr{E}\kern1.6pt) = \{y \in \mathscr{Y}\,:\, \exists (x,e) \in \mathscr{M}_1\times \mathscr{E}\text{ s.t.} \ y=F(x,e) \} \end{equation*}

denote the image of $F\colon \mathscr{X}\times \mathscr{Z}\to \mathscr{Y}$ on the class $\mathscr{M}_1\times \mathscr{E}$ . We consider inverse problems as:

(5) \begin{align} \text{Given noisy measurements } y = F(x,e) \text{ of } x \in \mathscr{M}_1\quad \text{ and }\quad e \in \mathscr{E}, \text{ recover } x, \end{align}

where $e$ represents noise and $x$ is the signal of interest. The goal of solving the inverse problem is to produce an approximation $\hat {x}$ of the true solution $x$ . In order to quantify the error of the approximation $\hat {x} \in \mathscr{X}$ to the sample signal $x\in \mathscr{M}_1$ , it is common to assume [Reference Cohen, Dahmen and DeVore41, Reference Foucart and Rauhut56, Reference Pinkus89] that $\mathscr{X}$ is a normed space, or even a Banach or Hilbert space. In the current work, we extend the scope to the more general setting of metric spaces. The use of metrics – rather than norms – allows for a more general theory, in which normed vector spaces are a special case. Thus, we equip the sets $\mathscr{X}$ , $\mathscr{Y}$ and $\mathscr{Z}$ with metrics $d_{\mathscr{X}}$ , $d_{\mathscr{Y}}$ and $d_{\mathscr{Z}}$ , respectively, and on each set, we consider the topology induced by the respective metric. To avoid certain pathological cases for metric spaces, we make assumptions on the choice of metrics involved. Our first assumption is the following.

Here, the first assumption ensures that the topologies induced by the metrics are separable, which is a convenient assumption for both theoretical and practical purposes. In particular, this assumption excludes metrics such as the discrete metric over an uncountable set, as one cannot find a countable base for an uncountable set using this metric.

For the second assumption, we recall that in metric spaces, a compact subset is automatically closed and bounded; however, the converse does not necessarily hold, unless the metrics satisfy the Heine-Borel property. Note that this 2 is not implied by 1, as for example the bounded metric $d_{\mathscr{X}}(x,y) = \min \{\|x-y\|_{\ell ^2}, 1\}$ on $\mathscr{X} = {\mathbb{C}}^N$ satisfies assumption1 (since $d_{\mathscr{X}}$ induces the same topology as the Euclidean topology, which is second countable), but not assumption2 (since ${\mathbb{C}}^N$ is closed and bounded but not compact with respect to $d_{\mathscr{X}}$ ). Finally, note that together with second countability, the Heine-Borel property implies in particular that $\mathscr{X}$ is a complete separable metric space, usually referred to as a Polish space.

2.2. Set-valued reconstruction maps

Now that the preliminaries have been clarified, we return to the problem of solving the inverse problem in (5). A reconstruction mapping for (5) is a mapping that takes a measurement $y=F(x,e)$ and returns one or more approximations $\hat {x}$ to the unknown signal $x$ . That is, a reconstruction mapping is a set-valued function $\varphi \colon \mathscr{M}_2^{\kern0.5pt\mathscr{E}} \rightrightarrows \mathscr{X}$ , where $\varphi$ takes values in the power set $2^{\mathscr{X}}$ of the set $\mathscr{X}$ . Note that it is necessary to consider set-valued maps, as model-based methods often write the reconstruction mapping as an optimisation problem. These problems might not have unique solutions; see, e.g., [Reference Colbrook, Antun and Hansen45, SI, Section 3.B] for a few standard examples. Finally, we mention that given a set-valued mapping $\varphi \colon \mathscr{M}_2^{\kern0.5pt\mathscr{E}} \rightrightarrows \mathscr{X}$ , we call a function $f \colon \mathscr{M}_2^{\kern0.5pt\mathscr{E}} \to \mathscr{X}$ a selector for $\varphi$ if it satisfies $f(y) \in \varphi (y)$ for each $y \in \mathscr{M}_2^{\kern0.5pt\mathscr{E}}$ .

Distances between sets in $\mathscr{X}$ will be measured via the Hausdorff distance. Given subsets $A,B \subseteq \mathscr{X}$ , their Hausdorff distance is

\begin{equation*} d_{\kern-1pt \mathscr{X}}^H(A,B)\,:\!=\, \max \Big \{\sup_{a \in A} \inf_{b\in B} d_{\mathscr{X}}(a,b), \sup _{b \in B} \inf _{a\in A} d_{\mathscr{X}}(a,b)\Big \}. \end{equation*}

The Hausdorff distance satisfies all the properties of a metric only when restricted to the subsets of $\mathscr{X}$ that are bounded (which ensures $d_{\kern-1pt \mathscr{X}}^H$ is finite) and closed (which ensures that $d_{\kern-1pt \mathscr{X}}^H(A,B)=0$ only if $A=B$ ). With a slight abuse of notation, we will denote $d_{\kern-1pt \mathscr{X}}^H(\{a\},B)$ by $d_{\kern-1pt \mathscr{X}}^H(a,B)$ . The Hausdorff distance between a point and a set should not be confused with the usual distance between a point and a set, $\operatorname {dist}_{\mathscr{X}}(a,B)\,:\!=\, \inf _{b\in B} d_{\mathscr{X}}(a,b)$ . Indeed, note that $\operatorname {dist}_{\mathscr{X}}(a,B)=\inf _{b\in B} d_{\mathscr{X}}(a,b)\leq \sup _{b\in B} d_{\mathscr{X}}(a,b)=d_{\kern-1pt \mathscr{X}}^H(a,B)$ .

We require an extra assumption that relates the forward map $F$ and the model class $\mathscr{M}_1$ . In particular, we require that for every $y$ , the set of possible true solutions $x$ ’s is bounded. Throughout the text, we denote by $\pi _1\colon \mathscr{X} \times \mathscr{Z} \to \mathscr{X}, (x,e) \mapsto x$ the projection on the first component.

Assumption 2. We assume that for every $y \in \mathscr{M}_2^{\kern0.5pt\mathscr{E}}$ the feasible set

(6) \begin{align} F_y\,:\!=\,\pi _1(F^{-1}(y)) = \{x \in \mathscr{M}_1\,:\, \exists e\in \mathscr{E} \text{ s.t. } F(x,e)=y\} \end{align}

is bounded.

The feasible set $F_y$ consists of all the candidate solutions $x$ ’s that are consistent with the measurement $y$ , for some realisation of the noise $e$ . Note that the definition of $\mathscr{M}_2^{\kern0.5pt\mathscr{E}}$ implies that the feasible set is non-empty. Additionally, in Remark 3.2, we outline assumptions on the forward map such that the feasible set contains more than one element.

The previous condition is satisfied, for example, if the model class $\mathscr{M}_1$ is compact, as assumed in e.g., [Reference Binev, Bonito, DeVore and Petrova25].

Finally, we clarify our notation for objects in a metric space $(X,d)$ . We denote by $B_d(x,r)$ the closed ball of centre $x\in X$ and radius $r\geq 0$ . If $A\subseteq X$ , then the closed ball around $A$ of radius $r\geq 0$ is

\begin{align*} B_d(A,r) = \{x \in X\,:\, \operatorname {dist}_d(x,A) \leq r\} = \bigcup _{x \in A} B_d(x,r) \end{align*}

where we recall that $\operatorname {dist}_d(x,A) = \inf _{a \in A} d(x,a)$ .

Finally, the diameter of $A\subseteq X$ is denoted by $\operatorname {diam}_d(A)\,:\!=\,\sup \{d(a,a')\,:\,a,a'\in A\}$ . The subscript $d$ is omitted whenever the metric is unambiguous from context.

3.1. Worst-case optimality bounds and an optimal map with worst-case noise

What is the best possible reconstruction error one can achieve for a given model class $\mathscr{M}_1$ ? This is an old question [Reference Micchelli and Rivlin83] that has been asked many times and in different settings [Reference Binev, Bonito, DeVore and Petrova25, Reference Bourrier, Davies, Peleg, Pérez and Gribonval31, Reference Cohen, Dahmen and DeVore41, Reference Ettehad and Foucart50, Reference Foucart, Liao, Shahrampour and Wang58, Reference Keriven and Gribonval73, Reference Traonmilin and Gribonval104, Reference Traonmilin, Gribonval and Vaiter105]. In the definition below, we investigate this question for measurements contaminated by worst-case noise. This definition has appeared in [Reference Ettehad and Foucart50, Reference Foucart, Liao, Shahrampour and Wang58] for the linear model with additive noise in a normed vector space and is here generalised to metric spaces.

Definition 1 (Optimality constant with worst-case noise). The optimality constant with worst-case noise of the inverse problem (1) is

\begin{align*} c_{\mathrm{opt}}^{\text{w}}(F,\mathscr{M}_1, \mathscr{E}\kern1.6pt) & = \inf _{\varphi \colon \mathscr{M}_2^{\kern0.5pt\mathscr{E}} \rightrightarrows \mathscr{X}} \sup _{x\in \mathscr{M}_1} \sup _{e \in \mathscr{E}} \ d_{\kern-1pt \mathscr{X}}^H(x, \varphi (F(x,e))). \end{align*}

A mapping $\varphi \colon \mathscr{M}_2^{\kern0.5pt\mathscr{E}} \rightrightarrows \mathscr{X}$ that attains such an infimum is called an optimal map with worst-case noise.

Given the optimality constant with worst-case noise of an inverse problem (1), the question arises on how to upper and lower bound such an optimality constant. As shown in Theorem3.1, the upper and lower bounds can be obtained by referring to a constant intrinsic to the problem, its kernel size with worst-case noise, as defined below.

Definition 2 (Kernel size with worst-case noise). The kernel size with worst-case noise of the problem (1) is

(7) \begin{align} \operatorname {kersize}^{\text{w}}(F,\mathscr{M}_1, \mathscr{E}\kern1.6pt) &= \sup _{\substack { (x,e),(x',e')\in \mathscr{M}_1\times \mathscr{E} \text{ s.t. }\\ F(x,e) = F(x',e')} } d_{\mathscr{X}}(x,x'). \end{align}

The kernel size with worst-case noise gives the maximum distance between any two points $x,x'\in \mathscr{M}_1$ with identical measurement $y = F(x,e) = F(x',e')$ for some noise vectors $e,e'\in \mathscr{E}$ . It is worth observing that the optimality constant and the kernel size with worst-case noise also can be expressed as follows.

(8) \begin{align} c_{\mathrm{opt}}^{\text{w}}(F,\mathscr{M}_1, \mathscr{E}\kern1.6pt) & = \inf _{\varphi \colon \mathscr{M}_2^{\kern0.5pt\mathscr{E}} \rightrightarrows \mathscr{X}} \sup _{y\in \mathscr{M}_2^{\kern0.5pt\mathscr{E}}} \sup _{x \in F_y} \ d_{\kern-1pt \mathscr{X}}^H(x, \varphi (y)) \nonumber \\ \text{kersize}^{\text{w}}(F,\mathscr{M}_1, \mathscr{E}\kern1.6pt) & =\sup _{y \in \mathscr{M}_{2}^{\mathscr{E}}} \mathrm{diam}_{d_{\mathscr{X}}}(F_y). \end{align}

This establishes a connection of the optimality constant and the kernel size with the worst-case to the feasible sets $F_y$ . In our first theorem, we provide an upper and lower bound on the optimality constant in terms of the kernel size with worst-case noise. Moreover, we provide a variational expression for an optimal map with worst-case noise.

The previous theorem illustrates a fundamental limit for the inverse problem (5). Indeed, for (5), one would hope to find a solution whose error is as close to zero as possible. However, the lower bound in (9) shows that there is a fundamental constant intrinsic to the problem – the kernel size with worst-case noise – such that no worst-case reconstruction error can be made smaller than this constant for all possible choices of $x \in \mathscr{M}_1$ . Moreover, note that in the definition of the worst-case optimality constant, all potentially set-valued maps are included – in particular, no single-valued selector can obtain a smaller worst-case reconstruction error. Additionally, we can apply the axiom of choice to select a single-valued map $\bar {\Psi }$ from the set-valued optimal map in (10). By the definition of the Hausdorff distance, we have that this single-valued selection satisfies $d_{\mathscr{X}}(x,\bar {\Psi }(F(x,e))) \leq \sup _{z \in \Psi (F(x,e))}d_{\mathscr{X}}(x,z)=d_{\kern-1pt \mathscr{X}}^H(x,\Psi (F(x,e)))$ for all $x \in \mathscr{M}_1$ and $e \in \mathscr{E}$ . Hence, by the minimisation property of the optimal map in (10), the bounds also hold for any single-valued selector.

3.2. Average optimality bounds and optimal map with average error

The previous theorem provides fundamental limits when performance is assessed by considering worst-case reconstruction error for a given inverse problem of the form (5). Such bounds naturally lead to very pessimistic estimates of performance. This motivates the need for a model that considers the average error of a reconstruction mapping, given a probabilistic model of the data. Below, we will adapt the worst-case setup considered in the previous section to a probabilistic model. Note that in the machine learning literature, this notion of average error is often referred to as the risk of a given reconstruction mapping [Reference Shalev-Shwartz and Ben-David96, Chapter 3] [Reference Foucart57, Chapter 1].

We start by introducing the notation. For a topological space $(X,\tau )$ , the Borel $\sigma$ -algebra of $X$ , denoted by $\mathscr{B}(X)$ , is the $\sigma$ -algebra generated by the family $\tau$ of open sets. Elements of $\mathscr{B}(X)$ are called Borel sets. If $X$ is a metric space, then $\mathscr{B}(X)$ is the smallest family of sets containing all the open sets that are closed under countable intersections and countable disjoint unions. See, e.g., [Reference Aliprantis and Border6, Cor. 4.16] for further reference. A Borel measure on $X$ is a measure defined on the Borel $\sigma$ -algebra $\mathscr{B}(X)$ . Borel measurable functions are defined analogously.

Next, we need to define conditional probabilities on $\mathscr{M}_1\times \mathscr{E}$ for the considered measure $\mu$ for different values of $y \in \mathscr{M}_2^{\kern0.5pt\mathscr{E}}$ . To compute such conditional probabilities, we consider a disintegration of the measure $\mu$ . Intuitively, a disintegration of the measure $\mu$ given the mapping $F$ , is a family of probability measures $\{\mu ^y\}_{y\in \mathscr{M}_2^{\kern0.5pt\mathscr{E}}}$ such that for each $y\in \mathscr{M}_2^{\kern0.5pt\mathscr{E}}$ , $\mu ^y$ is concentrated on the set $F^{-1}(y)$ , and which allows us to reconstruct the original measure $\mu$ by integration. Note that these sets $\{F^{-1}(y)\}_{y\in \mathscr{M}_2^{\kern0.5pt\mathscr{E}}}$ might have measure zero with respect to $\mu$ . The concept of disintegration is introduced in the following definition, which is taken from [Reference Chang and Pollard40] and adapted to our Assumption3. See also [Reference Bogachev27, Chapter 10] or [Reference Kallenberg72, Chapter 1] for more on disintegration. Moreover, note that in [Reference Plaskota90] a similar tool – that of a regular conditional probability density – is used in order to prove analogous bounds when restricted to normed spaces and single-valued decoders.

Remark. Example of a disintegration along a projection. Let $\mu$ be Lebesgue measure on $\mathbb{R}^2$ and let $\pi _1(x,y)=x$ be the projection onto the first coordinate. Then, $\mu$ admits a disintegration with respect to $\pi _1$ given by the family of measures $\{\mu ^x\}_{x \in \mathbb{R}}$ , where $\mu ^x$ is Lebesgue measure on the fibre $\{x\} \times \mathbb{R}$ . In this case, the disintegration formula

\begin{equation*} \int _{\mathbb{R}^2} f(x,y)\, d\mu (x,y) = \int _{\mathbb{R}} \left ( \int _{\mathbb{R}} f(x,y)\, d\mu ^x(y) \right ) d\pi _{1*}\mu (x,y) \end{equation*}

for a non-negative, measurable and integrable function $f$ is the Fubini-Tonelli’s theorem (see [Reference Folland55 , Theorem 2.37]).

Note that while we assume that $\mu$ is a finite measure (and not necessarily a probability measure), the definition above requires that $\mu ^{y}$ ’s are probability measures. In Section 7.1, we show that a disintegration of $\mu$ always exists and that it is essentially unique in our setting given Assumption4, stated below.

Note that Assumption4 implies Assumption2, which will therefore be omitted from now on. Additionally, since $\mathscr{M}_1 \times \mathscr{E}$ is a Borel subset of $\mathscr{X} \times \mathscr{Z}$ , the Borel $\sigma$ -algebra $\mathscr{B}(\mathscr{M}_1\times \mathscr{E}\kern1.6pt)$ , that is induced by the subspace topology on $\mathscr{M}_1 \times \mathscr{E}$ , coincides with the trace $\sigma$ -algebra $\mathscr{B}(\mathscr{X}\times \mathscr{Z}\kern1.7pt)_{|\mathscr{M}_1\times \mathscr{E}} =\{ B \cap (\mathscr{M}_1 \times \mathscr{E}\kern1.6pt) \,:\, B \in \mathscr{B}(\mathscr{X} \times \mathscr{Z}\kern1.7pt) \},$ see e.g., [Reference Bogachev27, Section 1.1].

Next, let

\begin{equation*} r_\varphi \,:\, \mathscr{M}_1 \times \mathscr{E} \to [0,+\infty ], \quad r_\varphi (x,e) = d_{\kern-1pt \mathscr{X}}^H(x,\varphi (F(x,e))) \end{equation*}

denote the residual map of a given reconstruction mapping $\varphi \colon \mathscr{M}_2^{\kern0.5pt\mathscr{E}} \rightrightarrows \mathscr{X}$ and let

(11) \begin{equation} \mathscr{C}\,:\!=\, \{\varphi \colon \mathscr{M}_2^{\kern0.5pt\mathscr{E}} \rightrightarrows \mathscr{X}\,:\, r_\varphi \text{ is Borel measurable}\}. \end{equation}

denote the set of all reconstruction mappings with a Borel measurable residual map. For $p \in [1,\infty ]$ and a given reconstruction map $\varphi \colon \mathscr{M}_2^{\kern0.5pt\mathscr{E}} \rightrightarrows \mathscr{X}$ , we denote its $p$ th order error by

(12) \begin{equation} \mathrm{Err}^{\mathrm{a}}(\varphi ,p) = \begin{cases} \big(\!\int _{\mathscr{M}_1\times \mathscr{E}} d_{\kern-1pt \mathscr{X}}^H\big (x,\varphi (F(x,e))\big )^p \ d\mu (x,e) \big)^{\frac {1}{p}} &\text{for } 1\leq p \lt \infty \\ \operatorname {esssup}_{(x,e) \in \mathscr{M}_1\times \mathscr{E}} \ d_{\kern-1pt \mathscr{X}}^H(x, \varphi (F(x,e))) &\text{for } p=\infty \end{cases} \end{equation}

where the essential supremum for $p=\infty$ is taken with respect to the measure $\mu$ . Concretely, for $p\in [1,\infty ]$ , this quantity is the $L^p(\mathscr{M}_1\times \mathscr{E}, \mu )$ norm of the residual function $r_\varphi$ .

This definition of reconstruction error generalises the usual $L^p$ -norms to include a set-valued mapping and a metric $d_{\mathscr{X}}$ that is not necessarily induced by a norm in the single-valued case. However, the proposed setup includes many standard expectations as special cases. Indeed, let $\varphi$ be a single-valued map and let $d_{\mathscr{X}}$ be given by an $\ell ^q$ norm. Then, if we choose $p=q= 1$ , we recover the expected absolute error, whereas for $p=q=2$ , we find the expected root squared error. Moreover, for $p=\infty$ , the choice of metric $d_{\mathscr{X}}$ corresponds to the choice of the loss function in a machine learning setting [Reference Shalev-Shwartz and Ben-David96, Chapter 3] [Reference Foucart57, Chapter 1]. One can also view the case where $p=\infty$ as a weak form of worst-case error where all irregularities on sets of measure zero are ignored.

With the error term in (12) defined, we can now establish the notion of optimality constant with average error and kernel constant with average error.

Definition 4 (Optimality constant with average error). For $p \in [1,\infty ]$ , the optimality constant with average error of order $p$ for the inverse problem (5) is

(13) \begin{align} c_{\mathrm{opt}}^{\text{a}}(F,\mathscr{M}_1,\mathscr{E}, p) = \inf _{\varphi \in \mathscr{C}} \mathrm{Err}^{\mathrm{a}}(\varphi , p). \end{align}

A map $\varphi \in \mathscr{C}$ attaining the infimum in (13) for a given $p$ is called an optimal map with average error of order $p$ .

Definition 5 (Average kernel size). The average kernel size of the inverse problem (1) for $p \in [1,\infty )$ is given by

\begin{align*} {\operatorname {kersize}}^{\text{a}}(F,\mathscr{M}_1, \mathscr{E}, p) &= \Bigg ( \int _{\mathscr{M}_2^{\kern0.5pt\mathscr{E}}} \int _{F^{-1}(y)} \int _{F^{-1}(y)} d_{\mathscr{X}}(x,x')^p \, d\mu ^y(x,e) \ d\mu ^y(x',e') \ d(F_*\mu )(y) \Bigg )^{\frac {1}{p}}, \end{align*}

and for $p = \infty$ it is

(14) \begin{align} {\operatorname {kersize}}^{\text{a}}(F,\mathscr{M}_1, \mathscr{E}, \infty ) &= \mathop{\mathrm{esssup}}\limits_{y \in \mathscr{M}_2^{\kern0.5pt\mathscr{E}}} \mathop{\mathrm{esssup}}\limits_{\substack {(x,e) \in F^{-1}(y)\\ (x',e') \in F^{-1}(y)}} d_{\mathscr{X}}(x,x'), \end{align}

where the left and right essential suprema are taken with respect to $F_*\mu$ on $\mathscr{M}_2^{\kern0.5pt\mathscr{E}}$ and $\mu ^y$ on $F^{-1}(y)$ , respectively.

Intuitively, the average kernel size measures the average distance between the $x$ -components of $(x,e), (x',e') \in \mathscr{M}_1\times \mathscr{E}$ that have the same measurement $F(x,e) = F(x',e')=y$ in the case of $p \in [1,\infty )$ , and the maximum of such distances (up to negligible sets) when $p = \infty$ .

Our main theorem in this section is stated below. It bounds the average optimality constant in terms of the average kernel size. It also ensures the existence of an optimal map, provides a variational expression for one such map and establishes some regularity properties of this mapping.

A key finding in Theorem3.2 is that the possibly set-valued $\Psi$ admits a measurable selector, i.e., a single-valued function $\psi \,:\,\mathscr{M}_2^{\kern0.5pt\mathscr{E}} \to \mathscr{X}$ which is Borel measurable and such that $\psi (y) \in \Psi (y)$ for every $y$ . Thus, Theorem3.2 not only provides fundamental limits for the reconstruction error of an inverse problem but also gives a (variational) expression for a mapping that is optimal. Moreover, such a reconstruction mapping satisfies some regularity properties, which one usually hopes for when solving an inverse problem. One can argue that measurability is still a weak condition, but in order to obtain stronger conditions (such as continuity of the reconstruction), one would need to impose stronger assumptions on the problem. Moreover, note that in the definition of the average optimality constant, all potentially set-valued maps are included. Hence, the bounds also hold for any measurable single-valued selector.

7.1. Existence and uniqueness of a disintegration of a measure given Assumptions1, 3 and 4

In this section, we prove the following proposition, which ensures that our setting guarantees the existence of a disintegration of the measure $\mu$ .

The proof of Proposition 7.1 is a special case of what is found in [Reference Chang and Pollard40]. Before jumping to the proof, in this section, we start by recalling some well-known definitions for measures and stating the relevant theorems from [Reference Chang and Pollard40]. Let $(X,\mathscr{B}(X))$ be the Borel measurable space associated with the topological space $X$ . A measure $\mu$ on $(X,\mathscr{B}(X))$ is said to be a Radon measure (sometimes also called a regular measure [Reference Aliprantis and Border6]) if

1. (1) $\mu (K)\lt +\infty$ for each compact $K \in \mathscr{B}(X)$ ,

2. (2) $\mu (B) = \inf \{\mu (V)\,:\, V \in \mathscr{B}(X), V \text{ open, and } B\subset V \}$ , for every $B \in \mathscr{B}(X)$ ( $\mu$ is outer regular), and

3. (3) $\mu (B) = \sup \{\mu (K)\,:\, K \in \mathscr{B}(X), K \text{ compact, and } K\subset B \}$ , for every $B \in \mathscr{B}(X)$ ( $\mu$ is tight).

Moreover, a measure $\mu$ is said to dominate a measure $\nu$ if $\mu (B) = 0$ implies $\nu (B)=0$ for every $B\in \mathscr{B}(X)$ . Suppose that $X$ can be covered by at most countably many Borel measurable sets $\{B_{i}\}_{i\in I}$ , $I\subset \mathbb{N}$ , and that $\mu (B_i) \lt \infty$ for each $i\in I$ . Then, $\mu$ is said to be a $\sigma$ -finite measure. In particular, every finite measure is $\sigma$ -finite. We also have the following results for finite measures that are used in the proof of Proposition 7.1.

In Definition3, one may replace the measure $F_*\mu$ with another measure $\rho$ , in which case $\{\mu ^y\}_y$ would be called a $(F,\rho )$ disintegration of $\mu$ . We refer the reader to [Reference Chang and Pollard40, Definition 1] for the detailed statement.

7.2. Proof of Theorem3.1

Proof of Theorem 3.1. We begin with the proof of (ii). First, let us introduce some notation: for fixed $y \in \mathscr{M}_2^{\kern0.5pt\mathscr{E}}$ , define the function

\begin{align*} f_y\colon \mathscr{X} \to [0,+\infty ), \quad f_y(z) = \sup _{x \in F_y} d_{\mathscr{X}}(x, z) = d_{\kern-1pt \mathscr{X}}^H(z, F_y) \end{align*}

and notice that $f_y$ appears in the definition of $\Psi$ in (10). Note that $f_y$ does not attain the value $+\infty$ , as by Assumption2 the feasible set $F_y$ is bounded. That is, we have the relation,

(19) \begin{equation} \Psi (y)= \mathop{\mathrm{argmin}}\limits_{z \in \mathscr{X}} f_y(z). \end{equation}

Furthermore, for each $y \in \mathscr{M}_2^{\kern0.5pt\mathscr{E}}$ let

\begin{equation*} r_y = \sup _{\substack {x \in F_y\\x' \in F_y}} d_{\mathscr{X}}(x, x') = {\operatorname {diam}}_{d_{\mathscr{X}}}(F_y). \end{equation*}

Next, we make a claim which, once it is established, we use to prove that $\Psi$ has non-empty, compact values. This ensures that $\Psi$ is well-defined.

We proceed to prove the claim and start by considering (I). We consider a general setting, and let $(X,d)$ be a metric space, $A \subseteq X$ be a bounded subset and $g(x)\,:\!=\, d^H(x,A) = \sup _{a \in A} d(x,a)$ . We claim that $|g(x)-g(y)|\leq d(x,y)$ for all $x,y \in X$ . To see this, consider $a, x, y \in X$ and note that

\begin{align*} d(x,a) \leq d(x,y) + d(y,a) \quad \implies \quad \sup _{a \in A}d(x,a) \leq d(x,y) + \sup _{a \in A} d(y,a). \end{align*}

Switching the roles of $x$ and $y$ , leads to the desired inequality. It follows that $g$ is continuous. Moreover, $ F_y$ is bounded by Assumption2. Thus, letting $(X,d)=(\mathscr{X}, d_{\mathscr{X}})$ , $A = F_y$ , $g=f_y$ above, proves (I).

To prove (II), we show that no point outside of the closed ball ${B}_{d_{\mathscr{X}}}(x,r_y)$ can be a minimiser of $f_y$ . First, note that $r_y = {\operatorname {diam}}_{d_{\mathscr{X}}}(\pi _1 (F_y))\lt \infty$ as $\pi _1 (F_y)$ is bounded. Moreover, by definition, we have that

\begin{align*} r_y = \sup _{x \in F_y} \sup _{x' \in F_y} d_{\mathscr{X}}(x, x') = \sup _{x \in F_y} f_y(x), \end{align*}

which implies that $r_y \geq f_y(x)$ for all $x \in F_y$ . Now, pick an $\hat {x} \in F_y$ . If $z\in \mathscr{X} \setminus {B}(\hat {x},r_y)$ is a point outside of the ball, then $d_{\mathscr{X}}(z,\hat {x}) \gt r_y$ , and

\begin{equation*} f_y(z) = \sup _{x' \in F_y} d_{\mathscr{X}}(x',z) \geq d_{\mathscr{X}}(\hat {x},z) \gt r_y \geq f_y(\hat {x}). \end{equation*}

It follows that any minimiser of $f_y$ must lie in the ball ${B}(\hat {x},r_y)$ . This proves our claim in (II).

Part (III) of the claim follows directly from the continuity of $f_y$ . Indeed, let $\alpha _y \,:\!=\, \min f_y \in [0, +\infty )$ . Then, since $\{\alpha _y\}\subset [0,\infty )$ is closed and $f_y$ is continuous, the preimage $f_y^{-1}(\{\alpha _y\}) = \Psi (y)$ is closed. This proves (III) and concludes our proof of the claim.

Next, we prove the following properties of $\Psi$ . These properties finalise the proof of statement (ii) of the theorem.

1. (1) $\Psi$ has non-empty and compact values;

2. (2) $\Psi$ is an optimal map;

We start with the proof of (a). Let $y \in \mathscr{M}_2^{\kern0.5pt\mathscr{E}}$ and consider $x \in F_y$ . From (II) and (19), we see that

(20) \begin{equation} \Psi (y) = \mathop{\mathrm{argmin}}\limits_{z \in \mathscr{X}}\,f_y(z) = \mathop{\mathrm{argmin}}\limits_{z \in {B}(x,r_y)}\, f_y(z). \end{equation}

By Assumption 12, $d_{\mathscr{X}}$ satisfies the Heine-Borel property, which implies that the closed and bounded ball $\mathscr{B}(x,r_y)$ is compact. Moreover, from (I), we know that the objective function $f_y$ is continuous. Thus, it follows from the Extreme Value Theorem that $f_y$ attains its minimum in (20). This implies that $\Psi$ has non-empty values. To see that $\Psi$ has compact values, observe that $\Psi (y)$ is closed by (III) and that $\Psi (y) \subseteq {B}(x,r_y)$ , where ${B}(x,r_y)$ is compact. Since a closed subset of a compact set is compact, we conclude that $\Psi (y)$ is compact.

Next, we prove (b). We will show that the minimum worst-case reconstruction error of $\Psi$ equals the optimality constant as given in Definition1. To this end, let $\varphi \colon \mathscr{M}_2^{\kern0.5pt\mathscr{E}} \rightrightarrows \mathscr{X}$ and fix $y \in \mathscr{M}_2^{\kern0.5pt\mathscr{E}}$ . Recall from above that $\Psi$ is non-empty. By construction, we have that

\begin{equation*} \sup _{x \in F_y} d_{\kern-1pt \mathscr{X}}^H(\Psi (y),x) \leq \sup _{x \in F_y} d_{\mathscr{X}}(x,z),\quad \text{for all $z \in \varphi (y)$.} \end{equation*}

It follows that

\begin{align*} \sup _{x \in F_y} d_{\kern-1pt \mathscr{X}}^H(\Psi (y),x) \leq \sup _{x \in F_y} \sup _{z \in \varphi (y)} d_{\mathscr{X}}(x,z) = \sup _{x \in F_y} d_{\kern-1pt \mathscr{X}}^H(x,\varphi (y)). \end{align*}

By taking the supremum with respect to $y\in \mathscr{M}_2^{\kern0.5pt\mathscr{E}}$ on both sides, we obtain

\begin{align*} \sup _{y \in \mathscr{M}_2^{\kern0.5pt\mathscr{E}}} \sup _{x \in F_y}d_{\mathscr{X}}^{H} (\Psi (y), x) \leq \sup _{y \in \mathscr{M}_2^{\kern0.5pt\mathscr{E}}} \sup _{x \in F_y} d_{\mathscr{X}}^{H}(\varphi (y), x). \end{align*}

As $F\colon \mathscr{M}_1\times \mathscr{E} \to \mathscr{M}_2^{\kern0.5pt\mathscr{E}}$ is surjective, the previous inequality can be rewritten as

\begin{align*} \sup _{(x,e)\in \mathscr{M}_1 \times \mathscr{E}} d_{\mathscr{X}}^{H} (\Psi (F(x,e)), x) \leq \sup _{(x,e)\in \mathscr{M}_1 \times \mathscr{E}} d_{\mathscr{X}}^{H} (\varphi (F(x,e)), x). \end{align*}

Now, since $\varphi \colon \mathscr{M}_2^{\kern0.5pt\mathscr{E}} \rightrightarrows \mathscr{X}$ was arbitrary, the above inequality holds for any $\varphi \colon \mathscr{M}_2^{\kern0.5pt\mathscr{E}} \rightrightarrows \mathscr{X}$ . Taking the infimum over all mappings on the right-hand side, we obtain the optimality constant:

\begin{align*} \sup _{(x,e)\in \mathscr{M}_1 \times \mathscr{E}} d_{\mathscr{X}}^{H} (\Psi (F(x,e)), x) \leq c_{\mathrm{opt}}^{\text{w}}(F,\mathscr{M}_1, \mathscr{E}\kern1.6pt). \end{align*}

The opposite inequality is trivial, since $\Psi \colon \mathscr{M}_2^{\kern0.5pt\mathscr{E}} \rightrightarrows \mathscr{X}$ is one of the reconstruction mappings over which the infimum is taken. Therefore,

\begin{align*} \sup _{(x,e)\in \mathscr{M}_1 \times \mathscr{E}} d_{\mathscr{X}}^{H} (\Psi (F(x,e)), x) = c_{\mathrm{opt}}^{\text{w}}(F,\mathscr{M}_1, \mathscr{E}\kern1.6pt), \end{align*}

and we conclude that $\Psi$ is an optimal map. This concludes the proof of statement (ii) in the theorem.

We proceed with the proof of (i) and start with the lower bound in (9). Let $\varphi \,:\,\mathscr{M}_2^{\kern0.5pt\mathscr{E}} \rightrightarrows \mathscr{X}$ and $y \in \mathscr{M}_2^{\kern0.5pt\mathscr{E}}$ . Then

\begin{align*} {\operatorname {diam}}_{d_{\mathscr{X}}}(F_y) = \sup _{x,x' \in F_y} d_{\mathscr{X}}(x,x') &\leq \sup _{x \in F_y} 2d_{\kern-1pt \mathscr{X}}^H(x, \varphi (y)). \end{align*}

Now, taking the supremum over all $y \in \mathscr{M}_2^{\kern0.5pt\mathscr{E}}$ gives the inequality

(21) \begin{align} \operatorname {kersize}^{\text{w}}(F,\mathscr{M}_1, \mathscr{E}\kern1.6pt)\leq \sup _{y \in \mathscr{M}_2^{\kern0.5pt\mathscr{E}}} \sup _{x \in F_y} 2d_{\kern-1pt \mathscr{X}}^H(x, \varphi (y)). \end{align}

Finally, since $\varphi$ was arbitrary, taking the infimum over all $\varphi \,:\,\mathscr{M}_2^{\kern0.5pt\mathscr{E}} \rightrightarrows \mathscr{X}$ in (21) gives

\begin{equation*} \operatorname {kersize}^{\text{w}}(F,\mathscr{M}_1, \mathscr{E}\kern1.6pt) \leq 2c_{\mathrm{opt}}^{\text{w}}(F,\mathscr{M}_1, \mathscr{E}\kern1.6pt). \end{equation*}

which proves the lower bound in (9).

For proving the upper bound in (9), we will make use of the mapping $\Psi$ in (10), which we know from statement (ii) is an optimal map. Let $y \in \mathscr{M}_2^{\kern0.5pt\mathscr{E}}$ and $x' \in F_y$ . Then by construction of $\Psi$ , we have that

\begin{equation*} \sup _{x \in F_y} d_{\kern-1pt \mathscr{X}}^H(\Psi (y),x) \leq \sup _{x \in F_y} d_{\mathscr{X}}(x,x')\leq \operatorname {diam}(F_y). \end{equation*}

Taking the supremum over all $y \in \mathscr{M}_2^{\kern0.5pt\mathscr{E}}$ on both sides above, gives

\begin{equation*} \sup _{y \in \mathscr{M}_2^{\kern0.5pt\mathscr{E}}} \sup _{x \in F_y} d_{\kern-1pt \mathscr{X}}^H(\Psi (y),x) =c_{\mathrm{opt}}^{\text{w}}(F, \mathscr{M}_1, \mathscr{E}\kern1.6pt) \leq \operatorname {kersize}^{\text{w}}(F,\mathscr{M}_1, \mathscr{E}\kern1.6pt), \end{equation*}

where we used the fact that $\Psi$ is an optimal map in the first equality. This establishes statement (i).

7.3. Preliminaries from measure theory

In order to prove Theorem3.2, we need to state and cite some existing results from measure theory and prove a preliminary lemma.

7.3.2. Measurability of set-valued functions

For a single-valued function $f \colon Y\to X$ , the inverse image of a set $A \subset X$ is $f^{-1}(A) \,:\!=\, \{y \in Y \colon f(y) \in A\}$ . For a set-valued function $\varphi \colon Y \rightrightarrows X$ , there are different ways to generalise the concept of an inverse image: Given a set $A \subset X$ , we say that the upper inverse of $A$ is $\varphi ^{\mathrm{u}}(A) \,:\!=\, \{y \in Y \,:\,\varphi (y) \subset A\}$ and we say that the lower inverse of $A$ is

\begin{equation*}\varphi ^{\ell }(A) \,:\!=\,\{y \in Y \,:\,\varphi (y) \cap A\neq \emptyset \}.\end{equation*}

Naturally, the notion of continuity of set-valued mappings between topological spaces depends on the definition of inverse. Interested readers are referred to [Reference Aliprantis and Border6, Chapter 17]. In this work, we shall be most concerned with the lower inverse of a set-valued mapping, since this notion of inverse allows us to pick a measurable selector. Next, we define two different notions of measurability for set-valued mappings based on the concept of lower inverse.

Definition 7 ([Reference Aliprantis and Border6, Definition 18.1]). Let $(Y, \Sigma )$ be a measurable space and $X$ a topological space. We say that a set-valued mapping $\varphi \,:\, Y \rightrightarrows X$ is:

• • weakly measurable, if $\varphi ^{\ell }(V) \in \Sigma$ for each open subset $V$ of $X$ ,

• • measurable, if $\varphi ^{\ell }(A)\in \Sigma$ for each closed subset $A$ of $X$ .

Importantly, one needs to remark here that the definition of weakly measurable for set-valued mappings in [Reference Aliprantis and Border6, Definition 18.1] is equivalent to that of measurable set-valued mappings [Reference Aubin and Frankowska14, Definition 8.1.1. (i), (ii)]. Additionally, we have that in some cases measurability implies weak measurability for set-valued mappings.

Lemma 7.5 ([Reference Aliprantis and Border6, Lemma 18.2]). Let $\varphi \,:\, Y \rightrightarrows X$ be a set-valued mapping from a measurable space $(Y,\Sigma )$ into a metric space. Then the following hold:

1. (1) If $\varphi$ is measurable, then it is also weakly measurable.

2. (2) If $\varphi$ is compact-valued and weakly measurable, then it is measurable.

Note that if the topology of $X$ above is induced by a metric, then every set-valued measurable mapping is also weakly measurable [Reference Aliprantis and Border6, Lemma 18.2]. Our main tool for proving Theorem3.2 is the following result.

Theorem 7.6 (Measurable maximum theorem, [Reference Aliprantis and Border6, Theorem 18.19]). Let $X$ be a separable metric space and $(S,\Sigma )$ a measurable space. Let $\varphi \colon S \rightrightarrows X$ be weakly measurable with non-empty compact values, and suppose $f\colon S \times X \to {\mathbb{R}}$ is a Carathéodory function. Define the value function $m\colon S \to {\mathbb{R}}$ by

\begin{equation*} m(s) = \max _{x \in \varphi (s)} \ f(s,x), \end{equation*}

and the correspondence $\Phi \colon S \rightrightarrows X$ of maximisers by

\begin{equation*} \Phi (s) = \{x \in \varphi (s) \ : \ f(s,x) = m(s)\}=\operatorname *{argmax}_{x \in \varphi (s)} f(s,x). \end{equation*}

Then $m$ is measurable, $\Phi$ has non-empty and compact values, and $\Phi$ is measurable and admits a measurable selector.

Note that for real-valued functions $\min _{x \in X} f(x) = \max _{x \in X} ({-}f(x))$ and the Measurable Maximum Theorem can be applied to minimisation problems as well. The Measurable Maximum Theorem will be applied in two ways. The first can be found in Proposition 7.7, which gives sufficient conditions for a map $\phi \colon \mathscr{M}_2^{\kern0.5pt\mathscr{E}} \rightrightarrows \mathscr{X}$ to be in the set $\mathscr{C}$ given by (11). The second use of the theorem above is found in the proof of part (ii) and (iii) of Theorem3.2.

Proposition 7.7. If $\phi \,:\, \mathscr{M}_2^{\kern0.5pt\mathscr{E}} \rightrightarrows \mathscr{X}$ is measurable and has non-empty compact values, then $\phi \in \mathscr{C}.$

Proof. By definition of $\mathscr{C}$ , we need to prove that the function

\begin{align*} r_\phi \,:\, \mathscr{M}_1 \times \mathscr{E} \to {\mathbb{R}}, \quad r_\phi (x,e) = d_{\kern-1pt \mathscr{X}}^H (x, \phi (F(x,e))) = \sup _{z \in \phi (F(x,e))} d_{\mathscr{X}}(x,z) \end{align*}

is measurable. Denote $S \,:\!=\, \mathscr{M}_1 \times \mathscr{E}$ , $X \,:\!=\, \mathscr{X}$ , and

\begin{align*} &\varphi \,:\!=\, \phi \circ F\,:\, \mathscr{M}_1\times \mathscr{E} \rightrightarrows \mathscr{X}, & \varphi (x,e) = \phi (F(x,e)), \\ &f \,:\!=\, d_{\mathscr{X}} \circ (\pi _1, \text{id}_{\mathscr{X}})\,:\, (\mathscr{M}_1 \times \mathscr{E}\kern1.6pt) \times \mathscr{X} \to {\mathbb{R}}, &f((x,e), z) = d_{\mathscr{X}}(x,z). \end{align*}

We now show that the set-valued mapping $\varphi \,:\!=\, \phi \circ F\,:\, \mathscr{M}_1\times \mathscr{E} \rightrightarrows \mathscr{X}$ is weakly measurable. Let $V \subset \mathscr{X}$ be an open set. Then, by the definition [Reference Aliprantis and Border6, Section 17.1] of the lower inverse, $\varphi$ is given by

\begin{align*} \varphi ^\ell (V) = \{(x,e) \in \mathscr{M}_1 \times \mathscr{E} \,:\, \varphi (x,e) \cap V \neq \emptyset \} = \{(x,e) \in \mathscr{M}_1 \times \mathscr{E} \,:\, \phi (F(x,e)) \cap V \neq \emptyset \}. \end{align*}

Observe that this set can be written as $\varphi ^\ell (V) = F^{-1}(\phi ^\ell (V)),$ where $\phi ^\ell (V) = \{y \in \mathscr{M}_2^{\kern0.5pt\mathscr{E}} \,:\, \phi (y) \cap V \neq \emptyset \}$ denotes the lower inverse of $V$ under $\phi$ . Since $\phi$ is a set-valued mapping that is measurable, by Lemma 7.5, it follows that $\phi$ is also weakly measurable. As $\phi \,:\, \mathscr{M}_2^{\kern0.5pt\mathscr{E}} \rightrightarrows \mathscr{X}$ is weakly measurable and as $V \subset \mathscr{X}$ is an open set, we have $\phi ^\ell (V) \in \mathscr{B}(\mathscr{M}_2^{\kern0.5pt\mathscr{E}})$ . Moreover, $F\colon (\mathscr{M}_1\times \mathscr{E}, \mathscr{B}(\mathscr{M}_1\times \mathscr{E}\kern1.6pt)) \to (\mathscr{M}_2^{\kern0.5pt\mathscr{E}}, \mathscr{B}(\mathscr{M}_2^{\kern0.5pt\mathscr{E}}))$ is Borel measurable by Assumption3. Therefore, the preimage of the Borel set $\phi ^\ell (V) \in \mathscr{B}(\mathscr{M}_2^{\kern0.5pt\mathscr{E}})$ under $F$ is Borel measurable

\begin{equation*} \varphi ^\ell (V) = F^{-1}(\phi ^\ell (V)) \in \mathscr{B}(\mathscr{M}_1 \times \mathscr{E}\kern1.6pt). \end{equation*}

Hence, the set-valued mapping $\varphi \,:\, \mathscr{M}_1\times \mathscr{E} \rightrightarrows \mathscr{X}$ is weakly measurable. Moreover, $\varphi \,:\, \mathscr{M}_1\times \mathscr{E} \rightrightarrows \mathscr{X}$ has non-empty compact values because $\phi \,:\, \mathscr{M}_2^{\kern0.5pt\mathscr{E}} \rightrightarrows \mathscr{X}$ has non-empty compact values by assumption. By Assumption3, $(\mathscr{M}_1\times \mathscr{E}, \mathscr{B}(\mathscr{M}_1\times \mathscr{E}\kern1.6pt), \mu )$ is a $\sigma -$ finite measure space. The space $(\mathscr{X},d_{\mathscr{X}})$ is separable, as it is second countable by Assumption 11, and together with Assumption 12, it is also complete. Finally, the function $f$ is continuous in both arguments and hence Carathéodory. Thus, the assumptions in Theorem7.6 are satisfied, and its application implies that the value function $m\,:\, \mathscr{M}_1 \times \mathscr{E}\to {\mathbb{R}}$

\begin{align*} m(x,e) = \max _{z \in \phi (F(x,e))} d_{\mathscr{X}}(x,z) \end{align*}

is measurable. It is immediate to notice that $m = r_\phi$ , so we conclude that $r_\phi$ is measurable. Hence we have proven that $\phi \in \mathscr{C}$ .

7.3.3. Disintegration of measures

Next, we prove a useful proposition that will be applied in the proof of Theorem3.2. For completeness, we start by recalling that every time we write an expression of the form

\begin{align*} \mathop{\mathrm{esssup}}\limits_{(x,e) \in \mathscr{M}_1 \times \mathscr{E}} f(x,e), \quad \quad \mathop{\mathrm{esssup}}\limits_{(x,e) \in F^{-1}(y)} f(x,e), \quad \quad \mathop{\mathrm{esssup}}\limits_{y \in \mathscr{M}_2^{\kern0.5pt\mathscr{E}}} f(y). \end{align*}

Whenever it is clear from context, it is implicit that we are taking the essential supremum with respect to $\mu$ on $\mathscr{M}_1 \times \mathscr{E}$ , with respect to $\mu ^y$ on $F_y$ , and with respect to $F_*\mu$ on $\mathscr{M}_2^{\kern0.5pt\mathscr{E}}$ . We also recall that $\pi _1\colon \mathscr{X}\times \mathscr{Z}\to \mathscr{X}$ refers to the projection on the first component $\pi _1(x,e)=x$ .

Proposition 7.8. Given Assumptions 1 , 3 and 4 , we have the following:

1. (1) For $A \in \mathscr{B} (\mathscr{M}_1\times \mathscr{E}\kern1.6pt)$ , $\mu (A) =0$ if and only if $\mu ^y(A) = 0$ for almost every $y \in \mathscr{M}_2^{\kern0.5pt\mathscr{E}}$ .

2. (2) Let $f\,:\, \mathscr{M}_1\times \mathscr{E}\to [0,+\infty )$ be Borel measurable. Then the function

   \begin{align*} m\colon \mathscr{M}_2^{\kern0.5pt\mathscr{E}} \to {\mathbb{R}}, \quad m(y) = \mathop{\mathrm{esssup}}\limits_{(x,e) \in F^{-1}(y)} f(x,e) \end{align*}
   is Borel measurable.

3. (3) Let $f\,:\, \mathscr{M}_1\times \mathscr{E} \to [0,+\infty )$ be Borel measurable. Then

   \begin{align*} \mathop{\mathrm{esssup}}\limits_{(x,e) \in \mathscr{M}_1\times \mathscr{E}} f(x,e) = \mathop{\mathrm{esssup}}\limits_{y \in \mathscr{M}_2^{\kern0.5pt\mathscr{E}}} \mathop{\mathrm{esssup}}\limits_{(x,e) \in F^{-1}(y)} f(x,e). \end{align*}

4. (5) Let $g\,:\, \mathscr{M}_1 \to [0,+\infty )$ be Borel measurable. Then

   \begin{align*} \int _{F^{-1}(y)} g(\pi _1(x,e))d\mu ^y(x,e) = \int _{F_y} g(x) d\big (\pi _{1*}\mu ^y\big )(x), \end{align*}
   and
   \begin{align*} \mu ^y-\mathop{\mathrm{esssup}}\limits_{(x,e) \in F^{-1}(y)} g(\pi _1(x,e)) = \pi _{1*}\mu ^y-\mathop{\mathrm{esssup}}\limits_{x\in F_y} g(x), \end{align*}
   where $\mu ^y-\operatorname {esssup}$ , respectively, and $\pi _{1*}\mu ^y-\operatorname {esssup}$ , denote the essential supremum with respect to the disintegration of measure $\mu ^y$ and, respectively, the pushforward of the disintegration of measure $\pi _{1*}\mu ^y$ .

Proof. We start with $(i)$ . Let $1_A$ denote the indicator function on $A \in \mathscr{B}(\mathscr{M}_1\times \mathscr{E}\kern1.6pt)$ . Suppose that $\mu (A) = 0$ , then by (iii) in Definition3, we have that

\begin{equation*} 0 = \mu (A) = \int _{\mathscr{M}_1 \times \mathscr{E}} 1_A \ d\mu = \int _{\mathscr{M}_2^{\kern0.5pt\mathscr{E}}} \Bigg ( \int _{F^{-1}(y)} 1_A \ d\mu ^y \Bigg )\ d(F_*\mu )(y). \end{equation*}

The integral of a positive function with respect to a positive measure is zero if and only if the integrand function is zero almost everywhere, so the previous equality is equivalent to

\begin{equation*} \int _{F^{-1}(y)} 1_A \ d\mu ^y = \mu ^{y}(A) = 0 \quad \text{for }\text{ almost every } y \in \mathscr{M}_2^{\kern0.5pt\mathscr{E}}. \end{equation*}

The reverse argument can be made with the same steps. Let us now prove $(ii)$ . Since the Borel $\sigma$ -algebra on $\mathbb{R}$ is generated by sets of form $(a, +\infty )$ , we proceed to show that $m^{-1}((a, +\infty ))$ is Borel measurable for any $a \in {\mathbb{R}}$ . We have

\begin{align*} m^{-1}((a,+\infty )) & = \big\{y \in \mathscr{M}_2^{\kern0.5pt\mathscr{E}}\,:\, m(y) \gt a\big\} \\ & = \big\{y \in \mathscr{M}_2^{\kern0.5pt\mathscr{E}}\,:\, \mu ^y(\{(x,e) \in \mathscr{M}_1\times \mathscr{E}\,:\, f(x,e) \gt a\})\gt 0\big\} \\ & = \big\{y \in \mathscr{M}_2^{\kern0.5pt\mathscr{E}}\,:\, \int _{\mathscr{M}_1\times \mathscr{E}} 1_{f^{-1}((a,\infty ))} \ d\mu ^y\gt 0\big\} \\ & = \big\{y \in \mathscr{M}_2^{\kern0.5pt\mathscr{E}}\,:\, h_a(y) \gt 0\big\} = h_a^{-1}((0,+\infty )), \end{align*}

where $h_a(y) = \int _{\mathscr{M}_1\times \mathscr{E}} 1_{f^{-1}((a,\infty ))} \ d\mu ^y$ . In particular, since $f$ is Borel measurable, $f^{-1}((a,\infty ))$ is a measurable set, and hence, $1_{f^{-1}((a,\infty ))}$ is a measurable function on $(\mathscr{M}_1\times \mathscr{E},\mathscr{B}(\mathscr{M}_1\times \mathscr{E}\kern1.6pt))$ . Now, from (ii), in Definition3, we know that the function $y \mapsto h_a(y) = \int _{\mathscr{M}_1\times \mathscr{E}} 1_{f^{-1}((a,\infty ))} \ d\mu ^y$ is measurable, and so $h_a^{-1}((0,+\infty )) = m^{-1}((a,+\infty ))$ is a Borel measurable subset of $\mathscr{M}_2^{\kern0.5pt\mathscr{E}}$ . As $a \in {\mathbb{R}}$ was arbitrary, this proves that $m$ is Borel-measurable. This concludes $(ii)$ . Next we consider $(iii)$ , and let $m$ be as in $(ii)$ . We start by showing that

(22) \begin{align} \mathop{\mathrm{esssup}}\limits_{(x,e) \in \mathscr{M}_1\times \mathscr{E}} f(x,e) \geq \mathop{\mathrm{esssup}}\limits_{y \in \mathscr{M}_2^{\kern0.5pt\mathscr{E}}} m(y). \end{align}

Let $K= \operatorname {esssup}_{(x,e) \in \mathscr{M}_1\times \mathscr{E}} f(x,e)$ . By definition, we have $\mu (\{(x,e) \in \mathscr{M}_1\times \mathscr{E}\,:\, f(x,e) \gt K \})=0$ . Hence, by Proposition 7.8, $(i)$ , and the fact that $\mu ^y$ is concentrated on $F^{-1}(y)$ , we have

\begin{align*} 0&=\mu ^y(\{(x,e) \in \mathscr{M}_1\times \mathscr{E}\,:\, f(x,e) \gt K\}) =\mu ^y(\{(x,e) \in F^{-1}(y)\,:\, f(x,e) \gt K \}) \end{align*}

for almost every $y \in \mathscr{M}_2^{\kern0.5pt\mathscr{E}}$ . So $m(y) = \operatorname {esssup}_{(x,e) \in F^{-1}(y)} f(x,e) \leq K = \operatorname {esssup}_{\mathscr{M}_1\times \mathscr{E}} f$ for almost every $y \in \mathscr{M}_2^{\kern0.5pt\mathscr{E}}$ . This proves (22). Next, we consider the reverse inequality. By definition of $\operatorname {esssup}_{\mathscr{M}_2^{\kern0.5pt\mathscr{E}}} m$ , we have

\begin{align*} m(y) =\mathop{\mathrm{esssup}}\limits_{(x,e) \in F^{-1}(y)} f(x,e) \leq \mathop{\mathrm{esssup}}\limits_{\mathscr{M}_2^{\kern0.5pt\mathscr{E}}} m \end{align*}

for almost every $y \in \mathscr{M}_2^{\kern0.5pt\mathscr{E}}$ . Hence, as $\mu ^y$ is concentrated on $F^{-1}(y)$

\begin{align*} \mu ^y(\{(x,e) \in F^{-1}(y)\,:\, f(x,e) \gt \mathop{\mathrm{esssup}}\limits_{\mathscr{M}_2^{\kern0.5pt\mathscr{E}}} m \})=\mu ^y(\{(x,e) \in \mathscr{M}_1\times \mathscr{E}\,:\, f(x,e) \gt \mathop{\mathrm{esssup}}\limits_{\mathscr{M}_2^{\kern0.5pt\mathscr{E}}} m \})=0 \end{align*}

for almost every $y \in \mathscr{M}_2^{\kern0.5pt\mathscr{E}}$ . By Proposition 7.8, $(i)$ , this is equivalent to $\mu (\{(x,e) \in \mathscr{M}_1\times \mathscr{E}\,:\, f(x,e) \gt \operatorname {esssup}_{\mathscr{M}_2^{\kern0.5pt\mathscr{E}}} m \})=0$ , which implies $\operatorname {esssup}_{(x,e) \in \mathscr{M}_1\times \mathscr{E}} f(x,e) \leq \operatorname {esssup}_{y \in \mathscr{M}_2^{\kern0.5pt\mathscr{E}}} m(y)$ , as desired. This concludes the proof of $(iii)$ .

Finally, let us prove $(iv)$ . Equality between integrals

\begin{align*} \int _{F^{-1}(y)} (g \circ \pi _1) \, d\mu ^y = \int _{F_y} g d\pi _{1*}\mu ^y \end{align*}

comes directly from the definition of pushforward measure and can be found in detail [Reference Aliprantis and Border6, Theorem 13.46]. To see the equality between essential suprema, take $M \in [0,+\infty )$ , then note that

\begin{align*} (\pi _{1*}\mu ^y)(g^{-1}(M, +\infty )) = \mu ^y(\pi _1^{-1}(g^{-1}(M, +\infty ))) = \mu ^y((g\circ \pi _1)^{-1}(M, +\infty )). \end{align*}

Taking $M = \operatorname {esssup}_{F^{-1}(y)} (g\circ \pi _1)$ , then the definition of essential supremum gives $\mu ^y((g\circ \pi _1)^{-1}(M, +\infty ))=0$ , which by the previous chain of equalities implies that $0 =(\pi _{1*}\mu ^y)(\{x \in F_y\,:\, g(x) \gt \operatorname {esssup}_{F^{-1}(y)} (g\circ \pi _1)\})$ , so that $g(x) \leq \operatorname {esssup}_{F^{-1}(y)} (g\circ \pi _1)$ for $\pi _{1*}\mu ^y$ -almost every $x \in F_y$ . This gives $\operatorname {esssup}_{x \in F_y} g(x) \leq \operatorname {esssup}_{F^{-1}(y)} (g\circ \pi _1)$ , by taking instead $M = \operatorname {esssup}_{x \in F_y} g(x)$ , the same reasoning proves the reverse inequality between essential suprema. Hence equality is proven, concluding the proof of $(iv)$ .

7.4. Proof of Theorem3.2

Having established the above preliminaries, we now proceed to proving Theorem3.2. In order to do so, we will split the Theorem up into two results, Propositions 7.9 and 7.10, and prove these. These results combined provide the proof of Theorem3.2.

Proposition 7.9 (Lower bound of part $(i)$ , Theorem3.2). Given the assumptions in Theorem 3.2 , then the following holds for every $p \in [1,\infty ]$ :

\begin{align*} \operatorname {kersize}^{\text{a}}(F,\mathscr{M}_1, \mathscr{E}, p) \leq 2c_{\mathrm{opt}}^{\text{a}}(F,\mathscr{M}_1, \mathscr{E}, p). \end{align*}

Proof of Proposition 7.9. Let $\varphi \,:\,\mathscr{M}_2^{\kern0.5pt\mathscr{E}} \rightrightarrows \mathscr{X}$ be an arbitrary reconstruction mapping. Fix $y \in \mathscr{M}_2^{\kern0.5pt\mathscr{E}}$ and consider $(x,e),(x',e') \in \mathscr{M}_1\times \mathscr{E}$ such that $F(x,e) = F(x',e')= y$ . Then, by the triangle inequality, we deduce

(23) \begin{equation} d_{\mathscr{X}}(x,x') \leq d_{\kern-1pt \mathscr{X}}^H(x, \varphi (F(x,e))) + d_{\kern-1pt \mathscr{X}}^H(x',\varphi (F(x',e'))). \end{equation}

Let us now distinguish the two cases where $p = \infty$ and $p\in [1, \infty )$ . The structure of the proof will be very similar in the two cases, with the main difference that the case $p = \infty$ involves essential suprema, while the case $p \in [1,+ \infty )$ involves integrals. We will fully prove the case $p\in [1, \infty )$ and provide a sketch of the proof of the case $p=\infty$ , as it is virtually identical. In both cases, however, Equation (23) will play a crucial role. To ensure that the essential suprema and integrals are well-defined, we assume that $\varphi \in \mathscr{C}$ .

Case $p\in [1, \infty )$ ; here, we use that for $a \in [0,\infty )$ the map $a \mapsto a^p$ is convex, and by the definition of convexity, we have that for $a,b \in [0,\infty )$ that $( \tfrac {1}{2} a + \tfrac {1}{2} b)^{p} \leq \tfrac {1}{2} a^{p} + \tfrac {1}{2} b^{p}$ . Replacing $a,b$ with $2a,2b$ yields $(a+b)^p \leq 2^{p-1}(a^p + b^p)$ for $a,b\geq 0$ . Now integrating (23) twice with respect to $\mu ^y$ and using that $(a+b)^p \leq 2^{p-1}(a^p + b^p)$ for $a,b\geq 0$ , we obtain

\begin{align*} &\int _{F^{-1}(y)} \int _{F^{-1}(y)} d_{\mathscr{X}}(x,x')^p \, d\mu ^y(x,e) \, d\mu ^y(x',e') \\& \leq \int _{F^{-1}(y)} \int _{F^{-1}(y)} \big(d_{\kern-1pt \mathscr{X}}^H(x, \varphi (F(x,e))) + d_{\kern-1pt \mathscr{X}}^H(x',\varphi (F(x',e'))) \big)^p \ d\mu ^y(x,e) \, d\mu ^y(x',e') \\& = 2^p\int _{F^{-1}(y)} d_{\kern-1pt \mathscr{X}}^H(x, \varphi (F(x,e)))^p \ d\mu ^y(x,e) \end{align*}

where in the last step we also used the fact that $\mu ^y$ is a probability measure and the integrals are well-defined as $\varphi \in \mathscr{C}$ . Now, integrating the above inequality with respect to $F_*\mu$ on $\mathscr{M}_2^{\kern0.5pt\mathscr{E}}$ , by (iii) in Definition3, and raising to the power $\frac {1}{p}$ gives that

\begin{align*} \operatorname {kersize}^{\text{a}}(F,\mathscr{M}_1, \mathscr{E}, p) & = \Bigg (\int _{\mathscr{M}_2^{\kern0.5pt\mathscr{E}}} \int _{F_y} \int _{F_y} d_{\mathscr{X}}(x,x')^p \ d\mu ^y(x,e) \ d\mu ^y(x',e') \, d(F_*\mu )(y) \Bigg )^{\frac {1}{p}} \\ &\leq \Bigg ( 2^p \int _{\mathscr{M}_2^{\kern0.5pt\mathscr{E}}} \int _{F_y} d_{\kern-1pt \mathscr{X}}^H(x, \varphi (F(x,e)))^p \ \ d\mu ^y(x,e) \ d(F_*\mu )(y)\Bigg )^{\frac {1}{p}} \\ & = 2 \Bigg ( \int _{\mathscr{M}_1\times \mathscr{E}} d_{\kern-1pt \mathscr{X}}^H(x, \varphi (F(x,e)))^p \ d\mu (x,e) \Bigg )^{\frac {1}{p}}. \end{align*}

Since $\varphi \in \mathscr{C}$ was arbitrary, by taking the infimum over $\varphi \in \mathscr{C}$ we obtain:

\begin{align*} \operatorname {kersize}^{\text{a}}(F,\mathscr{M}_1, \mathscr{E}, p) &\leq 2\inf _{\varphi \in \mathscr{C}}\Bigg ( \int _{\mathscr{M}_1\times \mathscr{E}} d_{\kern-1pt \mathscr{X}}^H(x, \varphi (F(x,e)))^p \ d\mu (x,e) \Bigg )^{\frac {1}{p}} \\ & = 2c_{\mathrm{opt}}^{\text{a}}(F,\mathscr{M}_1, \mathscr{E}, p). \end{align*}

The proposition is therefore also proven in the case $p \in [1,+\infty )$ .

Case $p = \infty$ ; the proof follows the basic structure of the case $p \in [1,\infty )$ . In (23), instead of integrating, we take the essential supremum respect to the measure $\mu ^y$ . Then in the next step, instead of integrating, we take the essential supremum in $y$ with respect to the measure $F_*\mu$ on $\mathscr{M}_2^{\kern0.5pt\mathscr{E}}$ and apply Proposition 7.8. Finally, as $\varphi \,:\,\mathscr{M}_2^{\kern0.5pt\mathscr{E}} \rightrightarrows \mathscr{X}$ was arbitrary, taking the infimum over $\varphi \in \mathscr{C}$ concludes the proof.

Proposition 7.10 (Part $(ii)$ and $(iii)$ and upper bound in (i) of Theorem3.2). The following holds for every $p \in [1,\infty ]$ :

\begin{equation*} c_{\mathrm{opt}}^{\text{a}}(F,\mathscr{M}_1, \mathscr{E}, p) \leq \operatorname {kersize}^{\text{a}}(F,\mathscr{M}_1, \mathscr{E}, p), \end{equation*}

and the map $\Psi \colon \mathscr{M}_2^{\kern0.5pt\mathscr{E}} \rightrightarrows \mathscr{X}$ given by,

(24) \begin{align} \Psi (y) &= \operatorname {argmin}_{z \in \mathscr{X}}\operatorname {esssup}_{(x,e) \in F^{-1}(y)} d_{\mathscr{X}}(x,z) & (p = \infty )\\[-10pt]\nonumber \end{align}

(25) \begin{align} \Psi (y) &= \operatorname {argmin}_{z \in \mathscr{X}} \int _{F^{-1}(y)} d_{\mathscr{X}}(x,z)^p \ d\mu ^y(x,e) & (p \in [1, \infty )) \end{align}

is an optimal map with average error of order $p$ . Moreover, $\Psi$ has non-empty compact values, is measurable and it admits a measurable selector.

Proof of Proposition 7.10. We distinguish the cases $p = \infty$ and $p \in [1,\infty )$ . In both cases, the structure of the proof consists in proving the following steps:

1. (1) $\Psi$ , defined either by (24) or (25), has non-empty values;

2. (2) $\Psi$ is measurable, has compact values and admits a measurable selector;

3. (3) $\Psi \in \mathscr{C} = \{\varphi \,:\, \mathscr{M}_2^{\kern0.5pt\mathscr{E}} \rightrightarrows \mathscr{X}\,:\, (x,e) \mapsto d_{\kern-1pt \mathscr{X}}^H(x,\varphi (F(x,e)) \text{is measurable}\}$ ;

4. (4) $\Psi$ is an optimal map with average error of order $p$ ;

5. (5) Upper bound: $c_{\mathrm{opt}}^{\text{a}}(F,\mathscr{M}_1, \mathscr{E}, p) \leq \operatorname {kersize}^{\text{a}}(F,\mathscr{M}_1,\mathscr{E},p)$ with $p=\infty$ or $p \in [1,+\infty )$ .

First, we consider the case $p \in [1,\infty )$ . Again, let us first introduce some notation, similar to above. Fix $y \in \mathscr{M}_2^{\kern0.5pt\mathscr{E}}$ . Define $f_y\,:\, \mathscr{X} \to [0,\infty )$ ,

\begin{equation*} f_y(z) = \int _{F^{-1}(y)} d_{\mathscr{X}}(x, z)^p \ d\mu ^y(x,e) \end{equation*}

for $z \in \mathscr{X}$ . Define also

\begin{align*} r_y &= \mathop{\mathrm{esssup}}\limits_{\substack {(x,e) \in F^{-1}(y)\\(x',e') \in F^{-1}(y)}} d_{\mathscr{X}}(x, x'), \\ E_y^{(x,e)} &= \{(x',e') \in F^{-1}(y)\,:\, d_{\mathscr{X}}(x,x') \gt r_y\} \quad \text{ for } (x,e) \in F^{-1}(y),\\ G_y &= \{(x,e) \in F^{-1}(y)\,:\, \mu ^y(E_{y}^{(x,e)}) = 0 \}. \end{align*}

Note that $f_y$ is Borel measurable. The function $((x,e),z) \mapsto 1_{F^{-1}(y)}(x,e)\, d_{\mathscr{X}}(x,z)$ is non-negative and Borel measurable. By the Fubini-Tonelli [Reference Folland55, Theorem 2.37] $f_y$ , as $z \mapsto \int _{F^{-1}(y)} d_{\mathscr{X}}(x, z)^p \ d\mu ^y(x,e)$ , is Borel measurable. Additionally, by a similar line of reasoning, one can show that the function $y \mapsto r_y$ is Borel measurable. Additionally, as the metric space $(\mathscr{M}_1,d_{\mathscr{X}})$ is compact by Assumption4, the set $\mathscr{M}_1$ is bounded. Thus, as $F^{-1}(y) \subset \mathscr{M}_1\times \mathscr{E}$ , we have that

\begin{align*} r_y \leq \sup _{\substack {(x,e) \in F^{-1}(y)\\(x',e') \in F^{-1}(y)}} d_{\mathscr{X}}(x, x') \leq \operatorname {diam}(\mathscr{M}_1)\lt \infty . \end{align*}

We now show that the set $G_y$ is non-empty and $\mu ^y(G_y)=1$ . Fix $y \in \mathscr{M}^{\mathscr{E}}$ . By definition of the essential supremum, it follows that

\begin{align*} (\mu ^y \otimes \mu ^y)\big (\big \{((x,e),(x',e')) \in F^{-1}(y)\times F^{-1}(y) \,:\, d_{\mathscr{X}}(x,x') \gt r_y \big \}\big )=0. \end{align*}

Then, by Fubini-Tonelli [Reference Folland55, Theorem 2.37],

\begin{align*} 0 &= (\mu ^y \otimes \mu ^y)\left (\big \{((x,e),(x',e')) \in F^{-1}(y)\times F^{-1}(y) \,:\, d_{\mathscr{X}}(x,x') \gt r_y \big \}\right )\\ &= \int _{F^{-1}(y)} \mu ^y\big (E_y^{(x,e)}\big )\, d\mu ^y(x,e). \end{align*}

Since the integrand is nonnegative, we conclude that

\begin{align*} \mu ^y\big (E_y^{(x,e)}\big )=0 \quad \text{for } \mu ^y\text{-a.e. } (x,e)\in F^{-1}(y). \end{align*}

Recall the definition $G_y = \{(x,e) \in F^{-1}(y) \,:\, \mu ^y(E_y^{(x,e)}) = 0\}$ . As the disintegration $\mu ^y$ is a probability measure that is concentrated on $F^{-1}(y)$ , Definition3 (i), we have that $\mu ^y(G_y)=1$ and, in particular, $G_y \neq \emptyset$ .

We proceed to prove the claim and start by considering (I). We consider a general setting and let $(X,d)$ be a metric space equipped with a probability measure $\nu$ concentrated on a bounded subset $A\subseteq X$ , and define

\begin{equation*} g(x) \,:\!=\, \Big ( \int _A d(x,a)^p \, d\nu (a)\Big )^{\frac {1}{p}}=\|d(x,\cdot )\|_{L^p(X,\nu )} = \|d(x,\cdot )\|_p. \end{equation*}

We claim that $|g(x)-g(z)|\leq d(x,z)$ for all $x,y \in X$ . To see this, consider $a, x, z \in X$ and note that by the triangle inequality $d(x,a) \leq d(x,z) + d(z,a)$ . Taking $L^p(X,\nu )$ -norms in the variable $a$ and applying Minkowski’s inequality gives

\begin{align*} g(x) = \|d(x,\cdot )\|_p \leq \|d(x,z)+d(z,\cdot )\|_p \leq \|d(x,z)\|_p+\|d(z,\cdot )\|_p = d(x,z) + g(z), \end{align*}

where in the last passage we used that $\nu$ is a probability measure. Switching the roles of $x$ and $z$ , leads to the desired inequality. It follows that $g$ is continuous. By assumption4, since $\mathscr{M}_1$ is compact and $F_y\subseteq \mathscr{M}_1$ , then $F_y$ is bounded. Thus, letting $(X,d) = (\mathscr{X},d_{\mathscr{X}})$ , $\nu = \pi _{1*}\mu ^y$ , $A = F_y$ above, and recalling Proposition 7.8, (iv), then $g^p=f_y$ , which proves (I).

To prove (II), we will show that for $\mu ^y$ -almost every $(x,e) \in F^{-1}(y)$ we have

(26) \begin{align} \Psi (y) = \operatorname {argmin}_{z\in \mathscr{X}} \int _{F^{-1}(y)}d_{\mathscr{X}}(x',z)^p\ d\mu ^y(x',e') = \operatorname {argmin}_{z\in B_{d_{\mathscr{X}}}(x,2r_y)} f_y(z). \end{align}

Fix $(x,e) \in G_y$ . If $z\in \mathscr{X} \setminus B_{d_{\mathscr{X}}}(x,2r_y)$ , then for $\mu ^y$ -almost every $(x',e')\in F^{-1}(y)$ ,

\begin{equation*} d_{\mathscr{X}}(z,x') \geq d_{\mathscr{X}}(z,x)-d_{\mathscr{X}}(x,x') \gt 2r_y - r_y = r_y. \end{equation*}

Thus, the previous inequality holds for any $z\in \mathscr{X} \setminus B_{d_{\mathscr{X}}}(x,2r_y)$ . Thus,

\begin{align*} f_y(z) &= \int _{F^{-1}(y)}d_{\mathscr{X}}(z,x')^p\ d\mu ^y(x',e') \\ &\gt \int _{F^{-1}(y)} r_y^p \, d\mu ^y(x',e') = r_y^p. \end{align*}

On the other hand,

\begin{align*} f_y(x) &= \int _{F^{-1}(y)}d_{\mathscr{X}}(x,x')^p\ d\mu ^y(x',e') \\ & \leq \int _{F^{-1}(y)} r_y^p \ d\mu ^y(x',e') = r_y^p. \end{align*}

Therefore, $f_y(z) \gt f_y(x)$ whenever $z \notin B(x,2r_y)$ , which implies that points $z$ outside of such a ball cannot be minimisers, hence proving (26). This concludes part (II) of the claim.

With the claim, we can prove the required (a)–(e) properties of $\Psi$ . First, let us prove (a), namely that $\Psi$ in (25) has non-empty values. By the Heine-Borel property of the metric $d_{\mathscr{X}}$ , the set $B_{d_{\mathscr{X}}}(x,2r_y) \subset \mathscr{X}$ is compact, since it is a closed ball with respect to the metric $d_{\mathscr{X}}$ . Hence, the function $f_y$ is continuous by (I) and its minimisers are by (II) restricted to the compact set $B_{d_{\mathscr{X}}}(x,2r_y)$ . Therefore, the minimum in (25) is attained by the Extreme Value Theorem. This shows that the argmin is non-empty, and hence that $\Psi$ has non-empty values on $\mathscr{M}_2^{\kern0.5pt\mathscr{E}}$ .

We now proceed to prove (b), namely that $\Psi$ is measurable and has compact values. Recall that above we have shown that $\operatorname {diam}(\mathscr{M}_1)\lt \infty$ . We will apply the Maximum Measurable Theorem, 7.6, with $S = \mathscr{M}_2^{\kern0.5pt\mathscr{E}}$ , $X = \mathscr{X}$ , and

\begin{align*} \varphi &\,:\, \mathscr{M}_2^{\kern0.5pt\mathscr{E}} \rightrightarrows \mathscr{X}, \qquad \varphi (y) = B_{d_{\mathscr{X}}}(\mathscr{M}_1,2\operatorname {diam}(\mathscr{M}_1)), \\ f &\,:\,\mathscr{M}_2^{\kern0.5pt\mathscr{E}} \times \mathscr{X} \to {\mathbb{R}}, \ f(y,z) = f_y(z) = \int _{F^{-1}(y)} d_{\mathscr{X}}(x ,z)^p \ d\mu ^y(x,e). \end{align*}

In order to apply the theorem, we need to verify that the assumptions are satisfied. We start by proving that $\varphi$ is weakly measurable with non-empty compact values. Firstly, it is clear that, since $\varphi$ is constant, then $\varphi$ is weakly measurable and has non-empty values. Moreover, the only value $\varphi$ takes is $B_{d_{\mathscr{X}}}(\mathscr{M}_1,2\operatorname {diam}(\mathscr{M}_1))$ , which we now prove to be compact. Recall that the distance is $\operatorname {dist}_{d_{\mathscr{X}}}(x,A) = \inf _{a \in A} d_{\mathscr{X}}(x,a)$ . Note that, since $\mathscr{M}_1$ is compact by Assumption4, then $\mathscr{M}_1$ is bounded and hence $B_{d_{\mathscr{X}}}(\mathscr{M}_1,2\operatorname {diam}(\mathscr{M}_1))= \{x\in \mathscr{X}\,:\, \operatorname {dist}_{d_{\mathscr{X}}}(x, \mathscr{M}_1) \leq 2\text{diam}(\mathscr{M}_1)\}$ is bounded too.

We now show that the function $\operatorname {dist}_{d_{\mathscr{X}}}(\cdot , \mathscr{M}_1)$ is continuous. We consider a general setting, and let $(X,d)$ be a metric space, $A \subseteq X$ be a bounded subset and $g(x)\,:\!=\, \operatorname {dist}_{d}(x,A) = \inf _{a \in A} d(x,a)$ . We claim that $|g(x)-g(y)|\leq d(x,y)$ for all $x,y \in X$ . To see this, consider $a, x, y \in X$ and note that

\begin{align*} d(x,a) \leq d(x,y) + d(y,a) \quad \implies \quad \inf _{a \in A}d(x,a) \leq d(x,y) + \inf _{a \in A} d(y,a). \end{align*}

Switching the roles of $x$ and $y$ , leads to the desired inequality. It follows that $g$ is continuous. Moreover, since the function $\operatorname {dist}_{d_{\mathscr{X}}}(\cdot , \mathscr{M}_1)$ is continuous, the set

\begin{equation*}B_{d_{\mathscr{X}}}(\mathscr{M}_1,2\operatorname {diam}(\mathscr{M}_1)) = \operatorname {dist}_{d_{\mathscr{X}}}(\cdot ,\mathscr{M}_1)^{-1}([0,2\operatorname {diam}(\mathscr{M}_1)])\end{equation*}

is closed. Hence, we have proven that $B_{d_{\mathscr{X}}}(\mathscr{M}_1,2\text{diam}(\mathscr{M}_1))$ is closed and bounded, and by the Heine Borel property of $d_{\mathscr{X}}$ granted by Assumption4 it follows that $B_{d_{\mathscr{X}}}(\mathscr{M}_1,2\text{diam}(\mathscr{M}_1))$ is compact. This proves that $\varphi$ is weakly measurable with non-empty compact values. Secondly, to prove that $f$ is Carathéodory, we need to show that $f(y, \cdot ) = f_y$ is continuous for every fixed $y\in \mathscr{M}_2^{\kern0.5pt\mathscr{E}}$ and that $f(\cdot ,z)$ is measurable for every fixed $z\in \mathscr{M}_1$ . On the one hand, for every fixed $y\in \mathscr{M}_2^{\kern0.5pt\mathscr{E}}$ , the function $f_y$ is continuous on $\mathscr{X}$ as proven in claim (I). On the other hand, for every fixed $z$ , the function $f(\cdot ,z)\,:$ $y \mapsto \int _{F^{-1}(y)} d_{\mathscr{X}}(x ,z)^p \ d\mu ^y(x,e)$ is Borel measurable, described by Definition3 (ii). Then, by Theorem7.6, the possibly set-valued function $\Phi \,:\, \mathscr{M}_2^{\kern0.5pt\mathscr{E}} \rightrightarrows \mathscr{X}$ given by

\begin{align*} \Phi (y) = \mathop{\mathrm{argmin}}\limits_{z \in B_{d_{\mathscr{X}}}(\mathscr{M}_1,2\text{diam}(\mathscr{M}_1)) } \ \int _{F^{-1}(y)} d_{\mathscr{X}}(x ,z)^p \ d\mu ^y(x,e) \end{align*}

is measurable and has non-empty, compact values. Moreover, by combining (26) and the fact that for $(x,e) \in G_y$ , $B_{d_{\mathscr{X}}}(x,2r_y) \subseteq B_{d_{\mathscr{X}}}(\mathscr{M}_1,2\text{diam}(\mathscr{M}_1))$ , we deduce that $\Phi = \Psi$ . Hence, $\Psi$ is measurable and has non-empty, compact values.

We now prove (c), namely that $\Psi \in \mathscr{C}$ . This follows directly from Proposition 7.7.

We now proceed to prove (d), namely that $\Psi$ is an optimal map. Let $\varphi \in \mathscr{C}$ . By the minimising definition of $\Psi$ ,

\begin{align*} \int _{F^{-1}(y)} d_{\kern-1pt \mathscr{X}}^H(\Psi (y),x)^p \ d\mu ^y(x,e) \leq \int _{F^{-1}(y)} d_{\mathscr{X}}(z,x)^p \ d\mu ^y(x,e) \end{align*}

for every $z \in \varphi (y)$ . In particular, taking the supremum with respect to $z \in \varphi (y)$ , which coincides with considering the Hausdorff distance, and using Fatou’s Lemma yields

\begin{align*} \int _{F^{-1}(y)} d_{\kern-1pt \mathscr{X}}^H(\Psi (y),x)^p \ d\mu ^y(x,e) & \leq \sup _{z \in \varphi (y)} \int _{F^{-1}(y)} d_{\mathscr{X}}(z,x)^p \ d\mu ^y(x,e) \\ & \leq \int _{F^{-1}(y)} \sup _{z \in \varphi (y)} d_{\mathscr{X}}(z,x)^p \ d\mu ^y(x,e) \\ & \leq \int _{F^{-1}(y)} d_{\kern-1pt \mathscr{X}}^H(\varphi (y),x)^p \ d\mu ^y(x,e). \end{align*}

By integrating with respect to $y\in \mathscr{M}_2^{\kern0.5pt\mathscr{E}}$ , we obtain

\begin{align*} & \int _{y \in \mathscr{M}_2^{\kern0.5pt\mathscr{E}}} \int _{F^{-1}(y)} d_{\kern-1pt \mathscr{X}}^H(\Psi (y),x)^p \ d\mu ^y(x,e) \ d(F_*\mu )(y) \\ & \quad \leq \int _{y \in \mathscr{M}_2^{\kern0.5pt\mathscr{E}}} \int _{F^{-1}(y)} d_{\kern-1pt \mathscr{X}}^H(\varphi (y),x)^p \ d\mu ^y(x,e) \ d(F_*\mu )(y). \end{align*}

Due to Definition3 (iii) of the disintegration of measure, the above integrals can be rewritten as

\begin{align*} \int _{\mathscr{M}_1\times \mathscr{E}} d_{\kern-1pt \mathscr{X}}^H(\Psi (F(x,e)),x)^p \ d\mu (x,e) \leq \int _{\mathscr{M}_1\times \mathscr{E}} d_{\kern-1pt \mathscr{X}}^H(\varphi (F(x,e)),x)^p \ d\mu (x,e). \end{align*}

Now, as $\varphi \in \mathscr{C}$ was arbitrary and by raising both sides to the power $\frac {1}{p}$ , we obtain

\begin{align*} \Bigg (\int _{(x,e)\in \mathscr{M}_1\times \mathscr{E}} d_{\kern-1pt \mathscr{X}}^H(\Psi (F(x,e)),x)^p \ d\mu (x,e) \Bigg )^{\frac {1}{p}} \leq c_{\mathrm{opt}}^{\text{a}}(F,\mathscr{M}_1, \mathscr{E}, p). \end{align*}

The opposite inequality holds trivially, as $\Psi \in \mathscr{C}$ . Therefore, $\Psi$ is an optimal map.

Finally, we proceed to prove (e), namely the upper bound $ c_{\mathrm{opt}}^{\text{a}}(F,\mathscr{M}_1, \mathscr{E}, p) \leq \operatorname {kersize}^{\text{a}}(F,\mathscr{M}_1, \mathscr{E}, p).$ By the minimisation property of $\Phi$ , hence also of $\Psi$ , for every $(x',e') \in F^{-1}(y)$ and for $F_*\mu$ -a.e. $y \in \mathscr{M}_2^{\kern0.5pt\mathscr{E}}$ :

(27) \begin{align} \int _{F^{-1}(y)} d_{\kern-1pt \mathscr{X}}^H(x ,\Psi (y))^p \ d\mu ^y(x,e) \leq \int _{F^{-1}(y)} d_{\mathscr{X}}(x ,x')^p \ d\mu ^y(x,e). \end{align}

Integrating (27) with respect to $\mu ^y$ in the $(x',e')$ variables yields,

\begin{align*} \int _{F^{-1}(y)} d_{\kern-1pt \mathscr{X}}^H(x, \Psi (y))^p \ d\mu ^y(x,e) \leq \int _{F^{-1}(y)} \int _{F^{-1}(y)} d_{\mathscr{X}}(x, x')^p \ d\mu ^y(x,e) \ d\mu ^y(x',e'). \end{align*}

where we used that $\mu ^y$ is a probability measure. Integrating both sides over $y\in \mathscr{M}_2^{\kern0.5pt\mathscr{E}}$ with respect to $F_*\mu$ we obtain

\begin{align*} &\int _{\mathscr{M}_2^{\kern0.5pt\mathscr{E}}} \int _{F_y} d_{\kern-1pt \mathscr{X}}^H(x, \Psi (y))^p \ d\mu ^y(x,e) \ d(F_*\mu )(y)\\ & \quad \leq \int _{\mathscr{M}_2^{\kern0.5pt\mathscr{E}}} \int _{F^{-1}(y)} \int _{F^{-1}(y)} d_{\mathscr{X}}(x, x')^p\ d\mu ^y(x,e) \ d\mu ^y(x',e') \ d(F_*\mu )(y). \end{align*}

Using the definition of disintegration of the measure $\mu$ on the left hand side of the above inequality yields

\begin{align*} \int _{\mathscr{M}_1\times \mathscr{E}} d_{\kern-1pt \mathscr{X}}^H(x, \Psi (F(x,e)))^p \ d\mu (x,e) \leq \operatorname {kersize}^{\text{a}}(F,\mathscr{M}_1, \mathscr{E}, p)^p. \end{align*}

Then, raising both sides to the $\frac {1}{p}$ -th power, gives

\begin{align*} \Bigg (\int _{\mathscr{M}_1\times \mathscr{E}} d_{\kern-1pt \mathscr{X}}^H(x, \Psi (F(x,e)))^p \ d\mu (x,e) \Bigg )^{\frac {1}{p}} \leq \operatorname {kersize}^{\text{a}}(F,\mathscr{M}_1, \mathscr{E}, p). \end{align*}

And finally, since $\Psi \in \mathscr{C}$ , we conclude

\begin{align*} c_{\mathrm{opt}}^{\text{a}}(F,\mathscr{M}_1, \mathscr{E}, p) \leq \operatorname {kersize}^{\text{a}}(F,\mathscr{M}_1, \mathscr{E}, p). \end{align*}

This concludes the case $p \in [1,+\infty )$ . Hence, the proof is complete.

Now we consider the case $p=\infty$ . The proof only requires minor modifications to the case $p \in [1,\infty )$ , that we will describe in the following. The objective function for $y \in \mathscr{M}_2^{\kern0.5pt\mathscr{E}}$ and $z \in \mathscr{X}$ is

\begin{equation*} f_y(z) = \mathop{\mathrm{esssup}}\limits_{(x,e) \in F^{-1}(y)} d_{\mathscr{X}}(x, z). \end{equation*}

where the essential supremum is taken with respect to $\mu ^y$ . Then $\Psi (y) = \operatorname {argmin}_{\mathscr{X}} f_y$ . Define, as before,

\begin{equation*} r_y = \mathop{\mathrm{esssup}}\limits_{\substack {(x,e) \in F^{-1}(y)\\(x',e') \in F^{-1}(y)}} d_{\mathscr{X}}(x, x'). \end{equation*}

The claims are proven analogously to the case $p \in [1,\infty )$ , except that to prove (I), Minkowski’s inequality is replaced by the following. We consider a general setting, and let $(X,d)$ be a metric space, $A\subseteq X$ be a bounded subset, $\nu$ be a probability measure on $X$ concentrated on $A$ and $g(x)\,:\!=\, \operatorname {esssup}_{a \in A} d(x,a)$ . We claim that $|g(x)-g(z)|\leq d(x,z)$ for all $x,z \in X$ . To see this, consider $a, x, z \in X$ and notice that

\begin{align*} d(x,a) \leq d(x,z) + d(z,a) \quad \implies \quad \operatorname {esssup}_{a \in A}d(x,a) \leq d(x,z) + \operatorname {esssup}_{a \in A} d(z,a). \end{align*}

Switching the roles of $x$ and $z$ , leads to the desired inequality. It follows that $g$ is continuous. Claim (II) follows the same line of reasoning as in the case $p \in [1,\infty )$ by replacing the integration with the essential supremum with respect to $\mu ^y$ .

With the claim, we can show the properties given by the list (a)-(e) stated at the beginning of the proof, similarly to the case $p \in [1,\infty )$ . For the sake of brevity, we provide a sketch of the proof.

Part (a) follows the same line of reasoning as in the case $p \in [1,\infty )$ . In part (b) we again apply the Maximum Measurable Theorem7.6 with $f(y,z) = f_y(z) \,:\!=\, \operatorname {esssup}_{(x,e) \in F^{-1}(y)} d_{\mathscr{X}}(x ,z)$ and apply Proposition 7.8 to show that $f(\cdot ,z)\,:\, y \mapsto \operatorname {esssup}_{(x,e)\in F^{-1}(y)}d_{\mathscr{X}}(x,z)$ is Borel measurable. Part (c) is again a direct consequence of (b) and Proposition 7.7. Parts (d) and (e) follows the same line of reasoning as in the case $p \in [1,\infty )$ by replacing the integration with the essential supremum. This concludes the proof of the proposition in the case $p = \infty$ .

7.5. Proof of Proposition 4.1

Proof. We begin with part $(1)$ by showing that if $A$ satisfies the rNSP, (17), with respect to the set $\mathscr{M}_1$ , then $A$ is injective on $\mathscr{M}_1$ . Let $x,x' \in \mathscr{M}_1$ such that $Ax=Ax'$ , then $A(x-x')=0$ . Now we apply the rNSP, (17), to $h\,:\!=\, x-x'$ , and since $x-x' \in \mathscr{M}_1 - \mathscr{M}_1$ , this yields

\begin{align*} {\left \vert \kern -0.25ex\left \vert \kern -0.25ex\left \vert x-x' \right \vert \kern -0.25ex\right \vert \kern -0.25ex\right \vert }_{\mathscr{X}_1} \leq D_1 \mathrm{dist}_{\mathscr{X}_2}(x-x',\mathscr{M}_1-\mathscr{M}_1) + 0 = 0. \end{align*}

This implies that $h=x-x'=0$ . Hence $A$ is injective on $\mathscr{M}_1$ .

Additionally, if $A$ is injective on $\mathscr{M}_1$ , then for $x,x' \in \mathscr{M}_1$ such that $Ax=Ax'$ , then $x-x'=0$ and we have that

\begin{align*} (\mathscr{M}_1 - \mathscr{M}_1) \cap \mathscr{N}\kern1pt(A) = \{0\}. \end{align*}

For the converse direction, let $x,x' \in \mathscr{M}_1$ such that $Ax=Ax'$ . This is equivalent to $A(x-x')=0$ and as $(\mathscr{M}_1 - \mathscr{M}_1) \cap \mathscr{N}\kern1pt(A) = \{0\}$ , we have that $x-x'=0$ . Thus, $x=x'$ and $A$ is injective.

For part $(2)$ , let $y \in \mathscr{M}_2^{\kern0.5pt\mathscr{E}}$ and $x,x'\in \mathscr{M}_1$ and $e,e'\in \mathscr{E}$ be such that $y=F(x,e) = Ax+e =Ax'+e'= F(x',e')$ . From the rNSP (17), as $\mathrm{diam}_{d_{\mathscr{Y}}}(\mathscr{E}\kern1.6pt) = \sup _{e,e' \in \mathscr{E}}{\left \vert \kern -0.25ex\left \vert \kern -0.25ex\left \vert e-e' \right \vert \kern -0.25ex\right \vert \kern -0.25ex\right \vert }_{\mathscr{Y}} = \eta$ and since $x-x' \in \mathscr{M}_1 - \mathscr{M}_1$ , we then have that

\begin{align*} {\left \vert \kern -0.25ex\left \vert \kern -0.25ex\left \vert x-x' \right \vert \kern -0.25ex\right \vert \kern -0.25ex\right \vert }_{\mathscr{X}_1} &\leq D_1\mathrm{dist}_{\mathscr{X}_2}(x-x', \mathscr{M}_1 -\mathscr{M}_1) + D_2 {\left \vert \kern -0.25ex\left \vert \kern -0.25ex\left \vert A(x-x') \right \vert \kern -0.25ex\right \vert \kern -0.25ex\right \vert }_{\mathscr{Y}} \\ &= D_2{\left \vert \kern -0.25ex\left \vert \kern -0.25ex\left \vert e-e' \right \vert \kern -0.25ex\right \vert \kern -0.25ex\right \vert }_{\mathscr{Y}} \leq D_2\eta . \end{align*}

Taking supremum over all $x, x' \in F_y$ and, then, over $y \in \mathscr{M}_2^{\kern0.5pt\mathscr{E}}$ yields

\begin{align*} \mathrm{kersize}^{\text{w}}(F, \mathscr{M}_1, \mathscr{E}\kern1.6pt) = \sup _{y \in \mathscr{M}_2^{\kern0.5pt\mathscr{E}}} \ \sup _{x,x' \in F_y} d_{\mathscr{X}}(x,x') \le D_2\eta . \end{align*}

7.6. Proof of Proposition 4.2

Before introducing the Bayesian framework for inverse problems, we recall the concept of regular conditional distribution.

Regular conditional distributions do not always exist. The following positive result guarantees that a regular conditional distribution exists when the random variable that is being conditioned takes values in a completely metrisable and separable topological space, also referred to as a Polish space.