NEW FREQUENCY ESTIMATION METHOD

Dear comp.dsp people and others:

I posted quite a few messages to this group before, but unfortunately,
as far as I can see, people are not very responsive to new ideas,
especially if those ideas lie outside the scope of their immediate
expertise.

So, I have to post the same message again and again:

FORGET ABOUT FFT AND OTHER CONVENTIONAL LINEAR METHODS 

and try to use more general non-linear techniques for tasks related to
period and fundamental frequency estimation.
These new non-linear techniques based on concepts of system state
space and time series embedding (originally proposed more than 20
years ago for analyzing non-linear and chaotic time series) are much
more general, robust and accurate than any of the conventional linear
methods you are talking about.

I don't want to write a lot here, but I can give a couple of comments
on the frequency estimation for periodic (and quasi-periodic) signals.

If your signal is a pure sine wave, then you just need 3 samples to
find the unknown parameters of the equation x = A*sin(w*t + f)
If your sine wave is noisy, then you'd better have more than 3 samples
in order to find the best fit to the above equation.

If your signal is periodic (or quasi-periodic), but has an unknown
harmonic structure (or, equivalently, its wave shape is arbitrary and
unknown), then you need more than one complete period in order to
determine the period (or its inverse �fundamental frequency) of a
signal.

With ideal periodic and noiseless signals, time-domain methods based
on detecting successive events (e.g. largest signals peaks or
zero-crossings) theoretically allow measuring the period with infinite
precision having a signal segment just slightly longer than T, where T
is the fundamental period you are measuring.
For real life signals, however, which are not perfectly periodic and
often noisy, pure time-domain methods are not robust at all.
Short-term methods, such as those based on computing correlation,
spectrum or cepstrum of a windowed portion of a signal are much more
robust than time-domain methods and are widely employed for period
(frequency) estimation tasks.
(Sometimes, correlation-based methods are wrongly classified as
time-domain methods, but this is just not correct: correlation is a
short�term analysis technique intimately related to spectral
techniques via Wiener-Khinchin theorem. There is also a lot of
misunderstanding about the uncertainty principle or time-frequency
resolution going on, but I do not want to discuss it here).

With those conventional short-term methods the windowed portion of a
signal under analysis must include at least 2 complete periods  (and
more than that in most cases) of a signal, in order to determine the
period with some degree of reliability and accuracy.

THE ONE AND THE ONLY short-term method, which can determine
fundamental frequency (period) of an arbitrary signal with a portion
of a signal just slightly longer than one complete period (for clean
signals, at least) is the new nonlinear method based on signal
embedding into a multi-dimensional state space followed by a nearest
neighbor search.
This new method was first publicly presented at ICASSP 2002.
It is intended to REPLACE ALL CONVENTIONAL LINEAR METHODS of period
(fundamental frequency) estimation for ALL signal-processing
applications requiring estimating a period (frequency) of a
(quasi)-periodic signal.
You can download the paper and the Matlab demo from 
http://www.soundmathtech.com/pitch

(The original purpose of this research was solving a "hardy perennial"
pitch determination problem of speech signal processing, but the
proposed techniques are very general in nature and can be applied to
many other tasks in all areas of signal processing).

