A sharp bound for sampling widths in the uniform norm: kernel $D$-optimal designs and oversampling

Abstract

For every reproducing kernel Hilbert space ${\mathcal{H}}_K$ with bounded kernel $K$, we prove that the linear sampling widths $g_m^{\text{lin}}$ and Gelfand widths $c_n$ in the uniform norm satisfy $$g_m^{\text{lin}}(B_{{\mathcal{H}}_K}{)}_{\infty }\le \frac{m+1}{m-n+1}{c}_n(B_{{\mathcal{H}}_K}{)}_{\infty },m\ge n.$$ In a certain sense, the leading factor $(m+1)/(m-n+1)$ on the right-hand side is sharp. We transfer the problem into the selection of a maximal volume subset of kernel translates (kernel $D$-optimal design). Apart from basic linear algebra, our proof employs low rank approximation techniques and a version of the Eckart-Young-Mirsky theorem. The same argument gives corresponding bounds for the selection of a reduced basis in Hilbert spaces.