Discrete Laplace operator

From Wikipedia, the free encyclopedia

In mathematics, the discrete Laplace operator is an analog of the continuous Laplace operator, defined so that it has meaning on a graph or a discrete grid. The discrete Laplace operator occurs in physics problems such as the Ising model and loop quantum gravity, as well as in the study of discrete dynamical systems. It is also used in numerical analysis as a stand-in for the continuous Laplace operator, and in machine learning for clustering and semi-supervised learning on neighborhood graphs.

1 Definition
2 Spectrum
3 Theorems
4 Discrete Schrödinger operator
5 Discrete Green's function
6 References

[edit] Definition

There are various definitions of the discrete Laplacian, differing by sign and scale factor (sometimes one averages over the neighboring vertices, other times one just sums; this makes no difference for a regular graph).

Let G=(V,E) be a graph with vertices V and edges E. Let $\phi\colon V\to R$ be a ring-valued function of the vertices. Then, the discrete Laplacian $Δ$ acting on $φ$ is defined by

$(\Delta\phi)(v)=\sum_{w:d(w,v)=1}\left[\phi(w)-\phi(v)\right]\,$

where d(w,v) is the distance operator on the graph. Thus, this sum is over the nearest neighbors of the vertex v.

If the graph has weighted edges, that is, a weighting function $\gamma\colon E\to R$ is given, then the definition can be generalized to

$(\Delta_\gamma\phi)(v)=\sum_{w:d(w,v)=1}\gamma_{wv}\left[\phi(w)-\phi(v)\right]$

where $γ w v$ is the weight value on the edge $wv\in E$ .

Closely related is the averaging operator:

$(M\phi)(v)=\frac{1}{\deg v}\sum_{w:d(w,v)=1}\phi(w)$

[edit] Spectrum

The spectrum of the discrete Laplacian is of key interest; since it is a self-adjoint operator, it has a real spectrum. For the convention $Δ = I - M$ , the spectrum lies within $[0,2]$ (as the averaging operator has spectral values in $[ - 1,1]$ ) and contains 0 (for constant functions). The smallest non-zero eigenvalue is denoted $λ 1$ and is called the spectral gap. There is also the notion of the spectral radius, which has various definitions.

The eigenvectors don't depend on the convention above (for regular graphs), and are the same as for the averaging operator (as they differ by adding a multiple of the identity), though the eigenvalues differ according to the convention.

[edit] Theorems

If the graph is an infinite square lattice grid, then this definition of the Laplacian can be shown to correspond to the continuous Laplacian in the limit of an infinitely fine grid. Thus, for example, on a one-dimensional grid we have

$\frac{\partial^2F}{\partial x^2} = \lim_{\epsilon \rightarrow 0} \frac{[F(x+\epsilon)-F(x)]+[F(x-\epsilon)-F(x)]}{\epsilon^2}.$

This definition of the Laplacian is commonly used in numerical analysis and in image processing. In image processing, it is considered to be a type of digital filter, more specifically an edge filter, called the Laplace filter.

[edit] Discrete Schrödinger operator

Let $P:V\rightarrow\mathbb{R}$ be a potential function defined on the graph. Note that P can be considered to be a multiplicative operator acting diagonally on $φ$

(P φ)(v) = P (v)φ(v).

Then $H = Δ + P$ is the discrete Schrödinger operator, an analog of the continuous Schrödinger operator.

If the number of edges meeting at a vertex is uniformly bounded, and the potential is bounded, then H is bounded and self-adjoint.

The spectral properties of this Hamiltonian can be studied with Stone's theorem; this is a consequence of the duality between posets and Boolean algebras.

[edit] Discrete Green's function

The Green's function of the discrete Schrödinger operator is given in the resolvent formalism by

$G(v,w;\lambda)=\langle\delta_v| \frac{1}{H-\lambda}| \delta_w\rangle$

where $δ w$ is understood to be the Kronecker delta function on the graph: $δ w (v) = δ w v$ ; that is, it equals 1 if v=w and 0 otherwise.

For fixed $w\in V$ and $λ$ a complex number, the Green's function considered to be a function of v is the unique solution to

(H - λ) G (v, w;λ) = δ w (v).

[edit] References

This article needs additional citations for verification.
Please help improve this article by adding reliable references. Unsourced material may be challenged and removed. (December 2007)