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
    regularization

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

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

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

    Greetings, Uwe
     
    rocksportrocker, Feb 5, 2008
    #1
    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
    #2
    1. Advertisements

  3. rocksportrocker

    aruzinsky Guest

    Not exactly, but I have implemented Tikhonov style regularization
    with

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

    and

    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
    #3
    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.