Discrete Laplace operator
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.
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).
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.
Closely related to the discrete Laplacian is the averaging operator: In addition to considering the connectivity of nodes and edges in a graph, mesh Laplace operators take into account the geometry of a surface (e.g. the angles at the nodes).
For a two-dimensional manifold triangle mesh, the Laplace-Beltrami operator of a scalar function
The solution space is then approximated using so called form-functions of a pre-defined degree.
Discrete Laplace operator is often used in image processing e.g. in edge detection and motion estimation applications.
[5] For one-, two- and three-dimensional signals, the discrete Laplacian can be given as convolution with the following kernels:
It is stable for very smoothly varying fields, but for equations with rapidly varying solutions a more stable and isotropic form of the Laplacian operator is required,[6] such as the nine-point stencil, which includes the diagonals: Note that the nD version, which is based on the graph generalization of the Laplacian, assumes all neighbors to be at an equal distance, and hence leads to the following 2D filter with diagonals included, rather than the version above: These kernels are deduced by using discrete differential quotients.
It can be shown[8][9] that the following discrete approximation of the two-dimensional Laplacian operator as a convex combination of difference operators for γ ∈ [0, 1] is compatible with discrete scale-space properties, where specifically the value γ = 1/3 gives the best approximation of rotational symmetry.
which in turn is a convolution with the Laplacian of the interpolation function on the uniform (image) grid
An advantage of using Gaussians as interpolation functions is that they yield linear operators, including Laplacians, that are free from rotational artifacts of the coordinate frame in which
In other words, the discrete Laplacian filter of any size can be generated conveniently as the sampled Laplacian of Gaussian with spatial size befitting the needs of a particular application as controlled by its variance.
Monomials which are non-linear operators can also be implemented using a similar reconstruction and approximation approach provided that the signal is sufficiently over-sampled.
Note that the discrete Laplacian on an infinite grid has purely absolutely continuous spectrum, and therefore, no eigenvalues or eigenfunctions.
Thus, for example, on a one-dimensional grid we have This definition of the Laplacian is commonly used in numerical analysis and in image processing.
Plugging into the original expression (because L is a symmetric matrix, its unit-norm eigenvectors
of L are non-negative, showing that the solution to the diffusion equation approaches an equilibrium, because it only exponentially decays or remains constant.
; This approach has been applied to quantitative heat transfer modelling on unstructured grids.
, since In other words, the equilibrium state of the system is determined completely by the kernel of
disjoint connected components in the graph, then this vector of all ones can be split into the sum of
Since this is the solution to the heat diffusion equation, this makes perfect sense intuitively.
Over time, the exponential decay acts to distribute the values at these points evenly throughout the entire grid.
The complete Matlab source code that was used to generate this animation is provided below.
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.
The Green's function of the discrete Schrödinger operator is given in the resolvent formalism by where
a complex number, the Green's function considered to be a function of v is the unique solution to 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, are on the extended (affine) ADE Dynkin diagrams, of which there are 2 infinite families (A and D) and 3 exceptions (E).
The ordinary ADE graphs are the only graphs that admit a positive labeling with the following property: In terms of the Laplacian, the positive solutions to the inhomogeneous equation: 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 1968.
