Mathematical Foundations Of Signal Processing-Books Pdf

Mathematical Foundations of Signal Processing
04 Jun 2020 | 15 views | 0 downloads | 42 Pages | 754.15 KB

Share Pdf : Mathematical Foundations Of Signal Processing

Download and Preview : Mathematical Foundations Of Signal Processing


Report CopyRight/DMCA Form For : Mathematical Foundations Of Signal Processing



Transcription

In this lecture we study the question of how to efficiently encode a given class of signals We introduce. several mathematical techniques to construct optimal data representations for a number of signal types. Specifically we study the optimal approximation of functions governed by anisotropic singularities such. as edges in images,Introduction, One of the fundamental questions in the field of digital signal processing is how to efficiently represent or. encode a continuous signal by a bitstream of finite length In an age of ever increasing amounts of data it. is all the more relevant to find efficient representations for it in order to store the data or to transmit it. over a communication channel Of course different types of data require different representations What. works well for say sound data need not be the optimal choice for say medical image data. We will look at the encoding problem from a mathematical point of view. To this end we start by introducing mathematical models for certain signal classes in 2 as relatively. compact subsets of a Hilbert space Being merely mathematical models these signal classes will never. truly contain all the complexities of real world signals but they may serve as a decent approximation to. reality while being concrete enough to allow for a precise mathematical analysis. To give an example in order to model natural images we will introduce the mathematical model of. cartoon images which are two dimensional piecewise smooth functions with possible discontinuities along. curves These curved discontinuities model the edges of a natural image Since for most images the. main part of the information lies in its edges the model of cartoon images has proven to be a useful. mathematical formalization of natural images see Figure 1 1. The main question that we ask in this lecture is the following. Suppose we have a given signal class C and a desired precision 0 What is the minimal. number N of bits needed to encode any signal f C up to precision. Of course this question makes no sense mathematically as it stands We need to cast it more into. the mathematical language For instance What precisely do we mean by a signal class What does. encoding mean And what do we mean by up to precision. In what follows we will present rigorous answers to these questions together with some examples. Finally we will show a fundamental and perhaps surprising phenomenon For many signal classes one. can precisely quantify the optimal trade off between N the number of bits and the desired precision. To this end we will first in Section 2 introduce basic notions of coding theory After presenting several. interesting mathematical models for different types of real world signals we introduce for a signal class. C its optimal encoding rate which describes the optimal asymptotic tradeoff between the precision 0. and the number of bits needed to achieve such a precision which can be theoretically achieved uniformly. over all signals in C, In Section 3 we show the fundamental fact that for each signal class there exists a precise upper. bound on the optimal encoding rate Using the technique of hypercube embeddings introduced originally. by Donoho in 13 we explicitly calculate such upper bounds for all signal classes introduced earlier in. Section 2 These results are not new but the proofs are substantially simplified in comparison to 13 which. relies on results from the field of rate distortion theory 1 In contrast our presentation is completely. elementary and only requires some simple results from probability theory such as Chernoff type bounds. These are derived in Section A, The following Section 4 is then concerned with actually constructing optimal encoders using sparse. expansions in dictionaries We will mostly study sparse expansions in frames and introduce some elements. of nonlinear approximation theory 10 In particular we will see how one can design efficient encoding. schemes using appropriate frame expansions, Figure 1 1 Many parts of natural images can be modeled mathematically as piecewise smooth functions. with curved discontinuities, The remaining sections contain two important examples of signal classes and associated frame expan.
sions which generate optimal encoding schemes In Section 5 we will show that wavelet frames or bases. are optimally adapted for the sparse approximation of piecewise smooth univariate functions In Section. 6 we study the sparse approximation of cartoon images We first establish the fact that wavelets per. form subobtimally for this task Then we introduce curvelet tight frames which by a landmark result by. Cande s and Donoho 3 achieve optimally sparse representations of cartoon images which makes them an. extremely attractive representation system in image processing After that we introduce shearlet frames. 29 which are a related construction with the same desirable properties as curvelets and which have the. advantage of being much simpler to implement on digital data Finally we mention the notion of parabolic. molecules 24 which comprises a general framework for the sparse approximation of cartoon images and. which encompasses both curvelets and shearlets as special cases. Section 7 closes with some further examples of signal classes and frame constructions for their optimally. sparse representation, Finally in the Appendix A we collect some basic facts in probability theory and given an elementary. derivation of Chernoff s bound as needed in Section 2. We have decided to present the general results on coding complexity from Sections 2 3 and 4 in full. detail and hope to provide the reader with a useful and comprehensive reference on that topic In the. remaining sections we will then switch to a more informal presentation style as a more detailed treatment. would be beyond of the scope of this work,1 0 1 Notation. We comment on the notation which we shall use in the present work As usual we denote by Lp Rd. the usual Lebesgue spaces with associated norm k kp For a discrete set equipped with the counting. measure we denote the corresponding Lebesgue space by p or p if is known from the context. The associated norm will again be denoted k kp We use the symbol h i for the inner product on. the Hilbert space L2 Rd The Euclidean inner product on Rd is denoted by for Rd The. Euclidean norm x 1 2 of a vector Rd will be denoted by x For a function f L1 Rd we. can define the Fourier transform f Rd f x exp 2 ix dx By density this definition can be. extended to tempered distributions f We shall also use the notation T to denote the one dimensional. torus which can be identified with the half open interval 0 2 Sometimes we will use the notations. bxc max l Z l x and hxi 1 x2 1 2 The natural logarithm will be denoted log and the. logarithm with basis 2 will be denoted log2 We use the symbol A B to indicate that A CB with. a uniform constant C Finally we shall often use the letter C for a generic constant whose precise value. may change from line to line,Signal Classes and Encoding. Let us first agree on what we mean by a signal class Ideally we would like to consider such classes as. for instance music or say fingerprint images and so on But clearly such fuzzy definitions do not allow. for a rigorous analysis We have to mathematicize the concept of signal classes in order to gain a deeper. understanding To this end we shall fix a separable Hilbert space H and define the notion of signal class. as follows, Definition 2 1 A relatively compact subset C H is called a signal class. We list a few examples for signal classes which are commonly used as benchmarks for certain real. world signals It should be emphasized that these examples only constitute mathematical models and. may or may not have anything to do with the real world Nevertheless their provides us with important. insights of what we can expect in real life, In what follows we shall always have H L2 Rd for some d N i e we study signal classes which.
are compact subsets of the space of square integrable functions This makes sense in a signal processing. context but if our signal class consists of solutions to PDEs Sobolev spaces would be more appropriate. Example 2 2 Smooth Functions Given a smooth bounded domain C Rd define for k N and. CK C u L2 Rd u C k kukC k K and supp u C,where we denote. kukC k sup dl f x,and dl f the l th total derivative of f. Example 2 3 Piecewise Smooth Functions Given a bounded interval I a b R define for k N. the set of piecewise smooth functions on I as,CK I f1 0 c f2 c 1 where c I and f1 f2 CK I. where we denote by C the indicator function of a set C. Example 2 4 Star Shaped Images see 13 We now take a first step in modeling multivariate signals. with anisotropic and curved singularities We start with binary images To this end we take a C 2 function. T 0 defined on the torus T 0 2 where the boundary points are identified Additionally. we assume that there exists 0 0 1 such that 0 for all T Then we define the subset. B x R2 x r in polar coordinates with T r 2 1, Figure 2 1 Left A natural image is typically composed of smooth parts separated by edges and thus. resembles a cartoon image as defined in Example 2 5 The main features are still visible Right True. cartoon image, such that the boundary B of B is a closed regular C 2 Jordan curve in 0 1 2 parameterized by.
Furthermore we require that,k kC 2 K 2 3, For K 0 the set ST ARK is defined as the collection of all indicator functions B of subsets. B 0 1 2 which are translates of sets of the form 2 1 with a boundary obeying 2 2 and 2 3. Example 2 5 Cartoon Images see 3 Star shaped images are indicator functions of subsets of 0 1 2. A more realistic mathematical model for real world images is the set of cartoon images which is defined. CARTK f1 B f2 B ST ARK and f1 f2 CK 0 1 2, Figure 2 1 shows an illustration of cartoon images. Example 2 6 Textures see 9 Textures are signals with highly oscillatory repetative structures In. 9 the following model has been proposed for textures. T EXTK M sin M f x g x where f g CK 0 1 2,It consists of warped oscillatory patterns. Example 2 7 Mutilated Functions see 2 The class of mutilated functions has been introduced in. 2 as all functions of the form, M U T ILkK g u x h x g C k pw R h C k 0 1 d u Rd u 1. Functions in M U T ILkK are generally smooth aside from possible discontinuities across hyperplanes or. thogonal to the vector u Mutilated functions arise for instance as solution to linear transport PDEs. Figure 2 2 Left A fingerprint image resembles a texture image as defined in Example 2 6 Right True. texture image, We reiterate that the signal classes that we have seen in the previous examples do not necessarily.
correspond to what real world signals might look like But still it is reasonable to consider for instance. the class T EXTK M as a stylized model for fingerprint images or seismic data or the class CARTK as a. model for images with little texture see Figures 2 2 and 2 1. Having agreed on what we mean by signal classes in a mathematical sense we now define what we. mean by encoding such data which formally means a mapping that maps each u C to a bitstream of. finite length Our nomenclature is mostly based on conventions in the field of rate distortion theory 1. Definition 2 8 Let C be a signal class An encoding decoding pair E D consists of two mappings. E C 0 1 R D 0 1 R H, where R N denotes the runlength R E D of E D The of E D is defined as. E D sup ku D E u kH, Given an encoding decoding pair one encodes a signal u C simply by applying the mapping E and. thus digitizing the continuous signal u into a bitstream and the decoding works by applying the decoder. eg computing D E u H The goal of rate distortion theory is simply to develop encoding decoding. pairs with a runlength which is as short as possible while at the same time keeping the distortion small. In particular we want to understand the following quantity. Definition 2 9 Let C be a signal class Then we denote its optimal encoding rate by. s C sup s 0 There exists C 0 such that for each R N. there exists ER DR with R ER DR R and ER DR CR s 2 4. We remark that knowledge of s C exactly answers the question posed in the beginning of this section. Indeed for any s s C we can encode any signal u C up to precision 0 using up to a fixed. constant C 1 s bits Of course the larger s the better suppose we want to encode with a guaranteed. accuracy of six decimals i e 10 6 Then if s C 2 we would need about 1000 bits whereas we. would need about 1012 bits if s C 1 2, Summarizing the quantity s C represents a fundamental measure of the complexity of the signal. class and the theoretical limitations of encoding It is closely related to the concept of Kolmogorov. entropy 36, Remark 2 10 We briefly discuss the connection between Kologorov entropy aka Metric entropy and. optimal encoding Suppose we have a metric space X with distance function d for x X and r 0. denote by B x r the open ball around x with radius r in X Suppose that C X is relatively compact. Then for any 0 there is a finite N C which is minimal among all N N such that there exist. i 1 X satisfying,We say that xi N,constitute an cover of C.
The Kolmogorov Entropy is then defined as,H C log2 N C. Let us now see how this quantity is related to encoding Conforming to the setting we have developed. in this section we consider as our metric space the Hilbert space H and as C a signal class as defined. Mathematical Foundations of Signal Processing Philipp Grohs February 9 2016 Abstract In this lecture we study the question of how to e ciently encode a given class of signals We introduce several mathematical techniques to construct optimal data representations for a number of signal types Speci cally we study the optimal approximation of functions governed by anisotropic singularities

