how the singular value decomposition of A can be used to solve the system of linear equations

Question

Let $A$ be a real, $n\times n$, non-singular matrix. How can the singular value decomposition of A be used to solve the system of linear equations $A x = b$, where $b, x \in \Bbb R^n$?

Answer 1

Remember that $U$ and $V^T$ have to be orthogonal matrices meaning that their transposes are also their inverses. The inverse of a diagonal matrix is another diagonal matrix with with reciprocal values of the original entires.

So we can solve $U\Sigma V^Tx= b$ using left matrix multiplication of the inverses of $U,\Sigma, V^T$ and then we have $x = V\Sigma^{-1}U^Tb$.

Answer 2

From a Numerical Linear Algebra perspective, we must take into account the computational costs and feasibality of using SVD to solve the system of linear equations : $$ \mathbf{Ax}=\mathbf{b}\tag{1} $$ with $r:=\operatorname{rank}(\mathbf{A})\leq\min(m,n)$. Since $\mathbf{A}$ might not be full rank, we shall take advantage of the most imortant property of SVD which is that its pseudoinverse is well defined i.e., we can decompose $\mathbf{A}$ using the Economy SVD to two orthogonal matrices $\mathbf{U}_{r}\in\mathbb{R}^{m\times r}$ and $\mathbf{V}_{r}\in\mathbb{R}^{n\times r}$, and $\mathbf{S}_{r}:=\operatorname{diag}\begin{bmatrix}\sigma_{1}&\sigma_{2}&\cdots&\sigma_{r}\end{bmatrix}\in\mathbb{R}^{r\times r}$ containing the singular values of $\mathbf{A}$. Therefore, we have : $$ \mathbf{A}=\mathbf{U}_{r}\mathbf{S}_{r}\mathbf{V}_{r}^{\top} \tag{2} $$ for which we can rewrite $(1)$ as : \begin{align*} \mathbf{Ax}&\;=\;\mathbf{b}\\ \mathbf{U}_{r}\mathbf{S}_{r}\mathbf{V}_{r}^{\top}\mathbf{x}&\;=\;\mathbf{b}\\ \mathbf{S}_{r}\mathbf{V}_{r}^{\top}\mathbf{x}&\;=\;\mathbf{U}_{r}^{\top}b \\ \mathbf{S}_{r}\mathbf{y}&\;=\;\mathbf{z} \end{align*} where $\mathbf{y}:=\mathbf{V}_{r}^{\top}\mathbf{x}$ and $\mathbf{z}:=\mathbf{U}_{r}^{\top}\mathbf{b}$. Therefore, all you need to do to solve $(1)$ numerically using SVD in the most effective way is to follow the procedure below :

$1$. Compute the Economy SVD of $\mathbf{A}$.

$2$. Compute $\mathbf{z}\quad \mathcal{O}(n^{2})$

$3$. Solve the system $\mathbf{S}_{r}\mathbf{y}=\mathbf{z}\quad\mathcal{O}(n)$

$4$. Compute $\mathbf{x}=\mathbf{V}_{r}\mathbf{y}\quad\mathcal{O}(n^{2})$

It is worth noting that computing the pseudoinverse directly is not recommended as it may lead to numerical instability.