1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Is this a homework question? And, what do you mean by "fastest"? $\endgroup$ – MBaz Mar 25 at 13:29
  • 1
    $\begingroup$ @MBaz Not a homework question. I've been reading around calculating a DCT using an FFT (e.g. 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 $\endgroup$ – David C Mar 25 at 13:57
0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$ – David C Mar 29 at 11:00
  • $\begingroup$ 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 $\endgroup$ – Laurent Duval Mar 29 at 11:34
  • $\begingroup$ Cool, thanks, I'll check it out. $\endgroup$ – David C Mar 29 at 13:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.