Why does SVD provide the least squares and least norm solution to $ A x = b $?

Question

I am studying the Singular Value Decomposition and its properties. It is widely used in order to solve equations of the form $Ax=b$. I have seen the following: When we have the equation system $Ax=b$, we calculate the SVD of A as $A=U\Sigma V^T$. Then we calculate $x'= V \Sigma^{+}U^Tb$. $\Sigma^{+}$ has the reciprocals ($\dfrac{1}{\sigma_i}$) of the singular values in its diagonal and zeros where $\sigma_i=0$. If the $b$ is in the range of $A$ then it is the solution that has the minimum norm (closest to origin). If it is not in the range, then it is the least-squares solution.

I fail to see how exactly this procedure always produces a $x'$ which is closest to origin if $b$ is in the range of A. (I can see the least-squares solution is an extension of this "closest to origin" property). From a geometric intuitive way if possible, how can we show this property of SVD?

Answer 1

First, consider the problem $\Sigma x = b$, where $$ \Sigma = \pmatrix{\sigma_1\\& \ddots\\&&\sigma_r\\ &&&0\\&&&&\ddots\\&&&&&0} $$ Note that $b$ is only in the range of $\Sigma$ if its entries $b_{r+1},\dots,b_n$ are all zero. Furthermore, you should be able to convince yourself (geometrically or otherwise) that the least squares solution must be $$ x = (b_1/\sigma_1,\dots,b_r/\sigma_r,0,\dots,0)^T = \Sigma^+ b $$ From there, note that $$ U\Sigma V^T x = b \implies\\ \Sigma (V^T x ) = U^T b $$ By the above argument, the least squares solution for $(V^T x)$ is given by $V^T x = \Sigma^+ U^T b$. Noting that $\|V^T x\| = \|x\|$, we can use this to conclude that $x = (V \Sigma ^+ U^T)b$ must be the least squares solution (for $x$).

I hope you find this explanation sufficient.

Answer 2

The pseudoinverse solution from the SVD is derived in proving standard least square problem with SVD.

Given $\mathbf{A}x=b$, where the data vector $b\notin\mathcal{N}\left( \mathbf{A}^{*} \right)$, the least squares solution exists and is given by $$ x_{LS} = \color{blue}{\mathbf{A}^{\dagger}b} + \color{red}{\left( \mathbf{I}_{n} - \mathbf{A}^{\dagger}\mathbf{A}\right) y}, \quad y\in\mathbb{C}^{n} $$ where blue vectors are in the range space $\color{blue}{\mathcal{R}\left( \mathbf{A}^{*} \right)}$ and red vectors are in the null space $\color{red}{\mathcal{N}\left( \mathbf{A} \right)}.$ The least squares solution $r^{2}$ minimizes the sum of the squares of the residual errors and is an affine space. That is $$ \lVert \mathbf{A} x_{LS} (y) - b \rVert_{2}^{2} = r^{2}_{min} $$ for all values of $y$.

What is the vector in this affine space with the smallest length? The length of the solution vectors is $$ \lVert x_{LS} \rVert_{2}^{2} = \lVert \color{blue}{\mathbf{A}^{\dagger}b} + \color{red}{\left( \mathbf{I}_{n} - \mathbf{A}^{\dagger}\mathbf{A}\right) y} \rVert_{2}^{2} = \lVert \color{blue}{\mathbf{A}^{\dagger}b} \rVert_{2}^{2} + \underbrace{\lVert \color{red}{\left( \mathbf{I}_{n} - \mathbf{A}^{\dagger}\mathbf{A}\right) y} \rVert_{2}^{2}}_{y=\mathbf{0}} $$ The solution vector of minimum length is $\color{blue}{\mathbf{A}^{\dagger}b}$, the point in the affine space closest to the origin.

Answer 3

The resource linked below really helped me understand this. The transformation $A$ can be interpreted in 2D as mapping the unit circle to an elipse. This can be done in a 3 step process using the SVD:

1. Rotate the unit circle so it can be stretched along its axis
2. Stretch each axis to form the ellipse
3. Rotate again to align the ellipse with the output space of $A$

To solve for $x$, you reverse this process, starting with $b$.

