Time-Frequency Seminar

RAlSFA is a sublinear randomized algorithm to recover a B-term Fourier representation in time O(Blog N) for a signal of length N for some sparse nonzero B. It outperforms the Fast Fourier Transform (FFT) in speed for sparse signals of large size. In this paper, we replace the FFT by the RAlSFA and develop a new sublinear spectral method. Its log N time should be compared with the O(Nlog N) cost of the traditional spectral method. We use the new method to solve partial differential equations in the following multiscale problems: u_t=a(x,x/alpha)u_x u(x,0)=f(x) and u_t=(a(x,x/alpha) u_x)_x u(x,0)=f(x) where a(x,x/alpha) is 1-periodic. Functions a(x,x/alpha) and f(x) are each well represented by sparse Fourier representations. Our theoretical analysis and numerical simulation support the advantage of the new method in speed over the traditional spectral methods, when N is large.

Time-Frequency Brown Bag Seminar's homepage.