Faltung (Mathematik)

In der Mathematik und besonders in der Funktionalanalysis beschreibt die Faltung einen mathematischen Operator, der für zwei Funktionen f und g eine dritte Funktion liefert.

Anschaulich kann die Faltung dadurch beschrieben werden, dass zuerst g um die y-Achse gespiegelt wird, und dann jeder Punkt von f, der ungleich 0 ist, durch eine Version von g ausgetauscht wird, deren Höhe je nach der Höhe des betreffenden Punktes von f skaliert wird.

Die daraus resultierende „Überlappung“ zwischen f und einer gespiegelten und verschobenen Version von g oder „Verschmierung“ von f kann z.B. verwendet werden, um einen gleitenden Durchschnitt zu bilden.

Ist g die Impulsantwort eines Hochpass-, Tiefpass- oder anderweitigen linearen Filters, dann ist $f*g$ die Filterantwort auf das Eingangssignal f mit eben diesem Filter.

Definition

Die Faltung $(f*g)\,$ zweier Funktionen $f,g:\mathbb {R} ^{n}\to \mathbb {C}$ ist definiert durch

$(f*g)(\xi ):=\int _{\mathbb {R} ^{n}}f(y)g(\xi -y)\mathrm {d} y\,$

Um die Definition möglichst allgemein zu halten, schränkt man den Raum der zulässigen Funktionen zunächst nicht ein und fordert stattdessen, dass das Integral für fast alle Werte von $\xi$ wohldefiniert ist.

Im Fall $f,g\in {\mathcal {L}}^{1}(\mathbb {R} ^{n})$, also integrierbare Funktionen, deren uneigentliches Betragsintegral endlich ist, kann man zeigen, dass diese Voraussetzung immer erfüllt ist. Also lässt sich die Faltung als Produkt auf ${\mathcal {L}}^{1}(\mathbb {R} ^{n})$ auffassen.

Definition für Funktionen auf Intervallen

Im Fall eines beschränkten Definitionsbereichs $\mathbb {D}$ setzt man $f$ und $g$ auf den gesamten Raum fort, um die Faltung ausführen zu können. Hierzu gibt es je nach Anwendung mehrere Ansätze.

Fortsetzung durch Null

Man setzt die Funktionen per Definition außerhalb des Definitionsbereiches durch die Nullfunktion fort: $f{\Big |}_{\mathbb {R} ^{n}\setminus \mathbb {D} }\equiv 0$.

Periodische Fortsetzung

Man setzt die Funktionen außerhalb des Definitionsbereiches periodisch fort und verwendet die unten definierte periodische Faltung.

Im Allgemeinen ist die Faltung für derart fortgesetzte Funktionen nicht mehr wohldefiniert. Eine oft auftretende Ausnahme bilden Funktionen mit kompaktem Träger $f\in C_{c}(\mathbb {D} )\cap {\mathcal {L}}^{1}(\mathbb {D} )$, die durch Null zu einer integrierbaren Funktion in ${\mathcal {L}}^{1}(\mathbb {R} ^{n})$ fortsetzbar sind.

Bedeutung

Faltung der Rechteckfunktion mit sich selbst ergibt die Dreieckfunktion. Rot ist f(t), grün g(t)

Eine anschauliche Deutung der eindimensionalen Faltung ist die Gewichtung einer von der Zeit abhängigen Funktion mit einer anderen. Der Funktionswert der Gewichtsfunktion $f$ an einer Stelle $\tau$ gibt an, wie stark der um $\tau$ zurückliegende Wert der gewichteten Funktion, also $g(t-\tau )$, in den Wert der Ergebnisfunktion zum Zeitpunkt $t$ eingeht.

Die Faltung ist ein geeignetes Modell zur Beschreibung zahlreicher physikalischer Vorgänge.

Glättungskern

Eine Methode, eine Funktion f zu „glätten“, besteht darin, sie mit einem so genannten Glättungskern zu falten. Die entstehende Funktion F ist glatt (unendlich oft stetig differenzierbar), ihr Träger ist nur etwas größer als der von f, und die Abweichung in der L1-Norm lässt sich durch eine vorgegebene positive Konstante beschränken.

