Is There a Sparse Representation for Noise?

Question

Is there sparse representation for stationary noise and nonstationary noise? How can I learn dictionary for each noise class? (my mean of noise is noises with which speech signals are often contaminated such as white gaussian noise, car noise, babble noise, impulsive noise....)

Answer 1

The question of the existence of a sparse basis of noise is closely related to the question of the effective dimensionality of the noise subspace.

First, it is important to realise that noise is a process, and not a signal. You can think of a full characterisation of any kind of noise by means of a function $p: S \to \mathbb{R}^+_0 $ that maps a signal $s$ to a probability $p(s)$ of finding that signal as the realisation of the noise process. This description is fully general and more useful than it may appear at first sight.

The ensemble of all possible noise signals $s$ together with their respective probability $p(s)$ is a very unhandy object to deal with mathematically. Finding a more practical description that still contains relevant information is possible.

Consider the orthogonal projector $P_s$ onto a signal $s$. This projector is a non-negative symmetric operator on the signal space.

If we have a fairly and sufficiently densely sampled set of possible signals $\{s_i:i\in\mathbb{N}\}$ with their respective probabilities $p(s_i)$, then the weighted convex sum of the projectors onto these sample signals $$E:=\frac{\sum_i p(s_i) P_{s_i}}{\sum_i p(s_i)\cdot\mathrm{trace}\left(\sum_i P_{s_i}\right)}$$ is also a non-negative symmetric operator on the signal space. (Note that this ad-hoc construction becomes somewhat more involved if done rigorously, but then would require a bit of measure theory on the signal space.)

The operator $E$ has some interesting properties. It's relatively straight forward to see, that its trace is bounded by $0$ from below and $1$ from above. The upper bound is attained exactly if $p(s)\equiv \mathrm{const}$. The trace of $E$ has an interesting interpretation as the effective relative dimensionality of the noise subspace $S_N$: $$\mathrm{trace}\left(E\right)\approx\frac{\mathrm{dim\,S_N}}{\mathrm{dim}\,S}$$

What is more, an orthogonal basis of the noise subspace can be derived from $E$ in form of its Eigenspectrum. If you sort the Eigenvectors of $E$ in order of their descending Eigenvalue and take the first $\mathrm{dim}\,S_N\approx\mathrm{ceil}\left(\mathrm{dim}\,S \cdot \mathrm{trace}(E) \right)$ vectors, you should have a basis that spans your noise subspace reasonably well.

So, how do we find $E$ in practice? Let us assume you have a noise generator that produces a single output signal. It is reasonable to assume that for such a noise generator, each received output signal is approximately equally likely. Therefore, generating an ensemble of noise signals with this generator samples the noise subspace evenly and with constant probability. The rest of the signal space has a probability of 0 and is not sampled. However, we do need a set of signals that sample the entire signal space to apply the definition of $E$ from above. Let us call the samples of the signal space that we do not take $\{ \bar{s}_j \}$ and the constant probability of those $s_i$ that we do take just $p$. Then the definition becomes

$$E=\frac{\sum_i p\,P_{s_i}+\sum_j 0\,P_{\bar{s}_j}}{\left(\sum_i p + \sum_j 0\right)\cdot\mathrm{trace}\left(\sum_i P_{s_i}+\sum_j P_{\bar{s}_j}\right)}$$

which simplifies to

$$E=\frac{\sum_i P_{s_i}}{\mathrm{trace}\left(\sum_i P_{s_i} \right) + \mathrm{trace}\left(\sum_j P_{\bar{s}_j} \right)}$$

We are stuck here, because don't know $\mathrm{trace}\left(\sum_j P_{\bar{s}_j} \right)$ and estimating it would require the dimensionality of the noise subspace, which we are trying to find. However, we can look at the operator

$$E'=\frac{\sum_i P_{s_i}}{\mathrm{trace}\left(\sum_i P_{s_i} \right)}$$ which is has the same Eigenstructure as $E$ up to scaling. Because of the assumptions we have made, the Eigenvalues of $E'$ associated with the Eigenvectors outside of the noise subspace are all 0. Because the trace of $E'$ equals $1$, the Eigenvalues associated with the Eigenvectors inside of the noise subspace approximately equal $\frac{1}{\mathrm{dim}\,S_N}$. So doing an Eigendecomposition of $E'$ will result in an orthogonal basis of the noise subspace and give a natural separation between the noise subspace and its orthogonal complement.

Numerically constructing $E'$ requires a bit of memory and summing of the projectors onto the generated signals. The following Eigendecomposition can be computationally challenging, but should be doable for reasonably sized signal vectors.

Answer 2

Let's think about it in a different way - Generate Noise from a Dictionary.

Let's create a Dictionary $ A \in \mathbb{R}^{m \times n} $ where each of its rows is normalized (Has Euclidean Norm of $ 1 $) and generated by a Gaussian Random Vector.

Now, let's create $ N $ random vector $ {\left\{ {r}_{i} \right\}}_{i = 1}^{N} $ by:

$$ {r}_{i} = A {g}_{i} $$

Where $ {g}_{i} $ are random vectors $ {g}_{i} \in \mathbb{R}^{n} $ with only $ k \ll n $ non zero elements (Let's say they are pre defined and deterministic otherwise we'll have to deal with multiplication of random variables).

Now, the output vectors are valid Gaussian Random Variables and given enough of them and some properties of $ A $ you'd be able to build a Dictionary which they are sparse with relation to it.

Yet it means the dictionary is random by itself and next time when you get new set of random data it won't be able to represent it correctly (It doesn't generalize).

While the above is not rigorous (It means to develop some intuition, not analytic analysis) it tells you why when we deal with finite amount of data it can be done but for noise as in general it won't work.