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

Question

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?

Answer 1

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.