# Solution to Least Squares problem using Singular Value Decomposition

Let $A_{mn}$, $m\geq n$ have full column rank and $A=U_1 \Sigma V^T$ be its reduces singular value decomposition. Show that the linear least squares problem $min_{x \in R^n} \||y-Ax||_2$ is solved at $x= V \Sigma^-1 U_1^Ty$.

Here is my attempt, just want to make sure it is correct.

Since A has full column rank there is a unique solution and that solution satisfies the normal equations, ie $A^Ty= A^TA x$. So if we manage to show that the given x makes the right hand side of the equation equal to the left, then we are done.

$A^Ty= V \Sigma^T U_1^Ty$ and $A^TAx=V \Sigma^T U_1^T U_1 \Sigma V^T V \Sigma^{-1} U_1^Ty= V \Sigma^T U_1^Ty$ since $V^TV=I$ and $U_1^TU_1=I$.

Hence both sides are equal and the equation is satisfied, so x is the solution.

I am just wondering whether we can use $U_1^T U_1 =I$ and $V^TV=I$ even though its the reduced singular value? Those still hold correct? Thanks in advance

Our aim is to to solve the least-squares problem $$Ax = y$$ or equivalently, $$U_1\Sigma V^tx = y .$$ It is not necessary to multiply both sides by $A^t$ but you have not done a mathematical mistake by doing that multiplication. However, numerical analysts would not happy if you do that multiplication. Pre-multiply by $U_1^t$ and use the property $U_1^tU_1 = I$. $$U_1^t U_1 \Sigma V^t x = \Sigma V^t x = U_1^t y$$ Premultiply by the inverse of the diagonal singular value matrix $\Sigma$ to get $$V^t x = \Sigma^{-1}U_1^t y$$ where we have assumed that all the singular values are non-zero. Premultiply by $V^t$ and note that $VV^t = I$. $$VV^t x = x = V \Sigma^{-1} U_1^ty$$ which gives the required answer.
Basically, we have multiplied the original equation by the Moore-Penrose generalised inverse defined by $V\Sigma^{-1}U_1^t$ and used the property $VV^t = I$.