non-uniform spectral interpolation in the frequency domain

Hi,

I'm researching ways to interpolate the sampled spectrum of a signal
as given by a 512 point FFT.  I typically only use the output of the
FFT as is, but I occasionally need to resample the continuous spectrum
in a non-uniform manner.  I can't take a longer FFT to interpolate by
zero-padding in the time domain, and usually only a few new samples of
the spectrum are needed anyway.  I found a solution at the following
link:

http://ccrma.stanford.edu/~jos/sasp/Ideal_Spectral_Interpolation_I.html

I used the given MATLAB function, and it works.  At the bottom of the
page it says that the computational requirements of the given method
can be reduced by using the sampled spectrum of the windowing function
that was used as an interpolation kernel in place of the aliased sinc
function.  At least I think that's what that bullet is telling me.  I
always use a function other than a rectangular pulse to window the
data before the 512 point FFT is taken, but I can't figure out how to
take advantage of this to reduce the complexity of the interpolation
method.  It seems that the given interpolation function always works,
as is, regardless of what windowing function I used.  It no longer
works if I try to replace the aliased sinc function with anything
else.

Does anyone have any advice?  I don�t necessarily need my interpolated
values to be extremely accurate, so my interpolation can be non-ideal.

Thanks in advance.

On Jan 14, 6:58&#4294967295;pm, Gilead <Gilead.Tisch...@gmail.com> wrote:
> Hi,
>
> I'm researching ways to interpolate the sampled spectrum of a signal
> as given by a 512 point FFT. &#4294967295;I typically only use the output of the
> FFT as is, but I occasionally need to resample the continuous spectrum
> in a non-uniform manner. &#4294967295;I can't take a longer FFT to interpolate by
> zero-padding in the time domain, and usually only a few new samples of
> the spectrum are needed anyway. &#4294967295;I found a solution at the following
> link:
>
> http://ccrma.stanford.edu/~jos/sasp/Ideal_Spectral_Interpolation_I.html
>
> I used the given MATLAB function, and it works. &#4294967295;At the bottom of the
> page it says that the computational requirements of the given method
> can be reduced by using the sampled spectrum of the windowing function
> that was used as an interpolation kernel in place of the aliased sinc
> function. &#4294967295;At least I think that's what that bullet is telling me. &#4294967295;I
> always use a function other than a rectangular pulse to window the
> data before the 512 point FFT is taken, but I can't figure out how to
> take advantage of this to reduce the complexity of the interpolation
> method. &#4294967295;It seems that the given interpolation function always works,
> as is, regardless of what windowing function I used. &#4294967295;It no longer
> works if I try to replace the aliased sinc function with anything
> else.
>
> Does anyone have any advice? &#4294967295;I don&#4294967295;t necessarily need my interpolated
> values to be extremely accurate, so my interpolation can be non-ideal.
>
> Thanks in advance.

Note in the reference you gave there is an error; the 2nd equation
with the delay term (to make it causal) is missing a "j".

The sinc function is unique in that the original points are not
altered (because when the sinc function is centered directly on a bin,
it goes through zero at all other bin frequencies and hence has no
contribution from its neighbors). If you use the spectrum of the
window function as the interpolation kernel, this will no longer be
true; the original points will be altered, so maybe this is why you
are thinking it does not work. However, you have to realize that you
have a window whether you want one or not; it's either rectanguar
(default), or one of the many good windows out there that you can
apply. It just so happens that in the rectangular case the optimal
interpolation is the sinc function, which does not alter the original
points. So I would not be bothered by the fact that the spectral
interpolation of the non-rectanguar-windowed sequence changes the
original points; this is normal.

It may, however, impact your computation burden. In the rectangualr
case, if you were using the original points, and also wanted some "in-
between" points, you only need to calculate the interpolation function
for the "in-between" points. Once you go non-rectangular, you will
need to calculate the interpolation function for ALL frequency points.




Bob Adams

On 15 Jan, 00:58, Gilead <Gilead.Tisch...@gmail.com> wrote:
> Hi,
>
> I'm researching ways to interpolate the sampled spectrum of a signal
> as given by a 512 point FFT. &#4294967295;I typically only use the output of the
> FFT as is, but I occasionally need to resample the continuous spectrum
> in a non-uniform manner. &#4294967295;I can't take a longer FFT to interpolate by
> zero-padding in the time domain, and usually only a few new samples of
> the spectrum are needed anyway. &#4294967295;

Do you need additional samples to the ones you have, or do you
need the spectrum to be resampled at a different uniform sampling
interval?

If you just need some additional samples (and depending on how
many additional spectrum samples are needed) you could compute
them directly from the DFT:

X(w) = sum x[n] exp(jwn)

This is simple to implement and not particularly expensive.
It might actually be the cheapest way if you need less than,
say, 5-10 additional spectrum samples.

Rune

On Wed, 14 Jan 2009 15:58:30 -0800 (PST), Gilead
<Gilead.Tischler@gmail.com> wrote:

>Hi,
>
>I'm researching ways to interpolate the sampled spectrum of a signal
>as given by a 512 point FFT.  I typically only use the output of the
>FFT as is, but I occasionally need to resample the continuous spectrum
>in a non-uniform manner.  I can't take a longer FFT to interpolate by
>zero-padding in the time domain, and usually only a few new samples of
>the spectrum are needed anyway.  I found a solution at the following
>link:
>
>http://ccrma.stanford.edu/~jos/sasp/Ideal_Spectral_Interpolation_I.html
>
>I used the given MATLAB function, and it works.  At the bottom of the
>page it says that the computational requirements of the given method
>can be reduced by using the sampled spectrum of the windowing function
>that was used as an interpolation kernel in place of the aliased sinc
>function.  At least I think that's what that bullet is telling me.  I
>always use a function other than a rectangular pulse to window the
>data before the 512 point FFT is taken, but I can't figure out how to
>take advantage of this to reduce the complexity of the interpolation
>method.  It seems that the given interpolation function always works,
>as is, regardless of what windowing function I used.  It no longer
>works if I try to replace the aliased sinc function with anything
>else.
>
>Does anyone have any advice?  I don&#4294967295;t necessarily need my interpolated
>values to be extremely accurate, so my interpolation can be non-ideal.
>
>Thanks in advance.

Hi Gilead,
  To add to what Robert Adams had to say: because you said 
you were "researching ways to interpolate" you might have a 
look at [1] the Goertzel algorithm which can compute 
spectral samples in between the normal DFT samples, 
and [2] the Zoom FFT algorithm.

Good Luck,
[-Rick-]