ChapterZero

Usually when we think of non-square systems of linear equations, we think of skinny full rank matrices: i.e., of systems of the form

One way of solving these systems is to use the (reduced) QR factorization, which decomposes into a matrix which has orthonormal columns, and an upper-triangular invertible matrix . Intuitively, the Q matrix is the result of applying the Gram-Schmidt orthonormalization process to the columns of , and combines the columns of to get back . There is also a full factorization, A= where is unitary, and is upper triangular. A full factorization can be obtained from a reduced one by completing the basis in , and adding zeros to the bottom of .

Something really cool, that I learnt today while doing my linear algebra homework, is that the QR factorization is useful for solving full-rank underdetermined systems as well. That is, suppose your problem is now

Then this has at least one solution, but there may be multiple ones. What if you’d like to select the solution with minimum Euclidean norm? The idea is that is a full-ranked skinny matrix, so has a QR decomposition: .

Then minimizing given is the same as minimizing it given , which is the same as minimizing it given (since , remember has orthonormal columns). But then is a projection, so the with minimum length that satisfies this equation is just . So the minimum length vectors that satisfies is simply . Pretty neat.