7
$\begingroup$

I have seen many posts stating that SVD is more stable as a preprocessing for solving least square or linear system problem than QR.

Certainly QR is less expensive than SVD, so I guess it makes sense.

But why?

$\endgroup$
0

2 Answers 2

Reset to default
8
$\begingroup$

You should check out chapter 3 in Demmel's text. Let me summarize some of the results for dense least-squares, for $A$ an $m\times n$ matrix:

  1. $A$ is well-conditioned: In this case, using the normal equations is around as accurate as other methods and is also the fastest, so using them is fine, even though they are not numerically stable.

  2. $A$ is not well-conditioned, but is not rank-deficient: Here, we we should use QR. QR is faster than the SVD and similarly stable (assuming you use a good algorithm for it i.e. not classical GS; try Householder reflections or Givens rotations).

  3. $A$ is rank-deficient: Here, QR without pivoting is faster, but less reliable than the SVD, which is slower. So, if you value reliability over speed, then you'd choose the SVD. It is worth noting that rank-revealing QR is actually between the two of them in terms of both speed and reliability.

In general, if $m\gg n$, then the costs are similar. Otherwise, QR is a bit cheaper than the SVD.

Also, as the other response says, you can truncate the SVD. If $$A=U\Sigma V^T=\sum\limits_{j=1}^n \sigma_ju_jv_j^T,$$ then the best rank $k$ approximation to $A$ in the $\left\lVert\cdot\right\rVert_2$ norm is $$A_k=\sum\limits_{j=1}^k \sigma_ju_jv_j^T=U\Sigma_k V^T,$$ where $\Sigma_k=\text{diag}(\sigma_1,\cdots,\sigma_k,0,\cdots,0).$

$\endgroup$
3
  • $\begingroup$ so the take home message is, if I don't care about speed, SVD is the most robust way to go? $\endgroup$
    – ArtificiallyIntelligence
    Jun 5, 2019 at 22:13
  • $\begingroup$ In terms of "standard methods," I'd say so. The SVD is serviceable in all of the above scenarios. In the rank-deficient case, rank-revealing schemes are a good compromise, if that's one you want to make, but they are more sophisticated and problem-dependent. $\endgroup$
    – cmk
    Jun 5, 2019 at 22:17
  • 1
    $\begingroup$ @ArtificiallyIntelligence To definitively answer your comment, if you don't care much about speed, then the SVD is the way to go! $\endgroup$
    – cmk
    Jun 5, 2019 at 22:19
1
$\begingroup$

It depends on the type of $QR$ decomposition. There are three basic ways to perform Gram-Schmidt: Classical Gram-Schmidt, Modified Gram-Schmidt and Householder. Classical Gram-Schmidt is unstable. Modified Gram Schmidt is somewhat more stable but not the best. Householder is stable.

Some methods of performing the SVD rely on the QR decomp. The time complexity is nearly the same I believe. The reason the $SVD$ is preferred to my understanding is you can use the truncated SVD rather easily.

When solving with the decomp you have

$$ Ax =b \implies QRx = b \\ Rx = Q^{T}b $$

You then perform back-sub. With the svd you have

$$ Ax =b \implies A^{\dagger} = V \Sigma^{\dagger} U^{T} \\ x^{*} = V \Sigma^{\dagger} U^{T} b $$

You can truncate the SVD by letting

$$ \Sigma^{\dagger} = \begin{align}\begin{cases} \frac{1}{\sigma_{i}} & \sigma_{i} > \epsilon \\ 0 & \textrm{ otherwise } \end{cases} \end{align} $$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .