# Recovering true data from multiple noisy versions

I am trying to find if there is any way to get the true data from multiple noisy versions, but the true data has a peculiar property.

Problem Statement

Consider a matrix $F=[f_1, f_2, ... , f_n]$ where $f_i$ is 1984-dimensional. Now, each $f_i$ can be expressed as $f_i=H^i+n_i$. Here $H^i$ is the true (unknown) data and $n_i$ is the embedded noise. The peculiar property is that each $H^i$ has high correlation with each other (in other words, all $H^i$ are similar to each other). I want to build a filter or a vector which when multiplied with $f_i$, will give me $H^i$ or approximated $H^i$ i.e. noise should reduce.

My thoughts

I understand we should place some extra assumptions on the noise type, like Gaussian etc. In my case, I don't think my noise is Gaussian. Each feature vector $f_i$ basically represents an image patch. So, noise can be random, but I am open to modelling the noise as Gaussian and see what happens. I think a machine learning approach will work better. I had two thoughs:

1. Learn a vector such that when multiplied with the data it should minimize $||w^Tf_i-w^Tf_{i+1}||$ should be minimized such that (say) $||w||\le1$.

2. Add up a subset of $f_i$ so that by adding up different $n_i$, it will approach Gaussian (?) and I assume there are methods to recover data when noise is Gaussian.

I am open to any other ideas as long as I get the desired result.

You can edit tags if necessary.

• Should that $F_i$ in the 4th line of the problem statement be $f_i$? – jbowman Jan 15 '14 at 20:58
• @whuber I cannot say anything about the correlations between $n_i$. I understand that it may not be possible to recover the true data but what I am looking at is a method to at least reduce it? If its possible at all. Also, I actually though if $H^i$ are similar then we may be able to take advantage of it. If that's not the case, then I guess this becomes impossible to solve then. As I said, I can assume some kind of correlation of some particular type of noise if that helps the cause. I can at least see what is happening. – Autonomous Jan 15 '14 at 21:31
• Far from it! Consider the limiting case of perfect correlation: you will have a dataset in which a single $H$ is observed repeatedly. Averaging the observations component by component does a great job with Gaussian noise; other procedures to combine the data are available for other assumptions about the noise. – whuber Jan 15 '14 at 21:35
• I might have misunderstood your question. Here's why: if all the $H^i$ are different, then how are we to distinguish them from the $H^i+n_i$? In other words, how is one to distinguish a noisy image from the original image if only one sample of that image is available? That's clearly impossible. In order to have any hope of getting an answer, you must posit some kind of quantitative relationship among the various $H^i$ and $n_i$ in order to get any kind of answer at all. ("High correlation" of the $H^i$ is not quantitative.) – whuber Jan 15 '14 at 23:22
• It's not quite clear, but it kind of sounds like we may be looking at some kind of principal-components-like type problem here. Perhaps. – Glen_b Mar 20 '14 at 5:14

I would try linear regression, at least as my first approach. To put it in strictly matrix terms, define $F_{-i}$ as $F$ with the $i^{th}$ column removed. Then construct the matrix $P_i = F_{-i}(F_{-i}^TF_{-i})^{-1}F_{-i}^T$ (the projection matrix.) Your estimate of $f_i$ would then be $\hat{f_i} = P_if_i$.

This minimizes the Euclidean distance between $f_i$ and $\hat{f_i}$ where $\hat{f_i}$ is located in the space spanned by the columns of $F_{-i}$. Since the $H^i$ are highly correlated, there should be some explanatory power in $F_{-i}$, but how much depends upon the variance of the noise vectors relative to the variance of the $H^i$ themselves.

This wouldn't work well if the distribution of your noise has fat tails relative to the Gaussian distribution, but I don't know enough about your topic area to make any statement about how likely that is.

Edit: Fixed the typo in line 5.

• How did you arrive at this. Can you point me to some reading material? Also, in the 5th line, should it be $F_{-i}$ instead of $F_{-1}$? What do you mean by explanatory power in $F_{-i}$ – Autonomous Jan 15 '14 at 21:51
• How does regression cope properly with the fact that all of the $f_i$ are affected by noise to the same degree? – whuber Jan 15 '14 at 23:05
• @whuber - Without some reasonable guesses at the various distributions involved, it's not clear to me that we can cope properly with the noise, but we can still try something. If the signal-to-noise ratio in the $f_i$ is fairly high (whatever that means), I wouldn't worry, since we don't care about the coefficient estimates as such. If we have low predictive power, then time to think of something else. If it's high, then the noise likely hasn't had an overwhelming effect. I should emphasize that I'd try this first and see what happens, rather than commit to it as the only approach. – jbowman Jan 15 '14 at 23:42

There are some interesting and useful methods for automatic noise estimation and removal using multiresolution support and wavelets. I have used this to clean Gaussian noise from images to great effect. There are also techniques that are applicable to Poisson noise. The key is to estimate the level of noise and follow that up with a wavelet approach to remove noise of thae predicted level.

Granted, this doesn't use the fact that there may be high correlation between the $H^i$ but in my experience the algorithms described in the references should work well

Another possibility is to normalise the $f_i$. As @whuber mentions, in the case of no noise and perfect correlation, the normalised $f_i$'s should be equal. Ask yourself what would happen in the case of perfect correlation between the $H^i$ but in the presence of noise. Can you predict the level (or distribution) of noise under these assumptions? And what happens when you add the additional assumption that the $H_i$ are not perfectly correlated (but are highly correlated).

Let's say that $F_{ti}=f_i(t)$, where $t\in [1,1984]$, then I'd simply use the average $\hat H_i=\frac{1}{1984}\sum_{t=1}^{1984} f_i(t)$.