# 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?

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

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.

• the sparsity is an empirical property of natural signals Could you explain this statement? Given an image, why should it be sparse? For example, is the lena image sparse? Jan 6, 2013 at 19:00
• When you write "random zero-mean filter", you mean a Gaussian filter, don't you? That is, something like h = fspecial('gaussian', 5)? I think that the convolution between an image and a Gaussian filter should produce a blurred image. I do not understand how you obtain your result... Moreover, does your histogram represent pixel intensity (x) versus number of pixels (y)? Does Lena histogram really show us a "sparse nature"? Jan 11, 2013 at 12:00
• No, I meant a random filter, e.g. h = randn(5), with zero mean, h = h - mean(h). Yes, $x$ is pixel intensity (after filtering) and $y$ is number of pixels in the histograms. Jan 11, 2013 at 12:12
• It is not yet clear. In brief, natural images are NOT sparse, but they can be approximated as a sparse combination on a set of filters (like Gabor filter). The noise cannot be approximated as a sparse combination on the same set of filters. Is this the ultimate meaning? Jan 11, 2013 at 21:27
• Yes. Images in the pixel representation are not sparse, but if you change the basis (using Gabor filters or other zero-mean filters), they are almost sparse (meaning high kurtosis, as evidenced by the filtered Lena image). So you could say that images are inherently sparse, you just have to pick the right representation. So, like you said, they can be represented using a sparse set of filters. Signals which don't have that property will not be approximated well by a sparse set of features. Jan 12, 2013 at 10:54