Show me the numbers

>I bought an English translation of Sir Issac Newton's 
>'Principia' at a garage sale last week.  (Newton's 
>Principia is considered by many historians to be one 
>of the greatest discourses ever produced by the 
>human intellect.)  In the Preface of that book Newton,
>with humility, tells his readers that he presents his 
>thoughts not to invite criticism but rather to invite 
>suggestions on how to make his material better.
>
>Cedron, if Sir Issac Newton can show a little humility 
>so can you.
>
>
>[-Rick-]

Rick,

I understand your point about the unseeminglyness of appearing to be a
braggart.  False humility is also quite unseemly too.  Perhaps worse,
because it also contains an element of deceit, whereas bragging is mostly
about exaggeration.

In rereading this excerpt from Newton, I got a possible  different
interpretation than one of humbleness.  Perhaps this is obviated in the
larger context, but I can easily read this as Newton saying "If you are
going to rag on me, don't bother, but if you got something useful to say,
I'd like to hear it."

Ced
---------------------------------------
Posted through http://www.DSPRelated.com

[...snip...]

>There really
>is little place for "exact solutions" in DSP applications. Perhaps a
>symbolic math group could be more interested. More of interest in DSP
applications
>are the details of implementation cost and the effects of noise and
>interference. 

Don't you think it's good when practice rests on solid theory?

[...snip...]

>
>How can the other algorithms be so different when, as you say, they
>approximate yours?

Are not 'x' and 'sin( x )' quite different?  Yet the former approximates
the latter in the neighborhood of zero quite well.

This is not an inapplicable example.  It is one of the approximation used
several times when you derive Jacobsen's estimator from my equation.

>
>If you'd like to start realistic testing of your algorithms you should
>find a better noise source than what you have described so far.

Actually, finding a better tester is even a better idea.  I am quite
grateful to Julien for stepping up and doing so.  I invite everyone to
test my algorithms to the fullest extent possible.  I am just as curious
as anyone of how they perform compared to other techniques.

[...snip...]

>
>So far, not everyone who can understand typical DSP literature agrees
with
>your content.
>
>Dale B. Dalrymple

So far, but at least now people seem to be looking at it more closely. 
I'm not sure what you mean by agreement.  It's hard to argue with the math
itself.  How I describe it, or how useful it is, are different matters.

Thanks for your input.

Ced

---------------------------------------
Posted through http://www.DSPRelated.com

>Cedron <103185@DSPRelated> wrote:
>
>>I think that my data tables show that my equations are considerably
more
>>accurate than Candan's.  What also distinguishes mine from the others
>>examined is that the accuracy is not sample size dependent.  Ergo, it
>>doesn't follow the shelf in Julien's/Candan's diagram, but lays right
>>along the Cramer-Rao bound for any sample size.
>
>Hey, that's great.  Go with it.
>
>Steve

I shall.  Thanks for your support.  After the ruckus I've caused, maybe
others will follow.

A funny thing happened on the way to the hat dance.

        double theAlpha = 3.5 * 2.0 * M_PI 
                        / (double) argSampleCount;
                        
        double thePhi = M_PI / 4.0;

        for( int s = 0; s < argSampleCount; s++ )
        {
            theClean[s] = cos( theAlpha * (double) s + thePhi );
        }


Bins  Dawg Error        Candan Error
----  ----------------  ----------------
   8  0.00000000000000  0.05200727841540
  10  0.00000000000000  0.00454007002421
  13  0.00000000000000  0.00244762957594
  16  0.00000000000000  0.00159637733536
  20  0.00000000000000  0.00101340980039
  25  0.00000000000000  0.00064270689573
  32  0.00000000000000  0.00038661330421
  40 -0.00000000000000  0.00024239658135
  51 -0.00000000000000  0.00014379777910
  64  0.00000000000000  0.00008630015836
  81  0.00000000000000  0.00004872632161
 102  0.00000000000000  0.00002566788368
 128  0.00000000000002  0.00001130078824
 161 -0.00000000000000  0.00000210472222
 203  0.00000000000000 -0.00000375601512
 256  0.00000000000001 -0.00000744452953
 323 -0.00000000000009 -0.00000976778380
 406 -0.00000000000008 -0.00001120848112
 512  0.00000000000004 -0.00001213058153
 645  0.00000000000026 -0.00001270833913
 813  0.00000000000057 -0.00001307308072
