Tikhonov regularization and SVD to compute condition number

[vibe3]

I am solving linear least squares problems with generalized Tikhonov regularization, minimizing the function:
$$\chi^2 = || b - A x ||^2 + \lambda^2 || L x ||$$
where $L$ is a diagonal regularization matrix and $\lambda$ is the regularization parameter. I am solving this system using the singular value decomposition, and I use the normal trick to convert the system into "Tikhonov standard form":
$$\tilde{A} = A L^{-1}, \tilde{x} = L x$$
so that
$$\chi^2 = || b - \tilde{A} \tilde{x} ||^2 + \lambda^2 || \tilde{x} ||$$
This system can now be solved easily with the SVD of $\tilde{A}$. My problem is that I want to compute the condition number of $A$ while solving the system, but I don't see any easy way to compute this since I calculate only the SVD of $\tilde{A}$. It seems that there is no simple relationship between the singular values of $A$ and the singular values of $\tilde{A}$, even when $L$ is a diagonal matrix.

Does anyone know of a solution to this problem, without having to separately compute the SVD of $A$ itself?

 

[jvicens]

I am familiar with linear least squares problems and generalized Tikhonov regularization. I can see that you have successfully converted the system into Tikhonov standard form and are using the SVD of the transformed matrix to solve it. Your concern about computing the condition number of A is valid, as the SVD of \tilde{A} does not provide direct information about the condition number of A.

One possible solution to this problem could be to use the concept of sensitivity analysis. This approach involves perturbing the data and calculating the change in the solution. In this case, you could perturb the data and calculate the change in the solution \tilde{x}. Then, using the relation \tilde{x} = L x, you can calculate the change in the solution x. This change can then be used to estimate the condition number of A.

Another approach could be to use the fact that the condition number of a matrix is the ratio of the largest and smallest singular values. While the SVD of \tilde{A} does not provide the singular values of A directly, it does provide the singular values of \tilde{A}. You can use these values to estimate the singular values of A and then calculate the condition number.

I would also suggest considering the use of an iterative method instead of the SVD to solve the system. Iterative methods, such as the conjugate gradient method, can be more efficient in computing the condition number of A. However, this may require additional computations, so it is important to consider the trade-off between accuracy and efficiency.

In summary, there are various ways to estimate the condition number of A while using the SVD of \tilde{A} to solve the system. Depending on your specific problem and requirements, you may need to choose the most appropriate approach. I hope this helps in your research.