Proof
For
\(R \in \mathbb {N}\), define
\(M_R := \mathrm {range}(D_R) \subset \mathbf {X}\). Furthermore, for
\(N,\ell \in \mathbb {N}\), let
$$\begin{aligned} \mathcal {G}_{N,\ell } := \big \{ \mathbf {x}\in \mathcal {S}\,\, :\,\, \forall \, R \in \mathbb {N}: {{\,\mathrm{dist}\,}}_{\mathbf {X}} (\mathbf {x}, M_R) \le N \cdot R^{-(s^*+ \frac{1}{\ell })} \big \} . \end{aligned}$$
Since
\({{\,\mathrm{dist}\,}}_{\mathbf {X}} (\cdot , M_R)\) is continuous, it is not hard to see that each set
\(\mathcal {G}_{N,\ell } \subset \mathcal {S}\) is closed. Denote by
\(\mathcal {G}_{N,\ell }^{\circ }\) the (relative) interior of
\(\mathcal {G}_{N,\ell }\) in
\(\mathcal {S}\).
Step 1: (If \(\mathcal {G}_{N,\ell }^\circ \ne \emptyset \), then there exist \(\mathbf {x}_0' \in \mathbf {X}\) and \(t > 0\) such that \(\mathbf {x}_0' + t \mathcal {S}\subset \mathcal {G}_{N,\ell }\)). Choose \(\mathbf {x}_0 \in \mathcal {G}_{N,\ell }^\circ \subset \mathcal {S}\) and note that \(\mathcal {S}\cap {{\,\mathrm{Ball}\,}}(\mathbf {x}_0, \varepsilon ; \mathbf {X}) \subset \mathcal {G}_{N,\ell }\) for a suitable \(\varepsilon \in (0, 1)\). We distinguish the two cases regarding the assumptions on \(\mathcal {S}\).
Case 1: \(\mathcal {S}\) is convex. Note that
\(\mathcal {S}\subset {{\,\mathrm{Ball}\,}}(\mathbf {0}, C; \mathbf {X})\) for a suitable
\(C \ge 1\), since
\(\mathcal {S}\) is bounded. Define
\(t := \frac{\varepsilon }{2 C} \in (0,1)\) and
\(\mathbf {x}_0' := (1 - t) \mathbf {x}_0 \in \mathbf {X}\). With these choices, we see for arbitrary
\(\mathbf {x}\in \mathcal {S}\) that
\(\mathbf {x}_0' + t \mathbf {x}\in \mathcal {S}\) by convexity, and furthermore
$$\begin{aligned} \big \Vert \mathbf {x}_0 - \big ( \mathbf {x}_0' + t \, \mathbf {x}\big ) \big \Vert _{\mathbf {X}} = t \cdot \Vert \mathbf {x}_0 - \mathbf {x}\Vert _{\mathbf {X}} \le 2 t C = \varepsilon . \end{aligned}$$
Thus,
\( \mathbf {x}_0' + t \mathcal {S}\subset \mathcal {S}\cap {{\,\mathrm{Ball}\,}}(\mathbf {x}_0, \varepsilon ; \mathbf {X}) \subset \mathcal {G}_{N,\ell } \).
Case 2: \(\mathcal {S}= \{ \mathbf {x}\in \mathbf {X}:\Vert \mathbf {x}\Vert _*\le r \}\) for some \(r \in (0,\infty )\).
With \(C,\kappa \ge 1\) as in Part 2 of the assumptions of the proposition, let \(0< \sigma< \frac{\varepsilon }{2 \kappa C (1 + r)}< \varepsilon < 1\) and define \(\mathbf {x}_0' := (1 - \sigma ) \, \mathbf {x}_0\), noting that \(\Vert \mathbf {x}_0' \Vert _*< r\). By continuity of \(\Vert \cdot \Vert _*\) with respect to itself, we can choose \(0< \delta < \frac{\varepsilon \cdot \min \{ 1, r\} }{2 \kappa C}\) such that \(\Vert \mathbf {x}_0' + \mathbf {y}\Vert _*< r\) for all \(\mathbf {y}\in \mathbf {X}\) satisfying \(\Vert \mathbf {y}\Vert _*\le \delta \). Define \(t := \frac{\delta }{r}\). For arbitrary \(\mathbf {y}\in \mathcal {S}\), we then have \(\Vert t \, \mathbf {y}\Vert _*\le t r = \delta \), and hence, \(\mathbf {x}_0' + t \, \mathbf {y}\in \mathcal {S}\). Furthermore, \( \Vert (\mathbf {x}_0 ' + t \, \mathbf {y}) - \mathbf {x}_0 \Vert _{\mathbf {X}} \le C \cdot \Vert - \sigma \mathbf {x}_0 + t \, \mathbf {y}\Vert _{*} \le \kappa \sigma C r + \kappa C \delta \le \varepsilon . \) Overall, we have shown that \( \mathbf {x}_0' + t \mathcal {S}\subset \mathcal {S}\cap {{\,\mathrm{Ball}\,}}(\mathbf {x}_0, \varepsilon ; \mathbf {X}) \subset \mathcal {G}_{N,\ell } , \) as desired.
Step 2: (We have \(\mathcal {G}_{N,\ell }^\circ = \emptyset \) for all \(N,\ell \in \mathbb {N}\)). Assume toward a contradiction that \(\mathcal {G}_{N,\ell }^\circ \ne \emptyset \). By Step 1, there then exist \(\mathbf {x}_0' \in \mathbf {X}\) and \(t > 0\) satisfying \(\mathbf {x}_0' + t \mathcal {S}\subset \mathcal {G}_{N,\ell }\). Thus, for each \(\mathbf {x}\in \mathcal {S}\), we have \(\mathbf {x}_0' + t \, \mathbf {x}\in \mathcal {G}_{N,\ell }\), and therefore \({{\,\mathrm{dist}\,}}_{\mathbf {X}} \big ( \mathbf {x}_0' + t \, \mathbf {x}, M_R \big ) \le N \cdot R^{-(s^*+ \frac{1}{\ell })}\) for all \(R \in \mathbb {N}\). Because of \(M_R = \mathrm {range} (D_R)\), this implies that there exists \(c_{\mathbf {x},R} \in \{0,1\}^R\) satisfying \(\Vert (\mathbf {x}_0' + t \mathbf {x}) - D_R(c_{\mathbf {x},R}) \Vert _{\mathbf {X}} \le N \cdot R^{-(s^*+ \frac{1}{\ell })}\).
Now, we define a new codec
by
$$\begin{aligned} \widetilde{E}_R : \mathcal {S}\rightarrow \{0,1\}^R , \mathbf {x}\mapsto c_{\mathbf {x},R} \qquad \text {and} \qquad \widetilde{D}_R : \{0,1\}^R \rightarrow \mathbf {X}, c \mapsto t^{-1} \cdot \big ( D_R (c) - \mathbf {x}_0' \big ) . \end{aligned}$$
For arbitrary
\(\mathbf {x}\in \mathcal {S}\), we then see
$$\begin{aligned} \big \Vert \mathbf {x}- \widetilde{D}_R \big ( \widetilde{E}_R (\mathbf {x}) \big ) \big \Vert _{\mathbf {X}}&= t^{-1} \cdot \big \Vert t \, \mathbf {x}- \big ( D_R(c_{\mathbf {x},R}) - \mathbf {x}_0' \big ) \big \Vert _{\mathbf {X}} \\&= t^{-1} \cdot \big \Vert (\mathbf {x}_0' + t \, \mathbf {x}) - D_R (c_{\mathbf {x},R}) \big \Vert _{\mathbf {X}} \le \frac{N}{t} \cdot R^{-(s^*+ \frac{1}{\ell })} \end{aligned}$$
for all
\(R \in \mathbb {N}\). By definition of the optimal exponent, this implies
, which is the desired contradiction. Hence,
\(\mathcal {G}_{N,\ell }^\circ = \emptyset \) for all
\(N,\ell \in \mathbb {N}\).
Step 3: (
Completing the proof). It is easy to see
; see Eq. (
1.2). We saw in the beginning of the proof that each
\(\mathcal {G}_{N,\ell }\) is closed, and in Step 2 that each
\(\mathcal {G}_{N,\ell }\) has empty interior (in
\(\mathcal {S}\)) and is hence nowhere dense in
\(\mathcal {S}\). By definition, this shows that
\(\bigcup _{N,\ell \in \mathbb {N}} \mathcal {G}_{N,\ell }\)— and hence also
—is of first category in
\(\mathcal {S}\).
Finally, we prove the existence of
\(\mathbf {x}\in \mathcal {S}\) satisfying Eq. (
G.1). Assume toward a contradiction that no such
\(\mathbf {x}\) exists. Then for each
\(\mathbf {x}\in \mathcal {S}\) there exist
\(n_\mathbf {x}, \ell _\mathbf {x}\in \mathbb {N}\) such that for every
\(R \ge n_{\mathbf {x}}\), we have
\({\Vert \mathbf {x}- D_R(E_R (\mathbf {x})) \Vert _{\mathbf {X}} < R^{-(s^*+ \frac{1}{\ell _\mathbf {x}})}}\). Thus, it is not hard to see that
$$\begin{aligned} {{\,\mathrm{dist}\,}}_{\mathbf {X}} (\mathbf {x}, M_R) \le \Vert \mathbf {x}- D_R (E_R (\mathbf {x})) \Vert _{\mathbf {X}} \le N_\mathbf {x}\cdot R^{-(s^*+ \frac{1}{\ell _{\mathbf {x}}})} \qquad \forall \, R \in \mathbb {N}, \end{aligned}$$
where we defined
\( N_\mathbf {x}:= 1 + \max \big \{ k^{s^*+ \frac{1}{\ell _\mathbf {x}}} \cdot \Vert \mathbf {x}- D_k (E_k (\mathbf {x})) \Vert _{\mathbf {X}} :1 \le k \le n_\mathbf {x}\big \} \).
Since
\(\mathbf {x}\in \mathcal {S}\) was arbitrary, this easily implies
\(\mathcal {S}= \bigcup _{N,\ell \in \mathbb {N}} \mathcal {G}_{N,\ell }\). Because
\(\mathcal {S}\subset \mathbf {X}\) is a closed set, and hence a complete metric space (equipped with the metric induced by
\(\Vert \cdot \Vert _{\mathbf {X}}\)), the Baire category theorem ( [
14, Theorem 5.9]) shows that there are certain
\(N,\ell \in \mathbb {N}\) such that
\(\mathcal {G}_{N,\ell }^\circ \ne \emptyset \), in contradiction to Step 2.
\(\square \)
As the second result in this appendix, we show that the preceding property does
not hold for general compact sets
\(\mathcal {S}\subset \mathbf {X}\), even if
\(\mathbf {X}= \mathcal {H}\) is a Hilbert space. In other words, some additional regularity assumption beyond compactness—like convexity— is necessary to ensure the property stated in Proposition
3.