Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Tikhonov regularization

  1. Jan 17, 2014 #1
    The least-squares solution of [itex]A x = b[/itex] using Tikhonov regularization with a matrix [itex]\mu^2 I[/itex] has the solution:

    [tex]
    x = \sum_i \left( \frac{\sigma_i^2}{\sigma_i^2 + \mu^2} \right) \left( \frac{u_i^T b}{\sigma_i} \right) v_i
    [/tex]

    where [itex]A = U S V^T[/itex] is the SVD of [itex]A[/itex] and [itex]u_i,v_i[/itex] are the columns of [itex]U,V[/itex].

    For ill-conditioned matrices, the singular values [itex]\sigma_i[/itex] could be tiny leading to problems in computing the quantity [itex]\left( \frac{\sigma_i^2}{\sigma_i^2 + \mu^2} \right)[/itex] since [itex]\sigma_i^2[/itex] could underflow.

    Does anyone know how to compute this solution safely and efficiently in IEEE double precision?
     
  2. jcsd
  3. Jan 18, 2014 #2

    AlephZero

    User Avatar
    Science Advisor
    Homework Helper

    If ##\sigma_i^2 \ll \mu^2##, then the corresponding term of the sum is approximately
    $$\frac{\sigma_i}{\mu^2} (u_i^T b) v_i$$

    But in practice you are unlikely to have a problem, because the ratio of ##\sigma_\min / \sigma_\max## will be limited by the numerical precision of the matrix ##A##, and unless ##A## has some pathological properties ##\sigma_\min / \sigma_\max## is unlikely to be less than about ##10^{-16}##.

    If all the SVs and ##\mu## are very small (e.g. less than ##10^{-100}##) so underflows are likely to affect everything, the best fix would be to rescale the original problem to make them of order 1.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Tikhonov regularization
  1. Regular Representation (Replies: 1)

Loading...