LU factorization and non-square matrices

For least-square solutions with a non-square or singular matrix, the LU factorization is useless — it doesn’t simplify the calculation.

QR factorization, in contrast, helps you solve least-squares problems because the R factor (in the “thin” QR factorization for matrices with full column rank) is square, invertible, and triangular, and also Q^T Q = I. (There are also more technical reasons why QR factorization works well having to do with the conditioning of the linear systems, as mentioned in Efficient way of doing linear regression - #33 by stevengj)

In particular, the least-square solution minimizing \Vert Ax - b\Vert corresponds (in theory) to solving the normal equations A^T A \hat{x} = A^T b. If you plug in A=QR, it simplifies (Q^T Q cancels, and R^T cancels because it is invertible), whereas for A = LU it does not (L^T L does not cancel, and U is not invertible).

Similar things happen for minimum-norm solutions (with “wide” matrices / underdetermined problems), though in that case one sometimes uses the LQ factorization instead of QR.

5 Likes