8
$\begingroup$

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?

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
2
$\begingroup$

Related questions have been considered in some depth by Dan Rockmore and collaborators. For more, check out Rockmore's web page.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .