# unusual regularization term

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

1. ### rocksportrockerGuest

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

2. ### Helmut JarauschGuest

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

3. ### aruzinskyGuest

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