\(L_2\)-norm sampling discretization and recovery of functions from RKHS with finite trace (Q2059812)

The authors study the reconstruction of complex-valued multivariate functions on a domain \(D \subset \mathbb R^d\) from values at the randomly sampled nodes \(\mathfrak{X}:=(\mathfrak {x}_1, \ldots, \mathfrak{x}_n) \in D^n\) via weighted least squares algorithms. The functions are modeled as elements from some reproducing kernel Hilbert space \(H(K)\), which is supposed to be compactly embedded into \(L_2(D,\rho_D)\). Its kernel is a positive definite Hermitian function \(K: D \times D \to \mathbb C\), which, in general, is only assumed to satisfy the finite trace condition \[ {\mathrm{tr}}(K) := \int_D K(\mathfrak{x, x}) d\rho_D(\mathfrak{x}) <\infty. \] Using a modification of the recovery operator \(\widetilde S_{\mathfrak X}^m\) from a prior work in [\textit{L. Kämmerer} et al., Constr. Approx. 54, No. 2, 295--352 (2021; Zbl 1484.41004); \textit{D. Krieg} and \textit{M. Ullrich}, Found. Comput. Math. 21, No. 4, 1141--1151 (2021; Zbl 1481.41014)], the authors are able to show (with constants) that the error \[ \sup_{\|f\|_{H(K)} \le 1} \left\|f - \widetilde S_{\mathfrak X}^m f\right\|_{L_2(D,\rho_D)} \] is bounded as \(\mathcal O(\sqrt{(\log n)/n})\) with high probability if \(\mathfrak X\) is drawn at random according to the product measure \((\rho_m(\mathfrak x) d\rho_D(\mathfrak x))^n\) with a prescribed density \(\rho_m\). In addition, the authors obtain similar estimates for the worst-case errors of the discretization of \(L_2\)-integral norms in \(H(K)\). The work complements previous results by the authors extending the class of kernels \(K\) and improving constants. The analysis was made possible by an improved spectral norm concentration inequality for infinite complex random matrices with independent rows (Theorem 1.1).