Question about DSP in Matlab (beginner)

Hi Kevin,

Awesome post, I'm going to reply before I call it a night.

>
>Cedron, you've posted a link to a 3 equation/3 unknown problem, for
>which you claim to have found a solution.  Well, I can't verify the
'newness'
>of it because I'm unwilling to plow through the mountain of books and
papers
>that deal with the subject.  But I don't doubt that it may very well be
a
>solved problem.

It is so fundamental, and not very difficult to solve, that it sure ought
to have been done by now.  I've plowed through a lot of web searches
looking for it, and have yet to find it.  I claim in the introduction that
current teaching considers it impossible and no one has challenged that
claim.  Eric Johnson, who I consider a foremost expert on the current
consensus, just confirmed the belief that exact results can not be
ascertained from a DFT in the last posting.

He also thinks that I should plow through a whole bunch of papers to not
find the bin value formulas I use in the 3 equation/3 unknown problem
after he claimed a cleaner version of them existed.

>
>You also state in the link that: "It turns out that the frequency
>solution is robust in the presence of noise and other signals ... ."  I
have a
>great deal of difficulty believing this one, perhaps because I have seen
too
>others make the same claim.  In the limit of low SNR, it is never true. 
>Every signal processing algorithm will fail in the presence of too much
>noise.
>

I do have empirical results, but no formal analysis.  I have tested them
under some rather heavy noise and they do quite well.


>And therein lies the problem: other authors at least give you some
>minimum SNR for which their technique will work, or some error analysis,
or
>computational results, etc.  For example, here are some links for the
Gaussian
>estimation technique used at CERN:
>
>http://mgasior.web.cern.ch/mgasior/pap/FFT_resol_note.pdf  (17 pages)
>
>http://cds.cern.ch/record/738182/files/ab-2004-023.pdf  (9 pages) 
>
>And Malek Gasior's doctoral and M. Sc. theses are available at:
>
>http://mgasior.web.cern.ch/mgasior/pap/
>
>He also has a book: Improving Frequency Resolution of Discrete Spectra -
>Algorithms of Three-Node Interpolation.
>

Thanks, I will look at these links.

>Now take a look at the first paper listed above.  There is a lot of
>detail about the performance of the method in the presence of noise
(see,
>specifically, their measurements in Figs. 18 and 19, and their error
>calculations in the paper).
>
>You, in contrast, have provided  ... well ... nothing.  So perhaps you
>shouldn't be surprised if some readers question the utility of your
method.

If you look back a little bit on this thread to my last long response to
rbj, I admit my expertise in standard noise testing is quite lacking.  I
also give the first few steps of a mathematical analysis, with an
explanation of why other tones, and a large part of the noise, is knocked
down.

The other statement I have made on the subject is that Eric Jacobsen's
frequency estimator is an approximation of my exact equation, so the
reaction to noise should be about the same.  I've actually confirmed this
empirically.

>
>As for some of your other statements, such as the 'uncertainty
>principle' in relation to DSP, which I see a lot of on stackexchange, ...
well,
>you'd be preaching to the choir as far as I'm concerned. It makes sense
in
>subatomic physics, but DSP???

Amen.

