Diskret Laplace-operatör

För den diskreta motsvarigheten till Laplace-transformen, se Z-transform .

Inom matematiken är den diskreta Laplace-operatorn analog med den kontinuerliga Laplace-operatorn , definierad som ett samband på en graf eller ett diskret rutnät . I fallet med en finitdimensionell graf (som har ett ändligt antal hörn och kanter) har den diskreta Laplace-operatorn ett mer allmänt namn: Laplace-matrisen .

Föreställningen om en diskret Laplace-operatör kommer från sådana fysiska problem som Ising-modellen och slingkvantgravitationen , och från studiet av dynamiska system . Denna operator används också i beräkningsmatematik som en analog till den kontinuerliga Laplace-operatorn. Känt som Laplace-filtret, finner det ofta tillämpning i bildbehandling . Dessutom används operatören i maskininlärning för klustring och halvautomatiserad inlärning på grannskapsgrafer.

Definition

Bildbehandling

Den diskreta Laplace-operatorn används ofta i bildbehandling, såsom kantdetektering eller rörelseuppskattning. Den diskreta Laplacian definieras som summan av andraderivatorna och beräknas som summan av dropparna på den centrala pixelns grannar.

Implementering i bildbehandling

För endimensionella, tvådimensionella och tredimensionella signaler kan den diskreta Laplacian specificeras som en faltning med följande kärnor:

Filter 1D:

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

Filter 2D:

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

eller med diagonaler:

Filter 2D:

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

3D-filter:

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

för det första planet = ; för den andra ; för den tredje ${\begin{bmatrix}0&0&0\\0&1&0\\0&0&0\end{bmatrix}}$ ${\begin{bmatrix}0&1&0\\1&-6&1\\0&1&0\end{bmatrix}}$ ${\begin{bmatrix}0&0&0\\0&1&0\\0&0&0\end{bmatrix}}$

Dessa kärnor härleds med användning av diskreta partiella derivator.

På grafer

Det finns olika definitioner av den diskreta laplacianen, som skiljer sig åt i tecken och skalfaktor (ibland medelvärden vid angränsande hörn, ibland bara summan; detta är irrelevant för en vanlig graf ).

Låt G =( V , E ) vara en graf med hörn V och kanter E . Vi definierar en funktion av värden från toppen av grafen till ringen . Då kommer den diskreta Laplacian av att definieras som $\phi \colon V\to R$ $R$ $\Delta$ $\phi$

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

där d ( w , v ) är avståndsfunktionen mellan grafens hörn. Denna summa är på de närmaste grannarna till v . Topparna i den slutliga grafen kan numreras, sedan kan mappningen skrivas som en kolumnvektor vars element är värdena för mappningen: . Ovanstående definition av Laplacian kan också skrivas om i vektorform med hjälp av Laplace-matrisen : $\phi$ $\phi _{v}=\phi (v)$ $L$

{\displaystyle (\Delta \phi )(v)=(L\cdot \phi )_{v))

Om grafkanterna har vikter, det vill säga viktfunktionen ges , så kan definitionen skrivas som $\gamma \colon E\to R$

(\Delta _{\gamma}\phi )(v)=\summa _{w:d(w,v)=1}\gamma _{wv}\left[\phi (w)-\phi (v)\höger]

var är kantens vikt . $\gamma _{wv}$ $wv\in E$

Nära ligger definitionen av den genomsnittliga operatorn :

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

Spektrum

Spektrumet för den diskreta Laplacian är av nyckelintresse; när det har ett självtillgränsande spektrum är det verkligt . Om , så ligger spektrumet i segmentet (medan medelvärdesoperatorn har sina spektrala värden i ) och innehåller noll (för konstanta funktioner). Det minsta egenvärdet som inte är noll kallas spektralgapet . Vanligtvis urskiljs också begreppet spektralradien, vilket vanligtvis definieras som det största egenvärdet. $\Delta =IM$ $[0,2]$ $[-1,1]$ $\lambda _{1}$

Egenvektorer är villkorsoberoende (för vanliga grafer), och de liknar egenvektorerna för en medelvärdesoperator (olika dessutom), även om egenvärdena kan skilja sig åt enligt konvention.

Satser

Om en graf är ett oändligt kvadratiskt gitter, kan dess definition av Laplacian relateras till det kontinuerliga Laplacian genom gränsen för det oändliga gittret. Till exempel i det endimensionella fallet vi har

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

Denna definition av Laplacian används ofta i beräkningsmatematik och bildbehandling . I det senare fallet betraktas det som ett slags digitalt filter , som ett gränsfilter , som kallas Laplace-filtret.

Diskret Schrödinger-operatör

Låt det finnas en potential på grafen. Observera att P också kan betraktas som en multiplikativ operator som verkar diagonalt på : $P:V\rightarrow R$ $\phi$

$(P\phi )(v)=P(v)\phi (v).$

Sedan finns det den diskreta Schrödinger-operatören , analog med den kontinuerliga Schrödinger-operatören . $H=\Delta+P$

Om antalet kanter på en vertex är likformigt avgränsat, är H avgränsad och självadjoint.

De spektrala egenskaperna hos dess Hamiltonian kan härledas från Stones teorem ; detta är en konsekvens av dualiteten mellan partiellt ordnade mängder och boolesk algebra .

På vanliga gitter har operatören vanligtvis både en vandringsvåg och Anderson-lokaliseringslösningar , beroende på potentialens periodicitet eller slumpmässighet.

Diskret gröns funktion

Greenens funktion för den diskreta Schrödinger-operatorn ges av upplösningen av den linjära operatorn :

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

där förstås som Kronecker-symbolen på grafen: d.v.s. den är lika med 1 om v = w och 0 annars. ${\displaystyle \delta _{w))$ ${\displaystyle \delta _{w}(v)=\delta _{wv))$

För fix och komplex betraktas den gröna funktionen som en funktion av v , en unik lösning på ekvationen $w\in V$ $\lambda$

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

Se även

Laplace matris

Länkar

Definition och tillämpning av spektralgapet