5. Positive Definite and Semidefinite Matrices
MIT 18.065 Matrix Methods in Data Analysis, Signal Processing, and Machine Learning, Spring 2018
Instructor: Gilbert Strang
View the complete course: ocw.mit.edu/18-065S18
KZread Playlist: • MIT 18.065 Matrix Meth...
In this lecture, Professor Strang continues reviewing key matrices, such as positive definite and semidefinite matrices. This lecture concludes his review of the highlights of linear algebra.
License: Creative Commons BY-NC-SA
More information at ocw.mit.edu/terms
More courses at ocw.mit.edu
Пікірлер: 102
DR. Strang thank you for another classic lecture and selection of examples on Positive Definite and Semidefinite Matrices.
For everyone asking about the bowl and eigenvalues analogy: Let X= (x,y) be the input vector (so that I can write X as a vector) and consider the energy functional f(X)=X^t S X. What would happen if we evaluate on the eigenvalues? First, why would I think to do this? The eigenvectors of the matrix give the "natural coordinates" to express the action of the matrix as a linear transformation, which then gives rise to all the "completing the square" type problems with quadratic forms in usual LA classes. The natural coordinates rotate the quadratic so it doesn't have off-diagonal terms. This means the function changes from something like f(x,y)=3x^2+6y^2+4xy to something like f(x,y)=(x^2+y^2)=(||X||^2), where ||X||^2 denotes the squared norm. So the functional looks like a very nice quadratic in this case, like the ones you may learn how to draw in a multivariate calc course. Going back to the current calculation which f(X)=X^tSX: if we evaluate in the eigen-directions, then our function becomes f(X_1)=X_1^t S X_1=X_1 lambda_1 X_1= lambda_1 ||X_1||^2 (a nice quadratic) and f(X_2)=X_2^t S X_2=X_2 lambda_2 X_2= lambda_2 ||X_2||^2 (another nice quadratic). The eigenvalues lambda_1, lambda_2 become scaling coefficients in the eigen-directions. A large scaling coefficient means we have a steep quadratic and a small coefficient means we have a quadratic that is stretched out horizontally. If the eigenvalue is close to zero, the quadratic functional will almost look like a horizontal plane (really, the tangent plane will be horizontal) and hence not be invertible, so any solver will have difficulty finding a solution due to infinitely many approximate solutions. Since the solver will see a bunch of feasible directions, it will bounce around the argmin vector without being able to confidently declare success. Poor solver. Of course, these are purely mathematical problems; rounding error will probably mitigate the search even further. Edit: changed "engenvalue" to "eigenvector" in 2nd paragraph.
Positive Semi-Definite matricies: 38.01
@jonasblom6177
2 жыл бұрын
thanks man
@guythat779
2 жыл бұрын
What a king
@Luke-ty2ur
2 жыл бұрын
u the man.
@miguiprytoluk
2 жыл бұрын
38:01
Sooo love Prof. Strang!!
listening to Strang is like getting a brain massage
@CrazyHorse151
3 жыл бұрын
Im only half through one lecture and I already love him. :'D
@PremiDhruv
Жыл бұрын
I was going through a headache, after 15 minutes of his lecture it got evaporated.
@emanueleria8151
4 ай бұрын
Sure
Awesome video sir! Thank you!
Lecture starts at 2:50
Where was the energy equation mentioned in previous lectures?
I wish Strang was my grandfather
@NguyenAn-kf9ho
3 жыл бұрын
maybe he s not because he will be sad if his grandson s stupid and cannot inverse a matrix.... just kidding XD
@prajwalchoudhary4824
3 жыл бұрын
@@NguyenAn-kf9ho lol
@hxqing
2 жыл бұрын
Wishing he was and isn't ? Better wishing he is.
Very comprehensive. Thanks
came here from 18.06 fall 2011 Singular value decomposition taught by Professor Strang
Great work
at 41:20, why the rank 1 matrix has 2 zero eigenvalues? because 3 - 1 = 2? does the professor mean that number of zero eigenvalues always equals to nullity of that matrix?
This professor is the platonic version of a professor
I am doing a project on this topic it really helped me a lot..thank you
@samirroy1412
3 жыл бұрын
@@vishalyadav2958 yes
@samirroy1412
3 жыл бұрын
U r doing phd or post grad?
@samirroy1412
3 жыл бұрын
U can follow horn n johnson and strang book... it's relatively easier to understand
Well thanks prof.
Thanks a lot !
Staring at 22:00, should not we follow in the opposite of the gradient direction to reach minima? Gradient gives the steepest ascent directions as far as I know.
@zma4543
4 жыл бұрын
I think you are right
@jenkinsj9224
3 жыл бұрын
Yes
These are great lectures! Is the autograder and programming assignment available somewhere?
@parthmalik1
Жыл бұрын
yes when u get admitted to MIT u can take up the class and partake in assignments
you ate the best
Thanks professor.
Love you sir .love from India .
at 14:18, the energy can also so be EQUAL to 0 (not JUST bigger than 0)! Then does this not mean that the matrix is positive SEMI definite as opposed to positive definite?
@32:00, Prof mentions "if the eigenvalues are far apart, that's when we have problems". What does he mean by that?
@nguyennguyenphuc5217
4 жыл бұрын
He means difference between eigenvalues, |lambda1 - lambda2|, is big, then we have the case where "the bowl is long and thin" he mentions right before that.
@gabrielmachado5708
4 жыл бұрын
@@nguyennguyenphuc5217, yes, it looks like it would make it easier to miss the point and bounce back and forth around the minimum
@debralegorreta1375
4 жыл бұрын
@@gabrielmachado5708 right. it the bowl is narrow and your descent is slightly off you'll start climbing again.... so we take baby steps.
hello, could anyone explains me the difference between energy function ans snorm taught by professor in lecture 8
Amazing
At 41min, Why is the number of nonzero eigenvalues the same as rank(A)?
@fustilarian1
5 жыл бұрын
The eigenvectors with non zero eigenvalues must be mapped to somewhere within the column space, in all other directions outside the column space it collapses to 0, bear in mind that the null space vectors are also solutions to Ax=\lambda x where \lambda is 0.
@MoodyG
5 жыл бұрын
The answer is at 41:17 ... you notice how we can decompose the matrix into a weighted sum of its eigenvectors.. the weights being the eigenvalues obviously, and since Rank(A) is by definition the number of linearly independent vectors in the column space of A, i.e., it is the same as the number of non-zero terms in the decomposition, which is in turn the number of non-zero eigenvalues
@quanyingliu7168
5 жыл бұрын
@@fustilarian1 Thanks for your explanation. That's very helpful.
At 28:00 what is the intuition behind shape of the bowl and large/small eigenvalues? He made it sound like a quite obvious statement. Also at 36:50, given that S and Q-1SQ are similar implies they have same eigen values. However, how do you show S and Q-1SQ are similar? OK I figured out the 36:50 part. It is the spectral theorem which sir had covered in previous class. S = Q (lambda) Q-1. Lambda = Q-1 S Q. As, lambda is defined as the matrix of eigen values of S, this implies that S and Q-1 S Q are similar. Please explain the part at 28:00 . Thanks!
@ramman405
5 жыл бұрын
Regarding similarity you don't need the spectral theorem, just to remember that we say that A and B are similar if there exists an invertible matrix M such that A = M^(-1) * B * M You can immediately verify that if A = Q^(-1) * S* Q, B = S, and M=Q, then the equation is satisfied so A=Q^(-1) *S* Q and B=S are similar. Regarding the bowl statement, it should be pretty clear when the eigenvectors are [1,0] and [0,1]. In that case the energy function is given by: [x,y] * S * [x,y]^T = x^2 * lambda1 + y^2 * lambda2. So in the xz-plane it is just the quadratic function scaled by lambda1. In the yz-plane it is just the quadratic function scaled by lambda2 (and in general it is a linear combination of the two). If either eigenvalue is much larger than the other the scalings will be disproportionate and therefore we will get a bowl with a steep slope in the direction of the large eigenvalue, and pretty flat slope in the direction of the small eigenvalue. However the whole point of diagonalization is that basically we can treat any diagonalizable matrix like the diagonal matrix of its eigenvalues as long as we do the appropriate orthogonal base change (or equivalently work in the correct coordinate system), so really we already know that the general bowl will be an orthogonal transformation of the bowl described above and therefore itself be a narrow valley bowl. Concretely, if v1,v2 is an orthonormal basis of eigenvectors of S, with associated eigenvalues lambda1,lambda2, then the energy function is v^T QDQ^T v where Q is the orthonormal matrix whose columns are v1,v2. D is the diagonal matrix with elements lambda1,lambda2. We can write v as a unique linear combination of the eigenvectors (it is a basis after all): v= x * v1 + y * v2 Then the energy function evaluates to: v^T QDQ^T v = v^T QD [x,y]^T = v^T Q[lambda1 * x, lambda2 * y] = v^T (lambda1 * x * v1 + lambda2 * y * v2) = lambda1 * x^2 + lambda2 * y^2, so again it is a bowl which in the direction of v1 is a 1-dimensional quadratic scaled by lambda1, and in the direction of v2 is a 1-dimensional quadratic scaled by lambda2. So if lambda1 is huge the slope in the direction v1 will be steep. Same as before, just from the point of view of the coordinate system given by the eigenvectors (v1,v2).
@jenkinsj9224
3 жыл бұрын
@@ramman405 thanks
Where can I find the online homework? I can't find it in OCW.
@mitocw
5 жыл бұрын
The homework can be found in the Assignments section of the course on MIT OpenCourseWare at: ocw.mit.edu/18-065S18. Best wishes on your studies!
@unalcachofa
5 жыл бұрын
@@mitocw are the Julia language online asigmants mentioned also available somewhere? I see only problems from the textbook in the Assignments section of the OCW
@mitocw
5 жыл бұрын
julialang.org/
@StuckNoLuck
4 жыл бұрын
@@mitocw Where can we locate the programming assignments?
@nicko6419
4 жыл бұрын
@@mitocw I have a question about the kzread.info/dash/bejne/qqeEj7Vwqa7HgqQ.html Where can I find this lab work about convolution? On MIT OpenCourceWare at ocw.mit.edu/courses/mathematics/18-065-matrix-methods-in-data-analysis-signal-processing-and-machine-learning-spring-2018/assignments/ I can find only book assignments ocw.mit.edu/courses/mathematics/18-065-matrix-methods-in-data-analysis-signal-processing-and-machine-learning-spring-2018/assignments/MIT18_065S18PSets.pdf#page=7 Could you help me? Thanks!
What is meant by energy whe X^t S X multiplication is carried?
@spoopedoop3142
4 жыл бұрын
Are you asking why this quadratic form is called energy?
@CM-Gram
4 жыл бұрын
@@spoopedoop3142 yes exactly
@possibly_hello_1270
3 жыл бұрын
@@CM-Gram Kinetic energy is 1/2mv^2, where v is the velocity vector, and potential energy is 1/2kx^2, where x is the position vector.
Does he mean "a * a^T" near the end of the video?
I am here to leave a like to the legend.
I think the shape of the bowl will change when we add (x^T)b at 17:00 . Am I right???
@jeevanel44
5 жыл бұрын
It will shift or tilt the bowl in X axis direction. You can try the vizualizer al-roomi.org/3DPlot/index.html
@hardikho
3 жыл бұрын
@@jeevanel44 Hey, sorry to bother you a year later - what expression would I input to receive the bowl shown here?
who's that eager student answering every question for everyone else on every class?
20:49 gradient descent
Who could possibly dislike this?
@allandogreat
4 жыл бұрын
who can't understand that.
Hopefully I can still love science at this age
when does he prove 3?
Hi , I need cours about matrices polynomial please .
Voice ❤️
Can we find homeworks/labs online?
@mitocw
Жыл бұрын
The course materials are available on MIT OpenCourseWare at: ocw.mit.edu/18-065S18. Best wishes on your studies!
Duster ❤️
always a minus fault .... sqrt(68) not sqrt(60) , so one eigenvalue neg , yes .... 🤣😊 But now does Matlab opposite , to mine abc formula : (8 +/- sqrt(68))/2 for eigenvalues 🙄
@jan-heinzwiers581
3 жыл бұрын
Octave : -0.12311 , 8.12311 agrees with abc formula
@jan-heinzwiers581
3 жыл бұрын
Matlab too 😀
Math ❤️
Mic ❤️
Chalk ❤️
14:17 14:17 14:17
10:00 energy 19:00 convex
@xc2530
Жыл бұрын
14:00 deep learning
@xc2530
Жыл бұрын
24:00 gradient descent
@xc2530
Жыл бұрын
27:00 eigenvalue tells the shape of the bowl
@xc2530
Жыл бұрын
38:00 semi def pos
Accent ❤️
20220517簽
No we don't have to use gradient decent in this case
看着他越来越老 唉 时光
what is Convext? like that ....hahah
wow hes old now....
I see that this professor does not take question in class. . Maybe if you email him.
@naterojas9272
4 жыл бұрын
Maybe no one raise their hand
i hope this professor doesnt get any sexual assault charges with that much winking because his lectures are awesome.
@alexandrek2555
Жыл бұрын
🤣
@freeeagle6074
Жыл бұрын
I guess not, unless the air gets personified and files a case.