2
$\begingroup$

I was experimenting with weighted ridge regression for a linear system, where the closed-form solution is given by: $$ b =(X^T WX + \lambda I)^{-1}X^T W y $$

and also weighted least squares whose closed-form solution is given by $$ b =(X^T WX)^{-1}X^T W y $$

The results in both cases are different with way better results from weighted least squares. But when I solve weighted ridge regression iteratively as shown below I get the same result as weighted least squares. $$ b^{(m+1)} = b^{(m)} + (X^T WX+ \lambda I)^{-1}X^T W z_{(m)} $$ $m$ is the iteration number, $z_{(m)}$ is the residual at every iteration. I am not sure why the result is the same when it is solved iteratively? Can someone please guide me in the right direction or explain this behavior?

$\endgroup$

2 Answers 2

3
$\begingroup$

Weighted least squares uses an analytic (weighted) least-squares solution, while ridge regression gives a maximum log likelihood result. Weighted ridge regression is uncommon.

Why does ridge regression not give the least-squares solution?

Typically when explaining ridge regression,$\lambda$ is introduced as a penalty (lagrange multiplier) on the L2 norm of $b$. Solving the system of equations, minimizing it least-squares, results in your first formula. If your problem has a least squares solution for which entries in $b$ is large, than this penalty will negatively effect the least squares error.

Iterating ridge regression vs Least squares

I do not understand why you would start to iterate ridge regression. But it is nevertheless worth exploring why this converges to the LS solution.

I will explain the iterative behaviour using ordinary least squares. While the proof for weighted LS becomes more challenging, it will surely be intuitive why it will have the same result. For my explanation I will use the singular value decomposition: $$X=U\Sigma V^T$$ Substituting into ridge regression and ordinary least squares: $$b_1=(X^T X+\lambda I)^{-1} X^T y \qquad b_2=(X^T X)^{-1} X^T y$$ yields: $$b_1=V(\Sigma^2+\lambda I)^{-1}\Sigma U^T y \qquad b_2=V\Sigma^{-2}\Sigma U^T y$$ Least squares is an analytic solution, for which the residual lies in the null-space of $X$. $$X^T(y-X b_2)=0$$ But in ridge regression an additional residual term appears (writing everything out will show this): $$Xb_1-Xb_2^{(m=1)}= U\Sigma [(\Sigma^2+\lambda I)^{-1}-\Sigma^{-2}] \Sigma U^T y$$ $$= U\Sigma [-\lambda\Sigma^{-2}(\Sigma^2+\lambda I)^{-2}] \Sigma U^T y$$ Further iterations can be compactly written down as: $$Xb_1-Xb_2^{(m=M)}= U[\Sigma [(\Sigma^2+\lambda I)^{-1}] \Sigma]^{M-1} \Sigma [-\lambda\Sigma^{-2}(\Sigma^2+\lambda I)^{-2}] \Sigma U^T y$$ Where you will notice that the diagonal terms $\frac{\sigma_i^2}{\sigma_i^2+\lambda}^{M-1}$ go to zero as $M$ increases. The residual term (the difference between LS and ridge regression) decays exponentially.

$\endgroup$
0
$\begingroup$

A note to add to @Vincent's answer

The iteration will stop if $X^TWz=0$. That's true at the WLS solution, since that's exactly the equations that define the WLS solution. So, if the iterated procedure does converge (which is not obvious without more work) it basically has to converge to the WLS solution.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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