>
>As for leakage, I'm not going to worry about the appropriateness of the
>word (unless talking to someone who wears Depends, or someone whose
faucet
>is giving them trouble), but I understand it from having read the
following
>many, many years ago:
>
>R. J. Webster, "Leakage Regulation in the Discrete Fourier Transform
>Spectrum," Proc.
>IEEE, vol. 68, no. 10, Oct. 1980, pp. 1339-1341.
>
>I even wrote a post that included two excerpts from the above at
>stackexchange:
>
>http://dsp.stackexchange.com/questions/15015/a-question-about-spectral-leakage
>
This link I followed.  Your excerpts, and the rest of that post for that
matter, (and rbj's point of view) is the DFT is a dirac delta windowing of
the continuous case.  My analysis is more a linear algebra, discrete from
the get go, no dependence on the continuous case conceptually point of
view.  How you see things sometimes depends on where you stand.  I was a
Calculus TA in college so the continuous case doesn't scare me, but I
think it does obfuscate some simple concepts in the discrete case when
they are explained in terms of concepts derived from the continuous case.

>As for other statements .. I'm not going to bother.  Too many other
>things to do.  Your method lives or dies based on the clarity (or lack
thereof)
>of your presentation, and any usefulness it can find in the real world.
>
>Kevin McGee

Thanks for the bothering you did do.  My intention with the blogs is to
give an introductory explanation to the properties of the DFT from a fresh
and different perspective than what I see the current one to be.  They are
meant to be instructional and explanatory and I've tried really hard to
make them so.  The target audience is really rookies who are unencumbered
by already having a certain way of looking at it.

Thanks for the advice.  Keep watching my space, I'm heading towards what
you asked for.

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

On 5/26/15 12:37 PM, Cedron wrote:

...
> Unless the three bin set covers the DC bin, a DC offset will have no
> effect.  Other tones will, but I will deal with that when I get to the
> multiple tone case.

so DC is different from an "other tone"?  DC will have leakage two.

>> 3 equations, 3 unknowns.  you could also do it in the time domain
>> (unless your 3 points are poorly selected).  again, no noise nor
>> interference is allowed.
>
> The advantage of doing it in the frequency space, the DFT bins, is that
> the noise will be spread out over all the bins and thus only the noise
> that impacts the three bins will have any effect.  So the DFT is acting as
> a noise filter.

you can make the same case with 3 time-domain samples.  the "noise" is 
spread out over all of the samples and only the noise that impacts the 
three samples selected will have any effect.

estimating frequency from only 3 bins or from only 3 samples is not 
always the best idea.

-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

>On 5/26/15 12:37 PM, Cedron wrote:
>
>...
>> Unless the three bin set covers the DC bin, a DC offset will have no
>> effect.  Other tones will, but I will deal with that when I get to the
>> multiple tone case.
>
>so DC is different from an "other tone"?  DC will have leakage two.
>
No it won't.

Let's consider DC a tone with a frequency of zero, so it fits "other
tone".  Like other integer frequency tones, it will not have leakage. or
if you prefer to look at it as the sidelobes will be zero.  It is
different than other integer frequency tones in that its bin magnitude is
its amplitude, not half the amplitude.  It is also different in that the
phase parameter is essentially meaningless.

>>> 3 equations, 3 unknowns.  you could also do it in the time domain
>>> (unless your 3 points are poorly selected).  again, no noise nor
>>> interference is allowed.
>>
>> The advantage of doing it in the frequency space, the DFT bins, is
that
>> the noise will be spread out over all the bins and thus only the noise
>> that impacts the three bins will have any effect.  So the DFT is
acting
>as
>> a noise filter.
>
>you can make the same case with 3 time-domain samples.  the "noise" is 
>spread out over all of the samples and only the noise that impacts the 
>three samples selected will have any effect.

I guess I kind of explained that poorly.  You can only do it in the time
domain if the signal is a single pure tone.  Any harmonics are technically
other tones.

I need to explain the noise filter better.  Suppose I have two dice and
roll them.  The expected outcome of their sum is 7, and there is a
variance measure.  I can consider there sum a biased random number.  If I
subtract 7, it becomes unbiased, the variance stays the same.

If I roll the dice 10 times and take the average sum, the expected value
is still 7, but the variance is much smaller.  If I roll it 1000 times,
the expected average value is still 7, but the variance is much much
smaller.

The more times I roll, the smaller the variance becomes, meaning the more
exceptional it is that I would get a result very far from 7.  The
probability distribution approaches a narrower and narrower bell curve.

So, if your noise is unbiased, the expected value is zero.  When you take
three points in the time domain, it is like rolling the dice three times. 
When you use three bins from the DFT, it is sort of like rolling the dice
N times for each bin.  I say "sort of" because you aren't doing a straight
average, you are doing a weighted average based on the sine and cosine
functions of the bin frequency.

This is why I made the point to the OP, way earlier in this thread, that
one of the reasons you might want use more sample points and a larger DFT
is for noise mitigation.

>
>estimating frequency from only 3 bins or from only 3 samples is not 
>always the best idea.
>
The frequency formula, expressed as 

cos( alpha ) = WBZ / WZ

can be arbitrarily extended to as many bins as you want with the proper
selection of W.  Each bin you add gives you one more degree of freedom in
your selection.

For simple tones, I can see no reason to do this.  Instantaneous frequency
of a varying frequency signal is a whole 'nuther kettle of fish.  One I
haven't tackled yet.

>-- 
>
>r b-j                  rbj@audioimagination.com
>
>"Imagination is more important than knowledge."

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

On Wed, 27 May 2015 00:22:48 -0500, "Cedron" <103185@DSPRelated>
wrote:

>>eric.jacobsen@ieee.org (Eric Jacobsen) writes:
>>> [...]
>>
>>Eric,
>>
>>I think Cedron's problem is one of attitude, which is indeed
>>a serious problem. 
>>
>>> You might consider using your real name, but I doubt that will change
>>> anything, either.
>>
>>Hear, hear. I don't understand what folks who post using a pseudonym
>>have to hide.
>>-- 
>>Randy Yates
>>Digital Signal Labs
>>http://www.digitalsignallabs.com
>
>There is no need to go ad hominem.  Contrary to his assertion, I am not
>upset with EJ, nor angry.  I use a pen name for some very valid reasons,
>they have nothing to do with hiding anything, nor is it a good idea, or
>necessary, for me to disclose them.  EJ is correct that wouldn't change
>anything.  He says he enjoys these kind of exchanges and I believe him.  I
>do too.

You used to post here with a proper name.   What changed?

>We clearly have some definitional disagreements, and he has made some
>downright false mathematical assertions that I will address tomorrow.  Now
>it is late, and I am tired.
>
>My "arrogant" statement about understanding leakage, which I stand by and
>explain further in my response, pertains to the equations I developed in
>my blog article titled "DFT Bin Value Formulas for Pure Real Tones".
>
>EJ is incorrect in asserting that I am not willing to put any effort in
>searching the literature for the equivalent equations.  The truth is, I
>have spent a lot of time and done a lot of reading and have considerable
>familiarity with the subject matter.  I have yet to find the same
>equations or an approach similar to the one I take.
>
>After I posted the blog, I found the following blog article on dsprelated,
>which is the closest I have found yet.
>
>"The DFT Magnitude of a Real-valued Cosine Sequence"
>Rick Lyons June 17, 2014
>
>However, his emphasis is explaining the magnitude of an integer frequency
>bin so he takes an approximation along the way.  He avoided the gooblygook
>as rbj called it.
>
>Personally, I think the explanation I give in my second blog article
>titled "DFT Graphical Interpretation: Centroids of Weighted Roots of
>Unity" gives a much more intuitive (though less mathematical) explanation
>of the same thing, i.e. why is the 1/2 there.  YMMV.
>
>Oh, for the record, all the derivations I am presenting in my blog
>articles were done with pen and paper first.
>
>Ced
>---------------------------------------
>Posted through http://www.DSPRelated.com

Eric Jacobsen
Anchor Hill Communications
http://www.anchorhill.com

[...snip...]

>>They are actually the equivalent of the DFT of a pure tone, not the
>>window.
>
>The FT of the window fully describes the peak and the sidelobes.  The
>sidelobes are what are called "leakage".  

No it doesn't.  Just to be clear, you are talking about the sinc = sin( pi
x ) / ( pi x ) function, right?

