This applies to "sparse" Fourier transforms. These have frequency bins
that either are mostly 0, or (for the inverse) can safely be truncated
to zero because their values are not significant. People who know more
about this field can perhaps tell us if Csound signals are of this
kind.

Even if Csound signals can be considered sparse, I am not sure whether
FFT compute times are terribly significant for Csound use cases.
Again, somebody who knows this field better might be able to say.

Regards,
Mike

On Thu, Feb 9, 2012 at 2:07 PM, nodnarb lleb  wrote:
> Hey Csounders,
>
> A research group at MIT claim to have discovered a new FFT algorithm that is
> faster than its predecessors. I haven't done the computations myself but I
> figured I'd share it with you all, in hope that we might be able to
> implement it into Csound. Here are some links to the algorithm
>
> http://groups.csail.mit.edu/netmit/sFFT/
> http://web.mit.edu/newsoffice/2012/faster-fourier-transforms-0118.html
>
> Keep me updated on any information/progress you guys have,
> Brandon



-- 
Michael Gogins
Irreducible Productions
http://www.michael-gogins.com
Michael dot Gogins at gmail dot com

The sparsity is very likely the problem from our point of view; it 
appears effectively to be a form of compression; possibly it does not 
have an exact inverse, which is something we rely on with the FFT. But 
one would have to read the papers in detail, and with math 
understanding,  to be sure. Still, it would be interesting to see if it 
would have any relevance to the sliding dft.

Richard Dobson


On 09/02/2012 19:29, Michael Gogins wrote:
> This applies to "sparse" Fourier transforms. These have frequency bins
> that either are mostly 0, or (for the inverse) can safely be truncated
> to zero because their values are not significant. People who know more
> about this field can perhaps tell us if Csound signals are of this
> kind.
>
> Even if Csound signals can be considered sparse, I am not sure whether
> FFT compute times are terribly significant for Csound use cases.
> Again, somebody who knows this field better might be able to say.
>
> Regards,
> Mike
>
> On Thu, Feb 9, 2012 at 2:07 PM, nodnarb lleb  wrote:
>> Hey Csounders,
>>
>> A research group at MIT claim to have discovered a new FFT algorithm that is
>> faster than its predecessors. I haven't done the computations myself but I
>> figured I'd share it with you all, in hope that we might be able to
>> implement it into Csound. Here are some links to the algorithm
>>
>> http://groups.csail.mit.edu/netmit/sFFT/
>> http://web.mit.edu/newsoffice/2012/faster-fourier-transforms-0118.html
>>
>> Keep me updated on any information/progress you guys have,
>> Brandon
>
>
>

Julius O. Smith III has a pretty good explanation of this.

John

All transforms that relate time and frequency are changes of basis in
the coordinate system representing sound, in some sense. These changes
of basis are subject to a mathematical uncertainty relation. Think of
a rectangular plot of time and frequency from time 0 to time t, and
from frequency f0 to frequency f1. This plot can be divided up into N
boxes in various ways that all preserve the same amount of
information. A digital PCM recording such as a CD audio file divides
up the rectangle into N time slices and 1 frequency slice. Applying
the discrete Fourier transform to this waveform transforms the basis
such that the rectangle has 1 time slice and N frequency slices. (I am
omitting discussion of negative frequencies, complex numbers, etc.).
The Gabor transform, which is essentially the same as the short-time
windowed discrete Fourier transform or "phase vocoder analysis",
divides up the box into N / K time slices and K frequency slices. The
rectangle is divided into equal boxes which may be narrower and taller
or wider and shorter as N/K changes. Each box is a "logon" or Gabor
cell or simple grain of sound. The wavelet transform divides up the
rectangle into the same N cells, but in such a way that each frequency
stripe has 2 times the number of cells of the next lower frequency
stripe. That means the uncertainty about time decreases as the
frequency increases, and is more like the way we hear. The grains of
sound last longer at lower frequency and are shorter at higher
frequency.

Regards,
Mike

On Fri, Feb 10, 2012 at 7:35 AM, Bernt Isak Wærstad  wrote:
> It could perhaps be good for pitch tracking where you're not concerned with
> the inverse? Anybody tried using wavelet transform for pitch tracking by the
> way? I've just heard that it would be more accurate than fourier, but I
> honestly haven't that much a clue of what the difference is.
>
>
> On Thu, Feb 9, 2012 at 8:52 PM, Richard Dobson
>  wrote:
>>
>> The sparsity is very likely the problem from our point of view; it appears
>> effectively to be a form of compression; possibly it does not have an exact
>> inverse, which is something we rely on with the FFT. But one would have to
>> read the papers in detail, and with math understanding,  to be sure. Still,
>> it would be interesting to see if it would have any relevance to the sliding
>> dft.
>>
>> Richard Dobson
>>
>>
>>
>> On 09/02/2012 19:29, Michael Gogins wrote:
>>>
>>> This applies to "sparse" Fourier transforms. These have frequency bins
>>> that either are mostly 0, or (for the inverse) can safely be truncated
>>> to zero because their values are not significant. People who know more
>>> about this field can perhaps tell us if Csound signals are of this
>>> kind.
>>>
>>> Even if Csound signals can be considered sparse, I am not sure whether
>>> FFT compute times are terribly significant for Csound use cases.
>>> Again, somebody who knows this field better might be able to say.
>>>
>>> Regards,
>>> Mike
>>>
>>> On Thu, Feb 9, 2012 at 2:07 PM, nodnarb lleb  wrote:
>>>>
>>>> Hey Csounders,
>>>>
>>>> A research group at MIT claim to have discovered a new FFT algorithm
>>>> that is
>>>> faster than its predecessors. I haven't done the computations myself but
>>>> I
>>>> figured I'd share it with you all, in hope that we might be able to
>>>> implement it into Csound. Here are some links to the algorithm
>>>>
>>>> http://groups.csail.mit.edu/netmit/sFFT/
>>>> http://web.mit.edu/newsoffice/2012/faster-fourier-transforms-0118.html
>>>>
>>>> Keep me updated on any information/progress you guys have,
>>>> Brandon
>>>
>>>
>>>
>>>
>>
>>
>>
>> Send bugs reports to the Sourceforge bug tracker
>>           https://sourceforge.net/tracker/?group_id=81968&atid=564599
>> Discussions of bugs and features can be posted here
>> To unsubscribe, send email sympa@lists.bath.ac.uk with body "unsubscribe
>> csound"
>>
>
>
>
> --
> Mvh.
>
> Bernt Isak Wærstad
>
>
>



-- 
Michael Gogins
Irreducible Productions
http://www.michael-gogins.com
Michael dot Gogins at gmail dot com