How does Parceval's theorem help with an efficient CQT?


by lidnele
Tags: efficient, parceval, theorem
lidnele
lidnele is offline
#1
Dec14-13, 01:29 PM
P: 3
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/Physi...2698-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.
Phys.Org News Partner Mathematics news on Phys.org
Researchers help Boston Marathon organizers plan for 2014 race
'Math detective' analyzes odds for suspicious lottery wins
Pseudo-mathematics and financial charlatanism
Stephen Tashi
Stephen Tashi is online now
#2
Dec16-13, 11:01 AM
Sci Advisor
P: 3,175
When I look at that document,the first page is blank. Anyone else able to see the first page ?
lidnele
lidnele is offline
#3
Dec16-13, 02:11 PM
P: 3
When I click on the link in my post, I get the PDF document displayed as it should. I can't see anything different between page one and the others (apart from the information, of course), so I don't know why the first page would appear to be invisible for you.

I use Safari and its built-in PDF reader, btw, although it shouldn't matter.

AlephZero
AlephZero is offline
#4
Dec16-13, 08:40 PM
Engineering
Sci Advisor
HW Helper
Thanks
P: 6,349

How does Parceval's theorem help with an efficient CQT?


I think the point is that in equation (5) the sum is not really over N-1 terms because most of the K* terms are close to zero, as shown in Fig 2. Fig 3 is presumably some measure of the error introduced by dropping the near-zero terms. If the objective is to identify discrete 12-tone or 24-tone pitches in a scale, errors of a fraction of a tone interval (e.g. less than half) probably don't matter.
lidnele
lidnele is offline
#5
Dec19-13, 11:54 AM
P: 3
Of course. It's funny how one's mind works. I've read the article several times, but somehow I've completely missed that (which some might argue is a central point of the article).

It makes a lot more sense now. Thanks.


Register to reply

Related Discussions
Fourier Series & Parceval's identity Calculus & Beyond Homework 6
More than efficient General Physics 4
An efficient AC. Mechanical Engineering 2
New Efficient AC General Engineering 28
which is more efficient Electrical Engineering 4