1024  0.00000000000032 -0.00001330207727
1290  0.00000000000161 -0.00001344651598
1625 -0.00000000000002 -0.00001353751043
2048 -0.00000000001037 -0.00001359495013
2580  0.00000000001400 -0.00001363105977
3251  0.00000000001019 -0.00001365383220
4096 -0.00000000002271 -0.00001366816828
5161 -0.00000000000754 -0.00001367720165
6502  0.00000000002139 -0.00001368288879
8192 -0.00000000004896 -0.00001368647281

I wanted to show that Candan's results approached mine as the number of
bins increased.  Look what happened!

Reality intruded.  Ain't that something?

Ced

---------------------------------------
Posted through http://www.DSPRelated.com

Cedron <103185@dsprelated> wrote:

(snip)
> The full title is "Exact Frequency Formula for a Pure Real Tone in a DFT".
> Its subject matter is theoretical.  You won't find a pure real tone in
> practice any more than you will find mathematical exactness.  Does that
> also mean you think that the term "pure tone" should be avoided when
> discussing DSP algorithms?
 
> This kind of goes back to Plato and the discussion of a perfect circle.

Seems to me that this is common in DSP.

It is often said that Nyquist sampling allows for exact reconstruction
of the original signal.  That is true if you have an infinite number of 
samples, or if the signal is periodic and sampled at an integer fraction
of the period. 

Conveniently for us, with a sufficiently large number of samples, the
end effect becomes small enough that we mostly ignore it. Reproduction
is plenty close enough, especially with quantization. 

So, yes, it is common to give a theoretical exact solution in a case
that is unobtainable in practice.

Physics has massless strings and frictionless pulleys, allowing for
exact solutions. With real stings and pulleys, it isn't so nice.

-- glen

Would somebody please answer Randy Yates' questions:

1) How do you classify an algorithm that gives you "exact" results when no
noise is present and a good estimate when it is? 

2) Are there other "estimators" that give exact results when no noise is
present?

Thank you,
Ced
---------------------------------------
Posted through http://www.DSPRelated.com

Rick Lyons  <R.Lyons@_BOGUS_ieee.org> wrote:

>On Fri, 29 May 2015 02:23:43 -0500, "tsd82" <105802@DSPRelated> wrote:

>>So I come back on my first statement about your method: it is not so bad,
>>especially at high SNR (as expected for an exact formula), but also at
>>medium SNR (down to about 5 dB). Under 5 dB, it behave rather simularly or
>>is less accurate that the other methods.

>This 'freq estimation based on DFT samples' topic has 
>been attacked by dozens of skilled DSP people for 
>decades.  It's not as simple as Cedron implies.
>And the results of all that study and effort are a 
>collection of "frequency estimation" methods.
>And none of those DSP folk, other than Cedron, has 
>claimed to produce "exact" frequency estimation results.

Well, with the noise free signal, and ignoring the trivial
case of all the energy being in one bin, applying trigonmetry
to any three bin values should yield the exact answer.

So only the noisy case is interesting.

>I think the word "exact" should be avoided when 
>discussing this 'freq estimation based on DFT samples' 
>topic.  Measuring the freq of a real-world, 
>noise-contaminated, sinusoidal signal is never, 
>as far as I can tell, "exact".

My gut feeling (unsupported by exact math) is that the frequency
error for the noisy case is going to be no lower than a value on the
on the order of

     1 / ( SNR * transform length )

Where SNR is expressed as a power ratio (not in dB).

My gut feeling (also unsupported by exact math) is that the best
estimate will use all of the bins, but will weight them using
some variant of maximal ratio combining so that the bins with
the least energy do not contribute disproportionate noise to the result.

This would be very straightforward for testing between two
or a small number of hypotheses -- e.g. whether the phase and frequency 
are [ f1, phi1 ] or [ f2, phi2 ].  It is probably provable that
MRC gives the best possible result for this limited case.

Steve

Cedron <103185@DSPRelated> wrote:

>[...snip...]
>
>>There really
>>is little place for "exact solutions" in DSP applications. Perhaps a
>>symbolic math group could be more interested. More of interest in DSP
>applications
>>are the details of implementation cost and the effects of noise and
>>interference. 
>
>Don't you think it's good when practice rests on solid theory?

I'm going to side with Cedron on this one.

"Exact" statements can be made in mathematics.  Everybody [*] knows
that you don't get these "exact" results in the real world, therefore,
nobody is confused when DSP engineers use the term "exact".
It simply means the claimed statement is correct as a mathematical 
derivation.  No big deal.