"Sidelobes" are a better word than "leakage", but I still don't really
like it because it is from the continuous, not the discrete, definition of
the FT.  All the "lobey- ness" is lost in the translation.

Saying the sinc function describes the adjacent bin values to the peak bin
fully is like saying the bell curve describes binomial distributions
fully.  It may be descriptive, but far from being fully descriptive.

Except for bin N/4, the bin value magnitudes fall off asymmetrically, the
sinc funtion is symmetric.  It does not explain the phase value changes
either.

The bin value formulas are a full description because they are derived
directly from the source definitions.

>
>You had stated earlier:
>
>"If you truly understood leakage, you wouldn't call it leakage and you
>wouldn't prattle on about an "uncertainty principle" in the DFT.
>Unless you can derive the equations in my blog article titled "DFT Bin
>Value Formulas for Pure Real Tones" (at dsprelated dot com), you don't
>understand leakage mathematically.  Sorry, you don't."
>
>Since the FT of the window is pretty simple to understand, and fully
>describes "leakage", and there are other ways to get there, too, I
>disagreed with that statement.   I haven't seen anything to back up
>your statements.

See above.  Notice that I said being able to derive, not just being able
to apply them.  Being able to derive them means understanding the
definition of the DFT, how to model a pure tone signal, Euler's equation,
and an understanding that a finite geometric series is involved.  Most
importantly, it means understanding that the equations are indeterminate
for integer frequency tones at the matching frequency bin.  You would also
understand that there is no uncertainty in the calculation whatsoever. 
All these things are necessary to truly understand "leakage".  Are they
sufficient?  Arguable.

>
>>1) What is the advantage of doing an FFT when you can just do a DFT? 
>>Calculation efficiency.  Only here the savings are even greater.
>>
>>2) What does a mathematically concise equation get you?  How about the
>>ability to infer behavior.  See the "Qualitative Analysis" section if
you
>>are curious.
>>
>>3) What does having a better answer to "What is leakage?" mean?
>
>I don't think it's better.
>

You don't have to.  I've just explained some of the reasons I think it
is.


>>>
>>>>You claimed a "cleaner" version of these existed.  I don't know how
>>>they
>>>>could be cleaner so I asked you for a reference.  All you have
provided
>>>so
>>>>far is name-dropping.
>>>
>>Once again, I am being very clear in what I asked for.
>
>And I gave a clear answer.   You are simply unwilling to pursue it.