Ein d-dimensionaler Glättungskern (engl. mollifier) ist eine unendlich oft stetig differenzierbare Funktion $j:\mathbb {R} ^{d}\to \mathbb {R} _{+}$, die nichtnegativ ist, ihren Träger in der abgeschlossenen Einheitskugel B(0, 1) hat und das Integral 1, durch entsprechende Wahl einer Konstanten c, besitzt.

Ein Beispiel ist der Glättungskern

$j(x)={\begin{cases}c\cdot \exp \!\left(-{\frac {1}{1-x^{2}}}\right)&-1<x<1\\0&\mathrm {sonst} \end{cases}}$

Aus dieser Funktion kann man weitere Glättungskerne bilden, indem man für e eine Zahl zwischen 0 und 1 setzt:

$j_{e}(x)={\frac {1}{e^{d}}}\cdot j\left({\frac {x}{e}}\right),$ wobei $j_{e}(x)=0$ für $|x|>e$.

Glättungskerne j und j_1/2

Beispiele

Sei

$f:\mathbb {R} \to \mathbb {R} ,\;x\mapsto {\begin{cases}1&-1\leq x\leq 2\\0&\mathrm {sonst} \end{cases}}$.

Durch Faltung von $f$ (rot dargestellt) mit dem Glättungskern $j_{1/2}$ entsteht eine glatte Funktion $F=f*j_{1/2}$ (blau dargestellt) mit kompaktem Träger, die von f in der L₁-Norm um etwa 0,4 abweicht, d.h.

$\int _{-\infty }^{\infty }|F(t)-f(t)|\mathrm {d} t<0{,}4$.

Bei der Faltung mit $j_{e}$ für e kleiner 1/2 erhält man glatte Funktionen, die in der Integralnorm noch dichter bei f liegen.

Eigenschaften der Faltung

Algebraische Eigenschaften

Die Menge $L^{1}(\mathbb {R} ^{n})$ bildet zusammen mit der Faltung einen kommutativen Ring, der kein neutrales Element besitzt. Im Detail gelten also die folgenden Eigenschaften:

• Kommutativität

$f*g=g*f\,$

• Assoziativität

$f*(g*h)=(f*g)*h=f*g*h\,$

• Distributivität

$f*(g+h)=(f*g)+(f*h)\,$

• Assoziativität mit der skalaren Multiplikation

$a(f*g)=(af)*g=f*(ag)\,$

Wobei $a$ eine beliebige komplexe Zahl ist.

Ableitungsregel

$\mathrm {D} (f*g)=\mathrm {D} f*g=f*\mathrm {D} g\,$

Dabei ist $\mathrm {D} f$ distributionelle Ableitung von $f$. Falls $f$ (total) differenzierbar ist, so stimmen distributionelle Ableitung und (totale) Ableitung überein. Zwei interessante Beispiele dazu sind:

• $(f*D\delta )(x)=Df(x)\,$, wobei $D\delta$ die Ableitung der Delta-Distribution ist. Die Ableitung lässt sich also als Faltungsoperator auffassen.
• $(f*\Theta )(x)=\int _{-\infty }^{x}f(t)\mathrm {d} t$, wobei $\Theta$ die Sprungfunktion ist, ergibt eine Stammfunktion für f.

Integration

Sind $f$ und $g$ integrierbare Funktionen so gilt

$\int _{\mathbb {R} ^{n}}(f*g)(x)dx=\left(\int _{\mathbb {R} ^{n}}f(x)dx\right)\left(\int _{\mathbb {R} ^{n}}g(x)dx\right).$

Dies ist eine einfache Folgerung aus dem Satz von Fubini.

Faltungstheorem

${\mathcal {F}}(f*g)=(2\pi )^{\tfrac {n}{2}}\,{\mathcal {F}}(f)\cdot {\mathcal {F}}(g),\quad f,g\in L^{1}(\mathbb {R} ^{n})$

Wobei ${\mathcal {F}}(f)$ die Fouriertransformierte von $f$ beschreibt. Ein ähnliches Theorem gilt auch für die Laplacetransformation.

Spiegelungsoperator

