So today we will start talking about d squared, and single value decomposition. D squared is a very important concept used many times in our engineering world. It was used for example by Gauss. In his calculation of the orbits, of earth around the sun. In computer vision b square is used many, many different cases. What we'll study through a sequence of examples. First, we're going to take a detour. So, a computation known as singular value decomposition or svd. It is one of the most useful tools you will encounter in our computation of vision problems in the next few lectures. Singular value decomposition, is a way of taking a matrix a, and decomposing to three separate components. So matrix a, could be of many forms, it come from many different reasons, and physical meanings. The end results is we have a matrix a of size m, by n. Given any matrix of a, which you can think of as a transformation themselves. We can decompose this matrix, into three components u, d, and v transpose, meaning that u, multiplied by d, multiplied by v transpose will reconstruct the matrix exactly. And this is a very interesting fact. Like any matrix a can be decomposed in this following fashion. And the u matrix that we have has a particular property. U matrix, can be thought of columns, and each columns with a u, has a property that take a half part between themself equal to one, meaning that each column, the u, is a norm of one. Furthermore, if I take two columns u, and take that part out between them, the answer is zero, meaning the u's are constructed, such that all the columns, are perpendicular to each other. Second perpendicular to first, third perpendicular to both first, and second. Such you can think of the u's, essentially basis function, spanning the same space, as the columns of a. Similarly, the draws of the v transpose, also had a following form that take any draws of the v transpose will have perpendicular vectors. Or mathematically, one could write, u transposed times u equal to and v transposed v equal to. So that's, the first fact of the singular value decomposition. That a matrix a can decompose into a set of column vectors u perpendicular to each other, a diagonal matrix d, and a set of rogue perpendicular vectors v transposed. And multiplying the three matrix, reconstruct the matrix a exactly. And we can always do this. In the math lab, this is function called svd. The second, fact of this decomposition is that the singular value matrix are diagonal forms. Meaning the elements are zero, and the non zero elements sits, on the diagonal. And the color coded here, dark large values. And one can always sort it, from large to small. So sigma one, larger than sigma two, all the way bigger than zero. So all the values on diagonals are positive, or zero. We will see cases when the last element is zero, or several of the elements are zero. The u matrix is going to be the size of same, as a and by n. The diagonal matrix singular value matrix is size, m by m, and the v transposed matrix is size m by m. We can think of the u matrix, as set of basis. For example, if a is made of curve, and since this space where every column of a is a curve, we can think of the u matrix enclose the basis function, where the first base is, for example, is a horizontal curve, and the second basis function is a curve going down. And the third basis encode a curve going up, and down. Then we can think of the matrix v together with the singular value d, provides a coefficient for every column a. So, the coefficient of the beta1, beta2, beta3. So through a scaling of a beta1, beta2, beta3, it provides a reconstruction in column of a, which is represented by a curve here. As such we can think of u is basis, and v, the columns of v transpose provide us the addresses. Multiply to the scale factor, give us the beta1 to beta n. So, the first factor we can think of is svd, as transforming matrix a, into it's basis function, and the transformed addresses. So let's just think of this painting by Mondrian. What is the svd of this painting? Well first of all, what is this painting? The painting in, our world is in fact a matrix. Where rows, and columns are pixels. And Mondrian, paintings are very good illustration of this basis, because all the Mondrian paintings are made of rows, and columns. So let's take this Mondrian painting, and first convert a colored image to a gray skull image, shown on the top left. Right here use the colormap jet in the matlab illustration, where red indicated bright pixels, blue means dark pixels. So this is a Mondrian in the black, and white world, but illustrated in the colormap jet. And we were take svd of this image, which is made of thousands rows, many thousand columns, we see that we can construct svd of this matrix. And to reconstruct from it a u matrix. And here, I illustrated only the first four columns of the u to highlight what it looks like. So first note, the first columns are almost uniforming it's values. The second column we can see, has some positive value which indicated in orange, and some negative values indicated in blue. As such, you can see that this perpendicular to the first column. In the image, what it's capturing, it's saying that Mondrian paintings are made of two halves. On the top half, which are one color, and the bottom part of the image is another color. Move out to the third column of u, we see, again, is made of some value, a positive some value, a negative Positive mean indicated in red, blue indicating the negative values. Again, this vector is perpendicular, the first two columns. And again if you look at this picture, what it is indicating is telling us the Mondrian paintings for this picture has several rows have the same color, hence we have a basis vector with uniform color in it. Now just take in the four columns of svd of this picture I can reconstruct this picture by taking the first four columns of U. The first four by four matrix of a singular value matrix D, and the four rows of v. And reconstructing the matrix through the matrix multiplication is shown in the bottom right. As you can see, this is not exactly the same but it's a very close approximation than where we started. As such, we can think of svd is a process of simplifying what's in the matrix, very large matrix and then using a set of basis functions, illustrating U and using a set of addresses in V. If I were to take more rows and more columns view matrix but not all of them. For example, I only take the first 20 columns of the u matrix, I can reconstruct the Mondrian painting fairly closely. In the center at what I've shown here is the log of the singular values. As you can see, the log of a single values drop off pretty rapidly, indicating that many dimensions in the basis function has a scale factor near 0. And we're going to use this factor for many different cases. And we're going to use this for using svd as a clean up process of cleaning up a matrix. Or we can use this factor to approximate a large dimensional matrix with a few basis functions. So now let's look at Gauss himself in rows and columns. So Gauss is not painted by Mondrian so he has many orientations edges horizontal, not lines with horizontal vertical directions, but nonetheless we can take Gauss' image as a matrix and reconstruct itself. So on the middle we have a Gauss image reconstructed with more basis functions and the right we see a Gauss image reconstruct with a few vectors. And this is shown in grayscale. As you can see, it still captured the structure of his face fairly reasonably with on a few basis functions. And this is because many rows and many columns of this image are redundant, they are not exactly the same but it can be represented by a few basis vectors. So this is a look at a picture as a matrix where there are thousands rows and thousands of columns. One can also look at a picture as a vector by taking all of the rows, all of the columns and stacking them into one, long vector. So if I have a 1000 by 1000 image, that would be a vector of a million dimension long. This is illustrating here images not as a matrix, but image as a vector. As such that I can take many, many pictures, many, many pictures of people's face for example. Each one forms a vector and I can stack the vector together each one, 1 million direction long, dimensional long, and then maybe thousand peoples, we have a million by thousand matrix. I can take a single value decomposition with that matrix that gives me a set of basic function u, and it reshape the use back to the image space. And this is what happens when we do that. On the left we have a set of images of the face. Each one stretch into vector space, placed column-wise next to each other. We computed svd of this matrix, and we take the first few columns of u, and reshape back to the image space. And this is called eigenfaces, as you can see those eigenfaces capture different characteristics of the face. For example some capture the hair, some capture the mouth. And from those basis functions, one can re-express our faces as addresses in those spaces. Here is a set of images captured by an artist for people in Berlin. On the left we have the first basis function for the man. On the right we have a first basis picture of the woman. Taking a view of eigenvectors as well as addresses, we can see here are three faces reconstructed by the same eigenvector or use different coefficients on this eigenvector. So, here we show different ethnic group it will show you by this eigenvector, address from one point address space to another point address space. Here we have a different eigenvector corresponding to the age changes. Again, as we change the address on this eigenvectors faces transform itself. So now we are seeing eigenvectors, singular value vectors, as our basis functions and as such that we can think of it as our basis functions and their addresses and together they reconstructed the matrix or in this case image for me. Once we have decomposed a matrix A into a singular value decomposition, u times d times v transpose, we can also understood the concept of rank and now space. A rank of matrix A is simply defined as the number of the non-zero singular values in the matrix d. So we call that r, rank of A equal to r. The number of elements non-zero on the diagonal. And r is going to be less than equal to the dimension of m or n. The null space is corresponding to exactly those elements associated with singular values equal to zero. So if the rank is r, then the columns in V or rows in V transpose associated with those dimensions where single value is 0, are the null space. So we take the columns, from r plus one all the way to n. If r is the rank, r plus one to n columns of V is the null space of A. And we have the following property that A Times the nullspace V, r plus one to n, equal to 0. And this fact will become very convenient for us as we start looking at a least square problem of form A times X equal to 0. So now, let's look at this example of singular varying decomposition. In the following matrix, we will reconstruct this matrix in the later lectures. And this matrix called a Fundamental Matrix. It's a very simple matrix, in three by three, relating two pictures taken from different position in the world. Take this matrix F. We can take the singular value decomposition SVD as the standard matlab. We can display the value U and V. And we see those values are perpendicular to each other. We can also look at the diagonal elements on the D. We see the first values are pretty large, the second value is not small but it's not 0. And the last value is e to the minus 16. In Matlab, this is a value close enough to 0. And we will use this fact as a way of cleaning up matrix in the future. That if I want to make a matrix of rank two, I simply compute the SVD and set the last element to 0 and reconstruct the matrix F. If I want to take an inversion of a matrix A, this also can be done fairly easily. Take SVD of A matrix first into U D V transpose and always take those inverse of a matrix A by simply inverting the diagnom elements itself. Taking the sigma to the one over sigma if sigma is larger than 0 and said zero otherwise. I would take the matrix V. D that transpose and that is the reverse of A. So now, we are ready to return to our topic of V square problems. There are two type of least square problems. One type, we'll have the form of matrix A times x equal to b or written to Ax-b and minimize the norm of that. Here the b is not zero. The second type of least square problem we have is the form of Ax, A is the matrix itself times x and we want to minimize the norm such as it is as close as possible to zero. So, the problem we are solving is ax equal to zero. For this problem, the the simple solution is actually very straight forward, where x equals zero. But we are not interested in a vector. We are interested in a vector that is not zero. In fact, have nominal one such that A times this vector x is as close as possible to the zero. We're already seeing a hint of that how to solve that in a single valid deep composition slides. We know that this vector is situated in a null space of A. We now illustrate this types of a least square through a simple line fitting process where A is a simple line fitting equation. In practice, there are many different types of as in different situations. We'll revisit many of those in the subsequent classes. For two dimensional data, we have a point, have this location x and y. And if a set of points happen to situated almost like on the line, we expect there will be a two parameter line controlled by the slope c and offset d, such is that cx + d = y. So, we can rewrite this process of looking for c and looking for d as the following least square problems. Where we want to minimize the norm of y- c times x- d. We want to minimize this quantity which is a square quantity for every data points we have. First, we want to do is construct this matrix A. So, how do we do that? For this equation, we take the y = ax + b into a simple matrix form. We take all the ys into a column vector, y1 to yN. We construct a matrix A is an nx2 matrix, where the first column is simply the x, and the second column is just ones. It's a simple two column matrix and unknown factors are left out in the 2x1 factors C and D. As we can see, we obtain this equation when we have a vector b correspond to the y's and a matrix A which is mi2 matrix correspond to the x and one. And we have obtained a generic form of v square where vector b- ax needs to be minimized. Now, let's look if we have only one point, we only have one data point. What will happen? We have infinite lines, in fact. We can fit any line we want through a single point. So, the solution is not defined, or there are many solutions. If I only have two points and that two points you need to find the line, the error will be zero. Only when I have multiple points, both of x y will have a problem where if all the points are not all aligned on the line, we do not have ax equal to b, we want to minimize this norm which we indicate the vertical distance from the point to this line. And this can be computed through a simple errorvation shown here. And the solution is represented by this equation. Where x is unknown two dimensional vectors c and d is calculated. So, what I would call the pseudo inverse of a. So, this line is summarized, the general solutions for at least square problems, ax=b. There are three cases. The first case, the one rank of A equal to R less than N. So, in a previews case, N is two, two columns. So, if your rank is less than two we only have one points. See in that case, we'll have many solutions. So, the solution for this problem is taking the inverse of A as we've shown before in the SVD slides and add onto it all possible linear combinations in the now space of A, so there are many solutions to this problem. When the rank of A is exactly equal to n, in our previous line fitting case where rank of A's were two, meaning there were many different rows of A, different points, but they exactly fit two The same line that we have the exact solution, where solution is simply A inverse times b. In most common cases, in most problem that we encounter, we have rank of A not equal to n. In fact we have the general least square problem and the solution is as what we have seen before through the pseudo inverse. In MATLAB this is a very simple, in fact it's called A\b and it computes the pseudo inverse for us. So this summarize the least square problem of Ax including b. Now we return to the type two of the least square of the form ax equal to zero, or ax the norm of that need to be minimized with the constraint that x is not equal to zero or the norm of x is equal to one. Return to our line fitting problem again. Last time we've seen the line fitting problem where we're minimizing the distance from the line, vertically to a point. So this is a reasonable assumption to make if the line is reasonably oriented. As we tilt the line vertically into a vertical direction. This computation becomes ill-defined. In fact, the better way to do this is to find the error, not in the vertical direction, but error in the direction perpendicular to the line itself. And this can be done using the equation shown here. Where we'd represent the line as a homogenous coordinates. Or made of three coefficient e, f and g. And then we will represent a point x, y through a three dimensional array of x, y1. Then we see the between the xy1 homogeneous point, with a line equation, should be equal to 0 if the line passes through that point. So therefore, the quantity, the between the homogeneous of the point x was the line. In fact it was the scaled perpendicular distance of that point of the line. And this is the quantity we want to minimize. We can rewrite this set of constraints, set of equations in the following form. Where we take the homogeneous coordinates of a point x, y, 1, for each points stacked on top of each other forming n by three matrix. And that's going to be the matrix A that we're interested in. And the indo vector corresponds to the line. So 3 prime at our vector efg correspond to the the homogeneous quadrants of the line. And we have A times this line need to be minimized. So we have to form an equation a x equal to zero, or we're going to minimize a quantity of a x and one of that. The trivia solution to this is obvious, where x is equal to zero. We're not interested in this point. And there's no such line as 0, 0, 0, no homogeneous coordinate system. We're interested in non 0 vector, such is that A times this vector is getting us close to this 0. And this vector, You will see is, in fact, the third columns of SVD of this matrix A. A in this case, again, recall, is a three column vector matrix, x, first column, y second column and one, the third column. And then we have end points. Corresponds to each data point we have. Only take this matrix a, compute a single value u d v transpose. Each [INAUDIBLE] are perpendicular to each other. We take the last rows of a v transpose, or the last column of v, and that Is the vector we want to minimize a x equal to zero. So once again we are looking for a x zero, there are three conditions. The first condition is when the rank of a is less than m minus one. And this case, again we have the ill defined parameters, there are many solutions to it. In fact, they correspond to any vectors in a null space of A. Take any linear combination of this null space vectors, satisfy the constraint, A axis is zero. If A A rank of A is exactly M minus 1. So if in our previous example, the rank is two, then we have the exact solution. Or the solution is set, the vector Vn. The last column in the single value decomposition or the column in the null space give us A x equal to 0. And there's only one vector in the null space in this case. In most general cases, we encounter the situation where A x is never equal to 0. In this case, to minimize this norm A x, we pick the last of the singular value g composition vn again. So if I wanted to pick a vector in the space of all the vectors, the one that minimize ax is the last columns of the v. So this factor will be used many many times. We will use a x zero to many different solutions for squares to triangulations. To. And we will come back to this square problem many times.