Goal: In this lab, you will learn to use Matlabs backslash operator for signal denoising.

Getting started: You will need to download the file m551lab10.m and put it in your working directory.

What you have to submit: The file m551lab10.m, which you will modify during the lab session.

Reminders About the Grading Software

Remember, the labs are graded with the help of software tools. If you do not follow the instructions, you will lose points. If the instructions ask you to assign a value to a variable, you must use the variable name given in the instructions. If the instructions ask you to make a variable named x1 and instead you make a variable named x or X or X1 or any name other than x1, the grading software will not find your variable and you will lose points. Required variables are listed in the lab instructions in a gray box like this:

Variables: x1, A, q

At times you will also be asked to answer questions in a comment in your M-file. You must format your text answers correctly. Questions that you must answer are shown in gray boxes in the lab. For example, if you see the instruction

Q7: What does the Matlab command lu do? your file must contain a line similar to the following somewhere

% Q7: It computes the LU decomposition of a matrix.

The important points about the formatting are

• The answer is on a single line.
• The first characters on the line is the comment character %.
• The answer is labeled in the form Qn:, where n stands for the question number from the gray box.

If you do not format your answers correctly, the grading software will not find them and you will lose points.

Basic Ideas

Consider the following figure.

This is a simulation of a noisy signal. The idea is that a broadcasting station (e.g., a radio transmitter) has sent out a smooth, time-varying signal s(t) (shown with the black curve). However, because of noise in the environment (e.g., scattering from trees, interfering signals, etc.), what we have received is a corrupted version of the signal s_cor(t) (the blue line). The noisy signal follows the general shape of the original signal, but also jumps up and down rapidly in time. Our job is to reconstruct as well as possible the original signal from the noisy signal by filtering out the noise.

Our first step is to convert the problem into the language of linear algebra. To do this, we will discretize time. That is, rather than working with the values of s(t) and s_cor(t) for all real numbers t, well sample s and s_cor at a finite set of time values {t₁,t₂,,t_n}. That allows us to represent s and s_cor as vectors in Rⁿ.

s(t1)