Es sei $S$ der Spiegelungsoperator mit $Sf(t)=f(-t)$ für alle $t$, dann gilt

• $(Sf*g)(t)=\int _{\mathbb {R} ^{n}}f(-\tau )g(t-\tau )\mathrm {d} \tau =\int _{\mathbb {R} ^{n}}f(\tau )g(\tau +t)\mathrm {d} \tau =S(f*Sg)(t)$ und
• $(Sf*Sg)(t)=\int _{\mathbb {R} ^{n}}f(\tau )g(-t-\tau )\mathrm {d} \tau =S(f*g)(t).$

Faltung dualer L^p-Funktionen ist stetig

Sei $f\in L^{p}(\mathbb {R} ^{n})$ und $g\in L^{q}$ mit $q>1$ und ${\frac {1}{p}}+{\frac {1}{q}}=1$. Dann ist die Faltung $f*g$ eine stetige Funktion auf $\mathbb {R} ^{n}$. Außerdem geht diese Faltung bei Unendlich gegen Null im folgenden Sinn, für jedes $\epsilon >0$ existiert eine Menge $R(\epsilon )\subset \mathbb {R} ^{n}$, so dass

$\sup _{|x|>R(\epsilon )}|(f*g)(x)|<\epsilon$

gilt. Diese Aussage ist ebenfalls richtig, wenn $f$ eine reelle Hardy-Funktion ist und $g$ in BMO liegt.

Verallgemeinerte Young'sche Ungleichung

Aus der Hölder'schen Ungleichung folgt die verallgemeinerte Young'sche Ungleichung

$\|f*g\|_{r}\leq \|f\|_{p}\|g\|_{q}$ für ${\frac {1}{p}}+{\frac {1}{q}}=1+{\frac {1}{r}}$ und $p,q,r\geq 1$.

Faltung periodischer Funktionen

Für periodische Funktionen $f$ und $g$ einer reellen Variablen mit Periode $T>0$ definiert man die Faltung als

$(f*g)(t)={\frac {1}{T}}\int _{a}^{a+T}f(\tau )g(t-\tau )\mathrm {d} \tau$,

wobei sich die Integration über ein beliebiges Intervall mit Periodenlänge $T$ erstreckt. Es ist $f*g$ wiederum eine periodische Funktion mit Periode $T$.

Für diesen Faltungsbegriff gelten die oben genannten Eigenschaften sinngemäß. Das Faltungstheorem lässt sich nun folgendermaßen formulieren: Lassen sich $f$ und $g$ in Fourierreihen $\sum _{n=-\infty }^{\infty }c_{n}\mathrm {e} ^{\mathrm {i} n\omega t}$ bzw. $\sum _{n=-\infty }^{\infty }d_{n}\mathrm {e} ^{\mathrm {i} n\omega t}$ mit $\omega =2\pi /T$ entwickeln, dann lautet die Fourierentwicklung der stetigen Funktion $f*g$

$(f*g)(t)\,=\sum _{n=-\infty }^{\infty }c_{n}d_{n}\mathrm {e} ^{\mathrm {i} n\omega t}$.

Die Fourierkoeffizienten des Faltungsprodukts sind also die gewöhnlichen komponentenweisen Produkte der Koeffizienten von $f$ und $g$.

Diskrete Faltung

In der digitalen Signalverarbeitung und der digitalen Bildverarbeitung hat man es meist mit diskreten Funktionen zu tun. Hier seien die Funktionen $f,g:D\to {\mathbb {C}}$ gegeben. Dabei ist der Definitionsbereich $D\subseteq {\mathbb {Z}}$.

Die diskrete Faltung ist definiert als:

$(f*g)(n)=\sum _{k\in D}f(k)g(n-k)$

Der Summationsbereich ist der gesamte Definitionsbereich $D$ beider Funktionen. Im Fall eines beschränkten Definitionsbereichs werden $f$ und $g$ meist durch Null fortgesetzt. Wenn man die Werte aber periodisch fortsetzt, kann man die Formel als Multiplipkation mit einer zyklischen Matrix interpretieren.

