So now that we know what sing, what
orthogonal matrices
are I want to introduce something called
the singular value factorization.
So this is a way you can take any matrix
and write it
as a product of an orthagonal matrix,
a diagonal matrix and another orthoganol
matrix.
Oh, so far, we have, if Q is orthogonal,
then Q inverse is equal to Q transpose.
I think I've mentioned diagonal matrices
before, but just to be, sort of.
pedantic about it I suppose.
A diagonal matrix has non-zero entries, or
entries that
may or may not be zero, down the diagonal.
So the diagonal elements are the elements
where the two subscripts match.
So it's the same row as, it's in the same
row as it is in columns so it would be.
D11, D22, D33 and anything where the
subsequents don't match outstrips, so
I is not equal to J, though it has to be
zero.
[COUGH]
So a diagonal matrix sort of looks like it
has nonzero entries,
down the main diagonal and everyone else
it has to be zero.
And if I have a diagonal matrix, this is
also something that's very easy to compute
the inverse of.
So, D inverse is just going to be the
inverses of the diagonal elements.
So I have 1 over d1, 1 over d2
so on down to 1 over dm.
And so D inverses is only going to
exist if all of these diagonal elements
are Non-zero.
So orthogonal matrices and diagonal
matrices have nice properties, so that
in particular this one nice property that
they're both easy to invert.
[NOISE]
And so my idea is wouldn't it be nice if
any matrix could be expressed
as a product of orthogonal matrices and
diagonal matrices?
[COUGH]
And it turns out it can and it's called a
singular value
factorization.
So every m by n matrix a can
be factored into.
So, u is a
orthoginal matrix.
Sigma is a diagnol matrix,
and v is a orthoginal matrix and the
factorization puts
v transpose.
So this is the picture for m greater than
n and
really the only thing that changes if the
number of columns
is greater than the number of rows then
this rectangle in
the middle turns sideways so it's fatter
than it is high.
And then the V matrix, the V transpose
matrix.
So this star is the same thing as
transpose.
This would just be the bigger matrix, and
U would be the smaller matrix, because
the, the dimensions have to line up still.
So I can take any rectangular matrix.
And factor it into an orthogonal factor,
a diagonal factor, and another orthogonal
factor.
And so, just a bit of terminology, so U is
an m by m
orthogonal matrix, and the columns are
going to
be called the left singular vectors of A.
Sigma, so this is the matrix in the middle
here, is an m by n diagonal matrix.
So since I'm drawing the picture for m
greater than n so it's a matrix
that has more rows then it has columns,
the rectangle is skinnier than it is tall.
And this dark band, this is meant to
be, this is where the non-zero elements
are allowed,
and every where else in this matrix, where
it's white, those elements are forced to
be zero.
They're required to be zero.
And so even though this matrix just to
make the dimensions work
out, it has to have the same dimensions as
the matrix A
It's only the elements where the indices,
so the row
index equals the column index, that are
allowed to be non-zero.
So, you end up with this rectangular chunk
of zeros in the bottom here too.
And so this matrix contains something
called the singular values of A.
And so, because the whole matrix is called
sigma, the singular values are also
denoted as sigmas.
And they actually end up being in sorted
order.
So the top left one here, sigma 1, is the
biggest,
then the one in the 2,2 position here is
sigma 2.
And so on down to sigma n in the n n
postion here.
And the singular values have to be greater
than or equal to zero.
[COUGH]
And then finally this matrix v on the
right
hand side is a n by n orthogonal matrix.
Whose columns contain the right singular
vectors of A.
And the motivation for this is that
multiplying any vector that
touches the unit circle, so this is a
vector of length one.
that.
So this set of vectors of length one is
called the unit circle.
When I multiply that by a two by two
matrix,
it's going to turn that unit circle into
an ellipse and
so I've got this picture that everybody
shows for this.
And what ends up happening is you have
these two directions that
are kind of hidden, they depend on the
matrix that I'm multiplying by
[COUGH].
So in this case my matrix A, it's got
these right singular vectors, V1
and V2, and if you imagine what I'm going
to do if I multiply A times X.
What I'm really going to do with this is a
times x is going to be equal to if I, if
I were doing a multiplication stage wise
I'd have to start on the right.
So first I would multiply
v transpose times x.
Then I would multiply sigma times the
results of that first multiplication.
And that I would multiply u times the
result of that second
multiplication so a times x, it's just
going to be v transpose times x.
Then sigma times that.
And then u times that.
And what's going to happen is for these
two special directions, v1 and v2
Those are going to get rotated to be the
new x and y axes.
So that's what the multiplication by v
transpose does.
Then, when I multiply by sigma, that's
just going
to stretch this thing in the x and y
direction.
So I'm going to stretch.
The y-values by a factor of sigma
2, and I'm going to stretch the x-values
by a factor of sigma 1.
And then finally when I multiply by u,
it's going to rotate that
because an orthogonal matrix, you can
think of it as a rotation.
And so it's going to rotate that back.
And so what I end up with are V2 times, or
A times V2 ends up becoming
this vector here and A times V1 ends up
becoming this vector here.
So, I think.
I've done all of this down below, so I
have 8 times v2 is going to be
equal to my singular value factorization
times, of a, times v2.
Then when I do the first multiplication,
so remember I'm
doing this to one of the right singular
vectors, v2.
So when I multiply v2 by this matrix v
transpose,
I'll have v1 times v2, but because they're
orthoginal,
that's going to be zero.
And then I have v2 times v2, and because
these are orthonormal vectors, that is
going to be equal to 1.
Then I want to multiply this vector 01 by
this matrix sigma
1 sigma 2, and that's going to give me the
vector 0 comma
sigma 2.
And then I'm going to multiply that by u,
and so
I'll have u1 times 0, plus u2 times sigma
2.
And that's sort of the story of how this
vector v2 gets turned into this vector
over here.
So just to give another example, so.
It's kind of tricky to see what happens
here.
Because this only works for these singular
vectors.
Because those are the ones that are
going to
end up being exactly on the axis again.
So I end up with a vector either 1,0 or
0,1 when I have the singular vector.
I pick a vector that's not a singular
vector.
And just to find my matrices like this so
I made my matrix a just by choosing
what I wanted its singular value
factorization to be.
So if I want to visualize this I'll start
out with choosing x to be a vector that
goes up 45 degrees and has length one And
then I'm going to multiply that by v
transposed.
So v rotates a vector right by 22 and a
half degrees.
V transposal, then, just rotate it left by
22 and a half degrees.
So, if I start out
with this vector, multiplying it by v
transposed So I'm changing
X, here, to be whatever V transposed times
the original X was.
That rotates this vector from here to the
left, until it's this direction.
But notice, it's still the same length.
Then I'm going to multiply by sigma.
So I'm going to stretch the X coordinate,
so I'll take this coordinate, here.
And multiply that by 1.5 and stretch the y
coordinate by 2.
So stretch the y coordinate.
So here, the y coordinate is twice as high
as it was over here.
And the x coordinate is one and a half
times what it was over here.
And then finally, I'm going to multiply
that
by u, and so notice now this gray vector
Is just the product of A times x.
Here, I rotated the vector.
Once I've multiplied it by the singular
values, notice it now
has the same length as the vector that I'm
aiming for.
And then U rotates the vector right by 45
degrees
and that ends up putting it exactly over
the grey vector.
So that's just a kind of some idea of what
this is
trying to do, where the idea of a singular
value decomposition came from.
So the idea is
you can think of matrix multiplication as
a rotation then some stretching and
the stretching happens in exactly the
coordinate
direction, so that's what makes it useful.
Coordinate directions have the easiest
ones to look in, and then you
have to rotate back to get the answer in
your original coordinate system.
So I've made an example of this in R, and
I think I didn't do this yet but I
will put this data set on the course
website
so you can download this, it's just these
points here.
And then there's a package called MASS
that has this function in it called
eqscplot.
This just stands for equal scale plot.
So all that's happening is, whatever scale
goes on
the y-axis, exactly the same scale goes on
the x-axis.
So the, the y range and the x range are
the, are the same two numbers.
[COUGH]
Oops.
And then I'm going to use the function in
R, so usually in linear algebra class
they'd
spend quite a lot of time explaining how
you would actually compute a singular
value decomposition.
I'm just trying to explain a little bit of
the interpretation
so r has a function that will compute it
for you.
It's called svd and I'm going to save the
results of this function as something
called svdr.
And this actually a structure in R called
a
list, and you can get at the individual
elements
of those, so the pieces of the list, the
things in the list, using the dollar sign
operator.
And so the three things that the singular
value factorization has are matrix u,
the singular vectors.
And the matrix v, and so I'm going to in
these next three steps here, oops.
Okay, I guess I can't highlight.
Oh, I can do it that way, okay.
So these three steps, I'm just plucking
out.
Those things that I want from the svd
output.
So the capital U will be the matrix u.
Here, just to save storage space.
If I have an answer that I know is a
diagonal matrix, usually R is not going to
give me back a whole matrix that only has
the diagonal that's non-zero.
So what R actually does is just gives me a
vector that's equal to the diagonal.
So I'm going to use this function diag, to
make
a diagonal matrix using the elements of
that vector.
So S here is going to be the matrix
with these diagonal values.
And then V is going to be.
The, the v.
So it's not v transpose that comes out of
the software, It's actually the matrix v.
And then to just make sure I got
everything right, this
is just u times s, or this is the sigma
part.
And then times the transpose of v.
And this function all equal.
Returns true if its two arguments, so this
thing which should all multiply
together to be this original matrix, and
the original matrix.
So if those things are, if every element
of those two
matrices is equal than all equal is going
to return true.
So this is just a little check to make
sure that I did things right.
And then what I want to do is look at what
are the, so
B is the right singular vectors, so it's
kind of hard to see because they
are short here, but there is a red vector
pointing up at about 45
degrees, and then this orange vector
pointing
down and right at about negative 45
degrees.
And what I've done is just plotted so
arrows draws an arrow on the plot.
So this is the red
arrow goes from 0,0, so it goes from
the origin, to the first singular vector
so that's
just how you would draw the first singular
vector, and the orange is the second
singular vector.
And so if you see what it's sort of
showing, when I make this, the plactive of
this data set, it kind of has one long
direction, and one short direction.
And so the singular, the right singular
vectors are telling me what those
directors are.
So, the first singular director is
pointing in the long direction.
And it also corresponds to the biggest
singular value.
And the orange arrows pointing, what it's
actually pointing and here it's going to
be
the shortest direction, but it's pointing
in the
longest direction that's perpendicular to
the first direction.
So, in a two-dimensional
plot there's only one direction
perpendicular to the first direction.
In three dimensions, If this were the
first direction,
then I can point to any direction in the
plane.
So, I would get the first direction being
sort of the most variation in this cloud.
The second direction being perpendicular
to the first one, but then showing
the second direction with the most
variation and then the third one
being the smallest.
So, right now this is just showing
the interpretation of the right singular
vectors.
And now what I can do is also multiply
them.
I need to, to rescale so they get bigger
based on the number of data points
I have.
So I need to rescale the singular values
by the square root of the number of data
points minus 1.
And now, not only does this plot tell you
what the directions
are, so the red direction is sort of the
length of.
The most spread out the data can be and it
also gives you the relative length so you
can compare the
length of the red arrow compared to the
length of
the orange arrow to try and get some idea
of the,
the ratio of how things are spread out in
the
red direction versus how their spread out
in the orange direction.