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$



Estimate for computing the $L^2$-norm of a function from its data
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](https://mathoverflow.net/questions/72891/error-estimates-for-multi-dimensional-riemann-sums).


