MATLAB 6 Least Squares Approximation - Signal Processing(DFT) Definition: Let the m x n matrix A have rank n. Then by the least squares solution of the system Ax = b is meant the solution x of the corresponding normal system byTTAAA. Note: The normal system has a unique solution bxTTAAA1)(; The orthogonal projection p of b into Col(A) is given by xp A. If the column vectors of A form an orthonormal set of vectors, then IAAT and the solution to the least squares problem is bxTA ********************************************************************* Let S be a subspace of an inner product space V and let Vx. Let }{nv,...,v,v21 be an orthonormal basis for S. If niiic1vpwhere iic vx,, then Sxp pis the element of S that is closest to x and is said to be the projection of x onto S. Let S be a nonempty subspace of mR and mRb. If }{kv,...,v,v21 is an orthonormal basis for S and ] [kV v...vv21, then the projection p of b onto S is given by bpTVV The matrix TVVis called the projection matrix corresponding to the subspace S of mR. The projection matrix is unique (Prove) Example 1: Let real} are ,|]0,,{[ yxyxST. Let T]4,3,5[w. If TT[0,1,0]&[1,0,0] 21vv, then T[5,3,0]wpTVV. Example 2: Find the least squares approximation to xeon the interval [0,1] by a linear function. Example 3: The trigonometric polynomial of degree n is the function of the form nkkknkxbkxaaxt10)sincos(2)( }sin ..., ,2sin ,sin ,cos ..., ,2cos ,cos ,21{ nxxxnxxxforms an orthonormal set with respect to the inner product dxxgxfgf )()(1,. The best least squares fit approximation to a continuous 2 periodic function )(xfby a trigonometric polynomial of degree n or less has Fourier Coefficients given by:1,0fa, ,cos, kxfak & kxfbksin,. Let )(21kkkibacand )(21kkkibac, 0k. Using these, it can be shown that nnkikxknecxt )( where dxikxexfkc )(21 The Discrete Fourier Series (Page 267) In what follows we assume that )(xfis a noisy signal (see figure 5.5.5 a in text). We will choose ]2,0[ instead of ],[. We want to approximate )(xf by nnkikxknecxt )( The trigonometric approximation represents the function by simple harmonics where the the k-th harmonic is )cos(kkkxr, where k is the angular frequency. A signal is smooth if the coefficients 0kc rapidly as k If some of the coefficients corresponding to larger frequencies are not small, the graph is noisy. We can filter the signal by setting these coefficients to zero. (see figure 5.5.5 b) In actual signal processing we do not have a mathematical formula for )(xf. Rather, the signal is sampled over a sequence of times Njxj2 and the function is represented by the N sample values ).(),...,(),(111100 NNxfyxfyxfy)]2(&)0([0fyfyN In this case, we cannot compute kc. Instead we use a numerical integration method, the trapezoidal rule, to approximate the integral. The approximations to the Fourier coefficients are given by 10)(1NjjikxejxfNkd If )2sin()2cos(2NiNNieN we can write 101NjjkNjyNkd The finite sequence {}kd is said to be the discrete Fourier transform of {}ky. The Fourier Transform can be determined by a single matrix vector multiplication. For example, if N = 4, )(4132100yyyyd)(413342241401yyyyd )(4136424412402yyyyd )(4139426413403yyyyd If z = (1/4)y = Tyyyy ] [413210, then the vector d = Tdddd ] [3210 is determined by multiplying z by the matrix i i i i F1 111 11 111111 1 1 11 1 1 1946434644424342444 called the Fourier Matrix FN is the NN matrix whose ),( kjelement is )1)(1(,kjNkjf. DFT algorithm is the method of computing the discrete Fourier transform. Exercises. 1. Derive the equation (5) on page 268. 2. Explain how the powers of 4 can be derived on the unit circle in the complex plane. 3. Determine all the powers of 8 by hand (using the unit circle) and write an exact form for 8F (no decimal approximations) 4. Use MATLAB to compute the DFT {0d, 1d, 2d, 3d, 4d, 5d, 6d, 7d} for the following data and plot the data 324.00y 456.01y 112.02y 202.03y 654.04y 234.05y 678.06y 867.07y 5. Plot the trigonometric polynomial)(xtn. 6. Compare the Exercise 8 with the built in MATLAB FFT (do an help