The fast Fourier transform allows decomposition into a sin/cos basis in $N \log(N)$ complexity. Can one generalize the algorithm (or the ideas used) to other bases, e.g. orthogonal polynomial bases such as Hermite, Legendre, Chebyshev,...? I have a special interest in Zernike polynomials as well. If so, how? If not, what is special about the sin/cos that separates it from the other cases?

Also asked previously on: https://math.stackexchange.com/questions/647613/fast-fourier-transform-for-non-trigoniometric-bases/1730645#1730645 not having quite a satisfying answer yet.

Also, in a related question here on MO (here), I see pointing to this document on why the FFT would be fast. How could I use this principle on general orthogonal bases?