Choice of weights for the Laplacian Eigenmaps algorithm

Question

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?

Answer 1

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!