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. 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. 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 ) {displaystyle G=(V,E)} be a graph with vertices V {displaystyle scriptstyle V} and edges E {displaystyle scriptstyle E} . Let ϕ : V → R {displaystyle phi colon V o R} be a function of the vertices taking values in a ring. Then, the discrete Laplacian Δ {displaystyle Delta } acting on ϕ {displaystyle phi } is defined by where d ( w , v ) {displaystyle 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, ϕ {displaystyle phi } can be written as a column vector; and so Δ ϕ {displaystyle Delta phi } is the product of the column vector and the Laplacian matrix, while ( Δ ϕ ) ( v ) {displaystyle (Delta phi )(v)} is just the v'th entry of the product vector. If the graph has weighted edges, that is, a weighting function γ : E → R {displaystyle gamma colon E o R} is given, then the definition can be generalized to where γ w v {displaystyle gamma _{wv}} is the weight value on the edge w v ∈ E {displaystyle wvin E} . 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 manifold triangle mesh, the Laplace-Beltrami operator of a scalar function u {displaystyle u} at a vertex i {displaystyle i} can be approximated as