Faltung (Mathematik)

Grundidee und Definition

Die Faltung (Konvolution) ist ein Operator der Analysis, der aus zwei Funktionen f und g eine neue Funktion f*g bildet. Anschaulich wird für jeden Zeitpunkt t gewichtet, wie stark frühere Werte g(t−τ) zum Ergebnis beitragen; die Gewichtung liefert f(τ). So kann man beispielsweise gleitende Durchschnitte bilden. Faltungen modellieren viele physikalische Vorgänge. Die Kreuzkorrelation entspricht der komplex konjugierten Faltung mit der gespiegelten Funktion \overline{f(-τ)}; bei Convolutional Neural Networks wird deshalb häufig die leichter implementierbare Kreuzkorrelation als „Faltung“ bezeichnet.

Für f,g: ℝⁿ → ℂ lautet die Definition (fg)(x) = ∫_{ℝⁿ} f(τ)g(x−τ) dτ. Das Integral muss für fast alle x wohldefiniert sein. Für zwei integrierbare Funktionen f,g ∈ L¹(ℝⁿ) ist dies nach dem Satz von Fubini immer gewährleistet. Bei periodischen Funktionen der Periode T>0 gilt (fg)(t) = (1/T)∫ₐᵃ⁺ᵀ f(τ)g(t−τ) dτ; das Ergebnis ist wieder T-periodisch. Auf beschränkten Definitionsbereichen setzt man Funktionen meist außerhalb des Bereichs durch 0 oder periodisch fort. Eine Nullfortsetzung ist etwa bei stetigen Funktionen mit kompaktem Träger möglich, die dadurch zu L¹(ℝⁿ)-Funktionen werden.

Glättung durch Faltung

Eine Faltung mit einem Glättungskern j heißt Glättung: F = j*f ist glatt, also unendlich oft stetig differenzierbar. Ihr Träger ist nur wenig größer als der von f, und ihre Abweichung von f in der L¹-Norm kann vorgegeben klein sein.

Ein d-dimensionaler Glättungskern (Mollifier) ist eine unendlich oft stetig differenzierbare, nichtnegative Funktion j: ℝᵈ → ℝ, deren Träger in der abgeschlossenen Einheitskugel B(0,1) liegt und deren Integral 1 ist. Ein Beispiel ist j(x) = c·exp(−1/(1−|x|²)) für |x|<1, sonst 0, wobei c so normiert wird, dass ∫_{ℝᵈ} j(x) dx = 1. Mit jₑ(x) = (1/eᵈ)·j(x/e) für e∈(0,1] erhält man Kerne mit jₑ(x)=0 für |x|>e. Für lokal integrierbare Funktionen und sogar Distributionen ist jₑf glatt; für e→0 konvergiert jₑf in der Topologie der Distributionen gegen f.

Beispiel: Die Rechteckfunktion f(x)=1 für −1≤x≤2 und 0 sonst wird durch f*j₁⁄₂ zu einer glatten Funktion mit kompaktem Träger. Ihre L¹-Abweichung erfüllt ∫_{ℝ}|F(t)−f(t)|dt<0,4. Für e<1/2 wird die Approximation in der Integralnorm noch genauer.

Wichtige Rechenregeln

Für L¹(ℝⁿ)-Funktionen ist die Faltung kommutativ, assoziativ und distributiv: fg=gf, f*(gh)=(fg)h, f(g+h)=fg+fh. Außerdem gilt für komplexe Zahlen a: a(f*g)=(af)g=f(ag). Die Struktur besitzt jedoch innerhalb von L¹(ℝⁿ) kein neutrales Element.

Die Young’sche Ungleichung besagt: Falls f∈L¹(ℝⁿ), g∈Lᵖ(ℝⁿ) und 1≤p≤∞, dann liegt fg ebenfalls in Lᵖ(ℝⁿ) und ‖fg‖{Lᵖ} ≤ ‖f‖{L¹}‖g‖{Lᵖ}. Verallgemeinert gilt ‖f*g‖{Lʳ} ≤ ‖f‖{Lᵖ}‖g‖{Lᑫ}, wenn 1/p+1/q=1+1/r und p,q,r≥1. Für duale Exponenten 1/p+1/q=1 ist f*g beschränkt und stetig; falls p≠∞≠q, verschwindet die Faltung im Unendlichen.

Ableitungen können auf einen der Faktoren übertragen werden: D(fg)=(Df)g=fDg. Insbesondere ist fΘ(x)=∫{−∞}ˣ f(t)dt eine Stammfunktion, wobei Θ die Sprungfunktion ist. Für integrierbare f und g gilt außerdem ∫{ℝⁿ}(f*g)(x)dx = (∫{ℝⁿ}f(x)dx)(∫{ℝⁿ}g(x)dx).

