Discrete Laplace operator


Discrete Laplace operator
For the discrete equivalent of the Laplace transform, see Z-transform.

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. For the case of a finite-dimensional graph (having a finite number of edges and vertices), the discrete Laplace operator is more commonly called the Laplacian matrix.

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. Common applications include image processing, where it is known as the Laplace filter, and in machine learning for clustering and semi-supervised learning on neighborhood graphs.

Contents

Definition

On Graphs

There are various definitions of the discrete Laplacian for graphs, 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). The traditional definition of the graph Laplacian, given below, corresponds to the negative continuous Laplacian on a domain with a free boundary.

Let G = (V,E) be a graph with vertices \scriptstyle V and edges \scriptstyle 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 graph distance between vertices w and v. Thus, this sum is over the nearest neighbors of the vertex v. For a graph with a finite number of edges and vertices, this definition is identical to that of the Laplacian matrix. That is, φ can be written as a column vector; and so Δϕ is the product of the column vector and the Laplacian matrix, while (Δϕ)(v) is just the v'th entry of the product vector.

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 to the discrete Laplacian is the averaging operator:

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

Approximations of the continuous Laplacian

Approximations of the Laplacian, obtained by the finite difference method or by the finite element method can also be called Discrete Laplacians. For example, the Laplacian in two dimensions can be approximated using the five-point stencil finite difference method, resulting in

 \Delta f(x,y) \approx \frac{f(x-h,y) + f(x+h,y) + f(x,y-h) + f(x,y+h) - 4f(x,y)}{h^2}, \,

where the grid size is h in both dimensions, so that the five point stencil of a point (xy) in the grid is

\{(x-h, y), (x, y), (x+h, y), (x, y-h), (x, y+h)\}. \,

If the grid size h=1, the result is the negative discrete Laplacian on the graph, which is the square lattice grid. There are no constraints here on the values of the function f(x,y) on the boundary of the lattice grid, thus this is the case of the homogeneous Neumann boundary condition, i.e., free boundary. Other types of boundary conditions, e.g., the homogeneous Dirichlet boundary condition, where f(x,y)=0 on the boundary of the grid, are rarely used for graph Laplacians, but are common in other applications.

Multidimensional discrete Laplacians on rectangular cuboid regular grids have very special properties, e.g., they are Kronecker sums of one-dimensional discrete Laplacians, see Kronecker sum of discrete Laplacians, in which case all its eigenvalues and eigenvectors can be explicitly calculated.

Image Processing

Discrete Laplace operator is often used in image processing e.g. in edge detection and motion estimation applications. The discrete Laplacian is defined as the sum of the second derivatives Laplace operator#Coordinate expressions and calculated as sum of differences over the nearest neighbours of the central pixel.

Implementation in Image Processing

For one, two and three dimensional signals, the discrete laplacian can be given as convolution with the following kernels:

1D-Filter: \vec{D}^2_x=\begin{bmatrix}1 & -2 & 1\end{bmatrix}
2D-Filter: \mathbf{D}^2_{xy}=\begin{bmatrix}0 & 1 & 0\\1 & -4 & 1\\0 & 1 & 0\end{bmatrix}

or, including the diagonals:

2D-Filter: \mathbf{D}^2_{xy}=\begin{bmatrix}1 & 1 & 1\\1 & -8 & 1\\1 & 1 & 1\end{bmatrix}
3D-Filter: \mathbf{D}^3_{xyz} is given by: first plane = \begin{bmatrix}0 & 0 & 0\\0 & 1 & 0\\0 & 0 & 0\end{bmatrix} ; second plane = \begin{bmatrix}0 & 1 & 0\\1 & -6 & 1\\0 & 1 & 0\end{bmatrix} ; third plane = \begin{bmatrix}0 & 0 & 0\\0 & 1 & 0\\0 & 0 & 0\end{bmatrix}

These kernels are deduced by using discrete differential quotients.

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, commonly taken as the largest eigenvalue.

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.

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.

Discrete Schrödinger operator

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

(P\phi)(v)=P(v)\phi(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.

On regular lattices, the operator typically has both traveling-wave as well as Anderson localization solutions, depending on whether the potential is periodic or random.

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-\lambda)G(v,w;\lambda)=\delta_w(v).\,

ADE classification

Certain equations involving the discrete Laplacian only have solutions on the simply-laced Dynkin diagrams (all edges multiplicity 1), and are an example of the ADE classification. Specifically, the only positive solutions to the homogeneous equation:

Δϕ = ϕ,

in words,

"Twice any label is the sum of the labels on adjacent vertices,"

are on the extended (affine) ADE Dynkin diagrams, of which there are 2 infinite families (A and D) and 3 exceptions (E). The resulting numbering is unique up to scale, and if the smallest value is set at 1, the other numbers are integers, ranging up to 6.

The ordinary ADE graphs are the only graphs that admit a positive labeling with the following property:

Twice any label minus two is the sum of the labels on adjacent vertices.

In terms of the Laplacian, the positive solutions to the inhomogeneous equation:

Δϕ = ϕ − 2.

The resulting numbering is unique (scale is specified by the "2"), and consists of integers; for E8 they range from 58 to 270, and have been observed as early as (Bourbaki 1968).

See also

References

  • Bourbaki, Nicolas (1968), "Chapters 4–6", Groupes et algebres de Lie, Paris: Hermann 

External links


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Laplace operator — This article is about the mathematical operator. For the Laplace probability distribution, see Laplace distribution. For graph theoretical notion, see Laplacian matrix. Del Squared redirects here. For other uses, see Del Squared (disambiguation) …   Wikipedia

  • Discrete Poisson equation — In mathematics, the discrete Poisson equation is the finite difference analog of the Poisson equation. In it, the discrete Laplace operator takes the place of the Laplace operator. The discrete Poisson equation is frequently used in numerical… …   Wikipedia

  • Convolution — For the usage in formal language theory, see Convolution (computer science). Convolution of two square pulses: the resulting waveform is a triangular pulse. One of the functions (in this case g) is first reflected about τ = 0 and then offset by t …   Wikipedia

  • List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia

  • Eigenvalues and eigenvectors — For more specific information regarding the eigenvalues and eigenvectors of matrices, see Eigendecomposition of a matrix. In this shear mapping the red arrow changes direction but the blue arrow does not. Therefore the blue arrow is an… …   Wikipedia

  • List of mathematics articles (D) — NOTOC D D distribution D module D D Agostino s K squared test D Alembert Euler condition D Alembert operator D Alembert s formula D Alembert s paradox D Alembert s principle Dagger category Dagger compact category Dagger symmetric monoidal… …   Wikipedia

  • Laplacian matrix — In the mathematical field of graph theory the Laplacian matrix, sometimes called admittance matrix or Kirchhoff matrix, is a matrix representation of a graph. Together with Kirchhoff s theorem it can be used to calculate the number of spanning… …   Wikipedia

  • Fourier series — Fourier transforms Continuous Fourier transform Fourier series Discrete Fourier transform Discrete time Fourier transform Related transforms …   Wikipedia

  • List of mathematics articles (L) — NOTOC L L (complexity) L BFGS L² cohomology L function L game L notation L system L theory L Analyse des Infiniment Petits pour l Intelligence des Lignes Courbes L Hôpital s rule L(R) La Géométrie Labeled graph Labelled enumeration theorem Lack… …   Wikipedia

  • Blob detection — Feature detection Output of a typical corner detection algorithm …   Wikipedia