We study the problem of finding a Fourier representation of B terms for a given discrete signal of length N. The Fast Fourier Transform (FFT) can find the optimal N-term representation in O(Nlog N) time, but our goal is to get sublinear algorithms for B < N, typically B << N. This is joint work with S. Muthukrishnan and M. Strauss.
Copyright. All Rights Reserved.