Related Books

RM38 RM44 RM44GR RM48 MOWER RM60 MOWER MK44 MK48 MK48

RM38 RM44 RM44GR RM48 MOWER RM60 MOWER MK44 MK48 MK48

rm42g rotary mower deck and chute ref part no description req d 1 c36805 deck mower 1

Hay Baler Parts

Hay Baler Parts

MISC BALER PARTS Parts are not original equipment parts and are not sponsored affiliated or otherwise connected with any major brand 43 Case IH A 712158 Bearing Plunger roller Case IH ROUND BALER 8435 8440 8450 8455 8455T 8460 8465 8465A 8465T SQUARE BALER 8540 8550 8555 8570 8575 8580 8590 ROUND BALER RS561 RS561 AUTO A M53320 Bearing Cone Wheel Hub Case IH

J J II CCaassee Tractor Parts

J J II CCaassee Tractor Parts

ccaassee parts manual 446 amp 448 s n 9770165 to 14041700 9774000 to 14044240 this is a manual produced byjensales inc without the authorization of j i case or it s successors j i case and it s successors are not responsible for the quality or accuracy of this manual trade marks and trade names contained and used herein are those of others and are used here in a descriptive sense to

Second Meeting Home Pacific Environment

Second Meeting Home Pacific Environment

Second Meeting of the Pacific Meteorological Council Apia Samoa SPREP 2017 49 p 29 cm ISBN 978 982 04 0670 4 print 978 982 04 0671 1 ecopy 1 Meteorological Services Oceania 2 Pacific Meteorology Oceania 3 Climatology Oceania I Secretariat of the Pacific Regional Environment Programme SPREP II Title 551 5092099 Secretariat of the Pacific Regional Environment

