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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.