Discrete Laplace Operator

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

In mathematics, the discrete Laplace operator is an analogue of the continuous Laplace operator , defined as relations on a graph or a discrete grid . In the case of a finite-dimensional graph (having a finite number of vertices and edges), the discrete Laplace operator has a more general name: the Laplace matrix .

The concept of the discrete Laplace operator comes from such physical problems as the Ising model and loop quantum gravity , as well as from the study of dynamical systems . This operator is also used in computational mathematics as an analogue of the continuous Laplace operator. Known as the Laplace filter, it often finds an application in image processing . In addition, the operator is used in machine learning for clustering and semi-automatic learning on neighborhood graphs.

Definition

Image Processing

The discrete Laplace operator is often used in image processing, for example, in the problem of boundary extraction or in motion estimation applications. The discrete Laplacian is defined as the sum of the second derivatives and is calculated as the sum of the differences at the neighbors of the central pixel.

Image Processing Implementation

For one-dimensional, two-dimensional, and three-dimensional signals, the discrete Laplacian can be specified as a convolution with the following kernels:

1D Filter:

{\vec {D}}_{x}^{2}={\begin{bmatrix}1&-2&1\end{bmatrix}}

{\ displaystyle {\ vec {D}} _ {x} ^ {2} = {\ begin {bmatrix} 1 & -2 & 1 \ end {bmatrix}}}

{\vec {D}}_{x}^{2}={\begin{bmatrix}1&-2&1\end{bmatrix}}

2D Filter:

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

{\ displaystyle \ mathbf {D} _ {xy} ^ {2} = {\ begin {bmatrix} 0 & 1 & 0 \\ 1 & -4 & 1 \\ 0 & 1 & 0 \ end {bmatrix}}}

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

or with diagonals:

2D Filter:

\mathbf {D} _{xy}^{2}={\begin{bmatrix}1&1&1\\1&-8&1\\1&1&1\end{bmatrix}}

{\ displaystyle \ mathbf {D} _ {xy} ^ {2} = {\ begin {bmatrix} 1 & 1 & 1 \\ 1 & -8 & 1 \\ 1 & 1 & 1 \ end {bmatrix}}}

3D Filter:

\mathbf {D} _{xyz}^{3}

{\ displaystyle \ mathbf {D} _ {xyz} ^ {3}}

for the first plane = ${\begin{bmatrix}0&0&0\\0&1&0\\0&0&0\end{bmatrix}}$ ${\ displaystyle {\ begin {bmatrix} 0 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \ end {bmatrix}}}$ ; for the second ${\begin{bmatrix}0&1&0\\1&-6&1\\0&1&0\end{bmatrix}}$ ${\ displaystyle {\ begin {bmatrix} 0 & 1 & 0 \\ 1 & -6 & 1 \\ 0 & 1 & 0 \ end {bmatrix}}}$ ; for the third ${\begin{bmatrix}0&0&0\\0&1&0\\0&0&0\end{bmatrix}}$ ${\ displaystyle {\ begin {bmatrix} 0 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \ end {bmatrix}}}$

These kernels are derived using discrete partial derivatives.

On graphs

There are different definitions of a discrete Laplacian, differing in sign and scale factor (sometimes averages on adjacent vertices, sometimes just a sum; this does not matter for a regular graph ).

Let G = ( V , E ) be a graph with vertices V and edges E. Define a value function $\phi \colon V\to R$ ${\ displaystyle \ phi \ colon V \ to R}$ . Then the discrete Laplacian $\Delta$ ${\ displaystyle \ Delta}$ from $\phi$ ${\ displaystyle \ phi}$ will be determined as

(\Delta \phi )(v)=\sum _{w:d(w,v)=1}\left[\phi (w)-\phi (v)\right]

{\ displaystyle (\ Delta \ phi) (v) = \ sum _ {w: d (w, v) = 1} \ left [\ phi (w) - \ phi (v) \ right]}

where d ( w , v ) is a function of the distance between the vertices of the graph. This sum is at the nearest neighbors of the vertex v . For a graph with a finite number of vertices and edges, this definition coincides with the Laplace matrix, i.e. $\phi$ ${\ displaystyle \ phi}$ can be written as a column vector, $\Delta \phi$ ${\ displaystyle \ Delta \ phi}$ there is a column vector multiplied by the Laplace matrix, and $(\Delta \phi )(v)$ ${\ displaystyle (\ Delta \ phi) (v)}$ there is only a record of the vector product for v.

