# Retrieve DFT coefficients from DCT coefficients

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.

• Is this a homework question? And, what do you mean by "fastest"? – MBaz Mar 25 at 13:29
• @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 – David C Mar 25 at 13:57

## 1 Answer

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.

• 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 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 at 11:34
• Cool, thanks, I'll check it out. – David C Mar 29 at 13:18