Re: real exact pruned DFT?

On Jun 12, 5:35 pm, glen herrmannsfeldt <g...@xxxxxxxxxxxxxxxx> wrote:
I'm a grad student in CS at yale and I'm looking for an algorithm to
compute k coefficients out of a size n DFT in less then O(n log n)
operations, possibly O(n log k). The problems are that a) the k
coefficients are scattered (not in a band) b) I need my solution to be
exact (no approximations)
I'm sure such solutions exist I just can't find references to them.
can anybody offer some help?
Every number generated by a computer is an approximation. What do you mean?

That is a good question, as FFT is an approximation (dues to different
rounding) to the DFT. (I am not so sure which is closer to a rounded
infinite precision transform, though, but they are likely different.)

First, by "exact algorithm", the original poster certainly means
"exact in exact arithmetic", which is the standard definition in the
field. As opposed to a method (e.g some wavelet techniques for pruned
DFTs by Guo and Burrus) that is an approximation even in exact
arithmetic.

Second, the DFT properly refers to the mathematical transformation,
not to a particular O(N^2) algorithm to compute it. And an FFT is a
particular algorithm for computing the DFT in O(N log N) operations,
which is exact in exact arithmetic. The FFT *itself* contains no
approximations, only the *implementation* on a computer. An
implementation of an FFT in floating-point arithmetic generates
floating point errors, but the floating point errors (at least, for
the Cooley-Tukey algorithm) are *substantially* smaller than those of
the usual O(N^2) algorithm (logarithmic vs. polynomial error growth).

Third, to answer the original poster's question, if the transform you
are computing is not too big (say, N <= 1024), you might consider
modifying the generator in FFTW (www.fftw.org). If you modify the
generator to set certain inputs to zero, or to only compute certain
outputs, it is powerful enough to automatically prune the unneeded
operations from the generated code. (This is how we generate real-
data transforms - we just set the imaginary parts of the input to zero
and it automatically prunes the operations by a factor of ~2.)

In general, if you have some weird scattered pattern of output
coefficients and N is large or arbitrary, pruning the FFT is fairly
difficult without automatic methods like the FFTW generator. Just how
difficult depends on the precise pattern of coefficients you want. In
principle, I think O(N log K) is possible [ Duhamel and Vetterli,
Signal Processing 19, 259-299 (1990) ], but achieving this in practice
is another matter, although I have some thoughts on the subject.

Regards,
Steven G. Johnson

.

Relevant Pages

  • Re: real exact pruned DFT?
    ... I'm a grad student in CS at yale and I'm looking for an algorithm to ... compute k coefficients out of a size n DFT in less then O ... coefficients are scattered b) I need my solution to be ...
    (comp.dsp)
  • real exact pruned DFT?
    ... I'm a grad student in CS at yale and I'm looking for an algorithm to ... compute k coefficients out of a size n DFT in less then O ... coefficients are scattered b) I need my solution to be ...
    (comp.dsp)
  • Re: DFT Function
    ... all values of the output array are very close to 1.0. ... shape (by connecting close-by points of the DFT) to ... the FT is the sequence of Fourier coefficients). ... David Bernier ...
    (sci.math)
  • Re: Autocorrelation matrix of a long sequence
    ... Convolution by DFT is circular, ... Time-reversing in time domain is not sufficient to ... (save some scaling coefficients), can alternatively be ...
    (comp.dsp)
  • Re: Autocorrelation matrix of a long sequence
    ... to zero-pad before computing the DFT. ... zero-pad further, to the next power of 2. ... handle wrap-around effects from circular convolution, ... (save some scaling coefficients), can alternatively be ...
    (comp.dsp)