7
$\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?

Improve this question
$\endgroup$
3
  • $\begingroup$ Do you teach the singular value decomposition? $\endgroup$
    – J W
    Sep 29, 2020 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, 2020 at 8:56
  • 5
    $\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$
    – Raciquel
    Sep 29, 2020 at 18:38

2 Answers 2

Reset to default
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.

Improve this answer
$\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, 2020 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, 2020 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, 2020 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.

Improve this answer
$\endgroup$
3
  • $\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, 2020 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, 2020 at 18:55
  • $\begingroup$ @DavidESpeyer Doesn't the Cholesky factorization encode Gaussian elimination for a symmetric positive definite matrix? So I think that the row reduction approach you described for solving the normal equations is equivalent (in some sense) to computing the Cholesky factorization of $A^T A$. $\endgroup$
    – littleO
    Jun 29, 2021 at 8:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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