6
$\begingroup$

I am teaching a "linear algebra for engineers" course, and am currently building my lectures on Gram-Schmidt, QR-decomposition and least squares equation solving.

$\bullet$ I can motivate Gram-Schmidt perfectly well. Geometrically, if I have a tilted plane in $\mathbb{R}^3$ and want to describe geometric figures in it, I want to work in orthonormal coordinates in order for lengths and angles to have their usual meaning. And, more abstractly, Gram-Schmidt leads to orthogonal polynomials, which come up in tons of PDE applications.

$\bullet$ I can motivate least-squares perfectly well, it is the first basic step in statistical modeling, and also key to solving linear equations with numerical errors.

But I don't really see why students need $QR$-decomposition or, more precisely, why they need the matrix $R$. Orthogonal projection is given by $Q Q^T$. Least squares solving can be presented as $R^{-1} Q^T$, but the formula $(A^T A)^{-1} A^T$ is also available. The latter is certainly nicer for hand computation; I'm not sure what is actually lurking inside computer algebra systems.

Why is it worth teaching the students to compute $R$, and to think about what it means?

$\endgroup$
4
  • $\begingroup$ Do you teach the singular value decomposition? $\endgroup$ – J W Sep 29 '20 at 8:44
  • 1
    $\begingroup$ @JW Yes, absolutely. This is a significant topic, we'll hit it in about a month later than this material. $\endgroup$ – David E Speyer Sep 29 '20 at 8:56
  • $\begingroup$ Agree re the SVD. I teach it too, but have often skipped the QR-decomposition itself when pressed for time. $\endgroup$ – J W Sep 29 '20 at 9:04
  • 4
    $\begingroup$ The QR factorization is used in signal and image processing, among other things. Since the course is “for engineers,” it might help them to at least know what it is, if not be familiar with it. A nice property: If $Ax=b+\epsilon$, where $\epsilon$ represents some noise, $Rx=Q^*b+Q^*\epsilon$ does not distort the noise. Maybe ask someone in Engineering how important it is? What do they expect the students to know? There are functions to compute the QR (and SVD) decomposition in MATLAB, Python (NumPy), R, Mathematica....probably any system an engineer is likely to use. $\endgroup$ – user2913 Sep 29 '20 at 18:38
7
$\begingroup$

I wouldn’t feel bad about leaving it out, but I think it’s a valuable conceptual example for understanding matrix algebra. Computing the QR decomposition is equivalent to applying Gram-Schmidt orthogonalization to the columns, and I think it’s really instructive to see how this corresponds exactly to the fact that Q is orthogonal and R is upper triangular (with positive diagonal): an iterative process has turned into a structural statement about a matrix factorization, which is a great example of what matrix algebra can do for you. Then this more abstract perspective is genuinely useful, because we can ask whether there are other, potentially better ways of computing this factorization, for example with improved numerical stability (the answer is yes). This question is much less natural if you view Gram-Schmidt orthogonalization as a specific process, rather than just one way of achieving an abstract goal. (Of course you could phrase the abstract goal without using matrix factorization, but this is a nice way to do it.)

I also rather like the QR algorithm for eigenvalues. It’s very slick and simple, if you don’t get into the details of how to do it most efficiently or how to analyze the convergence, and it’s a great example of an iterative approximation algorithm. This is an important step up in sophistication from exact, finite algebraic algorithms.

So my inclination would be to motivate the QR factorization as an example of the power of abstraction: by taking something familiar and turning it into a matrix factorization, we open up both new questions and new applications.

As for why the students need R, one way I’d explain it to them is that it relates the new, orthonormal basis to the old basis. In some applications, you don’t care about this: the original basis had no special significance, and you’re happy to throw it away forever and replace it with the new basis. However, sometimes the original basis is important (either because of some intrinsic conceptual meaning, or just because it’s hard coded into some dataset), and then keeping track of how you transformed the basis becomes worthwhile.

$\endgroup$
3
  • 1
    $\begingroup$ The essential difference between Gram-Schmidt and QR is that the numerical stability of GS depends on the order in which the vectors are calculated, but this is not the case with QR because of its relationship with eigenvalue extraction. In some sense, QR also gives an optimal choice of basis vector directions. $\endgroup$ – alephzero Sep 29 '20 at 20:04
  • $\begingroup$ @alephzero What do you mean? If you switch the order of the columns of a matrix $A$, the $QR$ decomposition of $A$ changes. $\endgroup$ – David E Speyer Sep 30 '20 at 2:04
  • $\begingroup$ @alephzero You sound a little mixed up. The QR decomposition is ultimately a math thing: given vectors $a_1,a_2,\dots,a_n$, write $a_i$ as a linear combination of orthogonal vectors $q_1,\dots,q_i$ in the span of $a_1,\dots,a_i$. Numerical stability comes into play when you ask about how to compute it, and GS has problems there, but probing issues of numerical stability is a lot harder to motivate than geometry, and it opens a followup can of worms in the form of "if GS is unstable, what's the alternative?" which introductory courses often don't really have the time to sort out. $\endgroup$ – Ian Sep 30 '20 at 3:42
5
$\begingroup$

Solving least squares problems by QR factorization is much more numerically stable than solving them by Cholesky factorization of the normal equations. This can easily be demonstrated on an ill-conditioned test problem.

$\endgroup$
2
  • $\begingroup$ I think the alternative most of my students would think of is inverting $A^T A$ by row reducing $[ A^T A | \mathrm{Id} ]$, not Cholesky factorization. I assume this is even worse? $\endgroup$ – David E Speyer Oct 5 '20 at 12:08
  • $\begingroup$ Yes, that would be just as bad. The obsession with row reduction in introductory courses in Linear Algebra is a problem that becomes apparent in more advanced courses where we have to teach students to use matrix factorizations. $\endgroup$ – Brian Borchers Oct 6 '20 at 18:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.