Multiresolution analysis: Difference between revisions

Revision as of 19:56, 16 April 2013

Latest revision as of 15:22, 1 February 2025

(33 intermediate revisions by 29 users not shown)

Line 1:

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

A '''multiresolution analysis (MRA)''' or '''multiscale approximation (MSA)''' is the design 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 equation]]s (the ''[[ironing method]]'') and the [[pyramid (image processing)|pyramid method]]s of [[image processing]] as introduced in 1981/83 by Peter J. Burt, Edward H. Adelson and James Crowley.

{{Distinguish|Multiple-scale analysis}}

A '''multiresolution analysis''' ('''MRA)''') or '''multiscale approximation''' ('''MSA)''') is the design 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 equation]]s (the ''[[ironing method]]'') and the [[pyramid (image processing)|pyramid method]]s of [[image processing]] as introduced in 1981/83 by Peter J. Burt, 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>

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

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

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

* ''Self-similarity'' in ''time'' demands that each subspace ''V_k'' is invariant under shifts by [[integer]] [[multiple (mathematics)|multiple]]s of ''2^-k''. 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>.

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

* ''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_Scaling (geometry)|scaling]] 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 (mathematics)|support]], then as the support of g gets smaller, the resolution of the ''l''-th subspace is higher than 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.

* ''Self-similarity'' in ''time'' demands that each subspace ''V_k'' is invariant under shifts by [[integer]] [[multiple (mathematics)|multiple]]s of ''2^-k''. That is, 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>.

* ''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_functionScaling function|scaling functions]]''' or '''[[father wavelets]]'''. In most cases one demands of those functions to be [[piecewise continuous]] with [[compact support]].

* ''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]] respectively [[Dilation (metric space)|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 (mathematics)|support]], then as the support of g gets smaller, the resolution of the ''l''-th subspace is higher than the resolution of the ''k''-th subspace.

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

* ''Regularity'' demands that the model 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^2(\mathbb{R})</math>, and that they are not too redundant, i.e., their intersection should only contain the zero element.

== Important conclusions ==

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

Assuming the scaling function has 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

:<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>

Oneone can show that the space <math>W_0\subset V_1V_{-1}</math>, which is defined as the (closed) linear hull of the mother wavelet's integer shifts, is the orthogonal complement to <math>V_0</math> inside <math>V_1V_{-1}</math>.<ref>{{cnCite web|dateurl=Aprilhttp://www.cmap.polytechnique.fr/~mallat/book.html|title=A 2013Wavelet 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{{cn|date=April 2013}}

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

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

One can show that the space <math>W_0\subset V_1</math>, which is defined as the (closed) linear hull of the mother wavelet's integer shifts, is the orthogonal complement to <math>V_0</math> inside <math>V_1</math>.{{cn|date=April 2013}} Or put differently, <math>V_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{{cn|date=April 2013}}

:<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>

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

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

==See also==

* [[MultiscaleMultigrid modelingmethod]]

* [[ScaleMultiscale spacemodeling]]

* [[WaveletScale space]]

*[[Category:Time–frequency analysis]]

*[[Wavelet]]

== References ==

{{inline|date=April 2013}}

{{Reflist}}

==References==

* {{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}}

* {{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]]

== External links ==

*[http://www.scribd.com/doc/135987896/A-Concise-Introduction-to-Wavelets René Puchinger's detailed introduction to wavelets] with coverage of multiresolution analysis of orthogonal and biorthogonal wavelets.

[[Category:Wavelets]]

[[Category:Time–frequency analysis]]