When performing image deconvolution (deblurring), people often make use of priors to get rid of the illness of the problem. One very common prior is total variation, a sparse prior. Compared to Gaussian prior, it is supposed to be better as it concentrate derivatives at a small number of pixels, which fulfill the assumption people have with clear images. So my question is: how can we understand that sparse prior such as total variation concentrate derivatives at a small number of pixels while the Gaussian prior cannot. Thanks.


I will divide my answer into 3 sections.

The Distribution of the Derivative of Images

Take a real world image, any image.
Apply the derivative operator on it (Namely apply the kernel $ \left[ 1, -1 \right] $ on it.
Display the histogram of the filtered image.

I took this image:

enter image description here

The histogram I got is this:

enter image description here

This distribution is very similar to Laplace Distribution.
Clearly, this distribution is "Sparse" namely most of the values are 0 (Or close) and very few are different.
In real world we assume most of the values which are small yet not zero are actually due to the noise.

Total Variation Optimization Problem

Look at the Optimization Function:

$$ \hat{x} = \arg \min_{x} {\| Hx -y \|}^{2} + \lambda {\| G x \|}_{1} $$

Where $ H $ is the Blur Operator and $ G $ is the Derivative Operator.

Now, you can look at it in the Sparse sense or you can look at it as the MAP solution given a Laplace prior for the Gradient.

As written above, it fits very well to real world images.

Sparse Optimization

Look at the Optimization Function:

$$ \hat{x} = \arg \min_{x} {\| Hx -y \|}^{2} + \lambda {\| G x \|}_{0} $$

Where $ H $ is the Blur Operator and $ G $ is the Derivative Operator.

This optimization problem clearly promote Sparse solution (With respect to the Derivative).
Yet, this is a very hard problem to solve.
Hence it was shown that under some circumstances the solution of the problem with $ {\ell}_{1} $ coincide with this solution.

Moreover, by looking at the Unit Sphere of different norms (And the Pseudo Norm $ {\ell}_{o} $, or more correctly Cardinality Function) you can see why the lower the norm the Sparse Solution it promotes.

All in all you have many point of view on the same problem.

  • $\begingroup$ Even if one writes this quite often, $\ell_0$ is no pseudo-norm. Nor a quasi-norm. $\endgroup$ – Laurent Duval Apr 30 '16 at 21:58
  • $\begingroup$ @LaurentDuval, How do you call it? Because by using this symbol means it is a Norm, hence something must indicate that though it is marked like one, it is not. $\endgroup$ – Royi Apr 30 '16 at 23:25
  • $\begingroup$ Norm, pseudo-norm, quasi-norm, semi-nom all have a feature related to homogeneity that $\ell_0$ does not possess (as far as I know). I have seen "count index", "counting measure", "cardinality function", "numerosity measure", "sparsity index", or "simply parsimony" $\endgroup$ – Laurent Duval May 1 '16 at 9:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.