Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Assume someone generate random number "s"(signal) which is $+1$ or $-1$ (uniformly distributed), and generate random number $n$ (noise) $N(0,\sigma)$ (i.e. normal distributed with mean zero, variance $\sigma^2$). Assume "$s$" and "$n$" are independent.

Then "he" sums: $r = s+n$ and gives number "$r$" to you.

Assume you have a sample of length "$n$" of numbers $r_1,\ldots, r_n$.

Question you want to estimate sigma - how to do it?

More precisely I need simple estimation, i.e. such that complexity of the algorithm will be more or less the same as for simple solutions (1 , 2 ) described below, but I want more higher accuracy than the naive solutions below.

If there some nice reference on this it would be helpful... "Simple" solutions are given below.

(Clarifications: you do not know "s_i" not "n_i", but you know that distribution of "s" and knows what "n" is N(0,sigma) , but you do not know sigma) ?


Motivation. Actually yours mobile phones solves this (or more complicated) problem every millisecond (or so). That is why complexity is an issue. "s" is sent bit, during propagation from base station to yours mobile phone it is spoiled. The simplest mathematical model of such propagation is to add random normal noise: so "r" - is received signal. Mobile phone wants to determine what have been sent +1 or -1. Now some profound algorithms first need estimation of noise level "n". After that they start determining "s".


Solution 1.

Denote by D(ksi) - variance of randome variable ksi.

So we know that D(r) = D(s) + D(n). D(s) is know to us D(s) =1. So we can estimate:

D(n) = D(r) -1 .

So use standard estimate of D(r) and just subtract "1" - and that is all.

Very simple ! But this estimate is rather bad - it can be negative for example and its variance is very far from ideal.


Solution 2.

Take numbers r_i and form numbers se_i = sign(r_i) (these are estimate of "s"). Calculate ne_i = r_i - se_i (these are estimates of noise).

Calculate D(ne_i) - take this as an answer...

This solution is actually perfect is "sigma" is small, but if "sigma" is large it is biased. I.e. mean of this estimate is not true sigma.


Solution 3.

I tried MLD solution. But to my surprise it is also biased for big noise. It leads to solution of transcendental equation. So the problems of complexity arises...

share|improve this question
    
I also asked at: stats.stackexchange.com/questions/19753 –  Alexander Chervov Dec 16 '11 at 7:18

2 Answers 2

You could try a moment-matching approach. In particular, define $\hat{s}$ to be the value of $s$ such that

$$\mbox{Pr}_{s}(-1 < r < 1) = \frac{\sum_i I(-1 < r_i < 1)}{N}$$

where $N$ is the number of observations. You can calculate the left hand side explicitly as $$\mbox{Pr}_s(-1 < r <1 \mid S = 1)\mbox{Pr}(S = 1) + \mbox{Pr}_s(-1< r <1 \mid S = -1)\mbox{Pr}(S = -1)$$

which simplifies (I think) to

$$\Phi(2/s) - 1/2,$$

where $\Phi(\cdot)$ denotes the cumulative distribution function for a standard normal random variable. Inverting this gets

$$\hat{s} = \frac{2}{\Phi^{-1}\left(\frac{\sum_i I(-1 < r_i < 1)}{N} + 1/2\right)}.$$

I'm not sure if this differs much from your Solution 3 in terms of complexity, but one evaluation of the inverse CDF of a Gaussian isn't so bad.

share|improve this answer
    
Thank You for the answer. However I am not quite get it. What means "I" ? Is it indicator equal to 1 or 0 dependently on condition satsfied or not ? –  Alexander Chervov Dec 11 '11 at 13:25
    
Can you comment, what general theory would say about such estimate - is it asymptotically consistent, effective ? –  Alexander Chervov Dec 11 '11 at 13:29
    
Actually I simplified a little my task signal can be not only +-1, but +-3 +-1 ( real ( QAM16) ) and +-7, +-5, +-3, +-1, (real(QAM64)). Is it possible to modify Yours approach ? –  Alexander Chervov Dec 11 '11 at 13:31
1  
Yes, $I$ is the indicator function in this case, sorry to be unclear. The way this works is that it choses $\hat{s}$ to match the theoretical probability of being between -1 and 1 to the observed frequency. This estimator should be consistent, but I am unsure how efficient it will be. In the simple case of +/-1 it should do pretty well. The approach can be adapted, but is much more involved and probably not worth it when there are more than two signal possibilities -- I was leveraging the symmetry of the situation when solving for $s$. –  R Hahn Dec 11 '11 at 14:20

You can do it by essentially iterating (2). First you get your sigma estimate using (2). This is not so great as you've said. Now that you have a (bad) sigma estimate, you can use this to get a first-approximation posterior distribution over the -1, +1 values. So instead of assigning them hard values according to their sign, you can use the gaussian pdf to probabilistically assign them -1 or 1 based on the bad sigma estimate. Then you can re-estimate the posterior expected sigma based on these fuzzy -1, +1 re-estimates. You can iterate between re-estimating sigma and re-estimating the soft -1, +1 distribution.

This is an application of the expectation-maximization principle, so this algorithm will converge to a local maximum likelihood estimate of sigma. Furthermore the likelihood landscape of sigma seems plain enough to not have misleading local optima, so this should also converge to the global maximum likelihood (and therefore statistically consistent) estimate of sigma.

share|improve this answer
    
Thank You that is good idea, I also thought that kind of soft-estimate is relevant, I did not tried it, since time lacking... Can You suggest some refrence on "expectation-maximization" ? Something very very introductory ? –  Alexander Chervov Dec 11 '11 at 13:33
1  
@Alexander: Edited to add wiki links. –  psd Dec 12 '11 at 16:08
1  
@Alexander: Regarding statistical efficiency and consistency, I think that while both this answer and the answer given by Hahn are statistically consistent, I think that only this answer is asymptotically efficient. I don't have a proof of this, but my reasoning is that Hahn's answer goes through a statistic (proportion of data in [-1,1]) that is not statistically sufficient whereas MLE can be proved to be asymptotically efficient in certain well-behaved situations. –  psd Dec 12 '11 at 16:31

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.