Alexander the Great Amazon S3

Alexander the Great Amazon S3

Alexander the Great Level R 40 Ancient Greece Level R 40 Social Studies Big Idea Readers will learn about Alexander the Great s early life and conquests as well as the Hellenistic Age that followed his death For students reading at Literacy Level R 40 including Grade 4 readers Grade 5 8 students reading below level English language learners at TESOL Level 5

INTERACTIVE STUDENT NOTEBOOK Alexander the Great and His

INTERACTIVE STUDENT NOTEBOOK Alexander the Great and His

His Empire INTERACTIVE STUDENT NOTEBOOK Throughout history some rulers have been given the title Great For example Ramses II of Egypt is also known as Ramses the Great Why do you think a ruler from ancient times would be given this title In the space below list at least three possible reasons A great ruler A great ruler A great ruler Key Content Terms As you

Alexander the Great DBQ Fulton Science Academy STEM

Alexander the Great DBQ Fulton Science Academy STEM

DBQ How Great Was Alexander the Great Overview Alexander III of Macedonia streaked like a meteor across the ancient world When he was only 20 he inherited an empire that included the kingdom of Macedonia and the city states of Greece Almost immediately Alexander set out to conquer the Persian Empire which stretched from Egypt to India He achieved his dream by the time he was 30 but

