Approximation in Inner Product Spaces, and Fourier Approximation

Approximation in inner product spaces, and Fourier approximation Math 272, Spring 2018 Any typographical or other corrections about these notes are welcome. 1 Review of inner products An inner product space is a vector space V together with a choice of inner product. Recall that an inner product must be bilinear, symmetric, and positive definite. Since it is positive definite, the quantity h~u, ~ui is never negative, and is never 0 unless ~v = ~0. Therefore its square root is well-defined; we define the norm of a vector ~u ∈ V to be p k~uk = h~u, ~ui. Observe that the norm of a vector is a nonnegative number, and the only vector with norm 0 is the zero vector ~0 itself. In an inner product space, we call two vectors ~u, ~v orthogonal if h~u, ~v i = 0. We will also write ~u ⊥ ~v as a shorthand to mean that ~u, ~v are orthogonal. Because an inner product must be bilinear and symmetry, we also obtain the following expression for the squared norm of a sum of two vectors, which is analogous the to law of cosines in plane geometry. k~u + ~v k2 = h~u + ~v , ~u + ~v i = h~u + ~v , ~ui + h~u + ~v , ~v i = h~u, ~ui + h~v , ~ui + h~u, ~v i + h~v , ~v i = k~uk2 + k~v k2 + 2 h~u, ~v i . In particular, this gives the following version of the Pythagorean theorem for inner product spaces. Pythagorean theorem for inner products If ~u, ~v are orthogonal vectors in an inner product space, then k~u + ~v k2 = k~uk2 + k~v k2 . Proof. This follows from the equation k~u + ~v k2 = k~uk2 + k~v k2 + 2 h~u, ~v i (found above), together with the fact that h~u, ~v i = 0 (by defintion of orthogonality). 2 The approximation problem and its solution via orthogonality These notes are concerned with a process for solving the following problem, which is analogous (indeed, a generalization of) the least-squares problem that we discussed a couple weeks ago. The approximation problem in inner product spaces Given a list of vectors {~v1 , · · · , ~vn } in an inner product space and an additional vector ~b, what linear combination of {~v1 , · · · , ~vn } is closest to ~b? In other words, which values c1 , · · · , cn minimize the quantity n X ci~vi − ~b ? i=1 As in the case of the least-squares problem, the solution of this approximation problem is intimately tied with the idea of orthogonality. The problem can be reduced to solve a linear system of equations, once we have the following observation: the best possible linear combination is the one that makes the difference to ~b orthogonal to all of the vectors at our disposal. This is made precise in the following theorem. Main theorem on approximation Suppose that we are given S = {~v1 , · · · , ~vn } and ~b in an inner product space. If a linear combination ~v of S satisfies the orthogonality conditions ~vi ⊥ (~v − ~b) for all i, then ~v minimizes k~v − ~bk (among all possible linear combinations of S). The proof of this theorem follows the same method as the analogous theorem from the notes on least-squares. Indeed, it is the same proof; we simply replace any reference to a dot product with a use of whatever inner product is in use. Proof. Assume that ~v is a linear combination of S satisfying the given orthogonality conditions. Let w ~ be any other linear combination of S (i.e. w ~ is a linear combination of {~v1 , · · · , ~vn }, and ~ w ~ 6= ~v ). Then w ~ − ~v is a linear combination of {~ Dv1 , · · · , ~vn }. Since E each ~vi is orthogonal to ~v − b, and the inner product is bilinear, it follows that (w ~ − ~v ), ~v − ~b = 0, i.e. (w ~ − ~v ) ⊥ (~v − ~b). By the Pythagorean theorem for inner product spaces, it follows that kw ~ − ~bk2 = k(w ~ − ~v ) + (~v − ~b)k2 = kw ~ − ~v k2 + k~v − ~bk2 . Now, since w ~ 6= ~v , it follows (from positive definiteness of the inner product) that kw ~ − ~v k2 > 0. Therefore kw ~ − ~bk2 > k~v − ~bk2 . Therefore, w ~ is further from ~b than ~v is, so indeed ~v is the closest possible linear combination of {~v1 , · · · , ~vn } to ~b. What makes this theorem so powerful is that this list of orthogonality conditions amounts to a linear system of equations. Indeed, if we write ~v = c1~v1 + c2~v2 + · · · + cn~vn , then the condition ~vi ⊥ (~v − ~b) can be written D E ~vi , c1~v1 + c2~v2 + · · · + cn~vn − ~b = 0 D E h~vi , c1~v1 + c2~v2 + · · · + cn~vn i = ~vi , ~b D E c1 h~vi , ~v1 i + c2 h~vi , ~v2 i + · · · + · · · + cn h~vi , ~vn i = ~vi , ~b , which constitutes a linear equation in the variables c1 , c2 , · · · cn . One way to write the resulting linear system of equations, analogous to the matrix form of the normal equation (from our discussion of least-squares) is the following. D E    ~v1 , ~b h~v1 , ~v1 i h~v1 , ~v2 i · · · h~v1 , ~vn i c1 D E  h~v2 , ~v1 i h~v2 , ~v2 i · · · h~v2 , ~vn i   c2   ~b  ~ v ,   2      .. .. ..   ..  =    .  . . .   .   ..  E D h~vn , ~v1 i h~vn , ~v2 i · · · h~vn , ~vn i cn ~vn , ~b 3 Examples: approximating functions with polynomials One fairly common situation in practice is curve-fitting: you may have some data from a measuring instrument or laboratory that can be graphed as a function of one variable, and perhaps that data is noisy in some way. it is often convenient to approximate the resulting curve using a low-degree polynomial. The machinery of the previous section gives a way to find a polynomial of “best fit.” The examples in this section show one way that this could be done. These examples take place in the inner product space C[0, 1] (this is out notation from class; the book writes C (0) [0, 1])), with the inner product Z hf, gi = 1 f (x)g(x) dx. 0 Here the approximation problem can be understood as follows: we are looking to approximate a given function as a linear combination of some other previously chosen functions, where we measure the accuracy of an approximation by the integral of the squared difference between the functions. Example 1 Find the linear polynomial p(x) = c1 + c2 x that best approximates f (x) = ex on the interval [0, 1]. More precisely, p(x) should minimize the value of the integral Z 1 2 Z (p(x) − f (x)) dx = 0 0 1 (c1 + c2 x − ex )2 dx. Solution to Example 1 We can map this problem onto the notation of the previous sections as follows. The target we wish to approximate is ex ; this is the vector ~b. The vectors we wish to use to approximate it are 1 and x (regarded as “vectors” in the vector space C[0, 1]), so these are ~v1 , ~v2 . Thus we obtain the following pair of orthogonality conditions from the main theorem: 1 ⊥ c1 + c2 x − ex x ⊥ c1 + c2 x − ex which translate into the following pair of linear equations: c1 h1, 1i + c2 h1, xi = h1, ex i c2 hx, 1i + c2 hx, xi = hx, ex i . We can evaluate the inner products involved as follows (note: on homework for this class, feel free to use a tool such as Wolfram Alpha from a web browser, or Mathematica if you have it installed, to evaluate such integrals): Z 1 h1, 1i = dx 0 Z 1 h1, xi = x dx 0 Z 1 hx, 1i = x dx 0 Z 1 hx, xi = x2 dx 0 Z 1 h1, ex i = ex dx 0 Z 1 x hx, e i − xex = 1 = = = 1 2 1 2 1 3 = −e + 1 = 1 0 Therefore we must solve the linear system 1 c1 + c2 = −1 + e 2 1 1 c1 + c2 = 1. 2 3 This can be done using matrix inversion or row reduction, the result is c1 = −10 + 4e ≈ 0.873, c2 = 18 − 6e ≈ 1.690 Thus the best-fit line is g(x) = (−10 + 4e) + (18 − 6e)x. The figure below shows a plot of y = ex and the best-fit line y = p(x) found above. 2.5 2.0 1.5 1.0 0.2 0.4 0.6 0.8 1.0 Example 2 Find the quadratic polynomial p(x) = c1 + c2 x + c3 x2 the minimizes Z 1 (p(x) − ex )2 dx. 0 Solution to Example 2 We process similarly to before. Now we are taking a linear combination of three functions: 1, x, x2 . To keep the solution brief, we go straight to the matrix equation described at the end of the previous section. In this case, this equation is      h1, 1i h1, xi 1, x2 c1 h1, ex i  hx, 1i hx, xi x, x2  c2  =  hx, ex i  . x2 , 1 x2 , x x2 , x2 c2 x2 , ex Using Mathematica to compute all of these integrals, this matrix equation becomes the following.      1 12 13 c1 −1 + e  1 1 1  c2  =  1  2 3 4 1 1 1 c3 −2 + e 3 4 5 And solving this system (e.g. using Mathematica to avoid painful calculations) gives c1 = −105 + 39e, c2 = 98 − 216e, c3 = −570 + 210e Or, approximately, c1 = 1.101, c2 = 0.851, c3 = 0.839. Thus the best-fit quadratic function is roughly 1.01 + 0.851x + 0.839x2 . This quadratic function is an excellent fit on the interval [0,1], as the following plot shows. 2.5 2.0 1.5 0.2 0.4 0.6 0.8 1.0 It is interesting to note that there is another well-known quadratic approximation of ex , namely its degree-2 Taylor approximation 1 + x + 12 x2 . The approximation above is a better fit in the “least squared error” sense on [0,1], but the quality of its fit is specific to the interval [0,1]. Note that the two approximations have similar coefficients, but they are slightly different. 4 Fourier approximation We consider in this section a particularly useful case of the approximation problem we’ve described, where we attempt to approximate functions on the interval [−π, π]1 by functions from the following list. 1, sin x, cos x, sin(2x), cos(2x), sin(3x), cos(3x), · · · , sin(nx), cos(nx), · · · This list of functions has several wonderful properties. Chief among them is that they form an orthogonal set. That is: Proposition Any two of the functions listed above are orthogonal to each other. We omit the proof of this proposition, because the proof itself it not crucial to the intended applications (if you wish to work the proof out for yourself, I will note that the main ingredient is the use of trigonometric identities for products). The wonderful consequence of orthogonality is that the approximation problem becomes vastly simpler, as described in the following. 1 There is nothing special about this interval, except that it serves as a period for the functions sin x, cos x, which simplifies notation. If we were doing Fourier approximation on a different interval, we would typically perform a horizontal scaling on all the approximation functions. Simplified version of the main theorem, for the orthogonal case Suppose that S = {~v1 , · · · , ~vn } and ~b are given, in some inner product space. Suppose further that any two elements of S are orthogonal to each other. That is, if i 6= j then h~vi , ~vj i = 0. Then the linear combination of S that best approximates ~b is given by the formula D E n ~vi , ~b X ~v = ~vi . h~vi , ~vi i i=1 Note that, using the notion of projection, we could also write this formula as ~v = n X proj~vi~b. i=1 Proof. By the main theorem from earlier in this document, the best linear combination ~v = c1~v1 + c2~v2 + · · · + cn~vn should be chosen such that for each i, ~vi ⊥ (~v − ~b). This orthogonality condition can be rewritten, using inner products, as the equation D E h~vi , ~v1 i c1 + h~vi , ~v2 i c2 + · · · + h~vi , ~vn i cn = ~vi , ~b . However, all but one of the inner products on the left side of this equation are equal to 0, due to the orthogonality of the set {~v1 , · · · , ~vn }. The only one that doesn’t vanish is h~vi , ~vi i. So this equation simplifies to D E h~vi , ~vi i ci = ~vi , ~b . Thus for each choice of i, the orthogonality condition with ~vi uniquely identifies the coefficient of ~vi to be D E ~vi , ~b ci = . h~vi , ~vi i Plugging this coefficients into ~v = n X ci~vi gives the desired equation. i=1 We may now combine the proposition (on the orthogonality of the functions in question) with the simplified version of the main theorem to carry out Fourier approximation. Example: the square wave Consider the following piecewise-continuous function. ( −1 if − π ≤ x ≤ 0 f (x) = 1 if 0 < x ≤ π Find the linear combination g(x) of {1, sin x, cos x, sin(2x), cos(2x), sin(3x), cos(3x)} that minimizes Rπ −π (g(x) − f (x))2 dx. Full disclosure about something I am being slightly imprecise about: since f (x) is not a continuous function, it is not actually a member of the inner product space C[−π, π]. So I should really be speaking of the space of piecewise-continuous functions, which introduces some technicalities that are not crucial for the applications we are interested in. Since this distinction does not affect any of the methods involved, I will brush this issue under the rug and not worry about it. Solution: The function we are attempting to minimize can be written kg(x) − f (x)k2 . So this is an example of the type of approximation problem we have been studying. Due to the orthogonality of the functions to be combined, we may apply the simplified version of the main theorem. The function we seek is therefore given by g(x) = h1, f i hsin x, f i hcos x, f i ·1+ · sin x + · cos x h1, 1i hsin x, sin xi hcos x, cos xi hsin(2x), f i hcos(2x), f i + · sin(2x) + · cos(2x) hsin(2x), sin(2x)i hcos(2x), cos(2x)i hsin(3x), f i hcos(3x), f i + · sin(3x) + · cos(3x) hsin(3x), sin(3x)i hcos(3x), cos(3x)i Each of these inner products can be computed as an integral. To compute inner products with f (x) requires a bit of thought; the key fact is that integrals involving piecewise functions can be broken into pieces. So when taking inner products with f (x), we can use the formula Z π hg, f i = Z 0 g(x)f (x) dx = −π Z Z 0 g(x)(1) dx = − g(x)(−1) dx + −π π 0 So all of the inner products involving f can be found as follows. Z g(x) dx + −π π g(x) dx. 0 Z 0 π Z h1, f i = − dx = −π + π dx + −π 0 = 0 Z 0 π Z hsin x, f i = − sin x dx + −π sin x dx = 2 + 2 0 = 4 Z 0 Z hcos x, f i = − π cos x dx + −π cos x dx = 0 + 0 0 = 0 Z 0 π Z hsin(2x), f i = − sin(2x) dx + −π sin(2x) dx = 0 + 0 0 = 0 Z 0 π Z hcos(2x), f i = − cos(2x) dx + cos(2x) dx = 0 + 0 −π 0 = 0 Z 0 hsin(3x), f i = − sin(3x) dx + −π = π Z sin(3x) dx = 0 2 2 + 3 3 4 3 Z 0 Z hcos(3x), f i = − cos(3x) dx + −π π cos(3x) dx = 0 + 0 0 = 0 So in fact only two coefficients will be nonzero: that of sin x and that of sin(3x). We need two more inner products to write the result. Both can be computed using a trigonometric identity (the half-angle formula), or simply found with a computer. Z π hsin(x), sin(x)i = sin2 x dx = π Z π −π hsin(3x), sin(3x)i = sin2 (3x) dx = π −π Hence the approximation we seek is g(x) = 4 4 sin(x) + sin(3x). π 3π The plot below shows the graph of the original “square wave” together with this Fourier approximation. 1.0 0.5 -3 -2 1 -1 2 3 -0.5 -1.0 Note. In fact, it is not too difficult to derive the following general formulas for the inner product of the square wave with arbitrary “frequencies” of sine and cosine. hcos(nx), f (x)i = 0 for all n ( 4 if n is odd nπ hsin(nx), f (x)i = 0 if n is even Hence we can work out what the approximation will be for any number of included frequencies. For example, if we include all functions from our list up to sin(13x), cos(13x), then the approximation for the square wave will be f (x) = 4 4 4 4 4 4 sin(x) + sin(3x) + sin(5x) + sin(7x) + sin(9x) + sin(11x) π 3π 5π 7π 9π 11π The lot of this function is shown below. Note that it is a somewhat better approximation, but there is still a ways to go (more frequencies to include). 1.0 0.5 -3 -2 1 -1 -0.5 -1.0 2 3 5 Additional remarks on Fourier series What we have been discussing so far are Fourier approximations, which approximate a given function on [−π, π] by a finite linear combination of sines and cosines. In fact, what makes the list of functions 1, sin x, cos x, sin(2x), cos(2x), sin(3x), cos(3x), · · · , sin(nx), cos(nx), · · · truly miraculous is what happens when you pass to the limit, and consider the infinite sum given by the following formula: ∞ ∞ n=1 n=1 X X h1, f i hsin(nx), f i hcos(nx), f i ·1+ · sin(nx) + · cos(nx) h1, 1i hsin(nx), sin(nx)i hcos(nx), cos(nx)i For example, the Fourier series for the square wave can be written ∞ X n=0 4 sin((2n + 1)x). (2n + 1)π So the square wave can be decomposed into an (infinite) sum that includes odd frequencies only. This infinite sum is called the Fourier series of f (x). An amazing fact is that, if f (x) is a continuous function on [−π, π], this series converges exactly to f (x) (with one small caveat: at the endpoints ±π, the sum converges to the average of f (−π) and f (π)). If f (x) is only piecewise continuous, this sum still converges, but the result may differ from x at the discontinuities. The way this is usually summarized is: the list of functions above (1, sines, and cosines) form an orthogonal basis, since (in a suitable sense, if we allow infinite sums) they span the space of functions on this interval, in addition to being linearly independent. There are other orthonormal bases for such spaces of functions that have many useful applications. One that has been particularly useful recently, such as in the most recent version of the JPEG image compression algorithm, comes from the theory of wavalets. If you want to learn more, you should take Amherst’s course on Wavelets and Fourier Analysis (Math 320). A final comment: although sines and cosines are familiar from calculus and fairly tangible, in most more advanced courses it turns out to be somewhat more convenient to introduce complex numbers and instead use the functions einx (where n ranges over all integers, positive and negative). One benefit of this setup is that it is no longer necessary to distinguish between the two types of functions (sine and cosine). So this is the point of view that you will often see adopted in more advanced texts.