# 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

price elasticity of demand is the degree of responsiveness of a quantity demanded to the change in price of the commodity in question.
what is the importance of learning economics?
it helps to make the correct choice
it helps firm to produce products that will bring more profit
the difference between needs and wants
needs are things that we basically can't live without wants are just luxury things
Thelma
needs are things without them we can't live but want are things without we can live
KP
what is education
KP
it's a process in which we give or receiving methodical instructions
Thelma
what is mixed economy
Amex
what is a deadweight loss? how monopoly creates a deadweight loss?
who are u?
Lamine
haha
Cleaford
scarm
nura
what it this
Cleaford
hi y'all
Dope
how does group chat help y'all 🤔
Dope
hi y'all
Dope
how does group chat help y'all 🤔
Dope
how does group chat help y'all 🤔
Dope
to learn from one another
Lamine
oh okay
Dope
😟
Creative
Yes
Lamine
what is type of economic
how to understand basics of economics
what is demand schedle
When you make a Scedule of the demand you made
Rodeen
this is helpful for rbi grade b
What is macroeconomics
It's one of the two branches of Economics that deal with the aggregate economy.
Mayen
it's about inflation, occupation, gdp and so on
alberto
What is differences between Microeconomics and Macroeconomic?
Bethrand
microeconomics focuses on the action of individual agents in the economy such as businesses, workers and household. while macroeconomics looks at the economy as a whole. it focuses on broad issues in the economy such as government deficit, economy growth, levels of exports and imports, and
Thelma
inflationary increase in prices
Thelma
a price floor of 24 imposed
monopolistic competition
yap
nura
any one there to answer my question
Fixed Costs per week Variable Costs per bear Rent & Rates of Factory Hire & machines Heating & Lighting Repayment of Bank Loan K100.00 K45.00 K5.00 K50.00 Materials Foam Wages K6.00 K1.00 K1.00 Total K200.00 K8.00
Richard
one of the scarce resources that constrain our behaviour is time. each of us has only 24 hours in a day. how do you go about allocating your time in a given day among completing alternatives? once you choose a most important use of time. why do you not spend all your time to it. use the notion of op
mohsina mala..Bangla app hobe na
mani Baba. First learn the spelling of Economics
Economics- The study of how people use their limited resources to tey and satisfy unlimited wants.
Kelly
hmmm
Mani
etar bangla apps hobe na?
Mohsina
in a comparison of the stages of meiosis to the stage of mitosis, which stages are unique to meiosis and which stages have the same event in botg meiosis and mitosis
Got questions? Join the online conversation and get instant answers!