Why Sparse Priors Like Total Variation Opts to Concentrate Derivatives at a Small Number of Pixels?

Question

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.

Answer 1

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:

The histogram I got is this:

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.