0
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

The linear algebra equations are valid (i.e. the solution will be exact) only when the linear system of equations is not over-determined (i.e. more equations than unknowns). The SVD method, however, can also be used for non-square matrices which means for an over determined system. In such cases, LHS of the Ax=b will not be equal to RHS - hence, strictly speaking the SVD method of substituting A=UDV* into Ax=B to find out x (i.e. x = (V)*Inverse(D)*Transpose(U)*y will not yield exact solution, but gives only an approximate solution equivalent to the solution obtained through linear regression methods.

When the number of equations is greater than number of unknowns, there may not be any unique solution and SVD method would not solve the linear system of Ax=B.

But, if you use SVD for linear regression, R package gives a solution which is actually only an approximation for the given y (this is a solution for regression / least squares minimization problem and not the solution for Ax=B). Though theoretically, a plane might exists which contain all points of y, leading to zero residuals and zero standard error, but it is extremely unlikely. (This could highly mislead a new user who might think that the solution obtained from package is exact, with zero residuals!! Hence, for regression problem, it is better to use regression functions (lm) for finding out coefficients which also provides details about residuals along with the solution and SVD has other applications).

$\endgroup$

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.