Skip to content Skip to navigation Skip to collection information

OpenStax_CNX

You are here: Home » Content » Multiresolution Analysis, Filterbank Implementation, and Function Approximation using Wavelets » Approximation of functions with wavelets

Navigation

Lenses

What is a lens?

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

This content is ...

Endorsed by Endorsed (What does "Endorsed by" mean?)

This content has been endorsed by the organizations listed. Click each link for a list of all content endorsed by the organization.
  • IEEE-SPS

    This collection is included inLens: IEEE Signal Processing Society Lens
    By: IEEE Signal Processing Society

    Click the "IEEE-SPS" link to see all content they endorse.

Affiliated with (What does "Affiliated with" mean?)

This content is either by members of the organizations listed or about topics related to the organizations listed. Click each link to see a list of all content affiliated with the organization.
  • NSF Partnership display tagshide tags

    This collection is included inLens: NSF Partnership in Signal Processing
    By: Sidney Burrus

    Click the "NSF Partnership" link to see all content affiliated with them.

    Click the tag icon tag icon to display tags associated with this content.

Also in these lenses

  • UniqU content

    This collection is included inLens: UniqU's lens
    By: UniqU, LLC

    Click the "UniqU content" link to see all content selected in this lens.

  • Lens for Engineering

    This module and collection are included inLens: Lens for Engineering
    By: Sidney Burrus

    Click the "Lens for Engineering" link to see all content selected in this lens.

Recently Viewed

This feature requires Javascript to be enabled.

Tags

(What is a tag?)

These tags come from the endorsement, affiliation, and other lenses that include this content.
 

Approximation of functions with wavelets

Module by: Veronique Delouille. E-mail the author

Approximation of functions with wavelets

In Example from Multiresolution analysis, we saw the Haar wavelet basis. This is the simplest wavelet one can imagine, but its approximation properties are not very good. Indeed, the accuracy of the approximation is somehow related to the regularity of the functions ψψ and ϕ.ϕ. We will show this for different settings: in case the function ff is continuous, belongs to a Sobolev or to a Hölder space. But first we introduce the notion of regularity of a MRA.

Regularity of a multiresolution analysis

For wavelet bases (orthonormal or not), there is a link between the regularity of ψψ and the number of vanishing moments. More precisely, we have the following:

Proposition:

Let {ψj,k}{ψj,k} be an orthonormal basis (ONB) in L2(IR),L2(IR), with ψC[0.1ex]0.05em1.25exm,ψ(l)ψC[0.1ex]0.05em1.25exm,ψ(l) bounded for lmlm and |ψ(x)|C(1+|x|)-α|ψ(x)|C(1+|x|)-α for α>m+1.α>m+1. Then we have:
x l ψ ( x ) d x = 0 for l = 0 , 1 , ... , m . x l ψ ( x ) d x = 0 for l = 0 , 1 , ... , m .
(1)

(this describes the “decay in frequency domain”).

This proposition implies the following corollary:

Corollary:

Suppose the {ψj,k}{ψj,k} are orthonormal. Then it is impossible that ψψ has exponential decay, and that ψC[0.1ex]0.05em1.25ex,ψC[0.1ex]0.05em1.25ex, with all the derivatives bounded, unless ψ0ψ0

This corollary tells us that a trade-off has to be done: we have to choose for exponential (or faster) decay in, either time or frequency domain; we cannot have both. We now come to the definition of a r-r-regular MRA (see [5]).

Definition:

(Meyer, 1990) A MRA is called r-regular (rINrIN) when ϕC[0.1ex]0.05em1.25exrϕC[0.1ex]0.05em1.25exr and for all mIN,mIN, there exists a constant Cm>0Cm>0 such that:
| α ϕ ( x ) x α | C m ( 1 + | x | ) - m α r | α ϕ ( x ) x α | C m ( 1 + | x | ) - m α r
(2)

If one has a r-r-regular MRA, then the corresponding wavelet ψ(x)C[0.1ex]0.05em1.25exr,ψ(x)C[0.1ex]0.05em1.25exr, satisfies Equation 2 and has rr vanishing moments:

x k ψ ( x ) d x = 0 , k = 0 , 1 , ... , r . x k ψ ( x ) d x = 0 , k = 0 , 1 , ... , r .
(3)

We now have the tools needed to measure the decay of approximation error when the resolution (or the finest level) increases.

Approximation of a continuous function

Proposition:

