Estimate for computing the $L^2$-norm of a function from its data

Question

Let $f:\mathbb{T}^m \to \mathbb{R}$ is a function of bounded variation(BV). Let $D=\{\boldsymbol{p}_i,i=1,2,3\ldots\}$ be a countable dense subset of $(0,1)^m$. Let $E_n, n = 1,2,3\ldots$ be a sequence of sets defined as $E_n = \{\boldsymbol{p_i}/\boldsymbol{p_i}\in D, i = 1,2,3\ldots n\}$.

Define the mesh norm of the data points set $E_n$ over the domain $\Omega = (0,1)^m$ as \begin{equation}\label{mesh_norm} \zeta_n = \sup\limits_{\boldsymbol{x}\in\Omega}\inf\limits_{\boldsymbol{p}\in E_n}\|\boldsymbol{x}-\boldsymbol{p}\|_2 \end{equation}

As $D$ is dense we know that $$\lim\limits_{n\to\infty}\zeta_n = 0$$

Also as $f$ is BV, we have $$ \lim\limits_{n\to\infty}\left(\|f\|^2_{L^2(\mathbb{T}^m)}-\frac{1}{n}\sum\limits_{i=1}^n\left(f(\boldsymbol{p_i})\right)^2\right) = 0$$

Question

I am looking for an estimate between the above two expressions for sufficiently large $n$. That is how does LHS of the above expression decay as $\zeta_n$ decays with $n$.

Something like, for sufficiently large $n$, $$\left(\|f\|^2_{L^2(\mathbb{T}^m)}-\frac{1}{n}\sum\limits_{i=1}^n\left(f(\boldsymbol{p_i})\right)^2\right) \le h(\zeta_n)$$

I want to find such a best possible $h$.

PS: Note $h$ should be such that $\lim\limits_{n\to\infty}h(\zeta_n) = 0$

Answer 1

Assume $m=1$ and $f$ is of bounded variation on $[0,1]$. The problem is to estimate $$ \|f\|^2_{2}-\frac{1}{n}\sum\limits_{i=1}^n\left(f({p_i})\right)^2=\int_{0}^{1}f^{2}(t)dt -\frac{1}{n}\sum\limits_{i=1}^n f^{2}({p_i}), $$ as the number of points grows. Setting $g=f^{2}$, which is also of bounded variation, the question is about the rate of convergence of the Riemann sums of $g$ to its integral.

For a regular mesh $\{1/n,2/n,\ldots,1\}$, one has $$ \left|\int_{0}^{1}g(t)dt-\frac1n\sum_{k=1}^{n}g(k/n)\right|\leq\int_{0}^{1/n}\sum_{k=1}^{n} |g(t+(k-1)/n)-g(k/n)|dt\leq\frac{V(g)}{n}, $$ where $V(g)$ denotes the variation of $g$.

More generally, consider a tagged mesh $T=\{\sigma_{k},[s_{k-1},s_{k}],~k=1,\ldots,n\}$ of $[0,1]$ such that $T\ll\delta$ meaning that $\max_{k}(s_{k}-s_{k-1})<\delta$, and set $$ g(T)=\sum_{k=1}^{n}g(\sigma_{k})(s_{k}-s_{k-1}),\qquad \psi_{\delta}(g)=\sup _{T \ll \delta}\left|g(T)-\int_{0}^{1} g(t) dt\right| $$ Then, the following holds, for any function $g$, $$ \sup _{\delta>0} \frac{\psi_{\delta}(g)}{\delta} \leq V(g) \leq 2\liminf _{\delta \to 0}\frac{\psi_{\delta}(g)}{\delta}, $$ see J.A. Alewine, Rates of uniform convergence for Riemann integrals. Missouri J. Math. Sci. 26 (2014), 48-56.

Hence, for a function of bounded variation, its Riemann sums converge to its integral at a rate of $O(\delta)$, and that rate cannot be improved.

For several variables, you may have a look here.