regularization of $\hat{x} = \arg\min_x|Ax - b|^2 + \lambda|x|^2$ using SVD of $A$

190 Views Asked by At

Suppose that the following energy is provided $$ \hat{x} = \arg\min_x|Ax - b|^2 + \lambda|x|^2 $$ with a given matrix $A$, a vector $b$ and regularization paramter $\lambda$. Analyze how the solution of this minimization problem varies with $\lambda$ by using the singural value decomposition of $A$

by taking the gradient with respect to $x$ of the energy and by setting the gradient to zero, we obtain $$ A^\top(Ax - b) + \lambda x = 0 $$ Finally we obtain $$ x = (A^\top A + \lambda I_d)^{-1}A^\top b $$ Let us decompose $A$ via the SVD. Then, we obtain $$ A = USV^\top $$ where $U$ and $V$ are orthogonal matrices and $S$ is diagonal and with nonnegative entries. Then, we obtain $$ x = V(S^2 + \lambda I_d)^{-1}SU^\top b = V\text{diag}\Big\{\frac{s_i}{s_i^2 + \lambda}\Big\}_{i = 1,..., n}U^\top b $$ However if I plug in $A = USV^\top$ in $x = (A^\top A + \lambda I_d)^{-1}A^\top b$, I get \begin{align*} x&= (A^\top A + \lambda I_d)^{-1}A^\top b\\ &= ((USV^\top)^\top USV^\top + \lambda I_d)^{-1}(USV^\top)^\top b\\ &= (VSU^\top USV^\top + \lambda I_d)^{-1}VSU^\top b\\ &= (VS^2V^\top + \lambda I_d)^{-1}VSU^\top b\\ \end{align*} and I'm stuck to that point. Is it wrong? Which further steps are needed?

1

There are 1 best solutions below

0
On BEST ANSWER

final comment adapted as the answer:
one thing to observe is that the (scaled) identity matrix is similar to itself, so $\lambda I = V (\lambda I) V^{-1}$

I dropped the term $U^T b$ since it isn't needed. This really is working through diagonalization.

$(VS^2V^\top + \lambda I_d) = VDV^{T}$ for othogonal $V$ so its inverse is $VD^{-1}V^T$ and we have $VD^{-1}V^TV S = VD^{-1} S = V\text{diag}\Big\{\frac{s_i}{s_i^2 + \lambda}\Big\}_{i = 1,..., n}$.
All that needs to be done is to carefully evaluate diagonal matrix and its inverse.