Okay. Good morning, everybody. You see, there is a questionnaire, please, to fill that out and we'll collect it at the end.
Also, assignment three in the usual pattern is due Tuesday, the week after next.
I guess assignment two will be handed back on next Tuesday.
McHale Is there anything you want to tell people about assignments?
Okay, we're fine. All right. So today's our last day on linear algebra, and then the final few lectures of this term will be related to optimisation.
And what I want to do today is first talk at a high level about matrix factorisation and algorithms,
and then talk about the singular value decomposition. One of the most important of all, the matrix factorisation.
So. So Matrix Factorisation and I guess that Section 2.8.
Linear algebra is more or less it was more or less born in the 19th century.
And then after computers came along this way of thinking in terms of matrix factorisation came along.
It turned out that a fruitful way to think of algorithms was as taking a matrix A and turning it into some product of simpler matrices.
And in fact, I like to say that this is the central dogma of numerical linear algebra.
So central dogma of numerical linear algebra is that algorithms, at least the classical algorithms.
Correspond to matrix factorisation. This expression, the central dogma is one that Francis Crick made famous in biology,
where the central dogma is that DNA turns into RNA, which turns into proteins.
So I think it's a good idea that every field should have a central dogma that's ours.
It sort of came along gradually over the decades, 1950s, 1960s, and is now just absolutely the way that numerical people think about these algorithms.
The general flavour is that you take an arbitrary matrix and you turn it into pieces that might be diagonal or triangular or orthogonal.
Those are the three big ones diagonal try, diagonal, triangular or orthogonal.
From those pieces, you can work with pieces like that more easily than with general matrices.
For example, if you want to find eigenvalues of a matrix, the algorithms make the matrix diagonal.
And then of course, you know, the eigenvalues of a diagonal matrix.
They're the entries on the diagonal. Now what I want to do is summarise the seven most important factorisation in numerical linear algebra.
So here they are. The first one is the Q r factorisation.
We've seen most, but not all of these. And in my summary, I'm going to suppose that a is a real square matrix.
So that's of course not always true, but let's imagine that a is a real matrix of dimension.
And by M in that case the Q are factorisation is a factorisation of a matrix a an arbitrary real square matrix.
A into q times. R Where Q is orthogonal.
An hour is up a triangular. Let me remind you that if A were rectangular, then Q would have all the normal columns.
But when a square Q is square. So those are the normal columns mean that it's an orthogonal matrix.
Now, what is this used for? Well, it's used a lot. It's used all over the place.
But in particular, it's important in least squares calculations.
It's the starting point of anything you do and least squares, really.
And it's also a step in iterative algorithms for eigenvalues and related things.
So in particular for eigenvalues, which I like to write like that, and the singular value decomposition,
the way those things are computed is by an iterative algorithm where at each step you do Q, r, factorisation.
So this really transformed numerical linear algebra in the 1960s using the use of the q r factorisation as proposed by householder.
The second one I'd like to mention is Lou Factorisation.
Now, this is the oldest one in some sense. This is Gaussian elimination, basically.
This is what we all learn when we first encounter linear algebra.
You subtract multiples of one row of a matrix from other rows to introduce zeros.
You make a matrix triangular by Gaussian elimination that can be regarded as an l u factorisation.
Now, in the simplest form, it would be a equals l u, where that's lower triangular and that's upper triangular.
But more generally, there's a permutation matrix on the left.
So this would be the standard version of Gaussian elimination.
L is unit lower triangular.
That means that l is lower triangular with one is on the diagonal u is upper triangular.
And P is a permutation matrix. Now a permutation matrix is a matrix whose rows are permutations of the rows of the identity equivalently,
whose columns are permutations of the columns of the identity.
When you take p times A, you're commuting its rows.
Gaussian elimination typically is set up to per mute rows in order to make sure that the numbers we divide by are not too small.
So this is the standard version of Gaussian elimination with partial pivoting, which is the workhorse of solution of systems of equations.
Now, one of the handouts maybe you can look at now is an essay I wrote a few years ago about Gaussian elimination as an iterative algorithm.
There's some fascinating history here.
Let me remind you that conjugate gradient was invented in 1952, and the authors regarded it as both an iterative and a direct algorithm.
But somehow most of the world interpreted it mostly in those early years as a direct algorithm.
And then about 1971, with the work of John Reed and others, people began to interpret it as mostly an iterative algorithm.
Now. Gaussian elimination, weirdly.
Has a slightly analogous history. It's, of course, in some sense ancient certainly goes back to Gauss.
Actually, it goes back to the Chinese. 2000 years ago.
And of course, its main use is a direct is as a direct algorithm, which means you have a matrix.
You do the elimination and you get to the end and then you stop.
Now, that's still true. That's still the main use. But sort of in the last ten years.
There's a big business going around where people do low rank compressions of things.
So this is a big theme in large scale linear algebra these days where you take a matrix that
might be a million by a million and you try to represented by something of rank 100 or 200.
Now, what does that mean to be rank 100 or 200? It means.
u1v1 transpose plus you to the to transpose and so on up to some modest number 200, let's say.
So there's a picture of a rank one matrix plus another rank, one matrix plus another micron matrix and so on.
200 of them. That's a rank 200 matrix.
That's a fruitful way to approximate matrices of dimensions in the millions somehow, sometimes.
For example, the famous Netflix competition where people were trying to predict movie preferences.
Is in this general area. You have this vast matrix where one dimension is movies.
The other dimension is viewers of movies.
You only have a few of the entries, but if you make the approximation that the Matrix has reasonably low rank,
you can predict the next movie that you're going to like.
That turns out to be intimately related with Gaussian elimination.
And let me just draw the picture of why that is. Suppose you have a million by a million matrix or a 10 million by a million matrix.
Suppose you find the biggest entry in it and then consider that row and that column.
Well, the product of that row times, that column is a rank one approximation.
If you take your matrix and subtract off that rank, one approximation suitably scaled,
you get something which is now zero in that column and that row.
Then you do it again. So that was the first step.
At step two, you find the biggest entry of what remains, and you draw a row and a column through there, and then you subtract off that rank one term.
So we've now approximated this huge matrix by a rank to approximation.
If you continue that process, that turns out to be a pretty good way to find low rank approximations to matrices.
And lo and behold, that's exactly Gaussian elimination.
It's actually Gaussian elimination with not only row interchanges, but also column interchanges.
But basically, that's one way of interpreting the Gaussian elimination process.
So I'm telling you on this panel that every algorithm should be interpreted as a matrix factorisation.
But I'm contradicting myself over here because the easiest way to draw this picture is not as a matrix factorisation,
but just as a decomposition into a sum of rank one pieces.
So just to finish off the history of conjugate gradients as a direct algorithm essentially is dead and nobody would ever use it that way.
Hardly. Gaussian elimination remains mostly a direct algorithm, but this iterative side of it is growing in a dramatic way.
An important part of large scale data manipulation. Okay.
That's the end of the digression. Let's return to the picture.
Of course, I should summarise what L'ue is used for.
So it's used for systems of equations.
And low rank compression.
Now the next one is called classic factorisation, and that's Gaussian elimination in the special case of a symmetric, positive, definite matrix.
You remember my rule of thumb that half of the problems that arise in practice are symmetric.
Positive. Definite. Suppose if a is symmetric positive definite, then we can write a as an l u factor with a symmetry in it.
So we write a equals r. Transpose r.
So now hour is up for triangular. You can actually do this.
If a is a semi definite, it might have zero eigenvalues, but it can't have negative eigenvalues.
And this, of course, is used for symmetric positive definite systems.
Of equations. So in MATLAB, for example, if you type backslash, it actually figures out whether your matrix is symmetric or not.
If it's not symmetric, it uses L2 factorisation.
If it is symmetric, it tries to key factor zation and if that's successful, then it knows it was not only symmetric but positive definite.
If it's unsuccessful, it knows that it was symmetric but not positive.
Definite. And it goes back and uses lru factorisation. Let me mention.
And the fourth one is eigenvalue factorisation.
So when you do an eigenvalue factorisation, you're making a matrix diagonal.
So we could say like this A equals the D the inverse.
Now, this is not always possible because not every matrix is diagonal visible, but generically every matrix is.
If you take a matrix that isn't and perturb it a little bit, it will be.
So here what we have is a has to be a diagonal sizeable square matrix.
And this has to be non singular. And D is diagonal.
So this is called a similarity transformation. And as you know,
I'm sure the eigenvalues of a matrix are the same as the eigenvalues of an another matrix related to it by a similarity transformation.
So whatever V is, so long as it's not singular, the eigenvalues of A are the same as the eigenvalues of D,
and if D is diagonal, those are the diagonal entries. So let me just remind you of the point here, which is algorithms in all of these cases.
The algorithm that is the standard one consists of constructing the factorisation
to simplify the problem and then doing what you need to do in that simpler form.
So for example, if you want to solve a system of equations,
you turn the matrix into a lower triangular and an upper triangular product that then amounts to a succession of two problems,
each of which is triangular. It's easy to solve a triangular system by substitution.
You do one variable, then the next, then the next.
Similarly, in this case, if you can make the matrix diagonal, then of course it's trivial to solve the eigenvalue problem.
So that's how it's done. Somehow or other you make the matrix diagonal, then you've got an easy eigenvalue problem.
I have three more to mention, so I guess I'll leave those there and move here.
The fifth one is again eigenvalue factorisation, but in the special case of a symmetric matrix.
So I'll call it the orthogonal eigenvalue factorisation.
I remind you that if you have a real symmetric matrix then it has a complete set of orthogonal eigenvectors in the continuous analogue,
as if you have a mission operator like the Schrödinger operator.
It has a complete set of orthogonal eigen functions. So that's the case where everything works as beautifully as possible.
If you think of it in terms of matrices and factorisation, this becomes Q de, q transpose.
A special case of this in which V is orthogonal.
So in this case, Q is orthogonal. And D is diagonal.
So the algorithms for solving symmetric matrix eigenvalue problems consist of orthogonal operations that reduce it to diagonal form.
There's another eigenvalue factorisation, which in fact is closer to what the algorithms do than what I described here.
And that's called the sure factorisation.
So if you have a diagonal sizeable matrix, then there exists some similarity transformation which takes it to diagonal form.
But you can imagine there must be something, a little suspect about that operation because if your matrix is merely non diagonal,
Isabelle, something's got to go wrong here. And that is indeed true.
The inverse becomes huge, typically. It turns out that every matrix diagonal, visible or not, can be made triangular as opposed to diagonal.
So the sure factorisation is a equals q t q transpose.
Where Q is orthogonal and T is upper triangular.
So let me just emphasise again that for this kind of eigenvalue factorisation where you make the matrix diagonal,
diagonal that only works for matrices that are diagonal visible, whereas the sure factorisation works for any matrix, any square matrix.
So that in fact is what algorithms really do normally for eigenvalues of non symmetric matrices.
And then the final one is the singular value decomposition.
The SVOD, the singular value decomposition.
The roots of this are a century or more old, but it became big computationally in the 1960s, and the famous man who made it big was Gene Ghalib.
What you have here is a factorisation of a matrix a.
Into a product you and it's normally written sigma v transpose where you and V are orthogonal.
And sigma is diagonal. And more than that.
It's if we write it in the usual form, it would have entries sigma one, sigma two down to sigma n and these are real numbers that are sorted.
So Sigma one is bigger than or equal to Sigma two and so on down to Sigma N, bigger than or equal to zero.
So that's the singular value decomposition.
It reduces a to a diagonal matrix.
You can always do that. But the catch is it's using different vector matrices.
On the two side, you and V are both orthogonal, but they're not the same in general.
So that's not a similarity transformation. You can do it for any A, doesn't have to be real.
That doesn't have to be symmetric. So these are really seven of the glories of our field.
Every one is important.
This one is hugely important, both for classical dense matrices and in all sorts of ways in the large scale world, in data analysis and big data.
People are always doing things related to the CVD.
It's related to principal component analysis, and the proper, orthogonal,
decomposition and coherent way of transformations are many ways that people have discovered things related to the 3D over the years.
Now I want to draw your attention to the ones here that generalise to rectangular matrices.
So QR Factorisation certainly does generalise to a rectangular matrix.
L'ue. Factorisation also generalises to a rectangular matrix.
Khaleesi does not because it's assuming symmetry. Eigenvalues does not because eigenvalues only make sense for square matrices.
So of course, that one also doesn't and that one also doesn't, but the SVD generalises.
So those three apply to non symmetric and non square matrices.
Also, classically, nobody would think of U for a non square matrix because classically we think of it as solving a system of equations.
But as soon as you get into these rank compression things, you are certainly using non square matrices.
Okay. So what we're going to do now is play with these factors, Asians with the code called M16.
So all I'm going to do here is pick a five by five matrix that I like and then play with it with the five with the seven factorisation.
So let's say A equals magic of five, which is a magic square consisting of numbers that all add up to the same thing.
Rows and columns. You probably know what that number is.
If I take the sums of the columns, I get 65.
Each column adds up to 65. If I take the sums of the rows, I get 65.
Each row adds up to 65, gets the convenient non symmetric matrix to play with.
So let's look at the QR factorisation of a there it is.
Let's make formats short. So there's a and there's its QR factorisation.
Of course you can't really see that Q is orthogonal, but you can see that our is upper triangular to machine precision a should be equal to Q are so
if I say Q times are minus A you see a matrix whose entries are of size ten to the minus 14th.
So that's to our factorisation. Let's do L'ue. So there's a again, let's say l u p equals l u of a.
That's wrong. Now you have. Right. So you see there that l is lower triangular and moreover it has ones on the diagonal.
You is upper triangular and p is a permutation matrix.
I didn't say that. Normally P would be chosen at each step to bring the biggest entry in a column to the diagonal.
If that's done, then l is not on the unit lower triangular, but all the entries below the diagonal have size at most one in absolute value.
Notice all the entries of l are positive. That's.
Totally not typical. And I presume that's a property.
I don't know. I'm guessing that's the property of magic squares. I've never noticed it before.
Is it? Here we have a statistical question. Is a five by five example enough evidence that.
I can't resist trying it. Let's see what happens. Let's just for fun.
Say L you p equals lieu of magic of ten.
And let's will then print l. Okay. Now, I don't have an opinion, but you all must have.
Let's have votes. Who thinks that all the entries below the diagonal will be positive?
Who thinks that they will be a mix of positive and negative. Okay.
So the people most people think mixed. I maybe I'm inclined towards the other, but I really don't know.
Um. You're right. Okay. So the five by five case was coincidence.
Okay. Back to good old A. Oh, we didn't confirm that.
Sorry. There's a. Once more there is its L2 factorisation.
We didn't confirm that the factorisation gives the right thing, so let's do that p times a minus l times.
You should be zero. And sure enough it's ten to the minus 14th.
Okay. Now let's try a classic factorisation. So there's a and it's not symmetric, let alone positive.
Definite. If I try call of a, it says error, which is the right answer.
Now suppose I try r equals call of a transpose a.
That is symmetric positive, definite. So it proceeds happily and indeed our transpose times are.
Minus a transpose times a is of size machine precision that's actually larger than I'd like it to be.
Ten to the minus 12th. I don't know why it's so big. Let's do another one.
So there's a again, let's look at its eigenvalues.
They happened to be all real numbers. A priori they might have been complex, perhaps, but they're all real numbers.
We could say the comedy equals I gave a and then we have the matrix of eigenvectors.
The five columns are the eigenvectors and then the matrix of eigenvalues.
So. If a equals v v inverse, that's the same as saying a vehicle's v d.
So the columns of V are the eigenvectors of a.
And let's confirm that a times v minus V, times D should be zero.
So make sure you're with me on this. A times V amounts to multiplying a by each of the five columns of V,
and the results should be those columns scaled by the eigenvalues on the diagonal of V.
So if these are really eigenvectors, we should get zero.
And sure enough, ten to the -13. Okay.
Let's try of a plus a transpose.
That's a real not positive definite matrix. So it's symmetric but not positive.
Definite. It has real eigenvalues and some of them are negative.
So I could say QED equals I of a plus a and there you have the eigenvalues and you also have orthogonal or a normal eigenvectors.
130 Y 130. Well, the Magic Square has its biggest eigenvalue 65 and the eigenvector is the constants all ones.
Here, you see, that's that eigenvector constant. And because we've had a plus eight transpose, we have 65 plus 65.
And if I confirmed that that works, I could say a plus, a transpose minus.
Q Times, the times. Q transpose, and that is not zero.
What did I do wrong? Oh I'm sorry.
Cos I didn't do a placé transpose did I. Thank you.
That should have been A-plus transpose. And now 130 is on the bottom.
Right. That's okay. And let's now confirm.
Yeah. Machine precision. Okay.
Well, let me remind you again that the eigenvalues of a look like that and that every
matrix has a sure factorisation an orthogonal reduction to triangular form.
So if I say Q T equals sure of A, then you see we've got a orthogonal matrix and a triangular matrix.
So I could say A minus. Q Times T times.
Q Prime machine precision.
Finally, we're going to talk about the SVOD. Now, the SVOD of a if you guessed type that you get the numbers, which are its singular values.
If you type USV equals SVOD of a, you get the three matrices you FMV.
So there we have diagonal, singular values, all positive real numbers and the two orthogonal matrices.
You and V, I could say A minus you.
Times F, times v. Transpose.
So this kind of stuff is happening all the time. Whenever you compute with matrices, virtually anything you do will involve a matrix.
Factorisation. Okay.
So let's talk about the SVD in particular. So the speed is a very pretty topic.
It is more important than you could possibly imagine in practice.
It's used all over the place. And one of the prevailing facts decade after decade, especially at Oxford,
is that mathematics students are not taught as much about the speed as they should be.
At at more applied universities. The balance is better, but at a at a really high powered,
pure mathematical bastion like Oxford University, students are not taught enough about the speed.
I don't fully understand why that is. Of course, it's a newer concept in practice.
Eigenvalues. Students Learn All About. Eigenvalues are essentially an algebraic concept.
Singular values are more of a concept of analysis, so they almost have a completely different flavour.
And the algebra always wins at the undergraduate mathematics level.
So here, as in so many places, you probably find that engineers know more about singular values than mathematicians.
Okay. Let's get a sense of what's involved here.
So as I mentioned, the SVD consists of a factorisation into orthogonal times,
diagonal times, orthogonal, and the diagonal entries are non-negative real numbers in order.
And let's now allow you to be rectangular.
So if a I mean, if A is a rectangular matrix and by n for simplicity, I'll assume that M is bigger than or equal to N.
Then what we have here in the form that people would most often use it in practice.
Is a rectangular matrix. A is equal to a rectangular matrix U times a diagonal matrix sigma times a square matrix.
V So this is a equals u sigma v transpose and by n m by n and by n and by n u.
When we talked about square matrices, that was orthogonal, but now it will have all the normal columns.
So U has all the normal columns.
And of course V is orthogonal. So that's the standard way that the the SVD is used.
It's the idea is to take a matrix which maybe has a lot of rows and find new bases for the range and the domain.
So in effect, this is a basis for the domain and this is the basis for the range of a.
And here's the picture that is at the heart of everything. Take any matrix.
If it's an m by n matrix, then it's a map. From our end.
To our M. Let's see what happens when a is applied to a ball.
So just the out of the ball defined in the obvious way in our end all the vectors of size at most one.
Every matrix without exception. Always maps. The unit ball on to an ellipse, or more precisely, I should say, a hyper ellipsoid.
What's a hyper ellipsoid? It's a ball that gets stretched in linear fashions.
So every matrix, without exception. Will map 020, of course, and then it will map this ball into some hyper ellipse.
This is an end dimensional object. This would generically be an end dimensional hyper ellipsoid, but it might be flat in some dimensions.
So its, its actual dimension could be less than n in those degenerate cases.
Now, the SVOD is all about describing that map.
Suppose you have an ellipse? It has a major semi axis and a minor semi axis.
Generically speaking, you have no choice here except plus or minus signs.
If it happened that the two were of equal length and this was a circle, then you'd have a choice.
But generically, they're uniquely defined. So let's call this one.
Sigma one time, you one.
The length of this is the first singular value.
The direction of it is the first singular vector, which means the first column of you.
So you one is the first column of you. And let's pretend this is a picture in any dimensions.
So I'm going to call this one the last one. This will be sigma n.
U n. So I really should have used the red pen for consistency.
So we take our hyper ellipsoid and we look at its principal axes.
Those are the singular vectors you sub j times the corresponding singular values sigma subject,
and it's clear geometrically that that's a sensible thing you can do.
And now the remarkable fact, which of course, can be proved and may not be obvious at first,
is that the pre images of these principal axes are always orthogonal over here.
So we don't know where the pre image of that line is and who knows where.
Let's say there and let's call that V one.
That's the first column of the orthogonal matrix v and we don't know where the pre image of that will be, but it will be orthogonal to v one.
So let's suppose it's here. That's V two.
VM. Sorry, that's. We're thinking of that as the last one, aren't we. So that's what the SVT does.
That's the picture you should always have in your head. The SVT is about describing the orthogonal bases that correspond to each other.
When you map a unit ball onto a hyper ellipsoid and it's perhaps intuitively plausible that because of the orthogonal ity of those bases,
these are numerically a very good way to work. If you want to study the properties of a or of a inverse, this is a magnificent way to do that.
The singular value decomposition has no relevance to powers of a if a square.
And you want to talk about a to the 10th array to the millionth, the speed is irrelevant because the left and the right have different bases.
You can't you can't square it or qubit. You need eigenvalues for that.
The SVT is always about a itself, not powers. Okay.
Let me. I think I've actually said all this already, but let's just spell it out a little more fully.
So the picture I'm talking about is that you have a matrix A and we are thinking in terms of multiplying it by.
Vectors v one through v. N. That's equal to.
A matrix you won through U.N. Times.
The diagonal matrix. Sigma one through Sigma n.
So I got this equation by taking that picture and multiplying it on the right by V.
So the SVOD, this is the algebra corresponding to that picture a times a singular vector V
gives you the corresponding singular vector you scaled by a singular value.
So the picture and the algebra are the same. Now let's imagine that you have a vector B which is equal to a times that coefficient vector x.
Then another way to say that is that B is equal to U Sigma, the transpose x.
And another way to say that is that.
You transpose B? Is equal to Sigma Z, transpose x.
That's not a sum. That's a matrix sigma. And now that neurone in your brain fires and you see that this is the vector.
Of coefficients of X.
In the basis of columns of the.
Now an arbitrary M vector could not be represented in as a linear combination of these and.
Vectors you want through UN, but if it happens to be in this form, then it can be.
So this is a vector of coefficients.
Of be in the basis.
Of columns of you.
So in other words, what we're saying here is that if you take a matrix A and then change bases in both the domain and the range in this 3D fashion,
then the problem becomes diagonal. Every matrix is diagonal in some suitable, orthogonal, chosen basis.
And that's why the SVOD is so useful. Okay.
I'm going to play with it in a minute on the computer. But first, I want to tell you some key algebraic facts.
So here are some facts. And this is for rectangular, which, of course, has a special case would include square.
So one fact every a has a singular value decomposition.
In contrast to an eigenvalue decomposition. Singular vowels are unique.
But not singular vectors. The singular vectors always have plus or minus one choices, and in none generic cases they have further choices.
Beyond that, the two norm of a matrix is something we haven't defined, but it's a standard concept and it's equal to the first singular value of a.
The obvious norm of a matrix is also something we haven't defined.
People write at a sub f, but it's easy to define that one.
It's just the square root of the sum, of the squares,
of the entries of a and it's also equal to the square root of the sum of the squares, of the singular values.
So the definition is that it's the sum of the entries squared.
Square rooted. Well, that's equal to the sum of the singular value squared and then square root it.
It's also true that the singular values of a.
Are equal to some of the set of singular values of a is equal to the set of square roots of eigenvalues of a transpose.
So mathematically that means you can relate this as 3D to an eigenvalue problem, but it's an ongoing value problem for a different matrix.
And moreover, numerically, that's not something to do if you can avoid it because it sort of squares the condition number.
So that's not the standard way people compute the CVD,
but you could in principle compute the CVD by computing the eigenvalue decomposition of a transpose.
Couple more facts. The rank of AA is equal to the number of non-zero singular values.
So you can see that's a very practically important thing. When MATLAB computes the rank of a matrix, it finds the speed.
It ignores singular values that are down at machine precision and tells you how many singular values are well above machine precision.
The range of A is equal to the span of you.
One through you are where R is the rank.
So the singular vectors you sub j give you an orthogonal basis for the range of a.
And then I also want to write down three facts, four square matrices.
So first fact is that the product of the singular values so the product,
let's say of sigma sub j is equal to the product of the absolute values of the eigenvalues, which in turn is the absolute value of the determinant.
So singular values and eigenvalues have some connections.
The normal, the inverse.
And again, that would be the two norm of the inverse which we haven't defined is equal to one over the smallest singular value.
And finally. The condition number of a which is defined as the product of the norm of a.
And the norm of an inverse. Well, you know what that is?
Because the norm of AA is sigma one. The norm of AA inverse is one over sigma n.
So that's the ratio of the largest to the smallest singular value.
So the speed is everywhere in numerical linear algebra.
There isn't really time to talk about how it's used for low rank approximation, but let me just say a word or two.
I mentioned that Gaussian elimination can be thought of as a way to compress a matrix, to find a low rank approximation.
You have a million by million matrix. You find a rank 100 approximation.
Well, the SVD is the optimal such approximation in the to norm and also in the obedience norm.
So if you want the optimal rank 100 approximation to a million by million matrix,
then mathematically you get that by taking the first hundred singular values and singular vectors you and singular vectors.
V That's optimal in the mathematical sense.
The trouble is, it's hard to compute. There's no way to compute the speed of a million by million matrix.
So if the matrix is small enough that you can afford to compute, it says it gives you optimal algorithms for low rank approximation.
If the matrix is huge, people use approximations to the CVD such as Gaussian elimination.
And I just want to finish by playing around with some two by two matrices.
So this is now the code called M 17.
So if you glance at the code, you'll see it's an infinite loop. And at each step, it finds a random matrix of dimension two.
And then a computer test feed. And then it draws a picture of the map from that ball to the hyper ellipsoid.
Except it's not a hyper ellipsoid. It's just an ellipse. So I'll say M17.
So. There is a matrix, two by two matrix and it maps the unit ball in the plane to there.
And you can see we've drawn the singular vector U one times the singular value.
And similarly over here. Those seem to be on the axes.
That's an astonishing coincidence. It's completely random.
How did that happen? It's totally misleading. You should not expect the blue and the red lines to be on the axes.
What property of a made that the case. Can we spot that?
Michael, are you quick enough to spot that? Oh. Anyway.
I'm astonished. Somebody tell me later what property of A leads to that.
Let's do another one, which I hope will be more generic. Okay, that's more generic.
Let me draw your attention to the fact that there's no right hand rule here.
The red one is on the right of the blue one, and from the left over there,
it could go either way because some matrices are rotations and others are reflections.
And you can predict it has to do with whether the determinant is positive or negative.
So let's do a few more. That one also came out with a negative determinant.
I can tell by the orientation of the blue and the red. Let's find one with a positive determinant there.
Okay. So that must have a positive determinant because they're oriented the same way.
This is a very well conditioned matrix because the ellipse is nearly a circle.
Let's press the button a few times until we find an L Condition matrix.
I'm looking for an ellipse that's very narrow. So that's air conditioned.
Now. What does it mean to be ill conditioned? It means you're nearly rank deficient.
If that were actually gift the segment, you'd be perfectly rank deficient.
So if we look at that matrix, we should find that the first two columns are nearly multiples of one another.
And sure enough, it looks as if the second column is about three and a half times the first column.
Similarly, the second row is about nine.
Did I say that wrong? No, that's right.
And the second row is about -1.7 times the first drop or something like that.
So every matrix has this property in 2D, it's just ellipsoid, but in multiple dimensions.
It's an n dimensional ellipse. Okay. See you on Tuesday.