### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Math of Signal Representation MATH 4355

UH

GPA 3.69

### View Full Document

## 51

## 0

## Popular in Course

## Popular in Mathmatics

This 62 page Class Notes was uploaded by Alvena McDermott on Saturday September 19, 2015. The Class Notes belongs to MATH 4355 at University of Houston taught by Bernhard Bodmann in Fall. Since its upload, it has received 51 views. For similar materials see /class/208378/math-4355-university-of-houston in Mathmatics at University of Houston.

## Reviews for Math of Signal Representation

### 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: 09/19/15

From Fourier to Wavelets in 60 Slides Bernhard G Bodmann M ath Depa rtment U H Septem ber 20 2008 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 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 I l Why wavelets The scoop about wavelets 0 Similar filtering capabilities as Fourier seriestransform a 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 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 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 lltX7YgtlllelllYll We call them orthogonal if ltXygt 0 I l 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 An orthogonal pair of real valued polynomials A nearly collinear pair of 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 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 k7oo L2a b f 3 b a c ft Z ckeziiktbagt c 6 522 and for two such square integrable functions f and g we write b 7 ltaggt ftgtdt Again the inner product of f and g can be rewritten as inner product of their coefficients in 622 I l Definition 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 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 I mm 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 w l cosX and e2x isinx e1 X is an orthonormal basis for V0 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 I l Once we have orthonormal bases we can use them to expand vectors Theorem 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 k1 What is the result ltgt ll M2 V7 ekgtek ll irv v07 It turns out that 7 is the best you can get with a linear combination from 917 82 eN I l Orthogonal 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 N 7 v7 ekgteilt quot1 J satisfies ltV 77 W0gt 0 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 I l Here is why the vector 7 is the best possibleH 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 07 1 I mm ratz I Given V0 C L207r which has the orthonormal basis ek 1 of functions ekx sinUa Compute the projection of the constant function fx C C ER onto V0 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 The set Lsgxl L320 Ly Lg in L277r7 is an orthonormal set Theorem Ifa function is given as a series fx 30 2ak coskx bk sinkx k1 Which converges With respect to the norm in L277r7r then 1 7r 30i 27139 W fxdx7 an fxcosnxdx7 7r W and bn fxsinnxdx I l Let f be square integrable on 771397 7139 then the partial sums of the Fourier series N NX a0 i 2ak coskx i bk sinkx k1 converge in square mean to f Allian in 7 5Nxi2dx 0 This is just convergence in the norm of L277r7r Other types of convergence can also be proved but they require more assumptions I 39mm Fourier Transform Definition and elementary properties ff 6 L2R then A 1 L f w Iim 7 ft e tdt W TwiL exists for almost all w E R that is up to a set which does not count under the integral Moreover f E L2R and 1 Q iwt ft igll nOOEi w dw7 again up to a set off 6 R Which does not count in integrals When a function f E L277r7r is expanded in an orthonormal basis ejjgz f J6Zltfejgtej7 Pythagoras gives llfll2Zllt 81W jEZ A similar statement is true for the Fourier transform Theorem Plancherel Let f E L2R then denoting Ff we have llFlflll2 llfllzv 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 I l Let f h 6 L2 ht fbt for b gt 0 Then m 13g ft l7 iw t n 07 else then ht fbt has the Fourier transform m Let f h 6 EUR ht ft 7 a for some a E R Then m mam 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 z k7oo and the series on the right hand side converges in the norm of L2R and uniformly on R Sampling and reconstruction in action emit ltmg Bi ffiij iiio 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 07 else then for any integrable or squareintegrable f fgt ft 7 Xdx fxdx I mm Convolution as multiplication of Fourier transforms Let f g be integrable functions on R Then f g is again integrable and Ffg x27rfg If in addition g 6 EUR then F1g r g Convolving f with an integrable function g on R amounts to multiplying the Fourier transform f with x27rg 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 3 ER i 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 For filtering an Q bandlimited function only the restriction of the system function In to 799 matters because f vanishes outside of this interval We can thus expand min a Fourier series med Z akeiinkwQ7 keZ where we have changed the sign in the exponent because it is a series for a function on the frequency domain I am 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 1170 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 oo XYk Z XIYkilv 700 Oversampling Since any function with band limit Q is also aQ bandlimited for any a 1 we have a generalization of the sampling theorem Let f be square integrable and Q bandmited Then 7 00 k7r sinaQtik7r 01 El aQtikIr 39 lfwe now apply a filter which has a system function such that mw 1 if lwl Q then 00 Gr I ft Lft kg HEXLschaQt 7 kw where sinct I l 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 00 k7r cosQ lm 39 icosaQ lm 39 f 00 t 3371S2till7rES22 Note that for fixed 1 the series decays as k e 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 I l Haar Wavelets Spaces of piecewise constant functions Functions that are constant on all intervals n7 n 1 n E Z can be written as 00 fx Z amok k k7oo where O Xltl else Definition We define the space of squareintegrable integer wide step functions as v0 fx Z ak gtx 7 k a 6 522 k7oo 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 gt2fo7 kk6z as an orthonormal basis instead of gtX kkeZ I wm Definition The space of square integrable step functions of width 2 1 denoted by 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 V7 C V4 C C VoC V1 CC Vjsl C C VHl 341 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 gtXzJXdx 0121dX71121dx O and because 1 is supported in 01 it is orthogonal to all gtX7 k then I l 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 Z amw x 7 k keZ Then VJL VH1 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 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 E LZGR denote by Wj the orthogonal projection off onto ff0ZlVj 10 With vectors that are orthogonal and a series that converges in norm In Then short BUR V0W0W1W2 Suppose we have Zkez ak gt2X 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 Lemma For the Haar scaling function 1 and the wavelet 11 gt2quotX w2quot 1x WW gtlt2jx 71 aw 2quot 1x So we can 39use this to convert 2k ak gt2jx 7 k E into micmeme k dkw2 1x a k I i Given a square integrable function ZR ag 2jx 7 k then 600 Z bE WQHX e k Zali lw lx e k k k With I I boa 7 azjk 32Jk1 k 7 2 and 0 0 a171 7 azjk azjk1 k 7 2 39 We note that both of these expressions are obtained from a digital filter applied to 3 Z We can repeat this procedure iteratively to obtain a coefficient tree containing blinkezi bgill g bg72kgz and finally ems I l 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 a3 a9 by and I 1 I I 8amp1 at 7 bi and iterate this procedure 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 ma With these two operations we can express the analysis and reconstruction algorithm Let 1 1 h 7007077700 7 77 2727 77 k0 andlet 1 1 I 00 07 7 00 77272777 V k0 Then 1 1 Hxk hxk Exk 7 Exk and 1 1 LXkIXk Xk Xk1 I l Therefore 1 71 bi ag a 2 DHaW and I I 3571 DLaJk The reconstruction algorithm can also be cast in a similar form if we define the upsampling operator The upsampling operator U acts on a square summable sequence Xkkez by 7 XkZ keven Uxk 0 kodd Let FI and I be given by E0000 1 71 0 V7 77 k0 andlet IOOOO7 171707 f k0 Thus 3039 13071 UbUAX 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 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 bgil near discontinuities are large Comparison Signal vs Lllldlll h Hm Ht l J l i H wavelet roefFIripnt nurer m H y n i y Hm I u 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 Is there a version of j 1 which will compress piecewise quadraticcubicetc functions similarly a c n gt 39 eolltxn A ma 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 9 ljC VH1 foralleZ UJVJ L2R union is dense m4 0 f 6 VJ lt gt f2 jx 6 V0 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 9900 I mm 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 The rmg 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 mm Find scaling coef cients pdkez that belong to MRAs Design MRAs With special properties such as smooth scaling functions compactly supported ones etc 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 pw 5 2 pie k keZ l Pz E Zpkzk keZ 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 iPZi2 W ZNZ 17 iZi1 Example Haar MRA For 1 Pz 51 z we obtain for 2 1 that 1 1 PZ2 PFZNZ 1Z2 iliziz 122Z2 1 The next theorem addresses is whether the quadraturemirror property of Pz is enough to create a scaling function 1 for an MRA Given Pz Zk pkzk With a summable sequence pk satisfying 0 P1 1 9 iPZi2 iF Zi2 17izi 1 9 iPeiti gt 07 iti g 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 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 A wavelet 11 is obtained by W Zenkmwx 7 k k or alternatively 2a Qie 2 E52 With 1 02 5 Zielikmzk k If 1 is integrable then g M and WEN MiQie 2i 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 f ax l b for all X where 1X 7 0 gives vanishing wavelet coefficients 1 fxzpxdx 0 I l 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 Construction of the Daubechies wavelet Try the simplest case first a polynomial P Find a polynomial P such that p Pe i has the following properties 0 p0 1 0 WSW WE WW 1 9 WM gt 0 town2 5 g 7r2 and the associated it has vanishing zeroth and first moments The polynomial 1 3 3 3 37 3 872139s 1 8 873ig P35 is an example which belongs to the Daubechies wavelet The Daubechies wavelet 1i is continuous and has vanishing zeroth and first moments 1 xdx X Xdx 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 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

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

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

#### "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."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### 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.