If the edges of the graph have weights, i.e., a weight function is specified $\gamma \colon E\to R$ ${\ displaystyle \ gamma \ colon E \ to R}$ , then the definition can be written as

(\Delta _{\gamma }\phi )(v)=\sum _{w:d(w,v)=1}\gamma _{wv}\left[\phi (w)-\phi (v)\right]

{\ displaystyle (\ Delta _ {\ gamma} \ phi) (v) = \ sum _ {w: d (w, v) = 1} \ gamma _ {wv} \ left [\ phi (w) - \ phi (v) \ right]}

Where $\gamma _{wv}$ ${\ displaystyle \ gamma _ {wv}}$ have rib weight $wv\in E$ ${\ displaystyle wv \ in E}$ .

Close lies the definition of the averaging operator :

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

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

Spectrum

The discrete Laplacian spectrum is of key interest; when it has a self-adjoint spectrum , it is valid . If a $\Delta =I-M$ ${\ displaystyle \ Delta = IM}$ , then the spectrum lies in the interval $[0,2]$ ${\ displaystyle [0,2]}$ (while the averaging operator has its spectral values in $[-1,1]$ ${\ displaystyle [-1,1]}$ ) and contains zero (for constant functions). Smallest nonzero eigenvalue $\lambda _{1}$ ${\ displaystyle \ lambda _ {1}}$ called the spectral gap . The concept of spectral radius, usually defined as the largest eigenvalue, is also usually distinguished.

The eigenvectors are independent of conventions (for regular graphs), and they are similar to the eigenvectors of the averaging operator (differing by addition), although the eigenvalues may vary depending on the agreement.

Theorems

If the graph is an infinite square lattice, then its definition of the Laplacian can be connected with the continuous Laplacian through the limit of the infinite lattice. For example, in the one-dimensional case we have

{\frac {\partial ^{2}F}{\partial x^{2}}}=\lim _{\epsilon \rightarrow 0}{\frac {[F(x+\epsilon )-F(x)]+[F(x-\epsilon )-F(x)]}{\epsilon ^{2}}}.

{\ displaystyle {\ frac {\ partial ^ {2} F} {\ 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 often used in computational mathematics and image processing . In the latter case, it is considered as a kind of digital filter , as a boundary filter , called the Laplace filter.

Discrete Schrödinger operator

Let be $P:V\rightarrow R$ ${\ displaystyle P: V \ rightarrow R}$ there is a potential given on the graph. Note that P can also be considered as a multiplicative operator acting diagonally on $\phi$ ${\ displaystyle \ phi}$ :

$(P\phi )(v)=P(v)\phi (v).$ ${\ displaystyle (P \ phi) (v) = P (v) \ phi (v).}$

Then $H=\Delta +P$ ${\ displaystyle H = \ Delta + P}$ there is a discrete Schrödinger operator , an analogue of the continuous Schrödinger operator .

If the number of edges of the vertex is uniformly bounded, then H is bounded and self-adjoint.

The spectral properties of its Hamiltonian can be obtained from Stone's theorem ; this is a consequence of the duality between partially ordered sets and Boolean algebra .

On regular gratings, the operator usually has a traveling wave and Anderson localization solutions, depending on the periodicity or randomness of the potential.

Discrete Green Function

The Green function of the discrete Schrödinger operator is given by the resolvent of the linear operator :

G(v,w;\lambda )=\langle \delta _{v}|{\frac {1}{H-\lambda }}|\delta _{w}\rangle

{\ displaystyle G (v, w; \ lambda) = \ langle \ delta _ {v} | {\ frac {1} {H- \ lambda}} | \ delta _ {w} \ rangle}

Where $\delta _{w}$ ${\ displaystyle \ delta _ {w}}$ understood as the Kronecker symbol on the graph: $\delta _{w}(v)=\delta _{wv}$ ${\ displaystyle \ delta _ {w} (v) = \ delta _ {wv}}$ , that is, it is 1 if v = w , and 0 otherwise.

For fixed $w\in V$ ${\ displaystyle w \ in V}$ and integrated $\lambda$ ${\ displaystyle \ lambda}$ , the Green's function is considered as a function of v , a unique solution to the equation

(H-\lambda )G(v,w;\lambda )=\delta _{w}(v).

{\ displaystyle (H- \ lambda) G (v, w; \ lambda) = \ delta _ {w} (v).}

Links

Definition and application of the spectral gap