Alexander and the Hellenistic Age

Alexander and the Hellenistic Age

Empire under his control Alexander pushed further east into India He crossed the high Hindu Kush mountains into Northern India Alexander never lost a battle but his soldiers refused to go further east They began their long journey home Alexander s Early Death Before he could continue conquering Alexander came down with a fever and died at the age of 32 He left no heirs to his throne

The Great Empires of Prophecy

The Great Empires of Prophecy

The Great Empires of Prophecy From Babylon to the Fall of Rome To the intent that the living may know that the Most High ruleth in the kingdom of men Alonzo Trevier Jones Review and Herald Publishing Company Battle Creek Michigan Chicago Ill Atlanta GA 1898 Entered according to Act of Congress in the year 1891 by Alonzo Trevier Jones In the office of the Librarian

YEAR 3 ANCIENT GREECE UNIT 2 5 lessons

YEAR 3 ANCIENT GREECE UNIT 2 5 lessons

YEAR 3 ANCIENT GREECE UNIT 2 5 lessons ontents Include Greek Philosophy The Rise of Alexander the Great Alexander s conquests The death and legacy of Alexander Suggested Teacher Resources A Little History of the World by Ernst Gombrich chapters 7 8 9 and 10 Ancient Greece by Andrew Solway illustrated by Peter onnolly e has a good section on teaching Ancient Greece in the

How Great Was Alexander the Great

How Great Was Alexander the Great

Alexander the Great Mini Q How Great Was Alexander the Great A mosaic depicting Alexander at the Battle of Iss us 333 BCE Overview Alexander III of Macedonia streaked like a meteor across the ancient world Vhen he was only 20 he inherited an empire that included the kingdom of Macedonia and the city states of Greece Almost immediately Alexander set out to conquer the Persian