Hi Group I'm sorry about posting all my formulas without any delay. I just wanted to get them out there while they are new, so that other people can use them if they want. Michael Plet
Sorry about the many posts
Started by ●March 1, 2017
Reply by ●March 1, 20172017-03-01
>Hi Group > >I'm sorry about posting all my formulas without any delay. >I just wanted to get them out there while they are new, so that other >people can use them if they want. > >Michael PletMichael, You shouldn't apologize for what you have posted. Despite of what was said by a local "Usenet Bully" on your other thread, your formulas are very much on-topic for this forum. Also, you have labelled them clearly so if someone is not interested in this corner of DSP they can readily skip them. As far as I know you are the third person to develop exact frequency formulas for a single tone in a DFT behind myself and Martin Vicanek. I am still waiting for Jacobsen to post the closed form formulas he claimed he had that have been developed since Julien's comparison report. If they turn out to be exact, you may not be third. I'm glad my code worked for you and I appreciate that you mentioned my blog article. I also want to remind you that Julien also provides testing code along side of his paper which you can find here: http://www.tsdconseil.fr/log/scriptscilab/festim/index-en.html Ced --------------------------------------- Posted through http://www.DSPRelated.com
Reply by ●March 1, 20172017-03-01
On Wed, 01 Mar 2017 10:57:36 +0100, Michael Plet <me@home.com> wrote:>Hi Group > >I'm sorry about posting all my formulas without any delay. >I just wanted to get them out there while they are new, so that other >people can use them if they want. > >Michael PletCan I ask what your interest is in pursuing this? Is it academic interest or something else? Are you open to criticism on these? Feel free to contact me privately if you prefer. I was going to email you directly, but I suspect that me@home.com isn't actually your address. --- This email has been checked for viruses by Avast antivirus software. https://www.avast.com/antivirus
Reply by ●March 1, 20172017-03-01
On Wed, 01 Mar 2017 20:31:16 GMT, eric.jacobsen@ieee.org wrote:>On Wed, 01 Mar 2017 10:57:36 +0100, Michael Plet <me@home.com> wrote: > >>Hi Group >> >>I'm sorry about posting all my formulas without any delay. >>I just wanted to get them out there while they are new, so that other >>people can use them if they want. >> >>Michael Plet > >Can I ask what your interest is in pursuing this? Is it academic >interest or something else? Are you open to criticism on these? > >Feel free to contact me privately if you prefer. I was going to >email you directly, but I suspect that me@home.com isn't actually your >address. > > > >--- >This email has been checked for viruses by Avast antivirus software. >https://www.avast.com/antivirusI have a background in Computer Science and Mathematics. The reason I got interested in DSP is because of my love of music. I want to and have already used DSP to analyse music. For that reason I derived my first formula. Because I also like mathematical puzzles I enjoyed deriving more formulas. I realise that a single formula is not enough to analyse a piece of music with many events in both frequency and time. I am very much open to criticism. Michael
Reply by ●March 1, 20172017-03-01
On Wed, 01 Mar 2017 21:55:33 +0100, Michael Plet <me@home.com> wrote:>On Wed, 01 Mar 2017 20:31:16 GMT, eric.jacobsen@ieee.org wrote: > >>On Wed, 01 Mar 2017 10:57:36 +0100, Michael Plet <me@home.com> wrote: >> >>>Hi Group >>> >>>I'm sorry about posting all my formulas without any delay. >>>I just wanted to get them out there while they are new, so that other >>>people can use them if they want. >>> >>>Michael Plet >> >>Can I ask what your interest is in pursuing this? Is it academic >>interest or something else? Are you open to criticism on these? >> >>Feel free to contact me privately if you prefer. I was going to >>email you directly, but I suspect that me@home.com isn't actually your >>address. >> >> >> >>--- >>This email has been checked for viruses by Avast antivirus software. >>https://www.avast.com/antivirus > > >I have a background in Computer Science and Mathematics. >The reason I got interested in DSP is because of my love of music. >I want to and have already used DSP to analyse music. > >For that reason I derived my first formula. >Because I also like mathematical puzzles I enjoyed deriving more >formulas. > >I realise that a single formula is not enough to analyse a piece of >music with many events in both frequency and time. >I am very much open to criticism. > >MichaelThis sort of frequency interpolation has been around for a long time (many decades), with a lot of work having been done for subtle optimizations for various different applications. I've been involved directly in the context of signal processing for communication systems on this particular topic since the mid-1990s. The matlab/octave test suite I linked earlier was done during that early research, but I have a more developed test suite now that allows fairly quick testing and analysis of different methods. I plugged yours in over the last couple of days to see how it compared to other estimators. As I mentioned early on, the two-term estimators like you initially proposed generally suffer frequency-dependent errors, and it appears that yours is not an exception. You indicated in the results you posted that you used a phase of ~0.785 (radians, presumably), and at that particular phase the errors are masked. When I tried it there are substantial frequency-dependent errors at other phases, and the usual one that happens with two-term estimators is at zero frequency offset and zero phase, which also seems to be a problem with your two-term estimator. Yours also seems to have difficulty at pi radians and a few other phases. Randomizing the signal phase across trials helps to show whether the estimator is robust in these conditions. Even when the phase is favorable, though, the perforrmance is not favorably comparable to other estimators with much lower computational complexity. This is fairly typical, though, and I think may be part of why two-term estimators aren't very popular or at least don't get much attention. The last estimator you posted, using three terms, is not bad but is not as good as the usual estimators used as references (Candan's, Liao's, etc.), and is MUCH MUCH more computationally intensive. For that reason there isn't much motivation to use yours when there are better-performing estimators with much less computational complexity. I suspect that perhaps the large number of computations in yours, including transcendental functions, just adds a lot of accumulated quantization noise. Here are some results, with no added noise, which is the more interesting case for the bias-corrected estimators: http://ericjacobsen.org/Files/p5fintrpsims.jpg Your three-term estimator is the solid green trace. There are a number of other estimators in the same trials, including my old, simple one (black circles), my estimator with Candan's simple bias correction (blu x), Candan's complete estimator (magenta dots), Liao and Lo's correction to the QMJ estimator (red circles), and Lonnemo's estimator (black +). The bias-corrected or low-bias estimators are nearly indistinguishable at this level. Fig 1 is just the estimated frequency vs the test number, with test #1 being no frequency offset and then incrementing 1/10th of a bin offset with each test (so that test #6 is halfway between bins). The vertical axis is bin number. This just shows that the estimators are generally working. Fig 2. is the statistical variance of each estimator vs offset. Each offset has 5000 trials with random phase at each trial. Fig 3 is the statistical bias of each estimator vs offset. . FWIW, at this time the usual reference estimator for performance at high SNR is Candan's, because it matches the best performance with anything else out there and has the least relative computational complexity. For reference, Candan's estimator is computed as follows: First, compute delta using Jacobsen's (my) estimator, where y is the three-element complex-valued vector of the peak magnitude sample and the two adjacent samples. delta is then the interbin fractional error of the initial fequency estimate using only the peak bin. delta=real((y(1)-y(3))/((2*y(2))-y(1)-y(3))); Candan's estimator is then: freq=pkind+(atan((pi/tstlen)*c*delta))/(pi/tstlen); Where the resulting estimated frequency is in bins, pkind is the index of the peak magnitude sample, tstlen is the length of the DFT, and c is Candan's bias correction term which can be precomputed: c=tan(pi/tstlen)/(pi/tstlen); % Candan's correction term. In comparison your estimator requires numerous transcendental function computations as well as square roots, etc. For lower SNRs the noise tends to dominate performance so the simpler estimators tend to be preferable, e.g., mine with Candan's bias correction, which is just: delta=c*real((y(1)-y(3))/((2*y(2))-y(1)-y(3))); i.e., my estimator with one additional multiply. That's the blue x in the performance plots. There's a natural tradeoff between computational complexity and performance, with more complexity required for the higher SNR case where the estimator bias tends to dominate performance. Depending on the exact circumstances and desired properties (bias in middle or edges, max variance in middle or edges, etc., etc.), the tradeoffs may favor particular estimators over others, and there are a large number of existing estimators to pick from. In some applications divide operations are expensive and avoiding them is useful. For those applications other algorithms, like dichotomous search, may be favorable where the estimate is iterated down to the desired accuracy using (e.g.) vector multiplication with interpolating vectors. So it really does depend on what an implementer wants to accomplish and what tradeoffs are important in a particular application and implementation. If you're doing pitch detection that is a far different animal and other algorithms come into play. The estimators analyzed here pretty much all assume a single tone at the input, and if there is any other correlated energy present the performance can degrade substantially. If you're interested in music, pitch detection with signals rich in frequency content is also highly studied and gets discussed here from time to time, but the solutions are very different than the single-tone cases studied here. --- This email has been checked for viruses by Avast antivirus software. https://www.avast.com/antivirus
Reply by ●March 1, 20172017-03-01
[...snip...]> >Here are some results, with no added noise, which is the more >interesting case for the bias-corrected estimators: > >http://ericjacobsen.org/Files/p5fintrpsims.jpg > >Your three-term estimator is the solid green trace.[...snip...] I'm sorry, but these results look a little fishy to me. Would you please clarify your test conditions. 1) Did you use a real valued signal or a complex valued one? 2) What is your N? 3) What bin are you centered around? 4) Which of Michael's 3 bin formulas did you use? There is the all real values only, the imaginary values only, and the last one using magnitudes. 5) Are the vertical scale values the true values or in some other unit? (like my test program uses x100) I have not coded his last three formulas, the ones I just listed, but he did post results. In the noiseless case, they should be exact to the precision of the variables used, as his results indicate. Your results indicate otherwise. From the data you presented, I suspect you used a complex valued signal. Please rerun your tests with a real valued one. If this is not the case, then something else must be wrong. Ced P.S. I would still like to see the other closed form formulas you mentioned in the prior post. --------------------------------------- Posted through http://www.DSPRelated.com
Reply by ●March 1, 20172017-03-01
On Wed, 01 Mar 2017 19:57:23 -0600, "Cedron" <103185@DSPRelated> wrote:>[...snip...] >> >>Here are some results, with no added noise, which is the more >>interesting case for the bias-corrected estimators: >> >>http://ericjacobsen.org/Files/p5fintrpsims.jpg >> >>Your three-term estimator is the solid green trace. > >[...snip...] > >I'm sorry, but these results look a little fishy to me. Would you please >clarify your test conditions. > >1) Did you use a real valued signal or a complex valued one?Complex. Looking back, it's never been stated whether it is intended for real-only signals or not. Generally complex is assumed since it is the more general case of DFT application, so if that is incorrect it could matter.>2) What is your N?>3) What bin are you centered around? > >4) Which of Michael's 3 bin formulas did you use? There is the all real >values only, the imaginary values only, and the last one using >magnitudes. > >5) Are the vertical scale values the true values or in some other unit? >(like my test program uses x100) > >I have not coded his last three formulas, the ones I just listed, but he >did post results. In the noiseless case, they should be exact to the >precision of the variables used, as his results indicate. Your results >indicate otherwise. > >From the data you presented, I suspect you used a complex valued signal. >Please rerun your tests with a real valued one. If this is not the case, >then something else must be wrong. > >Ced > >P.S. I would still like to see the other closed form formulas you >mentioned in the prior post.You've trained me to not help you. You can do a lit search as well as anybody else. --- This email has been checked for viruses by Avast antivirus software. https://www.avast.com/antivirus
Reply by ●March 1, 20172017-03-01
On Wednesday, March 1, 2017 at 11:05:21 AM UTC-5, Cedron wrote:> > > >I'm sorry about posting all my formulas without any delay. > >I just wanted to get them out there while they are new, so that other > >people can use them if they want. > > > > You shouldn't apologize for what you have posted. Despite of what was > said by a local "Usenet Bully" on your other thread, your formulas are > very much on-topic for this forum.who's the bully?? Eric? Dale? (this time it can't be me, since i hadn't been here.) listen, this USENET group is unmoderated. any of use can be as rude or as helpful as we want. all the group can do is post approval or disapproval to hold us to account. may i suggest http://dsp.stackexchange.com/ as another form? you get to post your equations using LaTeX and you get to post in images like graphs from MATLAB or similar. it's moderated so there is a little more incentive to be polite. that your interest is mathematics and music makes this interesting to me. r b-j
Reply by ●March 1, 20172017-03-01
>Complex. Looking back, it's never been stated whether it is intended >for real-only signals or not. Generally complex is assumed since it >is the more general case of DFT application, so if that is incorrect >it could matter. >Yes, it does matter. You are correct that it was never stated. However, I think since the context is music analysis that a real signal is the better assumption. Finding exact formulas for the complex case is trivial compared to the real case. Proving that my 3 bin complex signal formula and Candan's second formula (both stated in Julien's paper) are mathematically equivalent is not trivial. Indeed, if any trig professors want to inflict a difficult trig identity problem on their students, this would be a good one.> >You've trained me to not help you. You can do a lit search as well >as anybody else. >Because I don't accept your say-so as fact? I have really tried to help you by pointing out the things that you say that aren't true. It seems to me that you are the one who doesn't accept things well. This is not to help me, this is for you to back your assertions. You claimed something exists, I have a curiosity about it. Ced --------------------------------------- Posted through http://www.DSPRelated.com
Reply by ●March 2, 20172017-03-02
On Wed, 01 Mar 2017 22:34:49 GMT, eric.jacobsen@ieee.org wrote:>On Wed, 01 Mar 2017 21:55:33 +0100, Michael Plet <me@home.com> wrote: > >>On Wed, 01 Mar 2017 20:31:16 GMT, eric.jacobsen@ieee.org wrote: >> >>>On Wed, 01 Mar 2017 10:57:36 +0100, Michael Plet <me@home.com> wrote: >>> >>>>Hi Group >>>> >>>>I'm sorry about posting all my formulas without any delay. >>>>I just wanted to get them out there while they are new, so that other >>>>people can use them if they want. >>>> >>>>Michael Plet >>> >>>Can I ask what your interest is in pursuing this? Is it academic >>>interest or something else? Are you open to criticism on these? >>> >>>Feel free to contact me privately if you prefer. I was going to >>>email you directly, but I suspect that me@home.com isn't actually your >>>address. >>> >>> >>> >>>--- >>>This email has been checked for viruses by Avast antivirus software. >>>https://www.avast.com/antivirus >> >> >>I have a background in Computer Science and Mathematics. >>The reason I got interested in DSP is because of my love of music. >>I want to and have already used DSP to analyse music. >> >>For that reason I derived my first formula. >>Because I also like mathematical puzzles I enjoyed deriving more >>formulas. >> >>I realise that a single formula is not enough to analyse a piece of >>music with many events in both frequency and time. >>I am very much open to criticism. >> >>Michael > >This sort of frequency interpolation has been around for a long time >(many decades), with a lot of work having been done for subtle >optimizations for various different applications. I've been involved >directly in the context of signal processing for communication systems >on this particular topic since the mid-1990s. The matlab/octave test >suite I linked earlier was done during that early research, but I have >a more developed test suite now that allows fairly quick testing and >analysis of different methods. I plugged yours in over the last couple >of days to see how it compared to other estimators. > >As I mentioned early on, the two-term estimators like you initially >proposed generally suffer frequency-dependent errors, and it appears >that yours is not an exception. You indicated in the results you >posted that you used a phase of ~0.785 (radians, presumably), and at >that particular phase the errors are masked. When I tried it there >are substantial frequency-dependent errors at other phases, and the >usual one that happens with two-term estimators is at zero frequency >offset and zero phase, which also seems to be a problem with your >two-term estimator. Yours also seems to have difficulty at pi >radians and a few other phases. Randomizing the signal phase across >trials helps to show whether the estimator is robust in these >conditions. > >Even when the phase is favorable, though, the perforrmance is not >favorably comparable to other estimators with much lower computational >complexity. This is fairly typical, though, and I think may be part >of why two-term estimators aren't very popular or at least don't get >much attention. > >The last estimator you posted, using three terms, is not bad but is >not as good as the usual estimators used as references (Candan's, >Liao's, etc.), and is MUCH MUCH more computationally intensive. For >that reason there isn't much motivation to use yours when there are >better-performing estimators with much less computational complexity. >I suspect that perhaps the large number of computations in yours, >including transcendental functions, just adds a lot of accumulated >quantization noise. > >Here are some results, with no added noise, which is the more >interesting case for the bias-corrected estimators: > >http://ericjacobsen.org/Files/p5fintrpsims.jpg > >Your three-term estimator is the solid green trace. There are a >number of other estimators in the same trials, including my old, >simple one (black circles), my estimator with Candan's simple bias >correction (blu x), Candan's complete estimator (magenta dots), Liao >and Lo's correction to the QMJ estimator (red circles), and Lonnemo's >estimator (black +). The bias-corrected or low-bias estimators are >nearly indistinguishable at this level. > >Fig 1 is just the estimated frequency vs the test number, with test #1 >being no frequency offset and then incrementing 1/10th of a bin offset >with each test (so that test #6 is halfway between bins). The >vertical axis is bin number. This just shows that the estimators are >generally working. > >Fig 2. is the statistical variance of each estimator vs offset. Each >offset has 5000 trials with random phase at each trial. > >Fig 3 is the statistical bias of each estimator vs offset. >. >FWIW, at this time the usual reference estimator for performance at >high SNR is Candan's, because it matches the best performance with >anything else out there and has the least relative computational >complexity. > >For reference, Candan's estimator is computed as follows: > >First, compute delta using Jacobsen's (my) estimator, where y is the >three-element complex-valued vector of the peak magnitude sample and >the two adjacent samples. delta is then the interbin fractional >error of the initial fequency estimate using only the peak bin. > >delta=real((y(1)-y(3))/((2*y(2))-y(1)-y(3))); > >Candan's estimator is then: > >freq=pkind+(atan((pi/tstlen)*c*delta))/(pi/tstlen); > >Where the resulting estimated frequency is in bins, pkind is the index >of the peak magnitude sample, tstlen is the length of the DFT, and c >is Candan's bias correction term which can be precomputed: > >c=tan(pi/tstlen)/(pi/tstlen); % Candan's correction term. > >In comparison your estimator requires numerous transcendental function >computations as well as square roots, etc. For lower SNRs the noise >tends to dominate performance so the simpler estimators tend to be >preferable, e.g., mine with Candan's bias correction, which is just: > >delta=c*real((y(1)-y(3))/((2*y(2))-y(1)-y(3))); > >i.e., my estimator with one additional multiply. That's the blue x >in the performance plots. > >There's a natural tradeoff between computational complexity and >performance, with more complexity required for the higher SNR case >where the estimator bias tends to dominate performance. Depending on >the exact circumstances and desired properties (bias in middle or >edges, max variance in middle or edges, etc., etc.), the tradeoffs may >favor particular estimators over others, and there are a large number >of existing estimators to pick from. > >In some applications divide operations are expensive and avoiding them >is useful. For those applications other algorithms, like dichotomous >search, may be favorable where the estimate is iterated down to the >desired accuracy using (e.g.) vector multiplication with interpolating >vectors. > >So it really does depend on what an implementer wants to accomplish >and what tradeoffs are important in a particular application and >implementation. If you're doing pitch detection that is a far >different animal and other algorithms come into play. The estimators >analyzed here pretty much all assume a single tone at the input, and >if there is any other correlated energy present the performance can >degrade substantially. If you're interested in music, pitch >detection with signals rich in frequency content is also highly >studied and gets discussed here from time to time, but the solutions >are very different than the single-tone cases studied here. > > > >--- >This email has been checked for viruses by Avast antivirus software. >https://www.avast.com/antivirusThank you very much for taking the time to test my formula. I was a little puzzled by the first picture. It seems to indicate that all the estimators are exact. I thought some of them were approximations. From a pure mathematical point of view my formulas are exact regardless of phase and amplitude. Of course as you say, quantization errors can occur when implementing on a computer. I can understand from the discussion below that you used a complex signal for testing. I have only used DSP for real signals (music), so my formulas for bin values have been based on real signals. If it is possible for you to do a test with real signals as input, I would appreciate that very much. Michael