Along these lines, an unrelated example.   I have always suspected
the black holes do not exist in reality, for the simple reason
that singularities tend to occur in mathematics but not in nature.
For many decades running, all except fringe astrophysicists
firmly believed (or at least would talk as though they believed)
that "black hole candidates" were indeed black holes, and not some
other sort of dense object.  There were always doubters, but they 
were always shouted down ... until Stephen Hawking became one 
of the doubters.

Steve

[*] Everybody except astrophysicists apparently... 

[...snip...]

>
>Well, with the noise free signal, and ignoring the trivial
>case of all the energy being in one bin, applying trigonmetry
>to any three bin values should yield the exact answer.
>
>So only the noisy case is interesting.
>

In a sense, my solution is "applying trigonometry to any three bin
values".  And in the pure tone case, can be solved from any three bin set.
 It can also be derived to use non-adjacent bins, but there is no
advantage to that.

If you think you have a slicker derivation than the way I did it, that
would be awesome.

I don't want to argue preferences, but I think the noiseless case is
interesting too, perhaps even more so.

[...snip...]

>
>My gut feeling (unsupported by exact math) is that the frequency
>error for the noisy case is going to be no lower than a value on the
>on the order of
>
>     1 / ( SNR * transform length )
>
>Where SNR is expressed as a power ratio (not in dB).
>
>My gut feeling (also unsupported by exact math) is that the best
>estimate will use all of the bins, but will weight them using
>some variant of maximal ratio combining so that the bins with
>the least energy do not contribute disproportionate noise to the result.

This conjecture flies in direct contradiction to the argument I made to
rbj in the Matlab thread concerning the DFT acting like a noise filter.

Let me try to disavow you of your notion using some supported approximate
math.  In the near integer case, the bin magnitudes drop off rapidly from
the peak bin.  In these cases the amount of signal information in the
further distant bins are insignificant.  They will quickly be swamped my
the noise level, so the SNR level will be so low that they can only bring
your average down, no matter what weighting scheme you use.

The case that might benefit the most for using more than three bins would
be when the frequency is half way between two bins.  Suppose that N is
large enough that we can consider the cosine values in the denominators in
my bin value formulas fairly linear and the numerators fairly steady. 
This means the bin magnitudes due to the signal on the set of bins just
outside the central twin peaks will be roughly one third of the two center
ones.  In terms of power, they will be roughly one ninth. There for the
SNR contributions from those bins will bring down whatever average is
calculated from the center two.  The next two set of bins will be roughly
one fifth in magnitude, and thus one twenty-fifth in power.  They can't
help bring up your average either.  And so on, the next set one seventh,
then odd numbers from there.  The highest SNR values are at the peak.

>
>This would be very straightforward for testing between two
>or a small number of hypotheses -- e.g. whether the phase and frequency 
>are [ f1, phi1 ] or [ f2, phi2 ].  It is probably provable that
>MRC gives the best possible result for this limited case.
>
>Steve

My empirical testing has shown that using a more than three bin version of
my formula, while still exact in the noiseless case, performs worse in the
presence of noise, confirming what I said above.

Ced

---------------------------------------
Posted through http://www.DSPRelated.com

Hi Cedron,

>1) How do you classify an algorithm that gives you "exact" results when
no
>noise is present and a good estimate when it is? 

Word wars...

>2) Are there other "estimators" that give exact results when no noise is
>present?

For real tones, I don't know yet. But for complex tones, the answer is
yes!
For example, this very simple one (Lank-Reed-Pollon) :
w = tan^{-1}(E[x_n x_{n-1}^star])



---------------------------------------
Posted through http://www.DSPRelated.com

>>2) Are there other "estimators" that give exact results when no noise
is
>>present?

After think twice about your question, I think we can have even more
minimal answer to your question:


1) Complex tone case: simply omega = tan^{-1}(x_1 * conj(x_0))
Difficult to do simpler. And it is an exact solution. And completly
useless and inefficient in practice too. I hope this can convince you of
the non revelence of this criterium of "exactness".

2) Real tone case: this is more complex (pun intended).
But a minimal answer could be found by writing 3 équations, but in the
time domain, instead of the frequency domain as your solution:
A*cos(phi) = x0
A*cos(2pi*f+phi) = x1
A*cos(4pi*f+phi) = x2

And solving this 3 unknown / 3 équations systems (although non linear) (I
let you do the solving, I am not brave enough),  will give you an
absolutely exact and absolutely inefficient solution too...

Fortunately, your formula is processing the 3 highest bins of the DFT,
this is why it is relatively efficient...

---------------------------------------
Posted through http://www.DSPRelated.com