Eigendecomposition : Data Science Basics

Key Takeaways

[Music] hey everyone welcome back today we're gonna be talking about eigen decomposition so I'll try to keep this video pretty short and sweet we're basically gonna go over what is an eigen decomposition how do you compute one by hand if you have two and then the most important part which is why are IND compositions actually useful for anything so first let's go ahead and talk about what it is you probably noticed the word eigen in the eigen decomposition and that's gonna be at the heart of how we actually derived so this has a lot to do with the eigenvalues and eigenvectors of a matrix which implies that the matrix we're working with in this setup has to be square because we know only square matrices have eigenvalues and eigenvectors so let's say we're working with this very small two-by-two matrix just for the beginning of this video so it's 1 4 9 and 1 so I have a whole separate video on eigenvectors and eigenvalues which I'll link in the description below but basically we can get the eigenvalues as 7 and negative 5 and then we can get the eigenvectors as 2 and 3 so this eigenvector matches up to the 7 and then 2 and negative 3 which matches up to the negative 5 now something we often also do is normalize the eigenvectors so that they have a unit norm so we can go ahead and do that and we would get u 1 and u 2 as the normalized eigen vectors corresponding to the first and second eigenvalue okay so so far a pretty standard procedure now what do we do with this if we look at all this set up we can actually compress this make it compact into a matrix form how do we do that so first we can look at these two equations which are literally the definition of what an eigen vector and eigen value is so a times u 1 u 1 being the normalized first eigenvector has to be equal to lambda 1 u 1 that's the definition same thing 8 times u 2 is equal to lambda 2 times u 2 so that's the definition again now we can put these two equations into a matrix form so we can put a on the Left put u 1 and u 2 which again are the normalized eigen vectors into their own little 2x2 matrix so just to be explicit here the first column is u1 and the second column is u2 and each these has two numbers so this in total is a 2x2 matrix and that is equal to u 1 u 2 so the same matrix that was right here times this diagonal matrix lambda 1 0 0 lambda 2 now it's not extremely obvious why this equation should be true but if you go ahead and actually do this very small matrix multiplication you'll see that what you get from this are exactly these two equations here okay so that means that we can write this in this form now let's give these guys a name so let's call this u 1 u 2 as just big u matrix and let's call this guy this lambda 1 lambda 2 diagonal matrix as big lambda so it looks like a a without the bar in the middle so that we now have this matrix equation which is a times u a times u is equal to u times lambda u times lambda and now what we can do to get a by itself we can apply the inverse of U on both sides so we can take inverse of U on this side inverse of U on this side and we get this and this thing that I've underlined in red is what's called the eigen decomposition if the reason it's called that is because we're decomposing a decomposing a matrix means splitting it up into its component matrices so we're taking a and representing it as three component matrices u lambda and u inverse okay and it's called an eigen decomposition because u contains the eigen vectors and lambda contains the eigen values so that's how you take an eigen decomposition what it means and how you would kind of do one manually if you had to although you pretty much never have to do that but now the most important part of the video is why is this actually useful at all what do we do by taking a matrix and splitting up into these three component matrices so consider this very very common routine procedure we need to do in data science which is taking a matrix to a power why is this a routine operation well think about what a matrix is from your very first definition of linear algebra you should have learned that a matrix is a linear transformation a much easier way to say it is a function which Maps some vector to another vector and often in data science and machine learning where some kind of algorithm where we're applying this linear transformation had every step of the algorithm which means that we have to apply this matrix several times which ends up becoming a matrix ^ some number so let's say we're trying to compute a a again just being any square matrix that we have the eigen decomposition for let's say we're trying to a to the power of some number P okay let's see what happens if we don't consider the eigen decomposition at all so let's just say that P is equal to 8 so we're trying to find a to the power of 8 I've actually explicitly written out eight days here and let's think about how we would do it being a little bit smart about it so we could first compute a squared so that's one matrix multiplication we just have to do and now we can do that for this pair this pair this pair and this pair so now the next step would be to compute a to the fourth by taking a squared and multiplying two of them together so now we have a to the fourth here and a to the fourth here the last step would be multiplying two of these a to the fourth together to get our final result of a to the eighth okay so we are a little bit smart about it in the sense that we grouped things together so that we weren't doing seven multiplications but how many multiplications that we actually have to do we had to find a squared then we had to find a to the fourth then we had to find a to the eighth so we have to do three multiplications in order to get this to happen and in general we're going to have to do log to of P okay so I'm going to write that here log to of P just a quick note why this is true so P here was 8 + log 2 of 8 is 3 which makes sense why we have to do three multiplications but in general when you group things into pairs like this the number of multiplications you're doing total is log 2 of whatever a number of things there were to begin with because this is logarithmically going down okay can we do better than this using the eigen decomposition the answer is yes so let's close this video by looking at how to make this a lot faster using an eigen decomposition so let's say we have the eigen decomposition of a which again is you lambda u inverse that means that a to the power of P we can write out as u lambda you in verse written P times at first glance it looks like I made this more complicated but there's a very special simplification we can make if we look at the fact that there's these U inverse use right next to each other several times in this big product and of course a matrix times its inverse is the identity so we don't have to even compute that so those all go away leaving a bunch of lambdas in the middle so that this big product simplifies nicely to u lambda matrix ^ P u inverse now the other big note is that lambda to the power of P is actually extremely easy to compute why because lambda is a diagonal matrix which means that the only nonzero entries in the matrix would live on the diagonal which means that taking that whole matrix to a power is the same thing as just taking any of the diagonal elements to the power of P that's written here as lambda to the P would be lambda 1 to the P lambda 2 to the P all the way to lambda n to the P and everything else would be 0 so this is not really as intense as doing a true matrix product it's literally just taking n numbers and raising them to some power ok so all that means that how many matrix multiplications do we actually have to do to get at our final result of a to the P well we just have to compute this quantity which means that we'll have to do one matrix multiplication for you times lambda to the P and then one more matrix multiplication for the result of that with u inverse on the other side which means we just have to do two matrix multiplications so compare two matrix multiplications with log two to the power of P as P gets very large let's say it's something like a hundred or a thousand this is gonna be way way way bigger than two okay so that's why the eigen decomposition is a useful tool for us data scientists and machine learning experts and whatever you might be doing because it's going to computationally take some very common operation like a matrix power and bring it down to a scale that doesn't cause us a huge computational overhead so hopefully you learn something about eigen decomposition through this video if you did please like and subscribe for more videos just like this any comments are welcome and I'll see you next time