- #1
lidnele
- 3
- 0
Hi,
First, apologies if this is the wrong forum or even the wrong website. The site popped up when searching for a math forum to help me implement an equation efficiently. I’m not sure if this is the place for discussing computational efficiency, but since the efficiency is achieved by way of mathematical theorems, I thought it might fit.
I’m trying to implement an efficient version of the constant Q transform in an attempt to determine pitch for a real-time application, but the math part of my brain has been sitting unused for some years and Google doesn’t seem to hold much information.
I’ve stumbled upon an algorithm derived by Judith Brown and Miller Puckette in an (easy to skim) article here:
http://academics.wellesley.edu/Physics/brown/pubs/effalgV92P2698-P2701.pdf
I’ve verified that the algorithm works (although not yet its speed), but I need to understand it better.
The gist of the article is (if I understand correctly, of course) that a kernel (equation 4) can be pre-calculated and then used repeatedly for multiplication with the input signal. That seems reasonable: less processing power required, much more memory needed.
The article seems to imply that using a form of Parceval’s relation (equation 3) is what provides the speed. I can’t understand the efficiency gain in multiplying an FFT’d kernel with an FFT’ed input, as opposed to just performing the multiplication in the time domain (first and second part of equation (5) in the article).
What’s the catch? I guess what I’d like to know is what the use of Parceval’s theorem really is (especially coupled to the CQT).
If this is such an elementary question that you don’t want to reward it with a lengthy answer, pointers to relevant articles would be sufficient.
Also, if the first thought that pops into your head is “that’s not at all efficient. I know a much better way to do this”, please write away.
Thanks in advance.
First, apologies if this is the wrong forum or even the wrong website. The site popped up when searching for a math forum to help me implement an equation efficiently. I’m not sure if this is the place for discussing computational efficiency, but since the efficiency is achieved by way of mathematical theorems, I thought it might fit.
I’m trying to implement an efficient version of the constant Q transform in an attempt to determine pitch for a real-time application, but the math part of my brain has been sitting unused for some years and Google doesn’t seem to hold much information.
I’ve stumbled upon an algorithm derived by Judith Brown and Miller Puckette in an (easy to skim) article here:
http://academics.wellesley.edu/Physics/brown/pubs/effalgV92P2698-P2701.pdf
I’ve verified that the algorithm works (although not yet its speed), but I need to understand it better.
The gist of the article is (if I understand correctly, of course) that a kernel (equation 4) can be pre-calculated and then used repeatedly for multiplication with the input signal. That seems reasonable: less processing power required, much more memory needed.
The article seems to imply that using a form of Parceval’s relation (equation 3) is what provides the speed. I can’t understand the efficiency gain in multiplying an FFT’d kernel with an FFT’ed input, as opposed to just performing the multiplication in the time domain (first and second part of equation (5) in the article).
What’s the catch? I guess what I’d like to know is what the use of Parceval’s theorem really is (especially coupled to the CQT).
If this is such an elementary question that you don’t want to reward it with a lengthy answer, pointers to relevant articles would be sufficient.
Also, if the first thought that pops into your head is “that’s not at all efficient. I know a much better way to do this”, please write away.
Thanks in advance.