In his thesis (section 2.3.3) Belkin uses the heat equation to derive an approximation for $\mathcal{L}f$:

$$\mathcal{L}f(x_i)\approx \frac{1}{t}\Big(f(x_i)-\alpha \sum_{x_j, ||x_i-x_j||<\epsilon}e^{-\frac{||x_i-x_j||^2}{4t}}f(x_j)\Big)$$ where $$\alpha=\Big(\sum_{x_j, ||x_i-x_j||<\epsilon}e^{-\frac{||x_i-x_j||^2}{4t}}\Big)^{-1}$$.

However, I'm not sure how these considerations lead to this choice of weights for the weight matrix (which will be used to construct the Laplacian):

$$W_{ij} = \begin{cases} e^{-\frac{||x_i-x_j||^2}{4t}} & if\ ||x_i-x_j||<\epsilon \\ 0 & otherwise \end{cases}$$

A very vague idea of mine was that the factors $\alpha$ and $\frac{1}{t}$ don't change for a given $x_i$ so if one choses the weights like above the resulting discrete Laplacian would (let aside those two constants) converge to the continuous version.

Any ideas or tips what I'd have to read up to in order to get a better understanding?


Recall the definition he makes for the graph Laplacian earlier, $L = D -W $. Now consider the map in the RHS parentheses which I'll call $L^*$, $$ L^*f(x_i) := f(x_i) - \alpha \sum_{x_j, ||x_i-x_j||<\epsilon}e^{-\frac{||x_i-x_j||^2}{4t}}f(x_j).$$ The suggested weight matrix definition is natural because it lets us write $$ L^* := I - D^{-1}W. $$ Here's a reference to a related paper with some easy to read exposition. Hope this helps!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.