I've written a series of blog articles on the DFT, I've got more to come. 
In each one, I have derived equations and provided numerical examples to
demonstrate them.  Some source code is also provided.  I've done my best
to describe their characteristics and meaning.  I do not consider myself a
good writer, but the math should be able to stand on its own.

Now these equations are all pertinent to the DFT, I don't think you can
argue that they aren't.  With a nod to angrydude, they are kind of
obvious.

Either they are known in the literature, or they aren't.  If you know,
tell me.  The answer is either "Nope, never seen them before" or "you will
find them here".  Where "here" is specific.

Whether they are useful or not is an independent issue.  They could very
well be known and rejected for some reason, regardless, they would still
be in the literature.


>>>FT is an estimator, so developments based on the FT aren't, by nature,
>>>"exact".

The fact that I have derived and demonstrated an exact frequency formula
for a pure real tone is a counter example and therefore disproves this
assertion.

>
>How does invertability guarantee "exactness"?   

Exactness means no loss of accuracy or precision.  If there is any
accuracy or precision lost in the transform, the inverse transform cannot
recover it.

>The transform matrix
>could be random numbers and it'd still be invertable.   

Not necessarily.  A matrix has to be full rank to be invertible.

>Or just change
>a few numbers in the matrix so that it looks sorta-DFT-ish but the
>results are crap.   It'd still be invertable.   Is it "exact"?   No.

Yes (if it retains full rank).  "Exactness" has nothing to do with
utility.

>
>>>Estimators are called "estimators" specifically because they're not
>>>exact.   
>>
>>Phew, I thought we might be dealing with another one of those "the
words
>>don't mean what the ordinarily mean" situations.
>>

Typo alert: "the" should have been "they".

>
>The point is that real-world applications typically look like
>stochastic processes.   

Irrelevant to understanding the theory.

"So often in actual applications "exact"
>solutions, especially if they use a lot of transcendental functions
>like yours, can get noisy results.   Sometimes the approximate
>computations are much better because they avoid functions with steep
>transfer functions that amplify noise.   This is why the application
>space is important, and why things should be evaluated in context for
>use in an application.   This is usually accomodated in papers by
>showing results in expected impairments, etc., etc., to see which
>actually works best.   An "exact" derivation is often nice and useful,
>and can be academically interesting, but it is not always practical.
>

I've started every article with "This is an article to hopefully give a
better understanding of the Discrete Fourier Transform (DFT) by...." not
"Here is a superior method to current techniques...."

>>>Not to take anything away from what you've done, which I admit I
>>>haven't looked at in great detail, but it seems to me to be another in
>>>a long line of these things.   If it's exact, fine.   I don't know if
>>>that means that it's useful to anybody or not, because there've been
>>>others with "exact" solutions that didn't perform very well when it
>>>came down to it.   I haven't evaluated yours so I don't know where it
>>>fits, but there are certainly plenty of others to pick from.
>>

You haven't taken anything away.  I believe our discussion has prompted at
least a few people to go read my blog articles.

>In this case, there are already numerous estimators that operate very
>close to the Cramer-Rao bound across the range of interest in SNR.
>If another estimator comes along that has a lot more complexity, it's
>already a very difficult sell because even if it does approach the
>CRB, it's more complex than the existing estimators that already have
>that performance.   Without some sort of advantage it won't get much
>interest.  So, it may be hard to generate interest for purposes other
>than academic curiosity.   There may also be some cases where the
>impairments are such that the CRB isn't a good comparison metric, but
>those will be pretty nichy and need their own evaluation criteria.

I've brought the equations to the table.  I understand their performance
from a theoretical point of view and by testing them empirically.  I am
not the best person to do standard performance evaluation.  Anybody who is
so able is welcome to do so.

>
>For me, the complexity is so high, orders of magnitude higher than
>modern solutions, that there isn't much reason to spend a lot of time
>looking at it.   The "exact" derivation, even if it is such, may be of
>interest to some but probably not for most practicioners given the
>existing, far simpler, solutions that are already operating at close
>to CRB limits.

This may pertain to the phase and amplitude (Method 1) equations I posted,
but certainly not to the bin value equation or the frequency formula.

The frequency formula, particularly if you build a small lookup table,
takes fewer calculations than most, if not all of the estimators on the
web pages I referenced earlier.

>
>I know why you're still upset with me,  and I also know that there's
>nothing I can do to change that, nor would I change anything.  I'm
>fine with you being upset with me until the end of time, that's your
>choice.   I also know that it's unlikely that anything anybody says
>will change your notions about this topic.  You might consider using
>your real name, but I doubt that will change anything, either.
>

