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.

Contents

[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 γwv 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 Δ = IM, 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) = δwv; 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

Languages