# Fundamentals of Matrix Computations, Watkins, exercise $4.3.9(e)$, SVD.

Given that

$$A=\begin{bmatrix} 1 & 2 \\ 2 & 4 \\ 3 & 6\end{bmatrix}, \qquad b=\begin{bmatrix} 1 \\ 1\\ 1\end{bmatrix},$$ what is the method to find all solutions of the least-squares problem $$\min \| A x- b \|_2$$ using SVD?

Recall that the solution space of $$Ax = b$$ can be written as $$\{ x_{\text{p}} + z : z \in \mathcal{N}(A) \},$$ where $$x_{\text{p}}$$ is a particular solution of $$Ax = b$$ and $$\mathcal{N}(A)$$ is the kernel of $$A$$.

In order to find all solutions of the least squares problem, the crucial point is to calculate a suitable particular solution of the system. This solutions turns out to be the minimum norm solution: Note that $$A$$ has a singular value decomposition

$$A = U \Sigma V^\intercal$$

with the usual notations. From this it is possible to calculate the pseudo-inverse $$A^+$$ of $$A$$, namely

$$A^+ = V \Sigma^+ U^\intercal.$$ (The pseudo-inverse of $$\Sigma$$ can be easily calculated by taking the reciprocals of all non-zero diagonal entries.) Using $$A^+$$ it can be shown that the minimum norm solution $$x_{\text{mn}}$$ of the least squares problem is

$$x_{\text{mn}} = A^+ b.$$

Once you have this, you only need to calculate a basis for the kernel of $$A$$.

Putting all together, you should calculate $$x_{\text{mn}}$$ and a basis for $$\mathcal{N}(A)$$. Then set $$x_{\text{mn}} = x_{\text{p}}$$ and you can write down the solution space.