Very nice. If I'm not mistaken, at 11:25, you change the order of xTv = vTx to pull out x on the right and factor it, not moving it like your little green arrow says.
Good video, even though the step from Px to P is a bit short and looks a bit confusing. Even if you just use the symmetrical properties of the scalar product.
At 10:38-------> When you get Px, the numerator of the second term is 2*v*x'*v, and in the next step for P the numerator of the second term becomes v*v'. I am confused which is scalar and which is matrix and how v gets its transpose suddenly. It would be great if you could please clarify.
+Paromita Banerjee (x'v) is a scalar inner product, so it's the same as (v'x). You can then associate the v and v' terms, and finally separate out x on the right of the P*x expression.
Thank you Toby, for the clear explanation. This made the basic concept clear. I feel you didn't mention the relation between P's and Q's. I understood from a different source that Qi is obtained by placing Pi as a submatrix in a bigger Identity matrix (size equal to size of Qi). Thank again!
+vshssvs7 It gets even more complicated. Most of the time the Q is not formed. Instead the HH vectors are collected and then applied in order (or reverse order) to evaluate Q times a vector.
Dear Toby, this is a wonderful video, thank you for your thoughtful explanation. I am digging deeper, and wondering, how do we compute v? I see in your code v = [-sign(z(1))*norm(z) - z(1)]; -z(2:end)]; Do mind replying a few sentences about this?
This is the clearest TH-cam video I've stumbled upon explaining the use of the Householder Transformation to generate the QR factorization. Many thanks. I've been struggling for almost a decade (very much part time) to understand exactly how this calculation works. But all my previous attempts have been stymied by the use of unexplained short hand notation. An excellent example of this is the Wikipedia page on the Householder Transformation. Shortly after the index of the article, the authors confuse the lay reader by using shorthand without providing any hint on the meaning of the nomenclature. Even in your video, it would have been more clear if you had enclosed the matrices in square brackets to clearly indicate that they are matrices. Similarly, use curly brackets around the vectors to clearly indicate vectors. Then the remaining variables would be numbers. Also, regarding the vectors, clarity would be improved is you could indicate if a vector is a column or row vector. I continue to wonder why teachers of Linear Algebra topics are so casual with their notation. The Wikipedia page on the Householder Transformation are very sloppy in this respect. About half way down the page, they work an example. But, in their worked example, they don't show their calculations of P1, P2, ... They do show all the iterations of A & Q. Also, they never calculate any of the R matrices. This shorthand is a significant barrier for a novice like me. One element that is missing in this video is a discussion on why it is useful to do a QR factorization. My interest is to calculate the matrix of Eigenvectors of an arbitrary, square matrix of real numbers since is common in engineering to study the Eigenvectors & Eigenvalues of a system matrix of a dynamics, state-space problem. Of course, most of the time, users will have access to MatLab or equivalent which provides user friendly access to LINPACK / LAPACK which includes efficient software for calculating these. But, understanding the fundamental algorithm can be a useful method to improve one's understanding of the process. Even with the clarity of this video, I remain baffled on the use of the terms, "mirror" and "reflector" to explain this. I've studied optics in college physics classes & certainly understand how light reflects off of a mirror. I can not see any analogy to optical reflection & this Householder "reflector." Because of your video, I now understand what I have to do to calculate the Q matrix in a QR factorization. But, I still don't understand why it works. At times in the past decade of so, I was under the impression that less than 1000 people in the world actually understand enough about calculating Eigenvectors efficiently to write their own code. Years ago I was browsing one of the Numerical Recipes books & noticed that the chapter on Eigensolutions contained a strong caution not to attempt to write your own software to calculate Eigen Solutions. These days, I think that maybe as many as 100000 people worldwide understand this topic.
Terrific explanation, simple and careful and simple steps to explain the essence. thank you so much for sharing. Wish id found this when i was learning this... i share this video to explain. You should make another to explain column pivoting tradeoffs. What i really want is a video to help me understsnd why qr iteration converges on eigenvalues...
The product is an orthogonal matrix. We might call it Q, but in anticipation of making it look like the standard formula at the end, we choose to name it Q^T (which is also an orthogonal matrix).
Hello! I have one question. I am not sure that you are right concerning multiplication of matrices P_i. As Q = I *P1*P2*P3.... But, you are doing like Pn *.....* P2 * P1*I. Thank you for your video!
I'm not sure I know exactly which part you mean. But we have A=QR, so Q^T A = R. If we find Q^T as a product of matrices, then Q is the product in the opposite order.
It's a good video, but the norm of w can't be negative by definition so something must have went wrong there, I think I still understand but it confused me a bit at first, I think the minus sign comes from V and you should define V in the opposite direction
The norm can't be negative, but the vector is being mapped by the reflection to either +norm(z)*e1 or -norm(z)*e1, i.e., to a vector with positive or negative first element. The definition of v also flips in the first term depending on which target is chosen.
This would have been much more helpful to me if you used an example with real numbers. Maybe that's just me personally since I'm an engineer and like to work with real things, but I'm still just having a really hard time understanding this.
You can look here: www.dropbox.com/sh/kxyc1on3k4f3sh0/AACnyHY2FmXgUpHmJvSYV6Qaa?dl=0&preview=TB_Lecture_10.html. It's brief, but does the job. The problem is that the numbers are either trivial or too ugly to do by hand.
In floating point, all numbers and operations are perturbed slightly (in the 16th digit). G-S is unstable, meaning that the errors in the results will be orders of magnitude larger than those original perturbations. Mainly, the basis vectors end up being far from orthogonal.
@@nshuang1009 Expressions that are equivalent for real numbers may not be so for floating point. Most often it's a subtraction that causes growth in error. If the computation can be rearranged to avoid such a step, it might avoid the growth in error.
Many many thanks to you. My Prof rushed through it in class while leaving me clueless. You made it clear and precise.
😎
@Ella Bottoni you forgot to change your account name bot.
same! instructor presented it like its somehow self-evident. This video is life saving.
Very nice. If I'm not mistaken, at 11:25, you change the order of xTv = vTx to pull out x on the right and factor it, not moving it like your little green arrow says.
Ah thank you ! I was trying to understand how you could do this and you explanation made me understand
Best explanation I've found on this, thanks a lot!
Good video, even though the step from
Px to P
is a bit short and looks a bit confusing.
Even if you just use the symmetrical properties of the scalar product.
who the fuck is e1?
Vector with first component 1, the rest 0. (I.e., standard basis vector.)
At 10:38-------> When you get Px, the numerator of the second term is 2*v*x'*v, and in the next step for P the numerator of the second term becomes v*v'. I am confused which is scalar and which is matrix and how v gets its transpose suddenly. It would be great if you could please clarify.
+Paromita Banerjee (x'v) is a scalar inner product, so it's the same as (v'x). You can then associate the v and v' terms, and finally separate out x on the right of the P*x expression.
+Toby Driscoll Makes complete sense, thanks a bunch!
To be fair the sketch in the video doesn't really help to clarify that very well ;)
thanks
Great presentation. Golub would be jealous.
Thank you Toby, for the clear explanation. This made the basic concept clear. I feel you didn't mention the relation between P's and Q's. I understood from a different source that Qi is obtained by placing Pi as a submatrix in a bigger Identity matrix (size equal to size of Qi). Thank again!
+vshssvs7 It gets even more complicated. Most of the time the Q is not formed. Instead the HH vectors are collected and then applied in order (or reverse order) to evaluate Q times a vector.
+Toby Driscoll Thank you Toby for clarification.
Dear Toby, this is a wonderful video, thank you for your thoughtful explanation. I am digging deeper, and wondering, how do we compute v? I see in your code v = [-sign(z(1))*norm(z) - z(1)]; -z(2:end)]; Do mind replying a few sentences about this?
Im wondering the same...
Very nice explanation. I wish there was also a video on Givens rotations
I found this one helpful: th-cam.com/video/moTxjgVEBfA/w-d-xo.html
Great explanation, best I've found on youtube. I just can't understand how to get subsequent Qs after calculating Q1
where do you get v
THANKS A ZILLION
Super 🤩
nice video sir
This is the clearest TH-cam video I've stumbled upon explaining the use of the Householder Transformation to generate the QR factorization. Many thanks.
I've been struggling for almost a decade (very much part time) to understand exactly how this calculation works. But all my previous attempts have been stymied by the use of unexplained short hand notation. An excellent example of this is the Wikipedia page on the Householder Transformation. Shortly after the index of the article, the authors confuse the lay reader by using shorthand without providing any hint on the meaning of the nomenclature. Even in your video, it would have been more clear if you had enclosed the matrices in square brackets to clearly indicate that they are matrices. Similarly, use curly brackets around the vectors to clearly indicate vectors. Then the remaining variables would be numbers. Also, regarding the vectors, clarity would be improved is you could indicate if a vector is a column or row vector. I continue to wonder why teachers of Linear Algebra topics are so casual with their notation. The Wikipedia page on the Householder Transformation are very sloppy in this respect. About half way down the page, they work an example. But, in their worked example, they don't show their calculations of P1, P2, ... They do show all the iterations of A & Q. Also, they never calculate any of the R matrices. This shorthand is a significant barrier for a novice like me.
One element that is missing in this video is a discussion on why it is useful to do a QR factorization. My interest is to calculate the matrix of Eigenvectors of an arbitrary, square matrix of real numbers since is common in engineering to study the Eigenvectors & Eigenvalues of a system matrix of a dynamics, state-space problem. Of course, most of the time, users will have access to MatLab or equivalent which provides user friendly access to LINPACK / LAPACK which includes efficient software for calculating these. But, understanding the fundamental algorithm can be a useful method to improve one's understanding of the process.
Even with the clarity of this video, I remain baffled on the use of the terms, "mirror" and "reflector" to explain this. I've studied optics in college physics classes & certainly understand how light reflects off of a mirror. I can not see any analogy to optical reflection & this Householder "reflector." Because of your video, I now understand what I have to do to calculate the Q matrix in a QR factorization. But, I still don't understand why it works.
At times in the past decade of so, I was under the impression that less than 1000 people in the world actually understand enough about calculating Eigenvectors efficiently to write their own code. Years ago I was browsing one of the Numerical Recipes books & noticed that the chapter on Eigensolutions contained a strong caution not to attempt to write your own software to calculate Eigen Solutions. These days, I think that maybe as many as 100000 people worldwide understand this topic.
Terrific explanation, simple and careful and simple steps to explain the essence. thank you so much for sharing. Wish id found this when i was learning this... i share this video to explain. You should make another to explain column pivoting tradeoffs. What i really want is a video to help me understsnd why qr iteration converges on eigenvalues...
why is the multiplication Q3Q2Q1 described as QT?
The product is an orthogonal matrix. We might call it Q, but in anticipation of making it look like the standard formula at the end, we choose to name it Q^T (which is also an orthogonal matrix).
uhuh, I see, thanks :) nice video btw
you do great job that show how and where P householder formal come from, and thank you
n^p for p = 2.376
Hello! I have one question. I am not sure that you are right concerning multiplication of matrices P_i. As Q = I *P1*P2*P3.... But, you are doing like Pn *.....* P2 * P1*I. Thank you for your video!
I'm not sure I know exactly which part you mean. But we have A=QR, so Q^T A = R. If we find Q^T as a product of matrices, then Q is the product in the opposite order.
Great explanation
thanks for Morocco
Hervorragendes Video. Endlich Mal anschaulich und verständlich erklärt. Vielen Dank dafür.
So clear! Thanks!
It's a good video, but the norm of w can't be negative by definition so something must have went wrong there, I think I still understand but it confused me a bit at first, I think the minus sign comes from V and you should define V in the opposite direction
The norm can't be negative, but the vector is being mapped by the reflection to either +norm(z)*e1 or -norm(z)*e1, i.e., to a vector with positive or negative first element. The definition of v also flips in the first term depending on which target is chosen.
Good explanation. This is much appreciated.
Nice video. Each step was clarified and justified. Good job :)
Eres el cherif men me has salvado todo el curso gracias por alegrarme la vida
Thanks Toby......................................keep it up.
Thanks a lot Toby for the explanation.
It has really helped me to understand the Householder method of decomposition.
Bravo!
This would have been much more helpful to me if you used an example with real numbers. Maybe that's just me personally since I'm an engineer and like to work with real things, but I'm still just having a really hard time understanding this.
You can look here: www.dropbox.com/sh/kxyc1on3k4f3sh0/AACnyHY2FmXgUpHmJvSYV6Qaa?dl=0&preview=TB_Lecture_10.html. It's brief, but does the job.
The problem is that the numbers are either trivial or too ugly to do by hand.
Toby Driscoll Thanks so much! I have to do this by hand in my applied linear algebra class, so I've been pretty lost.
Thank you, very well explained!
Excelent job!! helped a lot
I have a question: What does it mean that unstable in floating point? and why?
Thank you for the explanation of princple in the Gram-Schmidt QR.
In floating point, all numbers and operations are perturbed slightly (in the 16th digit). G-S is unstable, meaning that the errors in the results will be orders of magnitude larger than those original perturbations. Mainly, the basis vectors end up being far from orthogonal.
@@TobyDriscoll Thank you for your answer. I understood. Thanks a lot :-)
@@TobyDriscoll For other methods, why don't they have the same problem that unstable in floating-point? They also use floating-point for calculation.
@@nshuang1009 Expressions that are equivalent for real numbers may not be so for floating point. Most often it's a subtraction that causes growth in error. If the computation can be rearranged to avoid such a step, it might avoid the growth in error.
excellent !!
if it's possible i want a programme python and tanx for this amazing video :D
+Chiboub Amine Thanks for the compliment. I'm not much of a Python programmer, but numpy/scipy has a gateway to LINPACK, if you're doing serious work.
i do it already if you want to see it i'll send :D