# Laplacian-Beltrami approximation based on an empirical sample

Given a probability measure $\nu$ on a subset $M \subseteq \mathbb{R}^N$ we construct the corresponding operator

$$L^tf(x)=f(x)\int_{M} e^{-\frac{||x-y||^2}{4t}}d\nu(y)-\int_{M}f(y)e^{-\frac{||x-y||^2}{4t}}d\nu(y).$$

Let data points $x_1, \dots, x_n$ be sampled from $\nu$ on $M \subseteq \mathbb{R}^N$ and consider the following empirical approximation of $L^tf(x)$:

$$L^t_nf(x)=f(x)\frac{1}{n}\sum_{j=1}^ne^{-\frac{||x - x_j||^2}{4t}}-\frac{1}{n}\sum_{j=1}^nf(x_j)e^{-\frac{||x - x_j||^2}{4t}}.$$

How can I measure/quantify the quality of this empirical estimate in estimating the above operator $L^tf(x)$? Ex: Do I use Hoeffding's inequality? Wondering what would be a good way to do this?

• Could you please explain what the inner products $\langle x,x_j\rangle$ might mean when $x$ and $x_j$ are points on a manifold? Is this their inner product as vectors in $\mathbb{R}^N$ or is it something more intrinsic? (If it's the former, then using the language of manifolds is probably overkill here: it looks like you only need $M$ to be a measurable subset with finite measure w.r.t. $d\nu$. Smoothness and compactness appear to be irrelevant.) Also, why doesn't $L_n^t$ depend on $t$ at all? – whuber Aug 19 '12 at 17:58
• The inner-product is the vector dot product in $\mathbb{R^N}$ and thanks for noting- I have included $t$ in the definition of $L_{n}^{t}$. Yes, that's right $M$ is a measurable subset in $\mathbb{R^N}$ with a finite measure w.r.t $d\nu$. Also, the norm $||.||$ used in $L^tf(x)$ is the euclidean distance and not a geodesic distance, w.r.t any riemannian metric. Hence, true- the reference that generalizes the question to a manifold may be too restrictive. – hearse Aug 19 '12 at 18:43
• So, for any fixed $t$ and $x$ you are doing a MonteCarlo integration and you can get the usual error estimates in terms of the variance of what you are integrating or sample variance. Is it that you want to evaluate some operator norm of the error as you let $x$ vary? – Douglas Zare Aug 19 '12 at 18:54
• I am interested in the asymptotic convergence of $L_{n}^{t}f(x)$ to the continuous version of the operator as the sample size tends to infinity. Also, am interested in quantifying the accuracy of this approximation. Am not sure if the variance or standard error of a monte-carlo estimate of the integrals in the continuous operator would answer this question. What are your thoughts? To be more specific, a bound that quantifies the error, and also depends on $n$ would be the most useful for me. – hearse Aug 19 '12 at 19:11
• @VSPCP, two clarifications: Don't you mean the $x_i$'s are sampled from $\nu$ (assuming silently that $\nu$ is a probability measure)? And why are you replacing the norms in the operator by inner products in the empirical approximation $-$ I don't understand how to make sense of that. – NRH Aug 20 '12 at 7:25

This is only a hint on how to approach this problem, where I try to point out a number of questions that have to be clarified before a complete answer can be given. We assume that $\nu$ is a probability measure.

First, as an operator, $L^t$ needs a domain. We assume initially that the domain is the Hilbert space $H = L^2(M, \nu)$, but this will be taken up for revision at the end.

Lets also split the operator into two parts. Let $k_t(x,y) = e^{-||x-y||^2/4t}$. The first term in the operator can be written as $$f \mapsto \theta^t f$$ where $\theta^t = \int_M k_t(x,y) d\nu(y)$. Thus it is simply a scalar multiplication of the identity operator. The second term is $$f \mapsto I^t(f) := \int_M f(y) k_t(\cdot, y) d\nu(y),$$ which is an integral operator. Since $\nu$ is a probability measure and $|k_t(x,y)| \leq 1$ it follows that $I^t(f) \in H$ and $I^t$ is a bounded operator. As I understand the question, empirical versions of these two operators are formed by replacing the measure $\nu$ by an empirical measure $\varepsilon_n$ obtained by sampling $n$ points independently from $\nu$.

Focusing on the integral operator $I^t$ and its empirical approximation $I^t_n$ we would like to know if $I^t_n$ is a good approximation of $I^t$ and in which ways. If we fix $f \in H$ and $x \in M$ then $$I_n^t(f)(x) = \frac{1}{n} \sum_{i=1}^n f(x_i) k(x, x_i),$$ and since the random variables $f(x_i) k(x,x_i)$ for fixed $f$ and $x$ are i.i.d. with mean $I^t(f)(x)$ it follows from the usual law of large numbers that $$I^t_n(f)(x) \rightarrow I^t(f)(x) \quad \text{a.s.}$$ for $n \to \infty$. Since $f(x_i)^2 k(x_i, x)^2 \leq f(x_i)^2$ and $f \in H$ is square integrable, the random variables have finite variance and the standard CLT can be used to assess the accuracy.

However, we might want to say something about the approximation uniformly over $f$ and / or $x$. If we fix $f \in H$ does it hold that $$||I^t_n(f) - I^t(f)||_2 \rightarrow 0 \quad \text{a.s.}$$ for $n \to \infty$? Moreover, since $I_n^t$ and $I^t$ are bounded operators on $H$ we could also ask if $$||I^t_n - I^t|| \rightarrow 0 \quad \text{a.s.}$$ for $n \to \infty$ with $||\cdot||$ the operator norm on the Banach space of bounded operators?

In both cases above we ask for a law of large numbers to hold in a certain vector space $-$ the Hilbert space $H$ or the Banach space of bounded operators. A solid reference is Probability in Banach Spaces by Ledoux and Talagrand. Central limit results stating that $\sqrt{n}(I^t_n - I^t)$ or $\sqrt{n}(I^t_n(f) - I^t(f))$ are approximately Gaussian processes can also be obtained in some cases.

To obtain good results it might be necessary to restrict attention to a different domain than $H$. One possibility is a Sobolev space for nice choices of $M$ where the functions have some degree of smoothness.

• (+1) As usual, a nice, concise, informative answer. – cardinal Aug 20 '12 at 13:56