Optimal pointwise sampling for L^2 approximation

a universal constant. The sampling points are drawn according to some random distribution, the approximation is computed by a weighted least-squares method, and the error is assessed in expected

L^{2}

norm. This result improves on the results in [6,8] which require a sampling budget that is sub-optimal by a logarithmic factor, thanks to a sparsification strategy introduced in [17,18]. As a consequence, we obtain for any compact class

m a t h c a l K s u b s e t L^{2}

that the sampling number

h o_{C n}^{m r a n d} (m a t h c a l K)_{L^{2}}

in the randomized setting is dominated by the Kolmogorov

n

-width

d_{n} (m a t h c a l K)_{L^{2}}

. While our result shows the existence of a randomized sampling with such near-optimal properties, we discuss remaining issues concerning its generation by a computationally efficient algorithm.

Review text

The approximation of a function $u \in L^2(D,\mu)$, where $\mu$ is a measure on a set $D$, by an element $\tilde{u}$ of finite $n$ dimension subspace $V_n$ of $L^2(D,\mu)$, based on pointwise data of $u$ is studied. Therefore, to construct $\tilde{u}$ the evaluation of $u$ on a sample of $m$ points $X = \{x^1,\dots, x^m\} \in D^m$ is allowed. In addition, randomized sampling and reconstruction, in the sense that $X$ will be drawn according to a distribution $\sigma$ over $D^m$, so the error $u - \tilde{u}$ evaluated in some probabilistic sense is considered. The reconstruction map $R : D^m\times \mathbb{C}^m \to V_n$, is obtained through a weighted least-squares method. The computational cost for practically generating the sample $X$ by Kolmogorov $n$-widths is discussed.

Recommendations

Cites work

Cited in

(34)

This page was built for publication: Optimal pointwise sampling for $L^2$ approximation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2052170)