s(t2⁾ x = and x_cor.

s(t_n)

Our goal, then, is to use the corrupted signal x_cor to produce a smoothed signal y that is hopefully close to the original signal x (y x). One way to do this would be to use orthogonal projection onto a suitable basis. This time, however, well use a different technique, called regularization.

Let > 0 be a positive number (called the regularization parameter), and, for every y in Rⁿ, define

n1

f(y) = ky xcork2 + 2 X(yi+1 yi)2.

i=1

The first term in f(y) measures how close y is to the received signal x_cor; it is small for y x_cor and large for y 6 x_cor. The second term measures how rough y is. If each entry y_i+1 is not too different from the previous y_i, the sum of squares will be small. But if there are major changes from some y_i to the next y_i+1, these will cause the second term of f(y) to be large.

Now, consider choosing y to make f(y) as small as possible. By our previous analysis, we should expect the best y to strike a balance between being close to the received signal x_cor and being not-too-rough. The parameter quantifies the trade-off between these two goals. If is very close to 0, we wont care too much about roughness and so y will be very close to x_cor. If is very very large, we will focus almost entirely on roughness, and make each value of y_i+1 approximately equal to the previous:

yn yn1 yn2 y2 y1.

By tuning correctly, we might hope to balance between these two extremes and find a y thats not too rough but also not too far from x_cor.

Now, before we jump into the code, we only need to recognize the problem of minimizing f(y) as a least squares problem. To do this, we define the (n 1) n matrix D as

Now we will apply one final standard trick from linear algebra. (You dont need to understand why this works for the lab, but thinking about it after the lab is highly recommended. In working out why the following is true, you will be practicing a number of important skills from this class.) If we define the (2n1)n matrix A and the (2n 1)-vector b as

A and b

respectively, then

f(y) = kAy bk².

Tasks

1. Often, when defining matrices like A above, it is helpful to begin with n small enough that you can actually look at the matrix and check that it is correct. The first cell of the M-file, titled A small example demonstrates this technique. Run the cell and observe the output in the Matlab command window. Then read the code in the cell. Notice that, since A is a sparse matrix, we are using the sparse matrix functions speye and spdiags to create A. (Remember, if you dont know how to use a function, you can always use doc.)
2. Now, run the cell labeled Part 1. It should produce a figure like the one above. To complete this cell, you need to define the variables A1 and b1, corresponding to A and b, in the places indicated. (Hint: you can copy and paste from the first cell. Just make sure to rename A and b.)

Variables: A1, b1

If you look at the documentation for Matlabs backslash operator, you will see that, when applied to an overdetermined system, the result will be the least-squares solution. Thus, the code

% find the solution y1 = A1b1;

beneath your variable definitions produces the solution y that were looking for. If you have defined your variables correctly, running the cell should produce the following figure.

3. As you can see from the figure, the choice = 1 for this problem does filter some of the noise, but is still quite rough. Try several other values for . Notice that = 1000 is too large; the smoothed signal is essentially constant. A around 10 or 15 seems fairly good for this example.
4. Now, lets try a different choice of matrix D. Well use the (n 2) n matrix

1 2 1 0 0

0 1 2 1 0

D = .

• 0 1 2 1

In the cell labeled Part 2: Another small example, define the variable D2 where indicated. Hint:

>> e = ones(5,1); full(spdiags( [e,-2*e,e], [0,1,2], 3, 5 )) ans =

• -2 1 0 0

0 1 -2 1 0

0 0 1 -2 1

Run the cell and make sure the output looks correct. Variables: D2

5. In the cell labeled Part 3, complete the code to solve tMath 551 Fall 2018Lab 10Goal: In this lab, you will learn to use Matlabs backslash operator for signal denoising.Getting started: You will need to download the file m551lab10.m and put it in your working directory.What you have to submit: The file m551lab10.m, which you will modify during the lab session.
   

   Reminders About the Grading Software

   Remember, the labs are graded with the help of software tools. If you do not follow the instructions, you will lose points. If the instructions ask you to assign a value to a variable, you must use the variable name given in the instructions. If the instructions ask you to make a variable named x1 and instead you make a variable named x or X or X1 or any name other than x1, the grading software will not find your variable and you will lose points. Required variables are listed in the lab instructions in a gray box like this:

   Variables: x1, A, q

   At times you will also be asked to answer questions in a comment in your M-file. You must format your text answers correctly. Questions that you must answer are shown in gray boxes in the lab. For example, if you see the instructionQ7: What does the Matlab command lu do? your file must contain a line similar to the following somewhere% Q7: It computes the LU decomposition of a matrix.The important points about the formatting are

   • The answer is on a single line.
   • The first characters on the line is the comment character %.
   • The answer is labeled in the form Qn:, where n stands for the question number from the gray box.

   If you do not format your answers correctly, the grading software will not find them and you will lose points.

   Basic Ideas

   Consider the following figure.This is a simulation of a noisy signal. The idea is that a broadcasting station (e.g., a radio transmitter) has sent out a smooth, time-varying signal s(t) (shown with the black curve). However, because of noise in the environment (e.g., scattering from trees, interfering signals, etc.), what we have received is a corrupted version of the signal s_cor(t) (the blue line). The noisy signal follows the general shape of the original signal, but also jumps up and down rapidly in time. Our job is to reconstruct as well as possible the original signal from the noisy signal by filtering out the noise.Our first step is to convert the problem into the language of linear algebra. To do this, we will discretize time. That is, rather than working with the values of s(t) and s_cor(t) for all real numbers t, well sample s and s_cor at a finite set of time values {t₁,t₂,,t_n}. That allows us to represent s and s_cor as vectors in Rⁿ.s(t1)s(t2⁾ x = and x_cor.s(t_n)Our goal, then, is to use the corrupted signal x_cor to produce a smoothed signal y that is hopefully close to the original signal x (y x). One way to do this would be to use orthogonal projection onto a suitable basis. This time, however, well use a different technique, called regularization.Let > 0 be a positive number (called the regularization parameter), and, for every y in Rⁿ, definen1f(y) = ky xcork2 + 2 X(yi+1 yi)2.i=1The first term in f(y) measures how close y is to the received signal x_cor; it is small for y x_cor and large for y 6 x_cor. The second term measures how rough y is. If each entry y_i+1 is not too different from the previous y_i, the sum of squares will be small. But if there are major changes from some y_i to the next y_i+1, these will cause the second term of f(y) to be large.Now, consider choosing y to make f(y) as small as possible. By our previous analysis, we should expect the best y to strike a balance between being close to the received signal x_cor and being not-too-rough. The parameter quantifies the trade-off between these two goals. If is very close to 0, we wont care too much about roughness and so y will be very close to x_cor. If is very very large, we will focus almost entirely on roughness, and make each value of y_i+1 approximately equal to the previous:yn yn1 yn2 y2 y1.By tuning correctly, we might hope to balance between these two extremes and find a y thats not too rough but also not too far from x_cor.Now, before we jump into the code, we only need to recognize the problem of minimizing f(y) as a least squares problem. To do this, we define the (n 1) n matrix D as

   10D = 0Then	11	010	1	00...1	so that	y2 y1 3 y2 yDy = .yn yn1
   		f(y) = ky xcork2 + 2kDyk2.

   Now we will apply one final standard trick from linear algebra. (You dont need to understand why this works for the lab, but thinking about it after the lab is highly recommended. In working out why the following is true, you will be practicing a number of important skills from this class.) If we define the (2n1)n matrix A and the (2n 1)-vector b asA and b respectively, thenf(y) = kAy bk².

   Tasks

   1. Often, when defining matrices like A above, it is helpful to begin with n small enough that you can actually look at the matrix and check that it is correct. The first cell of the M-file, titled A small example demonstrates this technique. Run the cell and observe the output in the Matlab command window. Then read the code in the cell. Notice that, since A is a sparse matrix, we are using the sparse matrix functions speye and spdiags to create A. (Remember, if you dont know how to use a function, you can always use doc.)
   2. Now, run the cell labeled Part 1. It should produce a figure like the one above. To complete this cell, you need to define the variables A1 and b1, corresponding to A and b, in the places indicated. (Hint: you can copy and paste from the first cell. Just make sure to rename A and b.)

   Variables: A1, b1

   If you look at the documentation for Matlabs backslash operator, you will see that, when applied to an overdetermined system, the result will be the least-squares solution. Thus, the code% find the solution y1 = A1b1;beneath your variable definitions produces the solution y that were looking for. If you have defined your variables correctly, running the cell should produce the following figure.

   3. As you can see from the figure, the choice = 1 for this problem does filter some of the noise, but is still quite rough. Try several other values for . Notice that = 1000 is too large; the smoothed signal is essentially constant. A around 10 or 15 seems fairly good for this example.
   4. Now, lets try a different choice of matrix D. Well use the (n 2) n matrix

   1 2 1 0 00 1 2 1 0D = .

   • 0 1 2 1

   In the cell labeled Part 2: Another small example, define the variable D2 where indicated. Hint:>> e = ones(5,1); full(spdiags( [e,-2*e,e], [0,1,2], 3, 5 )) ans =

   • -2 1 0 0

   0 1 -2 1 00 0 1 -2 1Run the cell and make sure the output looks correct. Variables: D2

   5. In the cell labeled Part 3, complete the code to solve the problem (similar to Part 1) with the new choice of D. Be sure the variable names for A, b and y are A3, b3 and y3 Again, try a few choices for . When = 100, the figure should look like this:

   Variables: A3, b3, y3

   Q1: Describe the y that results when = 10⁵.he problem (similar to Part 1) with the new choice of D. Be sure the variable names for A, b and y are A3, b3 and y3 Again, try a few choices for . When = 100, the figure should look like this:

Variables: A3, b3, y3

Q1: Describe the y that results when = 10⁵.