1

A vector a is transformed via a discrete cosine transform (DCT) to give vector b. For example in Matlab

b=dct(a);.

Vector a is also transformed via a discrete Fourier transform (DFT) to give vector c. E.g.

c=fft(a);

What is the fastest way to determine c from b without using a or retrieving it? For example,

c=fft(idft(b));

is not allowed.

lennon310
  • 3,590
  • 19
  • 24
  • 27
David C
  • 13
  • 2
  • Is this a homework question? And, what do you mean by "fastest"? – MBaz Mar 25 '21 at 13:29
  • 1
    @MBaz Not a homework question. I've been reading around calculating a DCT using an FFT (e.g. https://dsp.stackexchange.com/a/10606) and was interested in the ability to directly transform between the two domains.

    I guess "fastest" is in the eye of the beholder. Lets go for a big-O style metric

     – David C Mar 25 '21 at 13:57

1 Answers1

0

Behind an FFT or a DCT operator, which can be implemented as a matrix product. Depending on the shape of your discrete vectors, you may have $b=D\times a$ and $c=F\times a$. So you can find your answer with a suitable matrix product. You can also find fast algorithms by decomposing each of the above matrices in simpler matrix product, or using lifting-like implementation. The very fastest can be more difficult to find.

Laurent Duval
  • 31,850
  • 3
  • 33
  • 101
  • Thank you for this. Could you expand on the lifting approach? My understanding is that lifting is primarily useful for solving non-linear problems but I'm unsure as to how it might be used to speed up this operation? – David C Mar 29 '21 at 11:00
  • Lifting is indeed a term with many meaning in different fields. A lifting scheme for filter banks (applicable to DFT, DCT) is a technique to better interleave "filter taps" and "subsampling", allowing faster operations, and also the introduction of (useful) non-linearities – Laurent Duval Mar 29 '21 at 11:34
  • Cool, thanks, I'll check it out. – David C Mar 29 '21 at 13:18