I'm not upset, just a bit disappointed.  All I am looking for is
confirmation of the novelty of my equations, not an education in
contemporary methodology.

I am using a pen name on purpose.  No it wouldn't change anything if I
didn't.  I'm not being a flame throwing troll.

>
>Eric Jacobsen
>Anchor Hill Communications
>http://www.anchorhill.com

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

>>There is no need to go ad hominem.  Contrary to his assertion, I am not
>>upset with EJ, nor angry.  I use a pen name for some very valid
reasons,
>>they have nothing to do with hiding anything, nor is it a good idea, or
>>necessary, for me to disclose them.  EJ is correct that wouldn't change
>>anything.  He says he enjoys these kind of exchanges and I believe him. 
I
>>do too.
>
>You used to post here with a proper name.   What changed?
>

A long long time ago, maybe a few times.  I posted more in alt.lang.asm,
but that wasn't much either and also a long long time ago.

"valid reasons" unrelated to DSP.

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

>On Wed, 27 May 2015 00:22:48 -0500, "Cedron" <103185@DSPRelated>
>wrote:
>
>>>eric.jacobsen@ieee.org (Eric Jacobsen) writes:
>>>> [...]
>>>
>>>Eric,
>>>
>>>I think Cedron's problem is one of attitude, which is indeed
>>>a serious problem. 
>>>
>>>> You might consider using your real name, but I doubt that will
change
>>>> anything, either.
>>>
>>>Hear, hear. I don't understand what folks who post using a pseudonym
>>>have to hide.
>>>-- 
>>>Randy Yates
>>>Digital Signal Labs
>>>http://www.digitalsignallabs.com
>>
>>There is no need to go ad hominem.  Contrary to his assertion, I am not
>>upset with EJ, nor angry.  I use a pen name for some very valid
reasons,
>>they have nothing to do with hiding anything, nor is it a good idea, or
>>necessary, for me to disclose them.  EJ is correct that wouldn't change
>>anything.  He says he enjoys these kind of exchanges and I believe him. 
I
>>do too.
>
>You used to post here with a proper name.   What changed?
>

I hope "Cedron" is not that nice guy "Vlad" back from the dead.

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

>
>I hope "Cedron" is not that nice guy "Vlad" back from the dead.
>
>Kaz
>---------------------------------------
>Posted through http://www.DSPRelated.com

Your hope is fulfilled.  Have I even once said "If you want my opinion you
have to pay for it"?

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

On 5/27/15 10:03 AM, Cedron wrote:
>> On 5/26/15 12:37 PM, Cedron wrote:
>>
>> ...
>>> Unless the three bin set covers the DC bin, a DC offset will have no
>>> effect.  Other tones will, but I will deal with that when I get to the
>>> multiple tone case.
>>
>> so DC is different from an "other tone"?  DC will have leakage two.
>>
> No it won't.
>

sorry dude.  you're gone.


-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

Dear Cedron,

If I understand well you blog post "Exact Frequency Formula for a Pure
Real Tone in a DFT", you are dealing with the overdetermined problem of
estimating the frequency from a real sinuosidal tone: 3 unknows
(frequency, phase and amplitude), and n knowns (for n signal samples). 

First, I think it not quite right to speak about an **exact solution** for
such a problem (except of course if you have only 3 samples at hand, or no
noise at all).

Second, considering the, umm, naivety, of your method (using only 3 bins
of a non-windowed DFT), and your claim, I quote, "this article should be
considered a watershed event in the discipline" (or maybe this is
self-derision?), I wonder if, before posting your blog notes, you have
ever tried to get ackwoledged of the classical methods used to solve this
problem?

For example, did you have a look to the classical gaussian window +
quadratic interpolation method
(https://ccrma.stanford.edu/~jos/sasp/Quadratic_Interpolation_Spectral_Peaks.html)?
I have not done any test myself, but just be intuition we can guess that
this method is much more accurate than yours: It uses a gaussian window in
the time domain, so in the frequency domain the lobe width is much reduced
than in your case, and then it does a quadratic interpolation with 3
points in the dB scale, which is also an exact solution (because DFT of
gaussian is also a gaussian, and then after log, it becomes just a
quadratic), and in the end there is much more signal energy in their 3 DFT
bins (thanks to their windowing) than in your 3, unwindowed, DFT bins.
Anyway, look at the link, it's better explained.

Regards,

Julien

PS: I am not a specialist in this domain, there seems to be a lot of other
methods to do that, and maybe there even better methods, or different
methods for different applications, I just cited you an example.

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