📂Matrix Algebra

Speed Comparison of LU, QR, and SVD in Least Squares

Summary ¹

For a matrix $A \in \mathbb{R}^{m \times n}$, suppose $m \ge n$. When performing least squares via LU decomposition, QR decomposition, and singular value decomposition, the time complexity is all equally $O \left( mn^{2} \right)$, but the number of flops actually required is roughly as follows.

• LU decomposition²: $$ mn^{2} + {\frac{ 2 }{ 3 }} n^{3} $$
• QR decomposition³: $$ 2mn^{2} - {\frac{ 2 }{ 3 }} n^{3} $$
• Singular value decomposition⁴: $$ 4mn^{2} - {\frac{ 4 }{ 3 }} n^{3} $$

However, this summary contains an ‘intentionally wrong part’, so do not take it at face value and be sure to read the main text.

Explanation

There are several ways to use matrix decomposition as a practical implementation of least squares, but three in particular are widely used: the method via LU decomposition (Cholesky decomposition), the method via QR decomposition, and the method via SVD decomposition. Note that whether it is LU decomposition, Cholesky decomposition, or Gaussian elimination, they are essentially methods of solving a linear system through forward and backward substitution, so from the standpoint of implementing least squares they can all be regarded as the same thing. In fact, the flops of Cholesky decomposition is $mn^{2} + {\frac{ 1 }{ 3 }} n^{3}$, which is slightly better than LU decomposition, but in practice, for the sake of stability, PLU decomposition with pivoting included is used.

Looking at the implementations of Julia⁵ or MATLAB⁶, one can essentially say that for $A$, QR decomposition is used when $m \ne n$, and LU decomposition is used when $m = n$.

In fact, the most important and dominant term in the comparison of flops is $m n^{2}$, and one can see that as we go from LU to QR to SVD, the amount of computation nearly doubles each time. However, this summary is organized to be easy to accept; the specific formulas themselves may vary depending on the flop count or the implementation method.

LU Decomposition

Actually, LU decomposition requires only $2n^{3}/3$ flops, but for least squares we must convert $A \mathbf{x} = \mathbf{b}$ into $A^{\top} A \mathbf{x} = A^{\top} \mathbf{b}$, so an additional $mn^{2}$ flops are required when computing $A^{\top} A$.

Naturally, in the case $m = n$ there is no need to compute $A^{\top} A$, so the leading term disappears and it becomes $2/3 n^{3}$, which is twice as fast as QR decomposition. Conversely, even in the case $m \gg n$, the weight of $n^{3}$ decreases, so it ends up being about twice as fast as QR decomposition. If you really have a well-conditioned matrix and must prioritize speed, there are times when it is better to use LU decomposition.

QR Decomposition

It is twice as slow as LU decomposition and twice as fast as SVD. In a sense it might be seen as being somewhere in the middle, but considering that SVD is so slow that it is rarely used by default for implementing least squares, it can be regarded as the most reliable and good method. Realistically, most of the least squares problems in this world are probably being solved through QR decomposition.

SVD

The organized flops of SVD, when using Golub-Kahan bidiagonalization, comes out to $4mn^{2}$ up front, but if we focus on singular value decomposition rather than just doing matrix decomposition, computations separate from the matrix decomposition increase or decrease, giving the following. $$ 2 mn^{2} + 11 n^{3} $$ This is the ‘intentionally wrong part’ mentioned earlier. In any case, it is a fact that it is slower than QR, and since there is no particular reason to use this method literally just for a single least squares computation, a more concise comparison was made.

Trade-off with Stability

Comparing the speeds and comparing the stability of the three methods, one can very clearly confirm the trade-off as follows.

Method	Speed	Stability
LU	Fast	Unstable
QR	Moderate	Stable
SVD	Slow	Very stable