Least squares comes in when step 2 creates a ellipse with a width of zero. When you're going through this process in reverse, when you get to step 2, un-stretching throws away that dimension with a width of zero. Still, you're left with the closest point to $b$ in the output space of $A$. Continuing through the reversed process gets you to $x'$.

In other words, the transformation $A$ maps the unit circle to a line instead of an ellipse, and you've found the $x$ for which $Ax$ results in the closest point on that line to point $b$.

https://www.cs.cornell.edu/courses/cs3220/2010sp/notes/svd.pdf

Answer 4

Let's fix the dimensions for the sake of making the example simpler and say that $A:\mathbb{R}^8\to\mathbb{R}^5$ and that $rank(A)=3$.

$A=U\Sigma V^T$ is the singular value decomposition of $A$ and $e_1, ..., e_5$ and $f_1, ..., f_8$ are the standard bases of $\mathbb{R}^5$ and $\mathbb{R}^8$ (respectively), i.e. $e_1 = [1, 0, 0, 0, 0]^T$ etc.

So $A(\mathbb{R}^8)$ is a 3-dimensional subspace of $\mathbb{R}^5$. What are the (or some) geometric interpretations of $U$, $\Sigma$ and $V$?

$U$ sends the basis vectors $e_i$ to the column vectors $Ue_i$ of $U$ which give us an orthogonal basis in $\mathbb{R}^5$ such that the first three column vectors span $Im(A)$. You can see this by noting that

$U\Sigma f_1 = U\sigma_1 e_1 \ne 0$

$U\Sigma f_2 = U\sigma_2 e_2 \ne 0$

$U\Sigma f_3 = U\sigma_3 e_3 \ne 0$

$U\Sigma f_4 = ... = U\Sigma f_8 = 0$

Since $U$ is orthogonal its inverse is $U^T$.

Similarly $V$ sends the basis vectors $f_i$ to the column vectors $Vf_i$ of $V$ which give us an orthogonal basis in $\mathbb{R}^8$ such that the last 5 span $ker(A)$:

$AVf_i = U\Sigma V^TVf_i = U\Sigma f_i \ne 0$ for $i$ = 1, 2, 3

$AVf_i = U\Sigma V^TVf_i = U\Sigma f_i = 0$ for $i$ = 4 .. 8

And the inverse of $V$ is $V^T$.

$\Sigma$ jams $\mathbb{R}^8$ into $\mathbb{R}^5$by mapping the one-dimensional spaces spanned by each of $f_1, f_2, f_3$ onto those spanned by $e_1, e_2, e_3$ (scaling them by $\sigma_1, \sigma_2, \sigma_3$ in the process) while squashing those spanned by $f_4..f_8$.

It follows that $A$ jams $\mathbb{R}^8$ into $\mathbb{R}^5$ by mapping the one-dimensional spaces spanned by each of $Vf_1, Vf_2, Vf_3$ onto those spanned by $Ue_1, Ue_2, Ue_3$ (scaling them by $\sigma_1, \sigma_2, \sigma_3$ in the process) while squashing those spanned by $Vf_4..Vf_8$.

The key here is that restricted to the space spanned by $Vf_1, Vf_2, Vf_3$ A is an isomorphism onto the space spanned by $Ue_1, Ue_2, Ue_3$, and that $V\Sigma^+U^T$ is the inverse (when restricted to $Ue_1, Ue_2, Ue_3$).

If we have $AX = b$ and $b \in Im(A)$ it follows that there exists a unique $x' \in <Vf_1, Vf_2, Vf_3>$ s.t. $Ax' = b$. Any other solution $x$ in $\mathbb{R}^8$ takes the form $x' + \delta$ for $\delta \in Ker(A)$. Now since we can decompose $\mathbb{R}^8$ into $<Vf_1, Vf_2, Vf_3> \oplus <Vf_4, .., Vf_8>$ we have $\lvert x\rvert^2 = <x' + \delta, x' + delta> = \lvert x'\rvert^2 + \lvert \delta\rvert^2$ and so $\lvert x\rvert >= \lvert x'\rvert$ - that is, $x'$ is the closest solution to the origin.