Discrete Laplace operator
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. Definitions. Graph Laplacians. 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 formula_1 be a graph with vertices formula_2 and edges formula_3. Let formula_4  be a function of the vertices taking values in a ring. Then, the discrete Laplacian formula_5 acting on formula_6 is defined by where formula_8 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, formula_9 can be written as a column vector; and so formula_10 is the product of the column vector and the Laplacian matrix, while formula_11 is just the "v"'th entry of the product  vector. If the graph has weighted edges, that is, a weighting function formula_12 is given, then the definition can be generalized to where formula_14 is the weight value on the edge formula_15. Closely related to the discrete Laplacian is the averaging operator: Mesh Laplacians. 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 manifold triangle mesh, the Laplace-Beltrami operator of a scalar function formula_17 at a vertex formula_18 can be approximated as where the sum is  over all adjacent vertices formula_20 of formula_18, formula_22 and formula_23 are the two angles opposite of the edge formula_24, and formula_25 is the "vertex area" of formula_18; that is, one third of the summed areas of triangles incident to formula_18. The above cotangent formula can be derived using many different methods among which are piecewise linear finite elements, finite volumes (see for a derivation), and discrete exterior calculus (see ). To facilitate computation, the Laplacian is encoded in a matrix formula_28 such that formula_29. Let formula_30 be the (sparse) "cotangent matrix" with entries formula_31 Where formula_32 denotes the neighborhood of formula_33 . And let formula_34 be the diagonal "mass matrix" formula_34 whose formula_18-th entry along the diagonal is the vertex area formula_37. Then formula_38 is the sought discretization of the Laplacian. A more general overview of mesh operators is given in. Finite differences. 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 where the grid size is "h" in both dimensions, so that the five-point stencil of  a point ("x", "y") in the grid is 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 no source at the boundary, that is, a no-flux boundary condition (aka, insulation, or homogeneous Neumann boundary condition). The control of the state variable at the boundary, as "f"("x", "y") given on the boundary of the grid (aka, Dirichlet boundary condition), is  rarely used for graph Laplacians, but is 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. Finite-element method. In this approach, the domain is discretized into smaller elements, often triangles or tetrahedra, but other elements such as rectangles or cuboids are possible. The solution space is then approximated using so called form-functions of a pre-defined degree. The differential equation containing the Laplace  operator is then transformed into a variational formulation, and a system of equations is constructed (linear or eigenvalue problems). The resulting matrices are usually very sparse and can be solved with iterative methods. 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. Since derivative filters are often sensitive to noise in an image, the Laplace operator is often preceded by a  smoothing filter (such as a Gaussian filter) in order to remove the noise before calculating the derivative. The smoothing filter and Laplace filter are often combined into a single filter. Implementation via operator discretization. For one-, two- and three-dimensional signals, the discrete Laplacian can be given as convolution with the following kernels: formula_43 corresponds to the (Five-point stencil) finite-difference formula seen previously. It is stable for very smoothly varying fields, but for equations with rapidly varying solutions more stable and isotropic form of the Laplacian operator is required, such as the nine-point stencil, which includes the  diagonals: Note that the "n"D 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 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. Regarding three -dimensional signals, it is shown that the Laplacian operator can be approximated by the two-parameter family of difference operators where Implementation via continuous reconstruction. A discrete signal, comprising images, can be viewed as a discrete representation of a continuous function formula_61, where the coordinate vector formula_62 and the value domain is real formula_63. Derivation operation is therefore directly applicable to the continuous function, formula_64. In particular any discrete image, with reasonable presumptions on the discretization process, e.g. assuming band limited functions, or wavelets expandable functions, etc. can be reconstructed by means of well-behaving interpolation functions underlying the reconstruction  formulation, where formula_66 are discrete representations of formula_64 on grid formula_68 and formula_69 are interpolation functions specific to the grid formula_68. On a uniform grid, such as images, and for bandlimited functions, interpolation functions are shift invariant amounting to formula_71 with formula_72 being an appropriately dilated sinc function defined in formula_73-dimensions i.e. formula_74. Other approximations of formula_75 on uniform grids, are appropriately dilated Gaussian functions in formula_73-dimensions. Accordingly the discrete Laplacian becomes a discrete version of the Laplacian of the continuous formula_61 which in turn is a convolution with the Laplacian of the interpolation function on the uniform  (image) grid formula_68. 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 formula_64 is represented via formula_81, in formula_73-dimensions, and are frequency aware by definition. A linear operator has not only a limited range in the formula_83 domain but also an effective range in the frequency domain (alternatively Gaussian scale space) which can be controlled explicitly via the variance of the Gaussian in a principled manner. The resulting filtering can be implemented by separable filters and decimation (signal processing)/pyramid (image  processing) representations for further computational efficiency in formula_73-dimensions. 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. Thereby, such non-linear operators e.g. Structure Tensor, and Generalized Structure Tensor which are used in pattern recognition for their total least-square optimality in orientation estimation, can be realized. Spectrum . The spectrum of the discrete Laplacian on an infinite grid is of key interest; since it is a self-adjoint operator, it has a real spectrum. For the convention formula_85 on formula_86, the spectrum lies within formula_87 (as the averaging operator has spectral values in formula_88). This may also be seen by applying the Fourier transform. Note that the discrete Laplacian on an infinite grid has purely absolutely continuous spectrum, and therefore, no eigenvalues or eigenfunctions. 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 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 heat equation. Suppose formula_90 describes a heat distribution across a graph, where formula_91 is the heat at vertex formula_92. According to Newton's law of cooling, the heat transferred from node formula_92 to node formula_94 is proportional to formula_95 if nodes formula_92 and  formula_94 are connected (if they are not connected, no heat is transferred). Then, for heat capacity formula_98, In matrix-vector notation, which gives Notice that this equation takes the same form as the heat equation, where the matrix −"L" is replacing the Laplacian operator formula_102; hence, the "graph Laplacian". To find a solution to this differential equation, apply standard techniques for solving a first-order matrix differential equation. That is, write formula_90 as a linear combination of eigenvectors formula_104 of "L" (so that formula_105) with time-dependent coefficients, formula_106 Plugging into the original expression (because "L" is a symmetric matrix , its unit-norm eigenvectors formula_104 are orthogonal): whose solution is As shown before, the eigenvalues formula_110 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 also shows that given formula_110 and the initial condition formula_112, the solution at any time "t" can be found. To find formula_112 for each formula_92 in terms of the overall initial condition formula_115, simply project formula_115 onto the unit-norm eigenvectors formula_104; This approach has been applied to quantitative heat transfer modelling on unstructured grids. In the case of  undirected graphs, this works because formula_119 is symmetric, and by the spectral theorem, its eigenvectors are all orthogonal. So the projection onto the eigenvectors of formula_119 is simply an orthogonal coordinate transformation of the initial condition to a set of coordinates which decay exponentially and independently of each other. Equilibrium behavior. To understand formula_121, the only terms formula_122 that remain are those where formula_123, since In other words, the equilibrium state of the system is determined completely by the kernel of formula_119. Since by definition, formula_126, the vector formula_127 of all ones is in the kernel. If there are formula_98  disjoint connected components in the graph, then this vector of all ones can be split into the sum of formula_98 independent formula_130 eigenvectors of ones and zeros, where each connected component corresponds to an eigenvector with ones at the elements in the connected component and zeros elsewhere. The consequence of this is that for a given initial condition formula_131 for a graph with formula_132 vertices where For each element formula_135 of formula_90, i.e. for each vertex formula_94 in the graph, it can be rewritten as In other words, at steady state, the value of formula_90 converges to the same value  at each of the vertices of the graph, which is the average of the initial values at all of the vertices. Since this is the solution to the heat diffusion equation, this makes perfect sense intuitively. We expect that neighboring elements in the graph will exchange energy until that energy is spread out evenly throughout all of the elements that are connected to each other. Example of the operator on a grid. This section shows an example of a function formula_90 diffusing over time through a graph. The graph in this example is constructed on a 2D discrete grid, with  points on the grid connected to their eight neighbors. Three initial points are specified to have a positive value, while the rest of the values in the grid are zero. 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. It shows the process of specifying initial conditions, projecting these initial conditions onto the eigenvalues of the Laplacian Matrix, and simulating the exponential decay of these projected initial conditions. N = 20; % The number of pixels along  a dimension of the image A = zeros(N, N); % The image Adj = zeros(N * N, N * N); % The adjacency matrix % Use 8 neighbors, and fill in the adjacency matrix dx = [- 1, 0, 1, - 1, 1, - 1, 0, 1]; dy = [- 1, - 1, - 1, 0, 0, 1, 1, 1]; for x = 1:N end % BELOW IS THE KEY CODE THAT COMPUTES THE SOLUTION TO THE DIFFERENTIAL EQUATION Deg = diag(sum(Adj, 2)); % Compute the degree matrix L = Deg - Adj; % Compute the laplacian matrix in terms of the degree and adjacency matrices [V, D] = eig(L); % Compute the eigenvalues/vectors  of the laplacian matrix D = diag(D); % Initial condition (place a few large positive values around and % make everything else zero) C0 = zeros(N, N); C0(2:5, 2:5) = 5; C0(10:15, 10:15) = 10; C0(2:5, 8:13) = 7; C0 = C0(:); C0V = V'*C0; % Transform the initial condition into the coordinate system % of the eigenvectors for t = 0:0.05:5 end Discrete Schrödinger operator. Let formula_141 be a potential function defined on the graph. Note that "P" can be considered to be a multiplicative operator acting diagonally on formula_6 Then formula_144 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. The Green's function of the discrete Schrödinger operator is given in the resolvent formalism by where formula_146 is understood to be the Kronecker delta  function on the graph: formula_147; that is, it equals "1" if "v"="w" and "0" otherwise. For fixed formula_148 and formula_149 a complex number, the Green's function considered to be a function of "v" is the unique solution to 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, 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: 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 E they range from 58 to 270, and have been observed as early as 1968.