Consider a finite-length discrete-time signal where, instead of
traditional linearly-spaced sample points, we have sample points on a
time grid of
 t = ln(k), 
k an integer from 1 to N. 

Such a sequence will have widely-spaced samples for small k, with
increasing sample density as k increases.

I would like to take the Fourier transform of such a sequence. I could
obviously do this using a modified DFT by correlating the sequence
with logarithmically-spaced samples of sin and cos waves. However, I
wonder if there is not a "fast" method of doing this that would save
computation. I'm pretty sure there is no existing soulution for this
problem. Any takers?

Regards

Bob Adams

"Liz" <robert.w.adams@verizon.net> wrote in message
news:9dec5a83.0312252059.71a97e5f@posting.google.com...
> Consider a finite-length discrete-time signal where, instead of
> traditional linearly-spaced sample points, we have sample points on a
> time grid of
>  t = ln(k),
> k an integer from 1 to N.
>
> Such a sequence will have widely-spaced samples for small k, with
> increasing sample density as k increases.
>
> I would like to take the Fourier transform of such a sequence. I could
> obviously do this using a modified DFT by correlating the sequence
> with logarithmically-spaced samples of sin and cos waves. However, I
> wonder if there is not a "fast" method of doing this that would save
> computation. I'm pretty sure there is no existing soulution for this
> problem. Any takers?

First, assure that the sampling rate is adequate for the large sample
intervals.  This is a big deal, so don't blow it off without thinking about
it carefully.  The log-sampled sinusoids for correlation would yield some
interesting results which might demand some sort of weighting.  Well, in
fact, log sampling the sinusoids would probably be unreasonable - a guess.

Then, why not interpolate to linear samples at the large sample intervals?

You should ask yourself what it is you expect the Fourier Transform to look
like in this situation?

Fred

robert.w.adams@verizon.net (Liz) wrote in message news:<9dec5a83.0312252059.71a97e5f@posting.google.com>...
> Consider a finite-length discrete-time signal where, instead of
> traditional linearly-spaced sample points, we have sample points on a
> time grid of
>  t = ln(k), 
> k an integer from 1 to N. 
> 
> Such a sequence will have widely-spaced samples for small k, with
> increasing sample density as k increases.
> 
> I would like to take the Fourier transform of such a sequence. I could
> obviously do this using a modified DFT by correlating the sequence
> with logarithmically-spaced samples of sin and cos waves. However, I
> wonder if there is not a "fast" method of doing this that would save
> computation. I'm pretty sure there is no existing soulution for this
> problem. Any takers?

Check out the writings of Barbarossa and Petrone at the University 
of Roma. They did some work on polynomial-phase signals in the early 
1990ies. These are signals where the exponent in the Fourier transform 
varies non-linearly.

Rune