1
00:00:00,220 --> 00:00:03,430
So, so far we talked about
singular value decomposition.

2
00:00:03,430 --> 00:00:05,720
We saw that it gives us the best possible

3
00:00:07,130 --> 00:00:10,240
projection in terms of
reconstruction error.

4
00:00:10,240 --> 00:00:14,065
But what we also saw it that there,
is that there are two, two drawbacks.

5
00:00:14,065 --> 00:00:17,190
First drawbacks was computational,
that it takes lots of time to compute.

6
00:00:17,190 --> 00:00:20,560
It kind of takes the cubic time
in the size the data to compute.

7
00:00:20,560 --> 00:00:25,600
And the second approx, problem was
that the results we get are these,

8
00:00:25,600 --> 00:00:29,470
dense vectors that can take lots of
space and they're hard to interpret.

9
00:00:29,470 --> 00:00:33,390
So the CUR Decomposition
is a different type

10
00:00:33,390 --> 00:00:35,510
of dimensionality reduction technique.

11
00:00:35,510 --> 00:00:37,020
We will talk about it next.

12
00:00:37,020 --> 00:00:38,765
And basically it tries to,

13
00:00:38,765 --> 00:00:44,030
alleviate some these,
drawbacks of singular value decomposition.

14
00:00:44,030 --> 00:00:45,750
So what is our goal?

15
00:00:45,750 --> 00:00:49,170
In, in general our goal is very
similar to the goal we had with

16
00:00:49,170 --> 00:00:50,450
singular value decomposition.

17
00:00:50,450 --> 00:00:52,540
So again, we are given matrix A.

18
00:00:52,540 --> 00:00:56,260
And we want to express it as
a product as three matrices.

19
00:00:56,260 --> 00:01:03,280
Now these three matrices are called C, U
and R and similar to what happens in SVD,

20
00:01:03,280 --> 00:01:07,620
our goal here will be that we want the
difference between the original data and

21
00:01:07,620 --> 00:01:10,408
the reconstructed data to
be as small as possible.

22
00:01:10,408 --> 00:01:15,254
While singular value decomposition gives
us the, the optimality guarantee and

23
00:01:15,254 --> 00:01:17,755
says this is the best what we can do.

24
00:01:17,755 --> 00:01:22,232
Here we will allow ourselves to some,
to maybe have a bit larger

25
00:01:22,232 --> 00:01:26,750
a deconstruction error, but, you know,
at a much smaller computational cost.

26
00:01:26,750 --> 00:01:30,340
And the way we will think
about this is the following.

27
00:01:30,340 --> 00:01:33,170
We are thinking that we
are given matrix A as an input.

28
00:01:34,350 --> 00:01:39,690
We want to express it as a product of
three special matrices C, U and R.

29
00:01:39,690 --> 00:01:42,650
And, as we do a singular
value decomposition,

30
00:01:42,650 --> 00:01:47,660
we will put some constraints on
the structure of matrices C and R.

31
00:01:47,660 --> 00:01:51,320
And the way we do this
constraint is very interesting.

32
00:01:51,320 --> 00:01:54,670
So let's see how we are putting
constraints in, on C and R.

33
00:01:54,670 --> 00:01:55,810
So the idea is the following.

34
00:01:55,810 --> 00:01:58,050
The constraint on our matrix C Is that,

35
00:01:58,050 --> 00:02:01,880
basically, it has to contain
columns from matrix A.

36
00:02:01,880 --> 00:02:06,660
So the way we will compose matrix C,
is that we will choose carefully, or

37
00:02:06,660 --> 00:02:10,430
using some algorithm, a set of,
columns from matrix A.

38
00:02:10,430 --> 00:02:12,810
And we will put those into matrix C.

39
00:02:12,810 --> 00:02:16,330
So, our matrix C is simply
a set of columns from A.

40
00:02:16,330 --> 00:02:22,380
Similarly we will take the matrix R and
we will do the same, but now for rows.

41
00:02:22,380 --> 00:02:27,000
So, [INAUDIBLE] we pick a set of rows
from matrix A and put them into R.

42
00:02:27,000 --> 00:02:31,160
So, why, why do we call matrix R,
R because R stands for

43
00:02:31,160 --> 00:02:36,070
rows and why do we call matrix C,
C because C stand for columns.

44
00:02:36,070 --> 00:02:39,960
Right, so what are we,
what are we doing so far is we will

45
00:02:39,960 --> 00:02:45,300
create matrix A as a product of three
other matrices where matrix C will

46
00:02:45,300 --> 00:02:50,840
simply contain columns from A and
matrix R will contain rows from A.

47
00:02:50,840 --> 00:02:54,250
And now, of course the question
will be what is the matrix U.

48
00:02:54,250 --> 00:02:58,530
So, the way we will compute the matrix
U is that we will compute what is

49
00:02:58,530 --> 00:03:02,680
called the pseudo-inverse of
the intersections of C and R.

50
00:03:02,680 --> 00:03:06,790
I will explain this in more detail, but
that's basically the high-level idea.

51
00:03:06,790 --> 00:03:10,790
Why is this a good idea is
because selecting rows and

