Multiresolution analysis: Difference between revisions

Revision as of 11:24, 30 May 2005

Latest revision as of 15:22, 1 February 2025

(88 intermediate revisions by 67 users not shown)

Line 1:

{{Short description|Design method of discrete wavelet transforms}}

A '''Multiresolution Analysis (MRA)''' or '''Multiscale Approximation (MSA)''' is the desing method of most of the practically relevant [[discrete wavelet transform]]s (DWT) and the justification for the [[algorithm]] of the [[fast wavelet transform]] (FWT). It was introduced in this context in 1988/89 by [[Stephane Mallat]] and [[Yves Meyer]] and has predecessors in the microlocal analysis in the theory of differential equations (the ''ironing method'') and the pyramid methods of image processing as introduced in 1981/83 by Peter J. Burt und Edward H. Adelson.

{{Distinguish|Multiple-scale analysis}}

A '''Multiresolutionmultiresolution Analysisanalysis''' ('''MRA)''') or '''Multiscalemultiscale Approximationapproximation''' ('''MSA)''') is the desingdesign method of most of the practically relevant [[discrete wavelet transform]]s (DWT) and the justification for the [[algorithm]] of the [[fast wavelet transform]] (FWT). It was introduced in this context in 1988/89 by [[Stephane Mallat]] and [[Yves Meyer]] and has predecessors in the [[microlocal analysis]] in the theory of [[differential equationsequation]]s (the ''ironing method'') and the [[pyramid methods(image processing)|pyramid method]]s of [[image processing]] as introduced in 1981/83 by Peter J. Burt und, Edward H. Adelson and [http://www-prima.inrialpes.fr/Prima/Homepages/jlc/jlc.html James L. Crowley].

== Definition ==

A multiresolution analysis of the [[Lp space|Lebesgue space]] <math>L^2(\mathbb{R})</math> consists of a [[sequence]] of nested [[linear subspace|subspaces]]

::<math>\{0\}\subset \dots\subset V_1\subset V_0\subset V_1V_{-1}\subset\dots\subset V_nV_{-n}\subset V_{-(n+1)}\subset\dots\subset L^2(\R)</math>

== Definition ==

that satisfies certain [[self-similarity]] relations in time/-space and scale/-frequency, as well as [[Complete metric space|completeness]] and regularity relations.

A ''Multiresolution Analysis'' of the space ''L&sup2;(IR)'' consists of a sequence of nested subspaces

:<math>\dots\subset V_0\subset V_1\subset\dots\subset V_n\subset V_{n+1}\subset\dots\subset L^2(\R)</math>

that satisfies certain self-similarity relations in time/space and scale/frequency, as well as completeness and regularity relations.

* ''Self-similarity'' in ''time'' demands that each subspace ''V_k'' is invariant under shifts by integer multiples of ''2^-k''. I.e., for each <math>f\in V_k,\; m\in\mathbb Z</math> there is a <math>g\in V_k</math> with <math>\forall x\in\mathbb R:\;f(x)=g(x+m2^{-k})</math>.

* ''Self-similarity'' in ''scale'' demands that all subspaces <math>V_k\subset V_l,\; k<l,</math> are time-scaled versions of each other, with scaling resp. dilation factor ''2^l-k''. I.e., for each <math>f\in V_k</math> there is a <math>g\in V_l</math> with <math>\forall x\in\mathbb R:\;g(x)=f(2^{l-k}x)</math>. If f has limited support, then the support of g gets smaller, the resolution of the ''l''-th subspace is higher then the resolution of the ''k''-th subspace.

* ''Regularity'' demands that the model subspace ''V₀'' be generated as the linear hull (algebraically or even topologically closed) of the integer shifts of one or a finite number of generating functions <math>\phi</math> or <math>\phi_1,\dots,\phi_r</math>. Those integer shifts should at least form a frame for the subspace <math>V_0\subset L^2(\R)</math>, which imposes certain conditions on the decay at infinity. The generating functions are also known as '''scaling functions''' or '''father wavelets'''. In most cases one demands of those functions to be (piecewise) continuous with compact support.

* ''Completeness'' demands that those nested subspaces fill the whole space, i.e., their union should be dense in ''L&sup2;(IR)'', and that they are not too redundant, i.e., their intersection should only contain the zero element.

* ''Self-similarity'' in ''time'' demands that each subspace ''V_k'' is invariant under shifts by [[integer]] multiples[[multiple (mathematics)|multiple]]s of ''2^-k''. I.e.That is, for each <math>f\in V_k,\; m\in\mathbb Z</math> therethe isfunction a <math>''g\in'' V_k</math>defined withas <math>\forall x\in\mathbb R:\;fg(x)=gf(x+-m2^{-k})</math> also contained in <math>V_k</math>.

* ''Self-similarity'' in ''scale'' demands that all subspaces <math>V_k\subset V_l,\; k<>l,</math> are time-scaled versions of each other, with [[Scaling (geometry)|scaling]] resp.respectively [[Dilation (metric space)|dilation]] factor ''2^l-''k-l''''. I.e., for each <math>f\in V_k</math> there is a <math>g\in V_l</math> with <math>\forall x\in\mathbb R:\;g(x)=f(2^{k-l-k}x)</math>. If f has limited support, then the support of g gets smaller, the resolution of the ''l''-th subspace is higher then the resolution of the ''k''-th subspace.

* In the sequence of subspaces, for ''k''>''l'' the space resolution 2^''l'' of the ''l''-th subspace is higher than the resolution 2^''k'' of the ''k''-th subspace.

* ''Regularity'' demands that the model [[linear subspace|subspace]] ''V₀'' be generated as the [[linear hull]] ([[algebraic closure|algebraically]] or even [[topologically closed]]) of the integer shifts of one or a finite number of generating functions <math>\phi</math> or <math>\phi_1,\dots,\phi_r</math>. Those integer shifts should at least form a frame for the subspace <math> V_0\subset L^2(\R) </math>, which imposes certain conditions on the decay at [[infinity]]. The generating functions are also known as '''[[Wavelet#Scaling function|scaling functions]]''' or '''[[father wavelets]]'''. In most cases one demands of those functions to be ([[piecewise) continuous]] with [[compact support]].

* ''Completeness'' demands that those nested subspaces fill the whole space, i.e., their union should be [[dense set|dense]] in ''<math> L&sup2;^2(IR\R)'' </math>, and that they are not too redundant, i.e., their [[intersection]] should only contain the [[zero element]].

== Important conclusions ==

This is only forIn the case of one continuous (or at least with bounded variation) compactly supported scaling function with orthogonal shifts, (theone may make a number of deductions. The proof of existence of thosethis class of functions is due to [[Ingrid Daubechies]]).

ThenAssuming therethe is,scaling becausefunction ofhas compact support, then <math>V_0\subset V_1V_{-1}</math>, implies that there is a finite sequence of coefficients <math>a_k=2< \langle\phi(x),\phi(2x-k)\rangle</math> for <math>|k|\leq N</math>, and <math>a_k=0</math> for <math>|k|>N</math>, such that

This is only for the case of one continuous (or at least with bounded variation) compactly supported scaling function with orthogonal shifts (the existence of those is due to [[Ingrid Daubechies]]).

:<math>\phi(x)=\sum_{k=-N}^N a_k\phi(2x-k).</math>.

Then there is, because of <math>V_0\subset V_1</math>, a finite sequence of coefficients <math>a_k=2<\phi(x),\phi(2x-k)></math>, <math>a_k=0</math> for |k|>N, such that

:<math>\phi(x)=\sum_{k=-N}^N a_k\phi(2x-k)</math>.

Defining another function, known as '''mother wavelet''' or just '''the wavelet'''

:<math>\psi(x):=\sum_{k=-N}^N (-1)^k a_{1-k}\phi(2x-k),</math>,

one can seeshow that the space <math>W_0\subset V_1V_{-1}</math>, which is defined as the (closed) linear hull of itsthe mother wavelet's integer shifts, is the orthogonal complement to <math>W_0V_0</math> inside <math>V_1V_{-1}</math>.<ref>{{Cite web|url=http://www.cmap.polytechnique.fr/~mallat/book.html|title=A Wavelet Tour of Signal Processing|last=Mallat, S.G.|website=www.di.ens.fr|access-date=2019-12-30}}</ref> Or put differently, <math>V_1V_{-1}</math> is the [[orthogonal direct sum|orthogonal sum]] (denoted by <math>\oplus</math>) of <math>W_0</math> and <math>V_0</math>. By self-similarity, there are scaled versions <math>W_k</math> of <math>W_0</math> and by completeness one has

:<math>L^2(\mathbb R)=\mbox{closure of }\bigoplus_{k\in\Z}W_k,</math>,

thus the set

:<math>\{\psi_{k,n}(x)=\sqrt2^{-k}\psi(2^kx{-k}x-n):\;k,n\in\Z\}</math>

is a countable complete [[orthonormal systemwavelet]] basis in <math>L^2(\R)</math>.

==See also==

thus the set

*[[Multigrid method]]

*[[Multiscale modeling]]

*[[Scale space]]

*[[Time–frequency analysis]]

*[[Wavelet]]

== References ==

:<math>\{\psi_{k,n}(x)=\sqrt2^k\psi(2^kx-n):\;k,n\in\Z\}</math>

{{Reflist}}

* {{cite book|first=Charles K.|last=Chui|title=An Introduction to Wavelets|year=1992|publisher=Academic Press|___location=San Diego|isbn=0-585-47090-1}}

is a countable complete orthonormal system in <math>\R</math>.

* {{cite book|author1-link=Ali Akansu|first1=A.N.|last1=Akansu|first2=R.A.|last2=Haddad|title=Multiresolution signal decomposition: transforms, subbands, and wavelets|publisher=Academic Press|year=1992|isbn=978-0-12-047141-6}}

* Crowley, J. L., (1982). [http://www-prima.inrialpes.fr/Prima/Homepages/jlc/papers/Crowley-Thesis81.pdf A Representations for Visual Information], Doctoral Thesis, Carnegie-Mellon University, 1982.

* {{cite book|author1-link=C. Sidney Burrus|first1=C.S.|last1=Burrus|first2=R.A.|last2=Gopinath|first3=H.|last3=Guo|title=Introduction to Wavelets and Wavelet Transforms: A Primer|publisher=Prentice-Hall|year=1997|isbn=0-13-489600-9}}

* {{cite book|first=S.G.|last=Mallat|url=http://www.cmap.polytechnique.fr/~mallat/book.html|title=A Wavelet Tour of Signal Processing|publisher=Academic Press|year=1999|isbn=0-12-466606-X}}

[[Category:Time–frequency analysis]]

[[Category:Wavelets]]