1 00:00:00,600 --> 00:00:04,290 Welcome to module 3 of digital signal processing. 2 00:00:04,290 --> 00:00:06,540 We have just seen the basics of signal processing. 3 00:00:06,540 --> 00:00:10,330 Mainly signals, operators, and examples. 4 00:00:10,330 --> 00:00:12,420 We now setup the mathematical frame work so 5 00:00:12,420 --> 00:00:15,478 that we can study signal processing in detail. 6 00:00:15,478 --> 00:00:19,780 In model 2.1, we start very slowly by introducing. 7 00:00:19,780 --> 00:00:24,198 Intuitive geometrical notions in the real plane, or so called R2. 8 00:00:24,198 --> 00:00:26,010 In models 3.2, 9 00:00:26,010 --> 00:00:29,430 we present the main characters, which are vectors, 10 00:00:29,430 --> 00:00:33,060 norms on vectors, inner products, and bases for 11 00:00:33,060 --> 00:00:35,756 spaces in particle for Hilbert spaces which is 12 00:00:35,756 --> 00:00:39,328 a natural generalization of Euclidean geometry to higher dimensions. 13 00:00:39,328 --> 00:00:43,470 Finally models 3.3 we consider approximations. 14 00:00:43,470 --> 00:00:46,450 Approximations are very important in signal processing for example 15 00:00:46,450 --> 00:00:50,270 for filter design, for lead square approximations, and so on. 16 00:00:51,730 --> 00:00:55,840 Let us get started with a review of the geometry in the play. 17 00:00:55,840 --> 00:00:58,540 This is very simple geometry as we know from. 18 00:00:58,540 --> 00:01:01,750 Great school exactly called Euclidean geometry and 19 00:01:01,750 --> 00:01:03,980 the key is that the ingredients namely, 20 00:01:03,980 --> 00:01:06,500 vectors in the plane are enough instructions 21 00:01:06,500 --> 00:01:08,590 that is very useful to represent signals. 22 00:01:08,590 --> 00:01:11,750 And so we have an intuition from two-dimensional geometries that 23 00:01:11,750 --> 00:01:16,370 we can generalize and manipulate signals later on very easily. 24 00:01:16,370 --> 00:01:17,560 The key insight 25 00:01:17,560 --> 00:01:21,960 is that signals indeed are vectors. Vector geometry is a natural setting. 26 00:01:21,960 --> 00:01:25,090 Notions like orthogonality are very general. 27 00:01:25,090 --> 00:01:28,750 Now, this intuition is, of course, very old. 28 00:01:28,750 --> 00:01:32,420 It goes actually back to Greek geometry, and to Euclid. 29 00:01:32,420 --> 00:01:36,340 And Euclid in his famed book called the elements actually 30 00:01:36,340 --> 00:01:40,490 wrote down the basics of geometry more than 2000 years ago. 31 00:01:40,490 --> 00:01:42,730 We can see this in a beautiful facsimile copy 32 00:01:42,730 --> 00:01:45,600 of Euclid's elements, and for example the 33 00:01:45,600 --> 00:01:48,910 Pythagorean theorem is proven in a geometric way. 34 00:01:48,910 --> 00:01:51,320 And this very theorem is actually called Parseval 35 00:01:51,320 --> 00:01:53,890 theorem, it's very important in signal processing in general. 36 00:01:57,140 --> 00:02:01,660 The module is split into three parts. The first one is a 37 00:02:01,660 --> 00:02:07,040 very lightweight introduction to signal processing seen as geometry. 38 00:02:07,040 --> 00:02:13,470 And that's really the Euclidian view of the world, and how we try to go from that. 39 00:02:13,470 --> 00:02:15,790 Very classic view to Hilbert spaces. 40 00:02:16,900 --> 00:02:22,540 Module 3.2 is more formal, defining vectors, vector spaces, 41 00:02:22,540 --> 00:02:24,866 inner products, and finally Hilbert spaces. 42 00:02:24,866 --> 00:02:30,130 Module 3.3 discusses the construction of bases 43 00:02:30,130 --> 00:02:33,830 for Hilbert spaces in particular, autonormal bases. 44 00:02:35,080 --> 00:02:37,370 Let me make just an introductory comment. 45 00:02:37,370 --> 00:02:41,000 So usually when we go to class and we talk about Hilbert 46 00:02:41,000 --> 00:02:45,630 spaces, people are sort of worried because it sounds abstract and mathematical. 47 00:02:46,800 --> 00:02:47,680 The goal here is 48 00:02:47,680 --> 00:02:51,780 to show that Hilbert spaces, which is the frame work 49 00:02:51,780 --> 00:02:57,280 to think about signal processing, is simply a generalization of the. 50 00:02:57,280 --> 00:02:59,970 Usual Euclidean geometry that we know. 51 00:02:59,970 --> 00:03:01,730 The spaces we live in. 52 00:03:01,730 --> 00:03:06,520 The three dimensional volumes of the physical space we inhabit. 53 00:03:06,520 --> 00:03:10,230 Or the four dimensional space when you add time. 54 00:03:10,230 --> 00:03:13,280 And so it is nothing to be scared about. 55 00:03:13,280 --> 00:03:16,000 Nothing forbidding. It's actually something very natural. 56 00:03:16,000 --> 00:03:20,960 And we're going to do this by entering this field very gradually. 57 00:03:22,590 --> 00:03:25,680 And we first start by putting an origin here. 58 00:03:25,680 --> 00:03:32,108 That's a black dot, it's the origin. Then, we can draw a vector x that 59 00:03:32,108 --> 00:03:38,370 has two coordinates, x0 and x1. Remember, our vectors are column vectors. 60 00:03:38,370 --> 00:03:41,270 So when we write this, we have to put a transpose. 61 00:03:42,400 --> 00:03:45,550 We can write the length of this vector 62 00:03:45,550 --> 00:03:49,200 which is the distance from the origin to the 63 00:03:49,200 --> 00:03:51,750 tip of the vector and that we write 64 00:03:51,750 --> 00:03:55,140 with this double bars to indicate the square norm. 65 00:03:56,910 --> 00:04:03,130 Then we can add a second vector in the plane, coordinates y0, y1. 66 00:04:03,130 --> 00:04:03,480 It has 67 00:04:03,480 --> 00:04:08,460 a length given by the norm of y. Once very have two 68 00:04:08,460 --> 00:04:14,000 vectors, very naturally there is angle between the two vectors given by alpha. 69 00:04:16,110 --> 00:04:18,820 Okay, so that's Euclidean geometry in R2. 70 00:04:20,750 --> 00:04:25,940 There is a particular configuration when the vectors have a right angle. 71 00:04:25,940 --> 00:04:28,470 So when alpha is equal to pi over 2, sometimes this 72 00:04:28,470 --> 00:04:33,020 is written here with a dot or with annotation like this. 73 00:04:33,020 --> 00:04:36,200 This shows that's a two vectors or orthogonal to each other. 74 00:04:40,160 --> 00:04:43,520 Now, the point we want to emphasize here 75 00:04:43,520 --> 00:04:46,870 is that vectors can be very general objects. 76 00:04:49,060 --> 00:04:55,020 So, one set of vectors that is interesting, it's functions 77 00:04:55,020 --> 00:05:01,710 over continuous time like here, this sine wave or another sine wave. 78 00:05:01,710 --> 00:05:03,170 For example over an integral. 79 00:05:03,170 --> 00:05:08,670 Here's integral minus 1 to 1. And we can define a space 80 00:05:08,670 --> 00:05:14,180 of all the functions over this integral minus 1 to 1 81 00:05:14,180 --> 00:05:16,810 that have a square integral. 82 00:05:16,810 --> 00:05:19,510 So if you square the function and integrate it 83 00:05:19,510 --> 00:05:23,420 over this integral it's going to be a finite value. 84 00:05:23,420 --> 00:05:28,760 And here we have two examples. So, x1, which is sine of f1 of t. 85 00:05:28,760 --> 00:05:31,730 X2, which is sine of 2 of t. 86 00:05:31,730 --> 00:05:36,070 And we can decide to calculate what is defined as the inner product. 87 00:05:36,070 --> 00:05:39,700 Which is simply the product of the two functions, 88 00:05:39,700 --> 00:05:43,480 integrated over the interval from minus 1 to 1. 89 00:05:43,480 --> 00:05:48,290 Okay, so this is very important options, that's the inner product between x1 and 90 00:05:48,290 --> 00:05:52,160 x2. What is to be noted here is that 91 00:05:52,160 --> 00:05:58,200 previously we had vectors in R2 with an angle 92 00:05:58,200 --> 00:06:04,720 alpha, with an orthogonal angle of 90 degrees, here, we have also two vectors. 93 00:06:04,720 --> 00:06:07,550 And the question is, can we have the same notions, okay? 94 00:06:08,660 --> 00:06:13,650 And sure enough, if we multiply the two 95 00:06:13,650 --> 00:06:16,640 functions together, we get this red function here. 96 00:06:17,680 --> 00:06:23,690 And if the two frequencies, f1 and f2. Are 97 00:06:24,760 --> 00:06:30,010 integer multiples of a fundamental, harmonically related frequency, 98 00:06:30,010 --> 00:06:33,220 it would turn out that these two vectors, these abstract 99 00:06:33,220 --> 00:06:36,935 vectors x1 and x2, will also be orthogonal to each other. 100 00:06:36,935 --> 00:06:39,460 We're going to calculate this, okay? 101 00:06:39,460 --> 00:06:40,730 So we take the product. 102 00:06:42,170 --> 00:06:44,210 And then we look at what is positive and 103 00:06:44,210 --> 00:06:47,460 what is negative because we are going to integrate. 104 00:06:47,460 --> 00:06:53,400 And we sort of see that for every positive part, this one, we have a negative part. 105 00:06:54,420 --> 00:06:55,070 This positive 106 00:06:55,070 --> 00:06:58,920 part we have a negative part. This one we have that one. 107 00:06:58,920 --> 00:07:03,510 And the same here and there, here and there, here and there. 108 00:07:03,510 --> 00:07:06,550 And so when you take the integral between minus 1 109 00:07:06,550 --> 00:07:10,060 and 1, the integral is going to be equal to 0. 110 00:07:10,060 --> 00:07:13,120 So conceptually we have exactly the same 111 00:07:13,120 --> 00:07:17,005 phenomenon as the two orthogonal vectors in R2. 112 00:07:17,005 --> 00:07:19,010 Okay, so that's the fundamental message. 113 00:07:19,010 --> 00:07:21,060 Vectors are very general objects. 114 00:07:21,060 --> 00:07:25,030 But they still have relationships like length, or norm. 115 00:07:25,030 --> 00:07:27,460 And angles between them. 116 00:07:27,460 --> 00:07:34,370 And that's the magic, both of Euclidean geometry and of Hilbert spaces. 117 00:07:34,370 --> 00:07:40,180 Okay, so once we have a space, we can define bases for this space. 118 00:07:40,180 --> 00:07:43,608 The simplest one is our tool, we're still in our tool here. 119 00:07:43,608 --> 00:07:46,104 Is an orthogonal basis with a 120 00:07:46,104 --> 00:07:53,180 first vector here e0, a second vector e1 and a right triangle between the two. 121 00:07:53,180 --> 00:07:55,820 Any vector x can be written as a linear 122 00:07:55,820 --> 00:07:59,900 combination here of e0 plus a linear combination of e1. 123 00:07:59,900 --> 00:08:03,300 Summing together, you get the vector x. 124 00:08:03,300 --> 00:08:04,080 Okay? 125 00:08:04,080 --> 00:08:08,730 A more general basis, still in R2 is a biorthogonal basis. 126 00:08:08,730 --> 00:08:12,210 So we have a vector v0, a vector v1. 127 00:08:12,210 --> 00:08:15,060 These two basis vectors span R2 but they are 128 00:08:15,060 --> 00:08:17,980 not orthogonal to each other but we can obviously 129 00:08:17,980 --> 00:08:24,925 write any vector x as a linear combination of v0 here plus v1 and that gives us x. 130 00:08:24,925 --> 00:08:26,810 Okay, so what is a basis? 131 00:08:26,810 --> 00:08:33,140 It's a set of vectors that spans the space of interest, and that 132 00:08:33,140 --> 00:08:37,555 is linear-independent, so it's a minimal set of vectors that span, for example 133 00:08:37,555 --> 00:08:39,520 R2, in this case it's two vectors, if we 134 00:08:39,520 --> 00:08:43,310 were in R3 it would be three vectors, etcetera. 135 00:08:45,090 --> 00:08:45,960 Okay. 136 00:08:45,960 --> 00:08:48,990 We can have sometimes too many vectors for the space. 137 00:08:48,990 --> 00:08:49,800 So we are still in R2. 138 00:08:51,580 --> 00:08:54,850 But we have now three vectors. So these guys are not linear independent. 139 00:08:54,850 --> 00:08:57,090 We're going to show this just in a second. 140 00:08:57,090 --> 00:08:59,770 But it is clear that we can write any 141 00:08:59,770 --> 00:09:02,950 point in R2 as a linear combination of these vectors 142 00:09:02,950 --> 00:09:05,570 because of course, two of them are already enough. 143 00:09:05,570 --> 00:09:07,300 So thirdly a third one. 144 00:09:07,300 --> 00:09:10,480 Can easily be ignored, or can also be helpful. 145 00:09:10,480 --> 00:09:13,820 Okay, now let's see that these guys are not linear independent, by actually 146 00:09:13,820 --> 00:09:18,520 verifying that a sum of the three vectors is actually equal to zero. 147 00:09:18,520 --> 00:09:29,050 So let's sum x1 plus x2 and finally, minus x0 and you see that. 148 00:09:29,050 --> 00:09:35,180 X1 plus x2 is equal to minus x0, and so we can verify this equation here. 149 00:09:35,180 --> 00:09:37,540 So these guys are depending on each other. 150 00:09:37,540 --> 00:09:42,320 Which is of course obvious because, for example, we can very well write 151 00:09:42,320 --> 00:09:47,600 in this case, it's x0 as a linear combination of x1, or x2, etcetera. 152 00:09:47,600 --> 00:09:48,000 Okay. 153 00:09:48,000 --> 00:09:51,340 So that's the case where the vectors are not linearly independent. 154 00:09:53,850 --> 00:09:56,310 If we have instead of too many vectors, we 155 00:09:56,310 --> 00:09:59,400 have not enough vectors for the space of interest. 156 00:09:59,400 --> 00:10:03,420 So for example here, we have R3, three dimensional. 157 00:10:03,420 --> 00:10:07,410 Physical space, for example, but we have only two vectors. 158 00:10:07,410 --> 00:10:11,150 Then, we cannot hope to describe any vector in R3. 159 00:10:11,150 --> 00:10:14,670 We can only describe its projection onto the 160 00:10:14,670 --> 00:10:19,020 subspace spanned by e1 and e0 in this case, 161 00:10:19,020 --> 00:10:22,650 so the vector x cannot be exactly represented. 162 00:10:22,650 --> 00:10:26,140 We can actually only project it here to an x at. 163 00:10:27,280 --> 00:10:30,700 This far character here, which is the best least squares 164 00:10:30,700 --> 00:10:35,930 approximation of x on the subspace spanned by e0 and e1. 165 00:10:35,930 --> 00:10:36,578 Fill in the 166 00:10:36,578 --> 00:10:37,082 [UNKNOWN] 167 00:10:37,082 --> 00:10:41,624 of subspace, which is, let's say it's a horizontal plane in this case. 168 00:10:41,624 --> 00:10:46,860 Now interesting questions appear when we go to spaces of infinite dimensions. 169 00:10:46,860 --> 00:10:53,570 So we look at the interval here of minus 1 to 1, which is a continuous interval. 170 00:10:53,570 --> 00:10:57,890 And so the intuition is that, there is no finite dimensional basis 171 00:10:57,890 --> 00:11:02,790 that will be able to represent an arbitrary function on this inverval. 172 00:11:02,790 --> 00:11:07,900 So let's look at the particular basis. It is built up from so called sine 173 00:11:07,900 --> 00:11:13,210 x over x or, more precisely, the n's basis vector here is given 174 00:11:13,210 --> 00:11:18,370 by sine pi n t over n, the final gentle minus 1 to 1. 175 00:11:18,370 --> 00:11:23,020 And we look at the summation of adding more and more of 176 00:11:23,020 --> 00:11:28,010 these basis vectors. So the summation goes from k is equal 177 00:11:28,010 --> 00:11:31,270 to 0 to capital N so it has n plus 1 terms. 178 00:11:31,270 --> 00:11:36,840 And we look at the vectors with index here 2k plus 1. 179 00:11:36,840 --> 00:11:38,240 Okay. 180 00:11:38,240 --> 00:11:42,360 So when capital N is equal to 0 we have one term, it's a sine wave. 181 00:11:44,400 --> 00:11:48,560 Then when we go to N is equal to 1, we have two terms. 182 00:11:48,560 --> 00:11:52,560 We have the addition of two vectors, N is equal to 2. 183 00:11:52,560 --> 00:11:58,130 We have three vectors, we start to see something interesting happening. 184 00:11:58,130 --> 00:12:02,023 Okay we still a very smooth function. N is equal to 10. 185 00:12:03,040 --> 00:12:05,550 We start to really see what will be the 186 00:12:05,550 --> 00:12:09,630 result or approximately the result which is a so called 187 00:12:09,630 --> 00:12:12,980 square wave, so something that will be close to minus 1, 188 00:12:12,980 --> 00:12:16,850 close to plus 1 and has a transition here around the origin. 189 00:12:16,850 --> 00:12:17,120 Okay? 190 00:12:17,120 --> 00:12:18,720 That's for N is equal to 10. 191 00:12:18,720 --> 00:12:22,100 N is equal to 50. 192 00:12:22,100 --> 00:12:25,364 Well, it looks more and more like the square wave, but it 193 00:12:25,364 --> 00:12:27,472 has these little wiggles, okay, in 194 00:12:27,472 --> 00:12:30,520 particular at the points of discontinuity, okay. 195 00:12:32,290 --> 00:12:35,270 And, N is 196 00:12:35,270 --> 00:12:40,940 equal 150, it looks very close to the square wave, except at the boundaries. 197 00:12:40,940 --> 00:12:45,010 So we see here something very particular happening. 198 00:12:45,010 --> 00:12:47,310 It's called non uniform convergence. 199 00:12:47,310 --> 00:12:52,330 It's a term from Fourier theories, theory, that we'll not investigate more. 200 00:12:52,330 --> 00:12:56,280 But it's something that is known, also, as a Gibb's phenomenon. 201 00:12:56,280 --> 00:13:00,830 And is an annoyance here in this approximation of this. 202 00:13:00,830 --> 00:13:05,880 Square wave or box functions by these sine waves.