Let {ψj,k}{ψj,k} come from a r-regular MRA. Then, we have, for a continuous function fC[0.1ex]0.05em1.25exs(0<s<r)fC[0.1ex]0.05em1.25exs(0<s<r)the following:
| < f , ψ j , k > | = O ( 2 - j ( s + 1 / 2 ) ) | < f , ψ j , k > | = O ( 2 - j ( s + 1 / 2 ) )
(4)

Proof:

(s=1s=1). As ψ(x)¯=0ψ(x)¯=0 and |f(x)-f(k/2j)|C|x-k/2j|,|f(x)-f(k/2j)|C|x-k/2j|, (ff is Lipschitz continuous), we have:
| < f , ψ j , k > | = | 2 j / 2 [ f ( x ) - f ( k / 2 j ) ] ψ ¯ ( 2 j x - k ) d x | , k Z Z C 2 j / 2 | x - k / 2 j | | ψ ¯ ( 2 j x - k ) | d x = C 2 - j / 2 | 2 j x - k | | ψ ¯ ( 2 j x - k ) | d x ( let u = 2 j x - k ) = 2 - j ( 1 + 1 / 2 ) C | u | | ψ ¯ ( u ) | d u < = O ( 2 - j ( 1 + 1 / 2 ) ) . | < f , ψ j , k > | = | 2 j / 2 [ f ( x ) - f ( k / 2 j ) ] ψ ¯ ( 2 j x - k ) d x | , k Z Z C 2 j / 2 | x - k / 2 j | | ψ ¯ ( 2 j x - k ) | d x = C 2 - j / 2 | 2 j x - k | | ψ ¯ ( 2 j x - k ) | d x ( let u = 2 j x - k ) = 2 - j ( 1 + 1 / 2 ) C | u | | ψ ¯ ( u ) | d u < = O ( 2 - j ( 1 + 1 / 2 ) ) .
(5)

For s>1,s>1, we use proposition Proposition 1 and we iterate.

Note that the reverse of Proposition 2 is true: Equation 4 entails that ff is in Cs.Cs.

Corollary:

Under the assumptions of Proposition 2, the error of approximation of a function fC[0.1ex]0.05em1.25exsfC[0.1ex]0.05em1.25exs at scale VJVJ is given by:
| | f - k < f , ϕ J , k > ϕ J , k | | 2 = O ( 2 - J s ) | | f - k < f , ϕ J , k > ϕ J , k | | 2 = O ( 2 - J s )
(6)

Proof:

Using the exact decomposition of ff given by Equation 30 from Multiresolution Analysis, one has:
| | f - P J f | | 2 = | | j J k < f , ψ j , k > ψ j , k | | 2 j J C 2 - j ( s + 1 / 2 ) | | k ψ j , k | | 2 | | f - P J f | | 2 = | | j J k < f , ψ j , k > ψ j , k | | 2 j J C 2 - j ( s + 1 / 2 ) | | k ψ j , k | | 2
(7)

Now, if we suppose that |ψ(k)|C'(1+|k|)-m,(ms+1),|ψ(k)|C'(1+|k|)-m,(ms+1), we obtain:

| | k ψ j , k | | 2 C ' 2 j / 2 | | k ψ j , k | | 2 C ' 2 j / 2
(8)

Putting inequalities Equation 7 and Equation 8 together, we have:

| | f - P J f | | 2 C ' ' j J 2 - j s = C ' ' ( 1 - 2 - s ) - 1 2 - J s = O ( 2 - J s ) | | f - P J f | | 2 C ' ' j J 2 - j s = C ' ' ( 1 - 2 - s ) - 1 2 - J s = O ( 2 - J s )
(9)

Hence, we verify with this last corollary that, as JJ increases, the approximation of ff becomes more accurate.

Approximation of functions in Sobolev spaces

Let us first recall the definition of weak differentiability, for this notion intervenes in the definition of a Sobolev space.

Definition:

Let ff be a function defined on the real line which is integrable on every bounded interval. If there exists a function gg defined on the real line which is integrable on every bounded interval such that:
x y , x y g ( u ) d u = f ( y ) - f ( x ) , x y , x y g ( u ) d u = f ( y ) - f ( x ) ,
(10)

then the function ff is called weakly differentiable. The function gg is defined almost everywhere, is called the weak derivative of ff and will be denoted by f'f'.

Definition:

