4
$\begingroup$

In the Tikhonov regularization problem, $\Vert Ax-b\Vert^{2}+\Vert\Gamma x\Vert^{2}$, with $\Gamma=\alpha I$ .The solution from SVD is $x=VDU^\top$, where $A=U\Sigma V^\top$ and $D_{ii}=\dfrac{\sigma_i}{\sigma_i^2+\alpha^2}$, with $\sigma_i$ given by the singular values from $\Sigma$.

The question? Is there a similar solution (in terms of SVD) when $\Gamma=\alpha_{i}I$, $i=1,...,$ number of rows.

$\endgroup$
2
  • $\begingroup$ How about substituting $y_i = \alpha_i x_i$ and using the SVD of the "rescaled" $A$? $\endgroup$
    – Dirk
    Sep 20 '11 at 19:54
  • $\begingroup$ I dont understand the solution can you be more specific to explain. $\endgroup$
    – user16409
    Sep 20 '11 at 21:20
2
$\begingroup$

Tikhonov regularization in its most general form is the solution of the problem

$$\min_{\mathbf x}\|\mathbf A\mathbf x-\mathbf b\|^2+\alpha^2\|\mathbf L\mathbf x\|^2$$

or the problem

$$\min_{\mathbf x}\left\|\begin{pmatrix}\mathbf A\\ \alpha \mathbf L\end{pmatrix}\mathbf x-\begin{pmatrix}\mathbf b\\ \mathbf 0\end{pmatrix}\right\|$$

Lars Elden gave a method for converting this general Tikhonov problem into an equivalent "standard form" regularization problem. I assume in the sequel that $\mathbf L$ is invertible; for singular $\mathbf L$ (and in fact for rectangular $\mathbf L$ as well), refer to Elden's paper for the required transformations (which involves the use of the QR decomposition).

In particular, if we let $\mathbf y=\mathbf L\mathbf x$, one can see that an equivalent standard Tikhonov problem is

$$\min_{\mathbf x}\|\mathbf A\mathbf L^{-1}\mathbf y-\mathbf b\|^2+\alpha^2\|\mathbf y\|^2$$

from which you can use the usual formulae for Tikhonov regularization to solve for $\mathbf y$. From this, one obtains the solution to the general problem as $\mathbf x=\mathbf L^{-1}\mathbf y$.

$\endgroup$
2
  • $\begingroup$ I am looking for a similar formula like in standard Tikhonov solution through SVD, where there is an explicit solution dependence on $\alpha$, i.e $x(\alpha)$. The advantage with $x(\alpha)$ is that once the SVD of $A$ is computed we can compute the solution for any $\alpha$, which is useful for very big matrices - $A$. If there is a similar formula then I would expect $x(\alpha_{i})$ for one SVD computation of $A$. $\endgroup$
    – user16409
    Sep 21 '11 at 19:58
  • 1
    $\begingroup$ As I said, you can now use the formula you gave. The only difference is that youneed to compute the SVD of $\mathbf A\mathbf L^{-1}$ instead of just $\mathbf A$ (and it is easy to invert a diagonal matrix). After all the Tikhonov machinery, multiply the result with $\mathbf L^{-1}$. $\endgroup$ Sep 21 '11 at 23:43
0
$\begingroup$

Observe that

$\min_x\left\|b - Ax \right\|_2 + \left\|\Gamma x\right\|_2= \min_{x} \left\| \left[ \begin{array}{c} b \\ 0 \end{array} \right] - \left[\begin{array}{c} A \\ \Gamma \end{array}\right]x\right\|_2$

which is your original problem reformulated as a least squares problem. $x$ is a solution of the minimization problem if and only if it satisfies the normal equations $\left(A^TA + \Gamma^T \Gamma\right) x = A^T b$. This is true for any $\Gamma$. For $\Gamma$ of full column rank we have a unique solution $x = \left(A^TA + \Gamma^T \Gamma\right)^{-1} A^Tb$. Using this formula you can invoke the SVD of $A$ and study the effect of your regularization matrix $\Gamma^T \Gamma$ for various structures of $\Gamma$.

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