Least-squares solution using SVD

What if $A$ is not full column rank?

$$A=QR$$

• The QR factorization exists but is not unique.
• $R$ is singular.
• So:

$$x=R^{-1}{Q}^{T}b\to \text{fails}$$

The problem is that the solution of the least-squares problem is non-unique.

• We need to look for the solution with minimum norm.
• This solution is unique.
• It satisfies two conditions:

1. ${\text{argmin}}_x\Vert Ax-b{\Vert }_2$: it solves the least-squares problem.
2. $x\perp N(A)$, that is, the solution has a minimum 2-norm.

Here are the solution steps.

Let’s start with the thin SVD:

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

Shape of matrices:

• Because $A$ is not full column rank, we have that the rank $r$ satisfies $r<n$.
• This is why matrix $V$ is thin. $V$ and $U$ both have $r$ columns. $U$ has $m$ rows and $V$ has $n$ rows. $\Sigma$ has size $r\times r$.

Let’s go back to the equation

$$A^T(Ax-b)=0$$

This is equivalent to:

$$U^T(Ax-b)=U^T(U\Sigma V^{T}x-b)=0$$

Since $U^{T}U=1$

$$\Sigma V^{T}x=U^{T}b$$

• But $V^{T}x$ does not uniquely define $x$.
• We need to add the condition that $x\perp N(A)$. This guarantees that $x$ has minimum 2-norm.
• From $A=U\Sigma V^T$:

$$x\perp N(A)\iff x\perp (\text{span}(V{)}^{\perp })\iff x\in \text{span}(V)$$

• Note that because $A$ is not full column rank, its null space $N(A)$ is non-trivial.
• As a result $V$ is a thin matrix and span($V$)${}^{\perp }$ is non-trivial as well.
• Let’s now search for the solution $y$:

$$x\in \text{span}(V)\iff x=Vy$$

• The solution is then

$$\Sigma V^{T}Vy=\Sigma y=U^{T}b$$

since $V^{T}V=I$.

• That system has a unique solution in $y$ because all the singular values ${\sigma }_i$, $1\le i\le r$, are non-zero.
• The final solution is therefore

$$x=V{\Sigma }^{-1}{U}^{T}b$$

The computational cost to calculate the SVD is $O(m{n}^2)$.

Least-squares problems, Singular value decomposition, Method of normal equation, Least-squares solution using QR