A function ff is NN-times weakly differentiable if it has derivatives f,f',...,f(N-1)f,f',...,f(N-1) which are continuous and f(N)f(N) which is a weak derivative.

We are now able to define Sobolev spaces.

Definition:

Let 1p<,m{0,1,...}.1p<,m{0,1,...}. The function fLp(IR)fLp(IR) belongs to the Sobolev space Wpm(IR)Wpm(IR) if it is m-times weakly differentiable, and if f(m)Lp(IR).f(m)Lp(IR). In particular, Wp0(IR)=Lp(IR).Wp0(IR)=Lp(IR).

The approximation properties of wavelet expansions on Sobolev spaces are given, among other, in Härdle et.al (see [3]). Suppose we have at our disposal a scaling function ϕϕ which generates a MRA. The approximation theorem can be stated as follows:

Theorem 0.1:

(Approx. in Sobolev space) Let ϕϕ be a scaling function such that {ϕ(.-k),kZZ}{ϕ(.-k),kZZ} is an ONB and the corresponding spaces VjVj are nested. In addition, let ϕϕ be such that
| ϕ ( x ) | | x | N + 1 d x < , | ϕ ( x ) | | x | N + 1 d x < ,
(11)

and let at least one of the following assumptions hold:

  1. ϕ W q N ( I R ) for some 1 q < ϕ W q N ( I R ) for some 1 q <
    (12)
  2. xnψ(x)dx=0,n=0,1,...,N,xnψ(x)dx=0,n=0,1,...,N, where ψψ is the mother wavelet associated to ϕ.ϕ.

Then, if ff belongs to the Sobolev space WpN+1(IR),WpN+1(IR), we have:

| | P j f - f | | p = O ( 2 - j ( N + 1 ) ) , as j , | | P j f - f | | p = O ( 2 - j ( N + 1 ) ) , as j ,
(13)

where PjPj is the projection operator onto Vj.Vj.

Approximation of functions in Hölder spaces

Here we assume for simplicity that ψψ has compact support and is C[0.1ex]0.05em1.25ex1C[0.1ex]0.05em1.25ex1 (the formulation of the theorems are slightly different for more general ψψ).

Theorem:

If ff is Hölder continuous with exponent α,0<α<1α,0<α<1 at x0,x0, then
max k { | < f , ψ j , k > | d i s t ( x 0 , s u p p ( ψ j , k ) ) - α } = O ( 2 - j ( 1 / 2 + α ) ) max k { | < f , ψ j , k > | d i s t ( x 0 , s u p p ( ψ j , k ) ) - α } = O ( 2 - j ( 1 / 2 + α ) )
(14)

The reverse of theorem Theorem 1 does not exactly hold: we must modify condition Equation 14 slightly. More precisely, we have the following:

Theorem:

Define, for ϵ>0ϵ>0, the set
S ( x 0 , j , ϵ ) = { k Z Z | s u p p ( ψ j , k ) ] x 0 - ϵ , x 0 + ϵ [ } . S ( x 0 , j , ϵ ) = { k Z Z | s u p p ( ψ j , k ) ] x 0 - ϵ , x 0 + ϵ [ } .
(15)

If, for some ϵ>0ϵ>0 and some α(0<α<1),α(0<α<1),

max k S ( x 0 , j , ϵ ) | < f , ψ j , k > | = O ( 2 - j ( 1 / 2 + α ) ) , max k S ( x 0 , j , ϵ ) | < f , ψ j , k > | = O ( 2 - j ( 1 / 2 + α ) ) ,
(16)

then ff is Hölder continuous with exponent αα at x0.x0.

References

  1. C.K. Chui. (1992). An Introduction to Wavelets. San Diego, CA: American Press.
  2. I. Daubechies. (1992). Ten Lectures on wavelets. Philadelphia: Society for Industrial and Applied Mathematics.
  3. W. Härdle, G. Kerkyacharian, D. Picard, and A. Tsybekov. (1998). Wavelets, Approximation, and Statistical Applications. Lectures notes in Statistics.
  4. S. Mallat. (1989). A theory for multiresolution signal decomposition: the wavelet representation. I.E.E.E Trans. on pattern analysis and machine intelligence, 11(7), 674-693.
  5. Y. Meyer. (1990). Ondelettes et Opérateurs, I: Ondelettes, II:. Operateurs de Calderón-Zygmund.

Collection Navigation

Content actions

Download:

Collection as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Module as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Add:

Collection to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks

Module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks