Question

Let $A$ and $B$ be any real matrices. I would like to find the solution of a linear system $Ax=B$ using the SVD decomposition of $A$ given by $A = U S V^t$. If I am not very wrong, I believe I can obtain this solution using

$\ \ \ X = VL^tU^tB$

in which

$\ \ \ L_{ij} = \begin{cases} 1/S_{ij} && \text{if} S_{ij} \not= 0 \\ 0 && \text{otherwise} \end{cases} $

This seems to work. However, for the case when $A$ has more columns than rows, I would like to find not only the best solution (in the least squares sense), but also the solution which has minimum norm. How can I do that?

$\\$

For example, by taking

$ \ \ \ A = \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{pmatrix} \ \ \ \ \text{and} \ \ \ B = \begin{pmatrix} 7 & 8 & 9 \\ 10 & 11 & 12 \end{pmatrix} $

The aforementioned method gives the solution

$\ \ \ \hat{X} = \begin{pmatrix} -2.1667 & -2.6667 & -3.1667 \\ 0.3333 & 0.3333 & 0.3333 \\ 2.8333 & 3.3333 & 3.8333 \\ \end{pmatrix} $

I can verify this is a valid solution by taking

$\ \ \ A\hat{X} = \begin{pmatrix} 7 & 8 & 9 \\ 10 & 11 & 12 \end{pmatrix}$

However, I am not sure this is the minimum norm solution.

Answer 1

Take a look at the wikipedia page on the Moore-Penrose pseudoinverse, specifically Sections 5.3, 6.1, and 6.3.