Our US patent application (Pub. 20030088401 at
http://www.uspto.gov/patft) has
more detailed description of the new method.
Again, it is mostly geared towards speech processing applications
(with some exceptions) and the only restriction is NON-COMMERCIAL use.

I hope that the existence of a patent will not prevent the widespread
use of the new methods: it is only intended to protect our rights in
certain commercial fields
(e.g. speech coding for wireless telecom).
I can answer questions related to commercial use of the new methods
via e-mail.
Otherwise, it is free for anybody to use.

Best Regards,

Dmitry E. Terez, Ph. D.

SoundMath Technologies, LLC
P.O. Box 846
Cherry Hill, New Jersey, 08003
USA

e-mail: terez@soundmathtech.com

Dmitry Terez wrote:


> Dear comp.dsp people and others:
> 
> I posted quite a few messages to this group before, but unfortunately,
> as far as I can see, people are not very responsive to new ideas,
> especially if those ideas lie outside the scope of their immediate
> expertise.
> 
> So, I have to post the same message again and again:
> 
> FORGET ABOUT FFT AND OTHER CONVENTIONAL LINEAR METHODS 

   ...

That sounds very interesting, and I'll look into it. It seems to bear
directly on a conversation that I'm carrying on right now with Randy
Yates about the tradeoffs between measurement interval and precision in
the presence of noise, and efficient ways to get answers quickly.

Ignoring new and better methods is not a new phenomenon. See, for
example, http://users.rcn.com/jyavins/servo.html for another such lapse.

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

Jerry Avins <jya@ieee.org> wrote...
> That sounds very interesting, and I'll look into it. It seems to bear
> directly on a conversation that I'm carrying on right now with Randy
> Yates about the tradeoffs between measurement interval and precision in
> the presence of noise, and efficient ways to get answers quickly.

Perhaps also relevant is my recently released Harminv software:

   http://ab-initio.mit.edu/harminv/

This uses a type of algorithm originally developed for quantum NMR
studies and the like, called a Filter Diagonalization Method (FDM),
which maps the problem of identifying frequencies onto a small
eigenproblem, instead of resorting to e.g. a fitting approach which
may have unreliable convergence.

Harminv solves a slightly different problem than the OP of this
thread, in that it only deals with identifying sinusoidal oscillating
modes.  On the other hand, it can solve for many modes at once (NMR
experiments can have hundreds) and can also find decay rates of
exponentially decaying sinusoids.

Like the OP, however, it is not limited by the uncertainty principle
of the Fourier transform because it assumes a particular form of the
signal (which, hopefully, you know is valid on physical grounds).

Hope this is helpful!

Cordially,
Steven G. Johnson

dt@soundmathtech.com (Dmitry Terez) wrote in message news:<63322c10.0405181225.21428845@posting.google.com>...

hello Dmitry (or Dr. Terez, however you like it),

i wish you and your company the best, and

> I posted quite a few messages to this group before, but unfortunately,
> as far as I can see, people are not very responsive to new ideas,

i *did* respond to your first annoucement in 2002

http://www.google.com/groups?threadm=B91BD60F.4BFE%25robert%40wavemechanics.com

and i imagine that this response was not welcome as it was not replied
to at first by you.  on a later thread i asked the same questions and
*did* get a reply

http://www.google.com/groups?threadm=BA952312.A942%25rbj%40surfglobal.net

but i had not been very satisfied with your defense of this method. 
particularly how it is, as published in you ICASSP paper, much
different than a form of Average Magnitude Difference Function (AMDF)
or Average Squared Difference Function (ASDF) with a step
non-linearity applied between the differencing and the summation. 
(and there seemed to be a really insufficient terms in that summation
to boot.  if i recall, only 3 terms.)   i made some pretty specific
points that in the first thread that i didn't really see addressed.

> especially if those ideas lie outside the scope of their immediate
> expertise.

pitch detection algorithms, particularly for musical application
(which includes sung vocals) are not at all outside the scope of my
immediate expertise.  i am not as much a "speech processing" guy, but
i'm pretty much into PDAs and have some commercial output.  i mention
briefly a pretty typical and robust method of ASDF in a 1996 AES
convention paper.

http://www.harmony-central.com/Synth/Articles/Wavetable_101/Wavetable-101.pdf

but i haven't published much in it since PDA tricks and techniques are
often tightly held little commercial secrets particularly regarding
the nearly intractable "octave problem" since that really is a
conflict between mathematical and perceptual imperitives.

> So, I have to post the same message again and again:

believe me, you haven't been ignored, but perhaps you have a tough
sell with this group.

> FORGET ABOUT FFT AND OTHER CONVENTIONAL LINEAR METHODS 
> 
> and try to use more general non-linear techniques for tasks related to
> period and fundamental frequency estimation.
> These new non-linear techniques based on concepts of system state
> space and time series embedding (originally proposed more than 20
> years ago for analyzing non-linear and chaotic time series) are much
> more general, robust and accurate than any of the conventional linear
> methods you are talking about.
> 
> I don't want to write a lot here, but I can give a couple of comments
> on the frequency estimation for periodic (and quasi-periodic) signals.
> 
> If your signal is a pure sine wave, then you just need 3 samples to
> find the unknown parameters of the equation x = A*sin(w*t + f)
> If your sine wave is noisy, then you'd better have more than 3 samples
> in order to find the best fit to the above equation.

of course.  AMDF or ASDF or autocorrellation uses many more than 3.

> If your signal is periodic (or quasi-periodic), but has an unknown
> harmonic structure (or, equivalently, its wave shape is arbitrary and
> unknown), then you need more than one complete period in order to
> determine the period (or its inverse ?fundamental frequency) of a
> signal.

of course.  otherwise a counter-example could always be thrown at a
method that purports to detect the period in less than one complete
period.  logically, you need TWO complete periods before you can
really be sure.

> With ideal periodic and noiseless signals, time-domain methods based
> on detecting successive events (e.g. largest signals peaks or
> zero-crossings) theoretically allow measuring the period with infinite
> precision having a signal segment just slightly longer than T, where T
> is the fundamental period you are measuring.
> For real life signals, however, which are not perfectly periodic and
> often noisy, pure time-domain methods are not robust at all.
> Short-term methods, such as those based on computing correlation,
> spectrum or cepstrum of a windowed portion of a signal are much more
> robust than time-domain methods and are widely employed for period
> (frequency) estimation tasks.
> (Sometimes, correlation-based methods are wrongly classified as
> time-domain methods, but this is just not correct: correlation is a
> short?term analysis technique intimately related to spectral
> techniques via Wiener-Khinchin theorem. There is also a lot of
> misunderstanding about the uncertainty principle or time-frequency
> resolution going on, but I do not want to discuss it here).
> 
> With those conventional short-term methods the windowed portion of a
> signal under analysis must include at least 2 complete periods  (and
> more than that in most cases) of a signal, in order to determine the
> period with some degree of reliability and accuracy.
> 
> THE ONE AND THE ONLY short-term method, which can determine
> fundamental frequency (period) of an arbitrary signal with a portion
> of a signal just slightly longer than one complete period (for clean
> signals, at least) is the new nonlinear method based on signal
> embedding into a multi-dimensional state space followed by a nearest
> neighbor search.
> This new method was first publicly presented at ICASSP 2002.
> It is intended to REPLACE ALL CONVENTIONAL LINEAR METHODS of period
> (fundamental frequency) estimation for ALL signal-processing
> applications requiring estimating a period (frequency) of a
> (quasi)-periodic signal.

that claim is pretty bold and, as i read your paper, not well
justified.

> You can download the paper and the Matlab demo from 
> http://www.soundmathtech.com/pitch

i'll download the code.  i hope it can run on an old version of Matlab
(5.3.something for the Mac).

r b-j

On 18 May 2004 13:25:38 -0700, dt@soundmathtech.com (Dmitry Terez)
wrote:

>Dear comp.dsp people and others:

Hello Dr. Terez,

>I posted quite a few messages to this group before, but unfortunately,
>as far as I can see, people are not very responsive to new ideas,
>especially if those ideas lie outside the scope of their immediate
>expertise.

That's not true.  Most of us are *very* 
interested in new DSP techniques if 
they turn out to be useful (practical)
in some way.


  (All the good words about Dr. Terez's method snipped)


I'd sure like to understand your technique 
but, sadly, I haven't learned "state space"
theory.

Your paper looks like a fine academic paper, 
with it's overwhelming technical language, and 
highly theoretical concepts.
I imagine it impressed your academic colleagues.
The problem is that the paper is written 
in a language that, I think, the average 
DSP engineer cannot understand. 

For example, your paper discusses something 
called an "embedding procedure", but as far 
as I can tell that procedure is not defined 
in your paper.

Your paper used *so* much terminology with 
which I'm unfamiliar.  I'll take the blame for that.
What would be nice is if you could explain your 
method in a way that working DSP engineers, without 
Ph.Ds, could understand.  Is such an explanation 
possible?

(Of course, there are many far-above-average 
engineers in this Newsgroup, far smarter than me, 
who *will* be able to understand your paper is 
it is now written.)

Is it possible to describe *exactly* what arithmetic 
operations you perform on some time-domain samples 
to estimate some signal's periodicity?  Is it possible 
to explain your method in a way that would enable 
someone write their own MATLAB code to implement 
your process?

If it is, if you're able to explain your method 
for detecting periodicity in simple language, with 
some time-domain equations, and understandable examples, 
I'd sure like to consider that explanation as a 
possible article in my "DSP Tips & Tricks" column 
in the IEEE Signal Processing magazine.

Dr. Terez, if your periodicity estimation method is as 
effective as you say, and if you're able to describe the 
method in a way allowing the average working DSP engineer 
to implement it, I think that would be a very meaningful 
contribution to the DSP literature of spectrum analysis.

Regards,
[-Rick-]

r.lyons@_BOGUS_ieee.org (Rick Lyons) writes:
> [...]
> Your paper used *so* much terminology with 
> which I'm unfamiliar.  I'll take the blame for that.
> What would be nice is if you could explain your 
> method in a way that working DSP engineers, without 
> Ph.Ds, could understand.  

I second that. I would also assert that even other Ph.Ds
may not understand the lingo of an adjacent field, so you
will probably do your cause much good to make it more
"accessible" (as r b-j would say!).
-- 
Randy Yates
Sony Ericsson Mobile Communications
Research Triangle Park, NC, USA
randy.yates@sonyericsson.com, 919-472-1124

On 2004-05-20, Rick Lyons <r.lyons@_BOGUS_ieee.org> wrote:
> What would be nice is if you could explain your 
> method in a way that working DSP engineers, without 
> Ph.Ds, could understand.  Is such an explanation 
> possible?

...

> Is it possible to describe *exactly* what arithmetic 
> operations you perform on some time-domain samples 
> to estimate some signal's periodicity?  Is it possible 
> to explain your method in a way that would enable 
> someone write their own MATLAB code to implement 
> your process?

My crude impression of it is this:

Make vectors out of the input signal delayed by equal intervals:
for N = 0 to framesize
 p(N) = <x[N],x[N-M],x[N-2M],x[N-3M]>

Find the distances between every pair of vectors(!):
for a=0 to framesize
  for b=0 to a
    Dist(a,b) = pythagorean distance(p(a),p(b))

Make a histogram of the distances:
H=hist(Dist);

Weight the larger distances of the histogram

Find peaks



-- 
        different MP3 every day!     http://gweep.net/~shifty/snackmaster
     .        .       .      .     .    .   .  . ... .  .   .    .     .      .
"Maybe if you ever picked up a goddamn keyboard   |     Niente 
 and compiler, you'd know yourself." -Matthew 7:1 | shifty@gweep.net

Randy Yates <randy.yates@sonyericsson.com> wrote in message news:<xxphdubgnq1.fsf@usrts005.corpusers.net>...
> r.lyons@_BOGUS_ieee.org (Rick Lyons) writes:
> > [...]
> > Your paper used *so* much terminology with 
> > which I'm unfamiliar.  I'll take the blame for that.
> > What would be nice is if you could explain your 
> > method in a way that working DSP engineers, without 
> > Ph.Ds, could understand.  
> 
> I second that. I would also assert that even other Ph.Ds
> may not understand the lingo of an adjacent field, so you
> will probably do your cause much good to make it more
> "accessible" (as r b-j would say!).

i am not sure how much good it would do his cause if his cause is to
sell the PDA (which i think he is trying to do).  the more transparent
the language, the more evident that his PDA really *is* a twist on
AMDF or ASDF or autocorrelation.  (there is a step nonlinearity in
between the differencing and the summation, but stuff like that has
been tried before, sometimes with good results for speech, but as i
told him, you toss in a non-invertable nonlinearity and i can concoct
a waveform that will fool the PDA.)

now if his cause is the more truly academically altruistic "search for
truth" and "discovery of knowledge", then making it transparent can
only help.

it's still reasonably accessable for the descibed case or time-delay. 
if he wants to define how he does it with SVD (i think i know what
that stands for), that would be welcome.

r b-j

Tachyon <shifty@sidehack.sat.gweep.net> wrote in message news:<slrncaphhr.1f4s.shifty@sidehack.sat.gweep.net>...
> On 2004-05-20, Rick Lyons <r.lyons@_BOGUS_ieee.org> wrote:
> > What would be nice is if you could explain your 
> > method in a way that working DSP engineers, without 
> > Ph.Ds, could understand.  Is such an explanation 
> > possible?
> 
> ...
> 
> > Is it possible to describe *exactly* what arithmetic 
> > operations you perform on some time-domain samples 
> > to estimate some signal's periodicity?  Is it possible 
> > to explain your method in a way that would enable 
> > someone write their own MATLAB code to implement 
> > your process?
> 
> My crude impression of it is this:
> 
> Make vectors out of the input signal delayed by equal intervals:
> for N = 0 to framesize
>  p(N) = <x[N],x[N-M],x[N-2M],x[N-3M]>
> 
> Find the distances between every pair of vectors(!):
> for a=0 to framesize
>   for b=0 to a
>     Dist(a,b) = pythagorean distance(p(a),p(b))
> 
> Make a histogram of the distances:
> H=hist(Dist);
> 
> Weight the larger distances of the histogram
> 
> Find peaks

Given that this synopsis is correct, how would this "new" frequency 
estimator be different from MUSIC, dating from 1977 or so?

For the record: I do have a PhD degree, and frequency estimation was 
a substantial part of the work I did. As a matter of fact, the "one and
only" method I actually got to work with noisy, non-perfect data 
dated back to 1795. Yep, that's right. The time of the French Revolution. 
Actually, it was a Baron who published the work (Gaspard Riche, Baron de 
Prony). One would magine this guy had other matters than frequency 
estimation on his mind at the time...

BTW: Whatever sarcatic tone might be detected here would best be directed 
at the OP, not at Tachyon.

Rune

Dear all,

I remember also this thread, been just a bystander here.
My post goes off-topic from periodicity detection
algorithms in general since it's not my expertise. 
But I want to continue a little about the important point brought out
by R B-J :

: now if his cause is the more truly academically altruistic "search for
: truth" and "discovery of knowledge", then making it transparent can
: only help.

This is so TRUE! I am myself an academic person, doing nothing "practical"
;-) such as DSP engineering. There is always the gap between the
theory and practise, and in my own definition, a "guru" ("pioneer", 
"the God of subject X") is a person, who fulfills the following two 
requirements:

	i)  (s)he knows what he is doing, and keeps searching for
	    the truth,
__AND__
	ii) He is able to tell other persons not so familiar
	    with this specific field, HOW to make his "optimal,
	    all-problems-solving, TheBest" method work/implement in 
	    practise.

In my own humble opinion, one has to be able to explain what is the idea
of your method to your own grandmother who has never gone to math, stat, 
DSP, or pattern recognition course. This may take some time and
patience ;-), but if you are not able to do it, the only conclusion 
is that you really don't understand what you are doing !

So, dear Dr. Terez, if your algorithm really solves the periodicity 
detection problem always optimally, you need to convince others as
well. If your algorithm is indeed essentially different from the 
well-known AMDF method as pointed out here already several times, you
need to first give a convincing reply to the questions pointed to 
you (now, for the second or third time already). Because if you
don't reply but just keep repeating your old words, 
at least that makes me an impression you have
something to hide -- maybe your algorithm isn't that good
after all! Maybe you indeed are trying just to sell your product.
This is the way acedemic discussion goes, period.

Sincerily yours,

Tomi Kinnunen