How QR decomposition solves the problem of expensive SVD?

[prgyn8]

Economical SVD using QR Decomposition

The typical SVD follows the basic principle:

$$ X = U , \Sigma , V^T, \quad X \in \mathbb{R}^{m \times n} $$

where $m \gg n$, making the matrix look tall & skinny.

For larger datasets, this process becomes expensive to run in systems (even linear algebra feels like looping in some cases).

---

To make this process efficient, QR factorization brings a little change to the equation:

QR factorization of $X$:

$$ X = QR $$

where

• $Q \in \mathbb{R}^{m \times n}$ has orthonormal columns
• $R \in \mathbb{R}^{n \times n}$ is upper triangular

---

Now, compute the SVD of the smaller $R$:

$$ R = \tilde{U} , \Sigma , V^T $$

---

Putting it back into the factorization:

$$ X = QR = Q , (\tilde{U} , \Sigma , V^T) $$

Here, the economical SVD is obtained with:

$$ U_r = Q \tilde{U}, \quad \Sigma = \Sigma, \quad V = V $$

---

👉 In this way, QR helps avoid dealing with the large $m \times m$ case of the full SVD, by reducing the problem to an $n \times n$ decomposition.

Here,

$$ R = \tilde{U} , \Sigma , V^T $$

is an upper triangular matrix, where the lower values are zero. And, also we're not dealing with $m in the process like we had in full SVD.