# 0.16 Nonlinear approximation and wavelet analysis  (Page 2/2)

 Page 2 / 2

Suppose $f$ is piecewise Lipschitz and ${f}_{k}$ ia a piecewise constant.

$|f\left(t\right)-{f}_{k}\left(t\right)|\approx \Delta$

where $\Delta$ is a constant equal to average of $f$ on right and left side of discontinuity in this interval.

$⇒||f-{f}_{k}{||}_{{L}_{2}}^{2}=O\left({k}^{-1}\right)$

where ${k}^{-1}$ is the width of the interval. Notice this rate is quite slow.

This problem naturally suggests the following remedy: use very small intervals near discontinuities and larger intervals insmooth regions. Specifically, suppose we use intervals of width ${k}^{-2\alpha }$ to contain the discontinuities and the intervals ofwidth ${k}^{-1}$ elsewhere. Then accordingly piecewise polynomial approximation ${\stackrel{˜}{f}}_{k}$ satisfies

$||f-{\stackrel{˜}{f}}_{k}{||}_{{L}_{2}}^{2}=O\left({k}^{-2\alpha }\right).$

We can accomplish this need for "adaptive resolution" or "multiresolution" using recursive partitions and trees.

## Recursive dyadic partitions

We discussed this idea already in our examination of classification trees. Here is the basic idea again, graphically.

Consider a function $f\in {B}^{\alpha }\left({C}_{\alpha }\right)$ that contains no more than m points of discontinuity, and is ${H}^{\alpha }\left({C}_{\alpha }\right)$ away from these points.

Lemma

Consider a complete RDP with n intervals, then there exists anassociated pruned RDP with $O\left(klogn\right)$ intervals, such that an associated piecewise degree $⌈\alpha ⌉$ polynomial approximation $\stackrel{˜}{\left(}{f\right)}_{k}$ , has a squared approximation error of $O\left(min\left({k}^{-2\alpha },{n}^{-1}\right)\right)$ .

Assume $n>k>m$ . Divide $\left[0,1\right]$ into $k$ intervals. If $f$ is smooth on a particular interval $I$ , then

$|f\left(t\right)-{\stackrel{˜}{f}}_{k}\left(t\right)|=O\left({k}^{-2\alpha }\right)\forall t\in I.$

In intervals that contain a discontinuity, recursively subdivide into two until the discontinuity is contained in an interval ofwidth ${n}^{-1}$ . This process results in at most $lo{g}_{2}n$ addition subintervals per discontinuity, and the squared approximationerror is $O\left(k-2\alpha \right)$ on all of them accept the $m$ intervals of width ${n}^{-1}$ containing the discontinuities where the error is $O\left(1\right)$ at each point.

Thus, the overall squared ${L}_{2}$ norm is

$||f-{\stackrel{˜}{f}}_{k}{||}_{{L}_{2}}^{2}=O\left(min\left({k}^{-2\alpha },{n}^{-1}\right)\right)$

and there are at most $k+lo{g}_{2}n$ intervals in the partition. Since k>m, we can upperbound the number of intervals by $2klo{g}_{2}n$ .

Note that if the initial complete RDP has $n\approx {k}^{2\alpha }$ intervals, then the squared error is $O\left({k}^{-2\alpha }\right)$ .

Thus, we only incur a factor of $2\alpha logk$ additional leafs and achieve the same overall approximation error as in the ${H}^{\alpha }\left({C}_{\alpha }\right)$ case. We will see that this is a small price to pay in order to handle not only smooth functions, but alsopiecewise smooth functions.

## Wavelet approximations

Let $f\in {L}^{2}\left(\left[0,1\right]\right)$ ; $\int {f}^{2}\left(t\right)dt<\infty$ .

A wavelet approximation is a series of the form

$f={c}_{o}+\sum _{j\ge 0}\sum _{k=1}^{{2}^{j}}{\psi }_{j,k}$

where ${c}_{o}$ is a constant $\left({c}_{o}={\int }_{0}^{1}f\left(t\right)dt\right)$ ,

$={\int }_{0}^{1}f\left(t\right){\psi }_{j,k}\left(t\right)dt$

and the basis functions ${\psi }_{j,k}$ are orthonormal, oscillatory signals, each with an associated scale ${2}^{-j}$ and position $k{2}^{-j}$ . ${\psi }_{j,k}$ is called the wavelet at scale ${2}^{-j}$ and position $k{2}^{-j}$ .

## Haar wavelets

${\psi }_{j,k}\left(t\right)={2}^{j/2}\left({\mathbf{1}}_{\left\{t\in \left[{2}^{-j}\left(k-1\right),{2}^{-j}\left(k-1/2\right)\right]\right\}}-{\mathbf{1}}_{\left\{t\in \left[{2}^{-j}\left(k-1/2\right),{2}^{-j}k\right]\right\}}\right)$
${\int }_{0}^{1}{\psi }_{j,k}\left(t\right)dt=0$
${\int }_{0}^{1}{\psi }_{j,k}^{2}\left(t\right)dt={\int }_{\left(k-1\right){2}^{-j}}^{k{2}^{-j}}{2}^{j}dt=1$
${\int }_{0}^{1}{\psi }_{j,k}\left(t\right){\psi }_{l,m}\left(t\right)dt={\delta }_{j,l}.{\delta }_{k,m}$
If $f$ is constant on $\left[{2}^{-j}\left(k-1\right),{2}^{-j}k\right]$ , then
$\int f{\psi }_{j,k}\left(t\right)=0.$

Suppose $f$ is piecewise constant with at most $m$ discontinuities. Let

${f}_{J}={c}_{o}+\sum _{j=0}^{J-1}\sum _{k=1}^{{2}^{j}}{\psi }_{j,k}.$

Then, ${f}_{J}$ has at most $mJ$ non-zero wavelet coefficients; i.e., $=0$ for all but $mJ$ terms, since at most one Haar Wavelet at each scale senses each point of discontinuity. Said another way, allbut at most $m$ of the wavelets at each scale have support over constant regions of $f$ .

${f}_{J}$ itself will be piecewise constant with discontinuities only possible occurring at end points of the intervals $\left[{2}^{-J}\left(k-1\right),{2}^{-J}k\right]$ . Therefore, in this case

$||f-{f}_{J}{||}_{{L}_{2}}^{2}=O\left({2}^{-J}\right).$

Daubechies wavelets are the extension of the Haar wavelet idea. Haar wavelets have one "vanishing moment":

${\int }_{0}^{1}{\psi }_{j,k}=0.$

Daubechies wavelets are "smoother" basis functions with extra vanishing moments. The Daubechies- $N$ wavelet has $N$ vanishing moments.

${\int }_{0}^{1}{t}^{l}{\psi }_{j,k}dt=0forl=0,1,...,N-1.$

The Daubechies-1 wavelet is just the Haar case.

If $f$ is a piecewise degree $\le N$ polynomial with at most m pieces, then using the Daubechies- $N$ wavelet system.

$||f-{f}_{J}{||}_{{L}_{2}}^{2}=O\left({2}^{-J}\right);$

and

${f}_{J}\left(t\right)={c}_{o}+\sum _{j=0}^{J-1}\sum _{k=1}^{{2}^{j}}{\psi }_{j,k}\left(t\right)$

has at most $O\left(mJ\right)$ non-zero wavelet coefficients. ${f}_{J}$ is called the Discrete Wavelet Transform (DWT) approximation of $f$ . The key idea is the same as we saw with trees.

## Sampled data

We can also use DWT's to analyze and represent discrete, sampled functions. Suppose,

$\underline{f}=\left[f\left(1/n\right),f\left(2/n\right),...,f\left(n/n\right)\right]$

then we can write $\underline{f}$ as

$\underline{f}={c}_{o}+\sum _{j=0}^{lo{g}_{2}n-1}\sum _{k=1}^{{2}^{j}}<\underline{f},{\underline{\psi }}_{j,k}>{\underline{\psi }}_{j,k}$

where

${\underline{\psi }}_{j,k}=\left[{\psi }_{j,k}\left(1\right),{\psi }_{j,k}\left(2\right),...,{\psi }_{j,k}\left(n\right)\right]$

is a discrete time analog of the continuous time wavelets we considered before. In particular,

$\sum _{i=1}^{n}{i}^{l}{\psi }_{j,k}\left(i\right)=0,l=0,1,...,N-1$

for the Daubechies- $N$ discrete wavelets.

$<\underline{f},{\underline{\psi }}_{j,k}>={\underline{f}}^{T}{\underline{\psi }}_{j,k}$

Thus, we also have an analogous approximation result: If $\underline{f}$ are samples from a piecewise degree $\le N$ polynomial function with a finite number $m$ of discontinuities, then $\underline{f}$ has $O\left(mJ\right)$ non-zero wavelet coefficients.

## ApproximatingFunctions with wavelets

Suppose $f\in {B}^{\alpha }\left({C}_{\alpha }\right)$ and has a finite number of discontinuities. Let ${f}_{p}$ denote piecewise degree- $N\left(N=⌈\alpha ⌉\right)$ polynomial approximation to $f$ with $O\left(k\right)$ pieces; a uniform partition into $k$ equal length intervals followed by addition splits at the points of discontinuity.

Then