52
00:03:10,790 --> 00:03:15,230
columns to fit them into C and R will
be something that we can do very fast.

53
00:03:15,230 --> 00:03:18,510
And this means that the whole computation,
computation will be very quick and

54
00:03:18,510 --> 00:03:19,850
very easy to do.

55
00:03:19,850 --> 00:03:20,480
Okay.
So

56
00:03:20,480 --> 00:03:23,460
the question is how does
CUR correspond to SVD?

57
00:03:23,460 --> 00:03:27,230
And is CUR decomposition
doing anything useful for us?

58
00:03:27,230 --> 00:03:30,560
So first let's assume the following case.

59
00:03:30,560 --> 00:03:36,010
Let's assume that A sub k is the best
k approximation to our input matrix A.

60
00:03:36,010 --> 00:03:39,130
We already know how to compute A sub k.

61
00:03:39,130 --> 00:03:40,750
We compute it using the SVD.

62
00:03:40,750 --> 00:03:45,720
Which means we take the matrix A,
do the singular value decomposition,

63
00:03:45,720 --> 00:03:49,950
take the first k largest singular values,
set the rest to zero,

64
00:03:49,950 --> 00:03:54,740
and, multiply the, the three matrices
together, and we obtain A, A sub k.

65
00:03:54,740 --> 00:03:56,340
And when I say, best, right?

66
00:03:56,340 --> 00:03:58,100
We already know what best means.

67
00:03:58,100 --> 00:04:02,560
Best means in terms of the frobenius norm,
which means that A minus A sub k,

68
00:04:02,560 --> 00:04:06,380
in terms of frobenius norm
is as small as possible.

69
00:04:06,380 --> 00:04:11,830
So now what Mahoney and Drineas proved
is the theorem that connects the quality

70
00:04:11,830 --> 00:04:15,370
of the CUR approximation to
that of SVD approximation.

71
00:04:15,370 --> 00:04:20,690
And what the theorem says is that
the reconstruction error of CUR is less

72
00:04:20,690 --> 00:04:26,340
than the reconstruction
error of SVD plus sum

73
00:04:26,340 --> 00:04:30,170
epsilon times, the Frobenius norm of A.

74
00:04:30,170 --> 00:04:33,280
So, basically,
Frobenius norm of A tells us how,

75
00:04:33,280 --> 00:04:36,400
what is the magnitude of
the values in matrix A.

76
00:04:36,400 --> 00:04:41,230
And what the, what the whole theorem says
is that the CUR reconstruction won't be

77
00:04:41,230 --> 00:04:43,850
too far away from the SVD reconstruction.

78
00:04:43,850 --> 00:04:48,890
It will be, it will be some additive,
additive error term away from the SVD

79
00:04:48,890 --> 00:04:53,630
reconstruction, which is kind of the best
possible reconstruction we could achieve.

80
00:04:53,630 --> 00:04:55,970
What are the conditions for this to hold?

81
00:04:55,970 --> 00:05:00,810
So if you want, if,
if we allowed SVD to pick k columns and

82
00:05:00,810 --> 00:05:02,490
paste k singular values.

83
00:05:02,490 --> 00:05:07,860
We will allow CUR in composi,
decomposition to pick k,

84
00:05:07,860 --> 00:05:13,540
k times log 1 over delta divided
by epsilon squared columns and

85
00:05:13,540 --> 00:05:18,090
k squared times log to the cube
1 over delta epsilon to

86
00:05:18,090 --> 00:05:21,930
the 6th rows where I can think of
epsilon to be something small,

87
00:05:21,930 --> 00:05:27,040
and I can also think delta,
as a, as a small quantity.

88
00:05:27,040 --> 00:05:29,730
Of course, what is important
to know here is that this is

89
00:05:29,730 --> 00:05:33,050
a probabilistic guarantee that says,
you know, this, this equation up here,

90
00:05:33,050 --> 00:05:38,030
this guarantee will be true with
probability of at least 1 minus delta.

91
00:05:38,030 --> 00:05:41,600
And, but what is important is that
basically here we establish the quality of

92
00:05:41,600 --> 00:05:46,030
the CUR decomposition, but
the computational time is much shorter.

93
00:05:46,030 --> 00:05:47,510
Right?
So co, co, computational time to

94
00:05:47,510 --> 00:05:52,730
do this is of order m times n, which
basically is the order of our data size.

95
00:05:52,730 --> 00:05:56,410
And that's much less than the,
what we had for SVD, where we,

96
00:05:56,410 --> 00:05:59,900
where we had it as m times n cubed.

97
00:05:59,900 --> 00:06:00,480
Okay?

98
00:06:00,480 --> 00:06:04,340
So what does this means,
this is kind of a complicated theorem, but

99
00:06:04,340 --> 00:06:08,300
what this means that in practice
we pick about 4k rows and columns.

100
00:06:08,300 --> 00:06:13,410
And we will do, as well as SVD does if,
when SVD picks, k rows and columns.

101
00:06:13,410 --> 00:06:15,500
So CUR needs more of those.

102
00:06:15,500 --> 00:06:21,520
But then we an important structure in the
real data which actually allows us that,

103
00:06:21,520 --> 00:06:24,840
to do much better with s
CUR than we can do with s