So, so far we talked about
singular value decomposition.
We saw that it gives us the best possible
projection in terms of
reconstruction error.
But what we also saw it that there,
is that there are two, two drawbacks.
First drawbacks was computational,
that it takes lots of time to compute.
It kind of takes the cubic time
in the size the data to compute.
And the second approx, problem was
that the results we get are these,
dense vectors that can take lots of
space and they're hard to interpret.
So the CUR Decomposition
is a different type
of dimensionality reduction technique.
We will talk about it next.
And basically it tries to,
alleviate some these,
drawbacks of singular value decomposition.
So what is our goal?
In, in general our goal is very
similar to the goal we had with
singular value decomposition.
So again, we are given matrix A.
And we want to express it as
a product as three matrices.
Now these three matrices are called C, U
and R and similar to what happens in SVD,
our goal here will be that we want the
difference between the original data and
the reconstructed data to
be as small as possible.
While singular value decomposition gives
us the, the optimality guarantee and
says this is the best what we can do.
Here we will allow ourselves to some,
to maybe have a bit larger
a deconstruction error, but, you know,
at a much smaller computational cost.
And the way we will think
about this is the following.
We are thinking that we
are given matrix A as an input.
We want to express it as a product of
three special matrices C, U and R.
And, as we do a singular
value decomposition,
we will put some constraints on
the structure of matrices C and R.
And the way we do this
constraint is very interesting.
So let's see how we are putting
constraints in, on C and R.
So the idea is the following.
The constraint on our matrix C Is that,
basically, it has to contain
columns from matrix A.
So the way we will compose matrix C,
is that we will choose carefully, or
using some algorithm, a set of,
columns from matrix A.
And we will put those into matrix C.
So, our matrix C is simply
a set of columns from A.
Similarly we will take the matrix R and
we will do the same, but now for rows.
So, [INAUDIBLE] we pick a set of rows
from matrix A and put them into R.
So, why, why do we call matrix R,
R because R stands for
rows and why do we call matrix C,
C because C stand for columns.
Right, so what are we,
what are we doing so far is we will
create matrix A as a product of three
other matrices where matrix C will
simply contain columns from A and
matrix R will contain rows from A.
And now, of course the question
will be what is the matrix U.
So, the way we will compute the matrix
U is that we will compute what is
called the pseudo-inverse of
the intersections of C and R.
I will explain this in more detail, but
that's basically the high-level idea.
Why is this a good idea is
because selecting rows and
columns to fit them into C and R will
be something that we can do very fast.
And this means that the whole computation,
computation will be very quick and
very easy to do.
Okay.
So
the question is how does
CUR correspond to SVD?
And is CUR decomposition
doing anything useful for us?
So first let's assume the following case.
Let's assume that A sub k is the best
k approximation to our input matrix A.
We already know how to compute A sub k.
We compute it using the SVD.
Which means we take the matrix A,
do the singular value decomposition,
take the first k largest singular values,
set the rest to zero,
and, multiply the, the three matrices
together, and we obtain A, A sub k.
And when I say, best, right?
We already know what best means.
Best means in terms of the frobenius norm,
which means that A minus A sub k,
in terms of frobenius norm
is as small as possible.
So now what Mahoney and Drineas proved
is the theorem that connects the quality
of the CUR approximation to
that of SVD approximation.
And what the theorem says is that
the reconstruction error of CUR is less
than the reconstruction
error of SVD plus sum
epsilon times, the Frobenius norm of A.
So, basically,
Frobenius norm of A tells us how,
what is the magnitude of
the values in matrix A.
And what the, what the whole theorem says
is that the CUR reconstruction won't be
too far away from the SVD reconstruction.
It will be, it will be some additive,
additive error term away from the SVD
reconstruction, which is kind of the best
possible reconstruction we could achieve.
What are the conditions for this to hold?
So if you want, if,
if we allowed SVD to pick k columns and
paste k singular values.
We will allow CUR in composi,
decomposition to pick k,
k times log 1 over delta divided
by epsilon squared columns and
k squared times log to the cube
1 over delta epsilon to
the 6th rows where I can think of
epsilon to be something small,
and I can also think delta,
as a, as a small quantity.
Of course, what is important
to know here is that this is
a probabilistic guarantee that says,
you know, this, this equation up here,
this guarantee will be true with
probability of at least 1 minus delta.
And, but what is important is that
basically here we establish the quality of
the CUR decomposition, but
the computational time is much shorter.
Right?
So co, co, computational time to
do this is of order m times n, which
basically is the order of our data size.
And that's much less than the,
what we had for SVD, where we,
where we had it as m times n cubed.
Okay?
So what does this means,
this is kind of a complicated theorem, but
what this means that in practice
we pick about 4k rows and columns.
And we will do, as well as SVD does if,
when SVD picks, k rows and columns.
So CUR needs more of those.
But then we an important structure in the
real data which actually allows us that,
to do much better with s
CUR than we can do with s