Sparse representations for denoising problems I have read in a huge number of papers that sparse models (sparse coding, dictionary learning, sparse matrix factorization, ...) are good solutions for image denoising problems.
I know that representing data as sparse combinations of atoms from a (overcomplete) dictionary should be the way the mammal primary visual cortex works. However it is not clear why sparse representations should eliminate noise, blur or other similar artifacts. Is there any valid mathematical explanation for this?
Thinking about Lena image (384x384):

Does its histogram really show us a "sparse nature"?

 A: The more non-Gaussian your data, the easier it is to distinguish it from Gaussian noise. If your model assumes that both the signal and the noise are independently Gaussian distributed, then there is no way for it to distinguish signal from noise and no way to denoise the observed signal.
A first step to removing independent Gaussian noise is to assume that the signal is correlated. A natural next step is to also allow for higher-order correlations, that is, to assume that the signal is non-Gaussian. Sparsity (high kurtosis, super-Gaussianity) is one form of non-Gaussianity. Sparse coding and related algorithms can be viewed as trying to find maximally non-Gaussian directions in the data. 
The sparsity is an empirical property of natural signals. If you look at the filter responses of pretty much any filter with zero mean, they will be sparsely distributed.



The center image is the image on the left filtered with a random zero-mean filter (5x5 pixels large). As you can see, most of the time the responses are close to zero (gray regions). The red histogram shows the distribution over filter responses. Some filters (Gabor like filters) will produce slightly sparser responses (blue histogram). Sparse coding algorithms are able to automatically find those. These directions produce histograms which are even more different from the Gaussian distribution (dashed line).
However, we could also come up with a signal where filter responses are sub-Gaussian and a sub-Gaussian assumption would therefore lead to better results.
In general, the more prior information about the signal you put into your model, the better the denoising results should become. Of course, not all information will be equally important, and different prior assumptions might lead to better results under different criteria for evaluating denoising algorithms.
Here is some additional information that might help.
Consider the following two-dimensional distribution: 

The histograms after projecting the data onto the red or blue vectors look like this this:

Note how the blue histogram is less sparse than the red histogram. In higher dimensions, this effect is much more pronounced (which has to do with the central limit theorem). That is, you might not even see the sparsity in the signal if you look at the wrong representation of the data.
The data points in the plot above basically correspond to image patches of your image, the blue vector to the pixel representation and the red vector to some filter.
