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

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 $$$$\label{mesh_norm} \zeta_n = \sup\limits_{\boldsymbol{x}\in\Omega}\inf\limits_{\boldsymbol{p}\in E_n}\|\boldsymbol{x}-\boldsymbol{p}\|_2$$$$

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$$

• A crosspost at MSE. Nov 15, 2020 at 8:21

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.

• Thanks for the answer. I think its the same for $m>1$ too. Nov 16, 2020 at 13:22
• From the answer of Gerry Myerson, the answer seem to be $\sim \zeta_nV(f^2)$ or is it $$\sim \zeta_n^mV(f^2)$$ Nov 20, 2020 at 16:34
• only $\zeta_n$ I guess. Nov 20, 2020 at 18:01