Das Produkt zweier Polynome $f$ und $g$ ist z.B. die diskrete Faltung ihrer mit Nullen fortgesetzten Koeffizientenfolgen. Die dabei auftretenden unendlichen Reihen haben stets nur endlich viele Summanden, die ungleich Null sind. Analog definiert man das Produkt zweier formaler Laurentreihen mit endlichem Hauptteil.

Ein in Bezug auf die Rechenleistung effizienter Algorithmus für die Berechnung der diskreten Faltung ist die Schnelle Faltung, die sich ihrerseits auf die Schnelle Fourier-Transformation (FFT) zur effizienten Berechnung der diskreten Fourier-Transformation stützt.

Eine interaktive Visualisierung als Java-Applet ist hierzu zu finden unter [1].

Distributionen

Hauptartikel: Faltung mit Distributionen

Faltung mit einer Funktion

Eine andere Verallgemeinerung ist die Faltung einer Distribution $T$ mit einer Funktion $\varphi \in C_{c}^{\infty }(\mathbb {R} ^{n})$. Diese ist definiert durch

$(T*\varphi )(x):=T(\tau _{x}\varphi )=T(\varphi (x-\cdot )),$

wobei $\tau _{x}$ ein Translations- und Spiegelungsoperator ist, welcher durch $\tau _{x}\phi (y)=\phi (x-y)$ definiert ist.

Faltung zweier Distributionen

Seien $u_{1}$ und $u_{2}$ zwei Distributionen, wobei eine einen kompakten Träger hat. Dann ist für alle $\varphi \in C_{c}^{\infty }(\mathbb {R} ^{n})$ die Faltung zwischen diesen Distributionen definiert durch

$(u_{1}*u_{2})*\phi =u_{1}*(u_{2}*\phi )$.

Eine weitergehende Aussage stellt sicher, dass es eine eindeutige Distribution $u\in {\mathcal {D}}'$ gibt mit

$u_{1}*(u_{2}*\phi )=u*\phi$

für alle $\varphi \in C_{c}^{\infty }(\mathbb {R} ^{n})$ .

Algebraische Eigenschaften

Seien $u_{1}$, $u_{2}$ und $u_{3}$ Distributionen, dann gilt

• Kommutativität

$u_{1}*u_{2}=u_{2}*u_{1}\,$

• Distributivität

$u_{1}*(u_{2}+u_{3})=(u_{1}*u_{2})+(u_{1}*u_{3})\,$

• Assoziativität mit der skalaren Multiplikation

$a(u_{1}*u_{2})=(au_{1})*u_{2}=u_{1}*(au_{2})\,$

Wobei $a$ eine beliebige komplexe Zahl ist.

• Neutrales Element
  • $(u_{1}*\delta )=u_{1}\,$, wobei $\delta$ die Delta-Distribution ist.

Faltungstheorem

Mit ${\mathcal {F}}$ wird die Fourier-Transformation von Distributionen bezeichnet. Sei nun $u_{1}\in S'(\mathbb {R} ^{n})$ eine temperierte Distribution und $u_{2}\in {\mathcal {E'}}(\mathbb {R} ^{n})$ eine Distribution mit kompaktem Träger. Dann ist $u_{1}*u_{2}\in S'(\mathbb {R} ^{n})$ und es gilt

${\mathcal {F}}(u_{1}*u_{2})=(2\pi )^{\tfrac {n}{2}}{\mathcal {F}}(u_{1})\cdot {\mathcal {F}}(u_{2})$.

Topologische Gruppen

Die beiden Faltungsbegriffe können gemeinsam beschrieben und verallgemeinert werden durch einen allgemeinen Faltungsbegriff für komplexwertige m-integrierbare Funktionen auf einer geeigneten topologischen Gruppe G mit einem Maß m (z. B. einer lokalkompakten hausdorffschen topologischen Gruppe mit einem Haar-Maß):

$(f*g)(x)=\int _{G}f(t)g(xt^{-1})\mathrm {d} m(t)\,$

Dieser Faltungsbegriff spielt eine zentrale Rolle in der Darstellungstheorie dieser Gruppen, deren wichtigste Vertreter die Lie-Gruppen bilden. Die Algebra der integrierbaren Funktionen mit dem Faltungsprodukt ist für kompakte Gruppen das Analogon zum Gruppenring einer endlichen Gruppe. Weiterführende Themen sind:

• Satz von Peter-Weyl
• Harmonische Analyse

Anwendung

• In der Optik können verschiedenste Bildstörungen als Faltung des Originalbildes mit einem entsprechenden Kern modelliert werden. In der digitalen Bildbearbeitung wird die Faltung daher benutzt, um solche Effekte zu simulieren. Auch andere digitale Effekte beruhen auf der Faltung.

• Bei einem linearen, zeitinvarianten Übertragungsglied ergibt sich die Antwort auf eine Anregung durch Faltung der Anregungsfunktion mit der Impulsantwort des Übertragungsglieds. Beispielsweise stellt die lineare Filterung eines elektronischen Signals die Faltung der Original-Funktion mit der Impulsantwort dar.

• Faltungen werden genutzt, um Lösungen bestimmter partieller Differentialgleichungen zu konstruieren

• Diffusions-Prozesse lassen sich durch die Faltung beschreiben.

• Wenn X und Y zwei stochastisch unabhängige Zufallsvariablen mit den Wahrscheinlichkeitsdichten f und g sind, dann ist die Dichte der Summe X+Y gleich der Faltung $f*g$.

• In der Akustik (Musik) wird die Faltung (unter Zuhilfenahme der FFT = schnelle Fouriertransformation) auch zur digitalen Erzeugung von Hall und Echos und zur Anpassung von Klangeigenschaften verwendet. Dazu wird die Impulsantwort des Raumes, dessen Klangcharakteristik man übernehmen möchte, mit dem Signal, das man beeinflussen möchte, gefaltet.

• In der Ingenieurmathematik und der Signalverarbeitung werden Eingangssignale (äußere Einflüsse) mit der Übertragungsfunktion (= Impulsantwort = Reaktion des betrachteten Systems auf einen Diracimpuls als Signaleingang) gefaltet, um die Antwort eines LTI-Systems auf beliebige Eingangssignale zu berechnen. Die Übertragungsfunktion ist nicht zu verwechseln mit der Übergangsfunktion. Erstere beschreibt die Gesamtheit aus System und einem Dirac-Impuls als Eingangs-Testfunktion, letztere die Gesamtheit aus System und einer Sprungfunktion als Eingangs-Testfunktion. Die Berechnungen finden meist nicht im Zeitbereich, sondern im Frequenzbereich statt. Dazu müssen sowohl das Signal als auch die das Systemverhalten beschreibende Übertragungsfunktion im Frequenzbereich vorliegen, oder ggf. aus dem Zeitbereich per Fouriertransformation oder einseitiger Laplacetransformation dorthin transformiert werden.

• In der numerischen Mathematik erhält man durch Faltung der Boxfunktion $N^{0}(t)$ mit $N^{k-1}(t)$ die B-Spline Basisfunktion $N^{k}(t)$ für den Vektorraum der stückweisen Polynome vom Grad k.

• Ebenfalls in der numerischen Mathematik kann die Faltung für eine effiziente Berechnung der Multiplikation vielstelliger Zahlen eingesetzt werden, da die Multiplikation im wesentlichen eine Faltung mit nachfolgendem Übertrag darstellt. Die Komplexität dieses Vorgehens ist mit ${\mathcal {O}}(n\cdot \log {(n)})$ nahe linear, während das „Schulverfahren“ quadratischen Aufwand ${\mathcal {O}}(n^{2})$ hat, wobei $n$ die Zahl der Stellen ist. Dies lohnt sich trotz des zusätzlichen Aufwands, der hierbei für die Fouriertransformation (und deren Umkehrung) erforderlich ist.

Literatur

• Bourbaki: Integration
• Kôsaku Yosida: Functional Analysis. Springer-Verlag, ISBN 3-540-58654-7.

Weblinks

• Interaktive Visualisierung der Faltung als Java-Applet
• Java-Applet zur Visualisierung der Faltung
• Weiteres Java-Applet zur Visualisierung der Faltung mit Anleitung (englisch)