auch Fast Wavelet Transform (FWT), Pyramidenalgorithmus, oder Mallat-Algorithmus genannt, ein Verfahren zur iterativen Berechnung der Waveletkoeffizien- ten eines Signals a_J.

Stellvertretend wird hier der Fall einer orthogonalen Wavelettransformation dargestellt; für biorthogonale oder Prä-Wavelets können ähnliche Algorithmen formuliert werden.

Sei das diskrete Signal a_J durch die Folge {a_J,k|k ∈ ℤ} von Abtastwerten gegeben. Die Funktion \begin{eqnarray}f(x)=\displaystyle \sum _{k=-\infty }^{\infty }{a}_{J,k}\cdot {\phi }_{J,k}(x)\end{eqnarray} ist dann im Raum V_J einer Multiskalenanalyse {V_j}_j∈ℤ des L²(ℝ) enthalten; dabei seien \({\phi }_{J,k}={2}^{\frac{J}{2}}\cdot \phi ({2}^{J}\cdot -k)\), und φ eine Skalierungsfunktion mit orthogonalen Translaten und kompaktem Träger. Für dieses J > 0 gilt also \begin{eqnarray}\begin{array}{lll}{V}_{J} & = & {V}_{J-1}\oplus {W}_{J-1}\\ & = & {V}_{0}\oplus {W}_{0}\oplus {W}_{1}\oplus {W}_{2}\oplus \ldots \oplus {W}_{J-1}.\end{array}\end{eqnarray}

Wegen der Orthogonalität von {φ(· − k)|k ∈ ℤ} gilt a_j,k = ⟨f,φ_j,k⟩; jedes a_j,k ist ein gewichtetes Mittel von f in der Umgebung von k. Die Waveletkoeffizienten des diskreten Signals a_J sind die Waveletkoeffizienten d_j,k von f, j = 0, 1,…,J − 1 : d_j,k = ⟨f, ψ_j,k⟩. Dabei ist \({\psi }_{j,k}={2}^{\frac{j}{2}}\cdot \psi ({2}^{j}\cdot -k)\), und ψ ist ein Wavelet. Diese Koeffizienten sind nur für j< J von Null verschieden, da f ∈ V_J. Die schnelle Wavelettransformation zerlegt sukzessive jede Approximation P_Vjf von f im Raum V_j in größere Approximationen \({P}_{{V}_{j-1}}f\) und die Detailinformation in \({P}_{{W}_{j-1}}f\). Da {φ_j,k|k ∈ ℤ} eine orthogonale Basis von V_j ist, sind die Projektionen \({P}_{{V}_{j}}\) durch a_j,k = ⟨f, φ_j,k⟩ charakterisiert. Die Waveletzerlegung berechnet sich als diskrete Faltung:

Zerlegung (Dekomposition): \begin{eqnarray}{a}_{j-1,l}=\displaystyle \sum _{k\in {\mathbb{Z}}}{h}_{k-2l}\cdot {a}_{j,k}\,\text{und}\,{d}_{j-1,l}=\displaystyle \sum _{k\in {\mathbb{Z}}}{g}_{k-2l}\cdot {a}_{j,k}.\end{eqnarray}

Dabei sind die endlichen Filter {h_k|k ∈ ℤ} bzw. {g_k|k ∈ ℤ} durch die Skalierungsgleichungen von Generator bzw. Wavelet induziert. Mit den Zerlegungsoperatoren \({({H}_{a})}_{k}=\displaystyle {\sum }_{l\in {\mathbb{Z}}}{h}_{l-2k}\cdot \,{a}_{l}\) und \({({G}_{a})}_{k}=\displaystyle {\sum }_{l\in {\mathbb{Z}}}{g}_{l-2k}\cdot \,{a}_{l}\) gilt \begin{eqnarray}{a}_{j-1}=H{a}_{j}\,\,\text{und}\,\,{d}_{j-1}=G{a}_{j}.\end{eqnarray}

Ein Eingabesignal a_J wird also gemäß folgendem Schema zerlegt: \begin{eqnarray}\begin{array}{cccccccc}{a}_{J} & \mathop{\to }\limits^{H} & {a}_{J-1} & \mathop{\to }\limits^{H} & {a}_{J-2} & \mathop{\to }\limits^{H} & {a}_{J-3} & \ldots \\ & \mathop{\searrow }\limits^{G} & {d}_{J-1} & \mathop{\searrow }\limits^{G} & {d}_{J-2} & \mathop{\searrow }\limits^{G} & {d}_{J-3} & \ldots \end{array}\end{eqnarray}

Die Anwendung von H entspricht dem Übergang zu einer gröberen Approximation und somit einem Tiefpaßfilter. Der Operator G resultiert aus der Koeffizientenfolge {g_k|k ∈ ℤ} der Skalierungsgleichung für die Wavelets und entspricht einem Hochpaßfilter. Das zerlegte Signal kann durch sukzessives Anwenden der Rücktransformation wieder vollständig rekonstruiert werden:

Synthese (Rekonstruktion): \begin{eqnarray}{a}_{j,l}=\displaystyle \sum _{k\in {\mathbb{Z}}}{h}_{l-2k}\cdot {a}_{j-1,k}+\displaystyle \sum _{k\in {\mathbb{Z}}}{g}_{l-2k}\cdot {d}_{j-1,k}.\end{eqnarray}

Für ein Signal der Länge n benötigt die schnelle Wavelettransformation O(n) Operationen und ist damit schneller als die schnelle Fouriertransformation (die O(n · log(n)) Operationen benötigt). Zusätzlich erlaubt sie häufig eine sehr effiziente Datenkompression. Dazu vernachlässigt man kleine Wavelet-Koeffizienten, die in den Bereichen auftreten, in denen das Ausgangssignal einen hohen Grad an Glattheit aufweist. Entsprechend liefern die Bereiche mit geringerer Glattheit (große Koeffizienten) den Hauptbeitrag an der Kompression. Auf diese Weise können im Idealfall hohe Kompressionsraten erzielt werden.