Das Faltungstheorem verbindet Faltung und Fouriertransformation: Bei der angegebenen Normierung gilt ℱ(f*g)=(2π)ⁿ⁄² ℱ(f)·ℱ(g). Umgekehrt ist ℱ(f)*ℱ(g)=(2π)ⁿ⁄²ℱ(f·g). Dadurch wird eine Faltung im Frequenzbereich zu einer punktweisen Multiplikation.

Diskrete Faltung und typische Beispiele

In der digitalen Signal- und Bildverarbeitung ersetzt bei diskreten Funktionen f,g: D⊆ℤ → ℂ eine Summe das Integral: (f*g)(n)=∑_{k∈D} f(k)g(n−k). Bei endlichem Definitionsbereich werden die Folgen meist mit Nullen ergänzt. Als Vektoren aufgefasst, lässt sich die Faltung durch eine Toeplitz-Matrix berechnen; bei periodischer statt nullweiser Ergänzung entsteht die zyklische Faltung. Effizient berechnet man diskrete Faltungen mit der Schnellen Faltung auf Grundlage der FFT.

Das Produkt zweier Polynome ist die diskrete Faltung ihrer mit Nullen fortgesetzten Koeffizientenfolgen. Allgemeiner entsteht für Folgen auf ℤ das Cauchy-Produkt (a*b)ₙ=∑ₖ₌₀ⁿaₖbₙ₋ₖ, wenn aₙ=bₙ=0 für n<0.

Ein wichtiges Wahrscheinlichkeitsbeispiel: Die Faltung zweier Normalverteilungen mit Mittelwerten μ₁, μ₂ und Standardabweichungen σ₁, σ₂ ist wieder normalverteilt, mit μ=μ₁+μ₂ und σ=√(σ₁²+σ₂²). Daher ergibt sich für L₁=(1±0,03) m und L₂=(2±0,04) m die Gesamtlänge L₃=(3±0,05) m.

Erweiterungen auf Distributionen und Gruppen

Die Faltung lässt sich auf Distributionen erweitern. Für eine Distribution T und eine Testfunktion φ∈C_c^∞(ℝⁿ) ist (Tφ)(x)=T(φ(x−·)). Für zwei Distributionen ist ihre Faltung definiert, wenn eine von ihnen kompakten Träger hat. Die Delta-Distribution δ ist dabei ein neutrales Element: uδ=u. Die üblichen Regeln Kommutativität, Distributivität und Verträglichkeit mit skalarer Multiplikation bleiben erhalten. Für eine temperierte Distribution u₁ und eine Distribution u₂ mit kompaktem Träger gilt ebenfalls das Faltungstheorem: ℱ(u₁*u₂)=(2π)ⁿ⁄²ℱ(u₁)·ℱ(u₂).

Auf einer geeigneten topologischen Gruppe G mit Maß m lautet die allgemeine Faltung (fg)(x)=∫_G f(t)g(xt⁻¹) dm(t). Für eine diskrete Gruppe wird daraus (fg)(s)=∑_{t∈G}f(t)g(t⁻¹s). Bei einer endlichen Gruppe bildet L¹(G) mit dieser Faltung eine Faltungsalgebra. Die Funktionen δₛ mit δₛ(t)=1 für t=s und 0 sonst erfüllen δₛ*δₜ=δₛₜ; damit ist die Faltungsalgebra zur Gruppenalgebra ℂ[G] isomorph.

Anwendungsfelder

Faltungen werden in vielen Bereichen verwendet: In der Bildverarbeitung dienen Faltungsmatrizen zum Glätten von Rauschen und zur Kantendetektion. Bei linearen zeitinvarianten Systemen ist die Antwort auf ein Eingangssignal die Faltung des Signals mit der Impulsantwort. Dies gilt etwa für elektronische Filter sowie für die digitale Erzeugung von Hall und Echo aus Raumimpulsantworten.

Bei partiellen Differentialgleichungen liefert Gf eine Lösung von Lu=f, wenn G eine Fundamentallösung des Operators L ist; auch Diffusionsprozesse lassen sich so beschreiben. Für unabhängige Zufallsvariablen X und Y mit Dichten f und g hat X+Y die Dichte fg.

Weitere Anwendungen sind B-Splines in der numerischen Mathematik, die schnelle Multiplikation vielstelliger Zahlen mit Aufwand O(n log(n)) statt O(n²), Niederschlags-Abfluss-Berechnungen mit Unit-Hydrographen und die Reflexionsseismik. Dort wird eine seismische Spur als Faltung von Impedanzkontrasten und einem Wavelet betrachtet; die Wiederherstellung der Schichtgrenzen heißt Dekonvolution.