### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Outline for MATH 4355 with Professor Bodmann at UH

### View Full Document

## 24

## 0

## Popular in Course

## Popular in Department

This 63 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Houston taught by a professor in Fall. Since its upload, it has received 24 views.

## Reviews for Outline for MATH 4355 with Professor Bodmann at UH

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 02/06/15

From Fourier to Wavelets in 60 Slides Bernhard G Bodmann M ath Depa rtment U H September 20 2008 rm HJHI Mn line 0 From Fourier to Filters 0 Inner product spaces 0 Fourier series 0 Fourier transform 0 Sampling and reconstruction 0 Convolution and filters 0 From analog to digital filters Wavelets 0 Haar wavelets 0 Multiresolution Analysis 0 The scaling relation 0 Properties of the scaling function and the wavelet o Decomposition and reconstruction 0 Wavelet design in the frequency domain 0 The Daubechies wavelet 0 Construction of the Daubechies wavelet Why wavelets The scoop about wavelets 0 Similar filtering capabilities as Fourier seriestransform o Adaptability to typical signals 0 Good for compression and denoising 0 Numerical implementation as fast as FFT 0 Wavelet design based on digital filters More information about analog digital conversion filtering wavelet design and applications in MATH 4355 Mathematics of Signal Representations From Fourier to Wavelets in 1 Semester in Spring 2009 NH iui ii llil Outline 0 From Fourier to Filters 0 Inner product spaces Fourier series Fourier transform Sampling and reconstruction Convolution and filters From analog to digital filters Inner Product Spaces The typical examples of vector spaces with an inner product are given by sequences or by functions A fundamental relationship between vectors in inner product spaces is orthogonality Definition Let 22 be the vector space of all bi infinite sequences X nez with 227 lxnl2 lt 00 For Xy 6 622 we define an inner product ltXygt Z Xn n7oo This means we can measure the length of a squaresummable sequence X the norm ltX7Xgt and an angle 9 between two non zero sequences X and y by 6050 lltX7Ygtlllelllll We call them orthogonal if ltXygt 0 HH iuHi Mu Trigonometric polynomials as inner product space An example for an inner product space of functions is given by all trigonometric polynomials convention i xil N V p 01 HOP Z ckeZWIkt7N EN all ck EC k7N equipped with the inner product 1 v W 0 vtWt dt An orthogonal pair of real valued polynomials Trigonometric polynomials from analog to digital Because of the orthogonality of complex exponentials the inner product of two trigonometric polynomials v and W is expressed in terms of their coefficients cakez and d kez as v Wgt Z ckdik keZ The space of sequences can be thought of as the space of digitized signals given by coefficients stored in a computer The function space of trig polynomials on the other hand can be thought of as a space of analog signals We havejust converted the inner product from an integral to a series from analog to digital without changing it llll iui ii llil Baa b We can make a more general type of function space by linear combinations of complex exponentials of the form eZWWb a Definition Let a7 b E R a lt b then we define L2a b f 3 b a c ft i ckeziiktbagt c 6 522 k7oo and for two such square integrable functions f and g we write b ltaggt timer Again the inner product of f and g can be rewritten as inner product of their coefficients in 622 ann iUH lulalhi Defin iti on Let V be a vector space with an inner product A set e17 e2 eN is called orthonormal if lleill 1 and lteejgt O for all i j We call e17 e2 eN an orthonormal basis for its linear span Given an infinite orthonormal set ennez we say that it is an orthonormal basis for all vectors obtained from summing the basis vectors with sq uare summable coefficients Definition Two subspaces V1 V2 are called orthogonal abbreviated V1 L V2 if all pairs X7 y with X 6 V1 and y 6 V2 are orthogonal mi lUHl mi Wm 1mm We consider two examples of subspaces of L2a7 b Example Let V0 be the complex subspace of L277r7r given by V0 fx 1 cosX l 2 sinx for 6162 6 C Then the set e17e2 e1x icosX and e2x w is an orthonormal basis for V0 sinx7 ann iUH inlalhi Another subspace of of L2O7 1 is the space of functions which are almost everywhere constant on 012 and 1271 It has the orthonormal basis gtzJ with 1 0 12 gtX1and1JX 717 1E 1 Such finite dimensional subspaces of L2a7 b are often chosen to specify approximations of signals ann iUH iniaihi Once we have orthonormal bases we can use them to expand vectors Let V0 be a subspace of an inner product space V and e17 e27 eN an orthonormal basis for V0 Then for all v 6 V0 N v Zltv7ekgtek kl What is the result irv v07 It turns out that 7 is the best you can get with a linear combination from 917 82 eN ogonal projections Let V0 be an inner product space V0 an N dimensional subspace With an orthonormal basis e17 e27 eN Then for v E V satisfies for all W0 6 V0 Since the difference vector v 7 i7 is orthogonal to V0 we call 7 the orthogonal projection of v onto V0 MN MW Mn Here is why the vector 7 is the best possible choice in the subspace V0 Let V0 be a finite dimensional subspace of an inner product space V Then for any v E V its orthogonal projection 7 onto V0 has the least squares property Hvi 17H min Hvi wiiz weVo Projection onto su b space of piecewise constant functions in L2071 iiii iUHi iiii Given V0 C L207r which has the orthonormal basis ek 1 of functions ek A X sinMx Compute the projection of the constant function fx C C ER onto V0 v This exercise amounts to computing the first N terms in the Fourier sine expansion of 1 We can include cosines choose the interval 77r77r and take N a 00 in order to get the Fourier series Theset m i M is an orthonormalset in L277r7 mi lUHl mi Wm 1mm Theorem Ifa function is given as a series fx 30 2ak coskx bk sinkx k1 Which converges With respect to the norm in L2739n397 then 1 7r 30 7 E 7 fxdx7 1 7r an 7 fx cosnxdx7 W W and 1 7r bn 7 fxsinnxdx 7r arm UH Matm Theorem Let f be square integrable on 771397 7139 then the partial sums of the Fourier series N NX a0 i zalt coskx i bk sinkx k1 converge in square mean to f Iim i in 7 5Nxi2dx 0 Naoo 4 Remark This is just convergence in the norm of L277r7r Other types of convergence can also be proved but they require more assumptions HH iUHi iiii Fourier Transform Definition and elementary properties ff 6 L2R then exists for almost all an E R that is up to a set which does not count under the integral Moreover f E L2R and again up to a set oft E R which does not count in integrals nn iUHi Mn When a function f E L277r7r is expanded in an orthonormal basis ejjgz f J6Zltfejgtej7 Pythagoras gives llfll2Zllt ejgtl2 jEZ A similar statement is true for the Fourier transform Theorem Plancherel Let f E L2R then denoting Ff we have llFlflll2 llfllz The same is true for inner products of g 6 EUR lt ggt ltFlfi7 Figh Transforming a signal from time to frequency domain preserves geometry inner products ann iUH lulalhi Proposition Let f h 6 EUR ht fbt for b gt 0 Then m g If 17 77r g t 7r at 7 07 else then ht fbt has the Fourier transform Haj sm rwb 7r LU Proposition Let f h 6 EUR ht ft 7 a for some a E R Then EM e iwam M NH Maiiii Definition A function f E L2R is called Q bandlimited if O for almost all ad with lwl gt Q Let f E L2R be Q bandlimited then it is continuous and and the series on the right hand side converges in the norm of L2R and uniformly on R um um Mann HQ Sampling and reconstruction in action 3 3 2 2 I I A 4D 75 m 4r 7 In lt 4 4 2 2 73 7 Cmm wtm mime Let g 6 L2R Then we denote the convolution of f and g by f gt 0 ft 7 Xgxdx Take 1 a7 0 g X g a gX 7 0 else 7 then for any integrable or squareintegrable f fgt ft 7 Xdx fxdx nn UHMaMH lm uIuirplieamim E Let f g be integrable functions on R Then f g is again integrable and Ffg x27rfg If in addition g 6 EUR then F 1fg fg 27r Convolving f with an integrable function g on R amounts to multiplying the Fourier transform f with x27rg i iUHlHlallil WQ Definition A filter on BUR is a linear map L L2R a L2R for which there is a bounded function In on R such that for all f E LZGR FLf m or equivalently Lf F 1mf The function In is called the system function of the filter Exercise Find the system function In for the filter Lft ft ft 7 a a e R HH iUH lwlalhi em 1 We now examine filtering for bandlimited signals Given a filter with a system function In and a bandlimited function f can we express the sampled values of Lf in terms of those of f Remark For filtering an Q bandlimited function only the restriction of the system function In to 799 matters because if vanishes outside of this interval We can thus expand min a Fourier series med 204keii7rkmQ7 keZ where we have changed the sign in the exponent because it is a series for a function on the frequency domain mi lUHl mi mew WIPE Given an Q bandlimited function f and a filter L With system function In Whose restriction to 79 Q has Fourier coefficients akkez Then Lag 2 milk 3073a 700 The upshot is that the convolution is replaced by a series formula for the sampled values of f Definition For two sequences Xy 6 22 we define the discrete convolution as 00 XYk Z XIYkil 700 l iUH Mallii Oversampling Since any function with band limit Q is also aQ bandlimited for any a 1 we have a generalization of the sampling theorem Proposition Let f be square integrable and Q bandmited Then 7 00 k7r sinaQt7 kn39 f 2 El aQti k7r 39 700 lfwe now apply a filter which has a system function such that mw 1 if lwl Q then ft Lft Z fLsincaQtikzr k7oo t where sinct M nn iUH inlalhi Since the requirement on the system function of L only concerns the interval 79 Q there is freedom in choosing L and thus the resulting function for reconstructing the signal This can be used to improve the convergence of the series used for reconstruction Let f be square integrable and Q bandimited Then k7r cosQ lm 39 7cos 39 lm 39 t 2 fl t 3371S2till7rE22 ll39 Note that for fixed 1 the series decays as k ann iUH lulalhi line 9 Wavelets 0 Haar wavelets 0 Multiresolution Analysis 0 The scaling relation 0 Properties of the scaling function and the wavelet o Decomposition and reconstruction 0 Wavelet design in the frequency domain 0 The Daubechies wavelet 0 Construction of the Daubechies wavelet Haar Wavelets Spaces of piecewise constant functions Functions that are constant on all intervals n7 n 1 n E Z can be written as fx Z amok k k7oo where 1 O 1 7 S X lt x 07 else Definition We define the space of squareintegrable integer wide step functions as 00 v0 fx Z ak gtx 7 k a 6 522 k7oo nn iUHi Mn Show that the translates 7 kk6z form an orthonormal basis for V0 Knowing the values of a function f at one point in each interval k7 k 1 determines the function completely How can we have a function space with more details Take 212 gt2X7 kk6z as an orthonormal basis instead of gtX kkeZ i iUHlHlalhi Wm IWQ Definition The space of square integrable step functions of width 2 1 denoted by V is the subspace of L2R with the orthonormal basis 2 72 gt2quotX kkeZ Functions in this space have possible discontinuities at X 2 jk k E Z This implies that sampling the function values at 2 evenly spaced points in the interval k7 k 1 determines the function on this interval We also note that forj gt 0 we have the inclusions V C V4 C C VoC V1CC Vjslc VJC VH1 i iuH Maw mm Proposition For any square integrable function f f 6 V0 if and only iff2lx E or equivalently f E ifand only if f2 lx 6 V0 Is there an orthonormal basis for layers of detail We would like to have a basis of translates for V1 Vol Try 1W gt2X 7 gt2X 1 1 X Xdx 0121dx 7 1121dx O and because 1 is supported in 01 it is orthogonal to all gtX k then nn iUH lwlaihi Detail spaces Indeed the translates of 1 form a basis for the detail spaces that bridge between V0 and V1 More generally we can define a subspace of VH1 which is orthogonal to Let be the span ofall functions in L2R such that fx 2 may 7 k keZ Then VJL VH1 ann lUH Malhl Haar decomposition Stripping layers of detail Now we can perform a recursive splitting Each E is expressed uniquely as the sum 639 W14 63971 where Wj1 E Wj1 and 61 6 Vj1 This orthogonal splitting is abbreviated by VJ W14 69 V171 Iterating the splitting gives Vj W14 69 W14 69 V14 and so on rm iuHi Mu Ifwe etj a 00 and keep the last term in this direct sum decomposition fixed say V0 then we obtain a unique representation of each vector as a series of vectors from j 2 0 and V0 For each f 6 EUR denote by Wj the orthogonal projection off onto Then 00 f f0 Z 039 j0 With vectors that are orthogonal and a series that converges in norm In short BUR V0W0W1W2 MN MW Mu Suppose we have Zkez ak gt2jx 7 k given by the values 3k How do we compute the coefficients with respect to the orthonormal basis of given by gtX kkeZ and 212W21X kkeZ0 gj717 L em in a For the Haar scaling function 1 and the wavelet 11 gt2quotX w2quot 1x WW and gtlt2jx 71 goal71x WW So we can 39use this to convert 2k ak gt2jx 7 k E into Ziame e k dkw2 1x e k nn iUH iniaihi Given a square integrable function 2k ag 2jx 7 k then 600 Z bE WQHX e k Zalj lw lx e k k k With bj71 7 3 agji31 k 2 and 0 0 a171 7 azjk azjk1 k 7 2 We note that both of these expressions are obtained from a digital filter applied to al lheg We can repeat this procedure iteratively to obtain a coefficient tree containing blinkezi bgill g bg72kgz and finally ems HH iUH Mallii Can we reverse this procedure that is reconstruct the coefficients 353 from bg71kez bg72kez 17506Z and 3506Z in this coefficient tree We can reverse the decomposition by 11 3g by and I 1 I I a2 7 by and iterate this procedure mi iUHi mi Wm Definition For any sequence Xkkez and hkkez both in 22 we define the digitaldiscrete filter of X by HXlt hxk Zxk hn HEZ Definition The downsampling operator D acts on a square summable sequence XkkeZ by DXk ng i iUHMaMii WW With these two operations we can express the analysis and reconstruction algorithm Let 1 1 h 70707 0777 7 00 7 2 2K7 7 k0 and let 1 1 I 7 7 00 702 2 00 V k0 Then 1 1 HXIlt hXk Xk 7 XkJrl 2 2 and 1 1 LXIlt IXk Exk i Expa ann iUH Marni Therefore 7 1 by v 5982 a aging mam and I I 3571 DLaJk The reconstruction algorithm can also be cast in a similar form if we define the upsampling operator Definition The upsampling operator U acts on a square summable sequence Xkkez by 7 XkZ keven Uxk 0 kodd i iUH iniaihi Let FI and I be given by E0000 1710 V k0 and let I0000 110 f k0 Thus 3039 ZUaW UbW rm UH Ma39m Wavelet decomposition and reconstruction with filters Split detail from lower resolution level by DHajk and I I 3571 DLaJk Fuse lower resolution and detail level aw maven marl rm iUH l lv3llll Application step detection If a function f E is slowly changing except for finitely many discontinuities then applying the decomposition shows that only wavelet coefficients bgill near discontinuities are large Comparison Signal vs wavelet coefficients rm iUHl Mn For piecewise constant functions many coefficients would be exactly zero ie can be discarded Only need to store detail coefficients close to steps and coefficients for low resolution level everywhere Note Downsampling reduces data by factor 2 in each decomposition step Compression Question Is there a version of j 1 which will compress piecewise quadraticcubicetc functions similarly The family of Daubechies wavelets have the desired property l m lUHl mi Wm Mm WW and Definition Let be a family of subspaces in EUR such that any Cauchy sequence in each converges Then is called a multiresolution analysis if the following properties hold 0 ljC VH1 foralleZ 9 L2R union is dense 3 m4 0 9 f6 VJlt gt f2 jx 6 V0 9 There is j 6 V0 such that gtX7 kk6z is an orthonormal basis for V0 Each is called an approximation subspace The resulting W VJL VH1 are called detail spaces ann um Mam 2mm In short MRAs have decomposition and reconstruction algorithms like the Haar wavelet transform As first example of a multiresolution analysis we note that the Haar scaling function satisfied the required properties A second example of a multiresolution analysis is given by the approximation spaces which consist of 2J7r bandlimited functions v f 6 Ban m 0 for all lwl gt 2j7r The Daubechies construction is in between these two examples HH iuHi Mu The seaming IfJ is a multiresolution analysis With scaling function 1 then there is a sequence p kez 6 22 such that for almost evetyx E R gtx 2 mm 7 k keZ and pk 2 100 gtX gt2X 7 kdx For the Haar MRA p0 pl 1 and all other pj are zero I rm iUH MaMH 11762 The seaming IfJ is a multiresolution analysis With scaling function 1 then there is a sequence p kez 6 22 such that for almost evetyx E R gtx 2 mm 7 k keZ and pk 2 100 gtX gt2X 7 kdx For the Haar MRA p0 pl 1 and all other pj are zero I rm iUH MaMH 11762 Problem Find scaling coef cients p kez that belong to MRAs Design MRAs With special properties such as smooth scaling functions compactly supported ones etc Strategy It will become apparent that the frequency domain formulation is convenient for such problems To this end we examine the two scale relation We use the notation 1 7 W0 5 2 pie k keZ or Pz Zpkzk keZ TWQ Theorem If the integer translates of gt E L2R form an orthonormal set and gtX Zkez pk gt2x 7 k then Pz satisfies the quadrature mirror property WIN W ZNZ 17 iZi1 Example Haar M RA For Pz 1 2 MH we obtain for 2 1 that 1 1 PZ2 PFZNZ 1Z21Z2 122Z2 1 nn UH MaMH The next theorem addresses is whether the quadraturemirror property of Pz is enough to create a scaling function 1 for an MRA Given Pz 2k pkzk With a summable sequence pk satisfying 0 P1 1 9 iF Zi2 iF Zi2 17izi 1 9 iPeiti gt 07 iti 7r2 then the iteration gtnx Z pmslex 7 k k starting With the Haar scaling function o0 converges to the scaling function 1 ofan MRA i iUH i iv3iiii The Daubechies wavelet Vanishing moments Suppose we are given an MRA with summable scaling coefficients pkkez which satisfy the three properties on the preceding slide Proposition A wavelet 11 is obtained by or alternatively With HH iUH Maihi If 1 is integrable then g M and WEN MlQe 2l This means ifQe i 2 has vanishing derivatives at E 0 then so does 11 For example assuming 130 0 then we can conclude 11JXdx X11Xdx 0 Consequently any function which is linear on the support of 1 fx ax l b for all X where 1X 7 0 gives vanishing wavelet coefficients 1 fxzpxdx 0 mi iUH l lv3llll Compression Wavelet coefficients for a piecewise linear signal If the wavelet has a vanishing first moment then the coefficients are zero where the signal is linear a mu is m a 1m n iUHl Mn Construction of the Daubechies wavelet Try the simplest case first a polynomial P Problem Find a polynomial P such that P P0946 has the following properties 0 p0 1 9 WSW WE 7W 1 9 p gt O for 77r2 S E 7r2 and the associated 1 has vanishing zeroth and first moments nn UH MaMH The polynomial 1 3 84 37 2i 17 P35 8 8 8 8 is an example which belongs to the Daubechies wavelet arm lUH Mallll The Daubechies wavelet 1i is continuous and has vanishing zeroth and first moments 11JXdx X11Xdx 0 Beyond 60 slides o Daubechies wavelets for piecewise quadratic cubic etc can also be found a More generally given a space of typical signals we can find wavelets which mimic signal properties and are most efficient for decomposition denoising and compression 0 Wavelets in higher dimensions stay tuned o Wavelets and oversampling Ditto o More detail Fourier and wavelets in smaller portions MATH 4355 Mathematics of Signal Representations Spring 2009 HH iuHi Mu Literature 0 Boggess and Narcowich A First Course in Wavelets with Fourier Analysis Prentice Hall 2001 o Mallat A Wavelet Tour of Signal Processing Academic Press 1999 o Wojtaszczyk A Mathematical Introduction to Wavelets Cambridge University Press 1997 o Weiss and Hernandez A First Course on Wavelets CRC Press 1996 ann iUH l lv3llll

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.