$|f\left(t\right)-{f}_{p}\left(t\right){|}^{2}=O\left({k}^{\left(}-2\alpha \right)\right)\forall t\in \left[0,1\right]$
$⇒|f\left(i/n\right)-{f}_{p}{\left(i/n\right)|}^{2}=O\left({k}^{-2\alpha }\right)i=1,...,n$
$⇒1/n||\underline{f}-{\underline{f}}_{p}{||}_{{L}_{2}}^{2}=O\left({k}^{-2\alpha }\right)\right)$

and ${\underline{f}}_{p}$ has $O\left(klo{g}_{2}n\right)$ non-zero coefficients according to our previous analysis.

## Wavelets in 2-d

Suppose $f$ is a 2-D image that is piecewise polynomial:

A pruned RDP of $k$ squares decorated with polyfits gives

$||f-{f}_{k}{||}_{{L}_{2}}^{2}=O\left({k}^{-1}\right).$

Let $\underline{f}{=\left[f\left(i/k,j/k\right)}_{i,j=1}^{n}$ sample range.

${f}_{n}\left(t\right)=\sum _{i,j=1}^{k}f\left(i/k,j/kk\right){\mathbf{1}}_{\left\{t\in \left[i-1/k,i/k\right)x\left[j-1/k,j/k\right)\right\}}$

then

$||f-{f}_{n}{||}_{{L}_{2}}^{2}=O\left({k}^{-1}\right)$

$O\left(1\right)$ error on $k$ of the ${k}^{2}$ pixels, near zero elsewhere. The DWT of $\underline{f}$ has $O\left(k\right)$ non-zero wavelet coefficients. $O\left({2}^{j}\right)$ at scale ${2}^{-j},j=0,1,...,logn.$

#### Questions & Answers

why one should read psychology
MAMATA Reply
cause of daibites is?
Suman
memory of development brain of the human psychologist
SERAJ Reply
?
lord
hlo
Ananya
Haw are you?
Shilan
hi
zge
hello
Emm
usef
hi
Gil
Haw are you?
Shilan
Aha ok
Shilan
hi
Daniella
waasup
Isaiah
hello
Sara
hello
androi
Haw are you
Shilan
im ok you
Daniella
Me to
Shilan
Thanks
Shilan
What's going?
Shilan
working
Daniella
hey everyone this Mahmoud
Mahmoud
is
Mahmoud
Fine
Shilan
Hello
Jobe
how is it going people?
Tomasz
kind
Alter
thanks
Alter
hi..!
Alter
yes we'll
Alter
yes we'll
Alter
hi
Suman
hi
Raynard
how did psychology begin?
Valerie Reply
of psychologys commencement, the traces can be seen in the work of Aristotle, where he talk about soul and body, likewise work in durrant, de anima, all these were somewhere supporting dualism, in which soul could exist separately from body
amaan
but if you talk about the moder psychology, Gustav fechner, is credited with performing scientific experiments, basis of his experiments in psychology with his studies perception.
amaan
hi, can you help me to find research related to child truma
Heba
yes same here I have cptsd and am looking for more info since my doctor doesn't know what to do I want to know what I can
Mark
does psychology deal with love?
Mohammed Reply
Maybe, i think
edem
I definitely would say yes
Clara
how so
Isaiah
*triarchic
Meredith
there are so many different reasons why you can fall in love with someone, many of them develope subconsciously -> psychology
Clara
love messes with the brain, a lot, ergo I believe that Psychology does indeed deal with love
I would like an example as to what and how you think it deals with.
Tyler
how can I discover that this individual has a long-term memory and shot- term memory?
Namuaha
what is synapse
Katie Reply
In the central nervous system, a synapse is a small gap at the end of a neuron that allows a signal to pass from one neuron to the next. synapse are found where nerve cells connect with other nerve cells
Najeem
a synapse the connection is where a neuron cell connects to another neuron cell.
Shaun
good
Jobe
what is psychology
Jobe
can you do auto book auto
Mariah Reply
WHT u mean?
usef
yes
MD
heyy, may i join the conversation please?
edem Reply
yes of course
Najeem
how to avoid theory of bias confirmation in real life
Scar
yes
Jobe
hello
Bhavin
hello to all
Genevieve
hey, may I join the conversation?
samra
salaam
Ibrahim
so i cn even do this after ba hons in psychology?
Avneet
the only eligibility criteria is that you should have 50% of aggregate in your psychology papers. (bachelors)
syeda
okay thank you so much❤ have a lovely day🙂
Avneet
you're welcome. glad it helped ^_^
syeda
To pursue a career as a psychotherapist you'll have to do your bachelors in psychology. (bsc honors is preferable). since there are many fields and you've chosen as a therapist. a masters degree in clinical psychology or therapy and family counseling is preferable.
syeda
so i cn even do this after ba hons in psychology?
Avneet
yes you can.
syeda
you're welcome. glad it helped ^_^
syeda
hello
Vhikkie
yh
Parker
hello
Avneet
is there any psychotherapist here? i need to know the qualification one hve to pursue.
Avneet
I'm clinic psychologist...
Shilan
Hey. I'm pursuing BA in Clinical Psychology
Aakarshan
the only eligibility criteria is that you should have 50% of aggregate in your psychology papers. (bachelors)
syeda
hello
Vhikkie
who is the father of psychology
Richy Reply
aristatil
Ramadevi
and please, how would you guys, describe the study of psychology at college ?
edem
psychologist student?
Aspen
i mean not yet but am about to start college so wanna know how is it(college in general and psychology course) please
edem
Psychology is the study of mind and behaviour. So if you will take psychology as a subject so you will get to know how your everything (physical, mental, social, spiritual aspects) effects your behaviour
sakina
With this brief knowledge you can help people to cope up with their problems and only you can guide them correctly
sakina
And if you go for further specialisations you can study hypnosis, face reading, body language etc
sakina
Thanks a lot🙏🏾 And ik some of the stuffs u said but i am also going to write thesis, right ?
edem
ok no prob, thanks a lot🙏🏾✨
edem
cerebellum
Khan
hae everyone, hope you are well this evning my question is what is the difference between drive and motivation
Michael
good question
Rainee
drive is more like an impulse or urge and i think they both go together (drive and motivation) even if there is a slight difference
edem
@ Michael Drive is delivered to be innate without the use of an external stimuli, motivation normally evolves an outside stimuli which may include praise, appreciate, or reward.
Reginald
*believed...sorry for typo
Reginald
@Reginald, can't the motivation come from the inner self?
edem
Good question, please give an example.
Reginald
can we say desire of success for example
edem
Wilhelm Wundt is the father of psychology
ipau
Wilhem Wundt thank you for the road that you opened.
Qwanta
You mean who is the father of having a great educated argumentative guess? nothing is more wrong than this question. The question is you should ask yourselfs is, how sure are you abour their scientific studying? one's percieved assimilated approach to judging another person and saying they are
Roger
the biggest problem with scientific research and data is that ya you could get the same result 1000 times then it could go the other way 1000 times, but we would never know that and we did, we would still say ya but the proof is there. The only thing science proves is that humanity has
Roger
no facts about human behavior in the scientific context, but more in the trial and error.. sorry to tell you, but so far no one has proven Father of anything, thats up to you and i, judgement is bias, science is good enough lazy
Roger
cognitive development is the growing and development of the brain.
Jessy Reply
Anyone knows about Techno-fascism?
Hussein Reply
Ecofascism is a theoretical political model in which an authoritarian government would require individuals to sacrifice their own interests to the "organic whole of nature". The term is also used as a rhetorical pejorative to undermine the environmental movement.
ipau
what's the big difference between prejudice and discrimination?
Danice Reply
A prejudiced person may not act on their attitude.  Therefore, someone can be prejudiced towards a certain group but not discriminate against them.  Also, prejudice includes all three components of an attitude (affective, behavioral and cognitive), whereas discrimination just involves behavior
Nancy Lee
hi
basher
hello
Rahul
what is all about cognitive development?
Kamohelo
cognitive development is the growing and development of the brain
Jessy
how do you control a variable when using spss whilst running a pearsons correlation analysis?
Jessie Reply
it dependa on your study. according to what you want to say and explain your result
Pouran
Hello
Jobe
why does it say her and she
Jayla Reply
stages of cognitive development
brivia Reply
sensory preoperatinal concrete formal
Rajendra
What's mental memory?
Namuaha
Memory is our ability to encode, store, retain and subsequently recall information and past experiences in the human brain. It can be thought of in general terms as the use of past experience to affect or influence current behaviour.
Shilan
What I mental memory?
Namuaha
What's mental memory?
Namuaha
my thankful
Namuaha
Shilan I love your definition
Jobe
what is psychology
Chethani Reply
the study of insecurities and the effect on the host .
Sera
Psychology is the scientific study of behavior & mental processes
Angela
psychology is science about learning human behaviour
Zhamshid
behaviorosm
Khan
is the study of human behaviour and mental processes
Jobe
Got questions? Join the online conversation and get instant answers!
Jobilize.com Reply

### Read also:

#### Get the best Algebra and trigonometry course in your pocket!

Source:  OpenStax, Statistical learning theory. OpenStax CNX. Apr 10, 2009 Download for free at http://cnx.org/content/col10532/1.3
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Statistical learning theory' conversation and receive update notifications?

 By By Qqq Qqq