unusual regularization term

Discussion in 'Numerical Analysis' started by rocksportrocker, Feb 5, 2008.

  1. Hi,

    I wondered if anybody considered a version of tikhonov-philips

    min_x || Ax -b ||^2 + a ||x||^q

    with q near to zero. So the second term would lead to very sparse

    How could one numerically solve this problem ? ||x||^q shows
    singularities in this case.

    Greetings, Uwe
    rocksportrocker, Feb 5, 2008
    1. Advertisements

  2. I'm just curious. Why do you think the solution vector is going to be sparse?
    If you plot the unit circle (wrt q-norm q < 1) =
    isoline of |x_1|^q +|x_2|^q = 1
    you see that heuristically a vector which concentrates all its "mass"
    into a single component has highest(!) q-norm. So, IHMO, your penalty term
    achieves just the opposite.

    Helmut Jarausch

    Lehrstuhl fuer Numerische Mathematik
    RWTH - Aachen University
    D 52056 Aachen, Germany
    Helmut Jarausch, Feb 8, 2008
    1. Advertisements

  3. rocksportrocker

    aruzinsky Guest

    Not exactly, but I have implemented Tikhonov style regularization

    min_x || Ax-b ||1 + a ||x||1


    min_x || Ax-b ||^2 + a ||x||1

    where ||.||1 is L1 norm.

    These are respectively linear and quadratic programming problems.
    Also, in image processing there is the total variation (TV) problem in
    which the regularization term is sum( sqrt(Ix*Ix + Iy*Iy) ), sum of
    discrete gradient magnitudes.

    I doubt that your function is convex for q<1 which means it will have
    local minima and the minimum must be solved by something like
    simulated annealing.
    aruzinsky, Feb 22, 2008
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.