And what does SVD do is the following if you take our
matrix A represent it exactly as a product of matrices u sigma and
v transpose before we said we can always do this.
But now, if we want to do dimensionality reduction, which basically means we,
means we take U sigma and V, but we take part of U and
cross it out, we take part of the sigma matrix, cross it out, and
we take, take part of the matrix V transpose and cross it out.
So, basically, now.
We represented everything instead of using R columns or, RO sin V,
re-represented using K, K ro, K ros, and K columns of V and U.
We obtain a new matrix, B.
Now that we multiply everything together and
the idea is that B is the best approximation of A.
So, what by best means is that the Frobenius norm,
the difference between A and B is small as possible, right?
So, in, in a case A and B are as close to each other as possible given
that we want to represent the data points with the small number of coordinates.
Okay?
So, to be very precise, here is, here is, what the, the theorem says.
The theorem says, let's take our input matrix A into an SVD only.
So it means, let's represent it as a product of matrices U, sigma and
V transposed, where sigma is the matrix of
singular values that are sorted in the decreasing order.
Then, let's define this new matrix B that is simply U times S, times V transposed.
Where what is important to note is now,
that matrix s is simply a diagonal matrix where the first K entries of s, are simply
the corresponding singular values from matrix sigma, and the rest is zero.
So now if we,
if we take, if we take this new product of some mat, I have the matrix here.
I have the matrix we transposed from before, but
now I basically took sigma and changed it into S.
Then I obtained this new matrix B, and the idea is that this matrix
B is the, the best reconstruction of A in a sense of the Frobenius norm.
So the way I can think of this is the following,.
So, I can think that B is simply a solution to the, to their question,
what is the best matrix B that I can find that minimizes the Frobenius norm,
where I want the rank of B to be equal to k.
So k is the number of dimensions we allow ourselves, the number of coordinates.
And what you want to find is the best v that most faithfully represents the data
represents the matrix a and what what do we learn from SVD is that if I'm given
matrix a represented as u sigma v transpose then I want to do dimensionality
reduction all I need to do is cross out the number of singular values.
Cross out, rows in, a and, cross out some, rows in b.
Now I multiply these matrixes together and I'll get,
I'll get a new, new matrix that is as close to the original one as possible.
So the reason why doing this works is the following.
Right, so, what singular value decomposition is
also called the spectral decomposition of a matrix.
And all this says right is what we know so
far is that we take our original matrix A and represent it as a...
Long and thin matrix U, the diagonal matrix sigma, and the matrix V transpose.
So, the reason is, why it's kind of zeroing out the low singular values?
What is the best thing we can do?
And the way we can learn this or
at least see why is that a good thing to do is the following.
We basically say, let's take our matrix A that has M rows, m columns.
And if you do the spectral decomposition of it, this basically means that we can
represent it as a, as a summation of k terms where we are taking sigma one which
is the first singular value, the u one the fir, the first draft singular vector.
Times, we want to transpose this as the first right singular vector, and then,
you know, plus the second singular value, the second left singular vector,
the second right singular vector, and so on, and so forth.
And, as I said before, we are assuming that, first,
we already know that singular values of sigma are greater than zero, and
we are also assuming now that they are sorted.
So, you know, the question is,
why is setting small sigma to 0 the right thing to do?
And the way we think about this is the following, right?
We already know that vectors Ui and Vi, they are unit length.
Right, so because the matrices U and V are column worth normal.
Which means every vector has a unit length.
So this basically means that when I take a product of U and V,
and then multiply the sigma.
Basically the sigma scales them, all right.
So, now if I want to have small error I want to,
I can kind of drop vectors that have small importance.
The basically have small sigma.
So, this is why zeroing small sigma's actually works and
produces the least possible amount of error.
And in this kind of un-informal argument we could also give up proof.
But this is the, the intuition why doing dimensionality deduction in a way of
setting small sigma's to zero actually works.
So of course, now the question is, how many dimensions to keep, right?
So if I take my matrix A, I do, I do it singular value decomposition, and
I obtain at the end some R which is the rank of the matrix
singular values and singular vectors, and r in, in kind of the worst case.
The r can be the, the smallest of m and n.
Right kind of the smallest the number of columns or followers of fixed point eight.
Then the question is, how many, how many while I'm doing Finsen introductions.
How many dimensions k should I keep, or
how many singular values sigma should I keep?
And a good rule of a thumb is that I should keep as many so
that my, I preserve 80 to 90% of the energy.
And the way I can do this is the following.
Basically, I define the total energy to be the sum of
the squares of the singular values.
And now what I want to do is,
I want to ensure that the sum over the singular values i to k.
Sigma i squared, right, is that a singular value, so I keep dividing these by the sum
of singular values, i up to r, r, these are all the singular values I get.
I want this ratio to be, to be around, point, eight, or 0.9.
And this is how many singular values I want to keep.
So that I still keep kind of 90% of the energy.
Of course, what we also have to talk about is,
what is the computational complexity of SVD.
And to compute SVD, there are standard linear algebra, algebra tools.
And basically computing SVD in some sense is cubic in the size of the data.
So it's the complexities n times m squared or
m times n squared, whichever of the two is less, right?
So, in some sense, it's, it's quadratic in the,
in the in the one dimension and linear in the, in the other dimension.
So what are the conclusions so far.
So what we know so far is the following.
We know that we can take any matrix A any old value matrix A.
That they presented by the product of three special matrixes, U sigma and
T transpose.
We know that this the composition is unique.
We know we can think of matrix U as a user to concept matrix.
We can think of matrix V as a movie to concept matrix, and we can
think of the matrix sigma, the singular values as the strength of each concept.
The other thing we learn in this, how do we do dimensionality reduction?
The way we do dimensionality reduction is by simply setting single
the smallest singular values to zero which also means we are kind of removing.
The corresponding left and right singular vectors to zero how many dimensions we,
we pick, we pick the them the enough singular values such that
the total energy that 80 to 90% of all the energy is preserved.
Energy defined as being the sum of the square singular values.
And, the other thing we, we saw from the data is that singular value is able to
basically peek up, or identify linear correlations in the data.
So, it's able to basically identify dimensions along which
the data is spread out the most.