| RAℓSFA (Randomized Algorithm for Sparse Fourier Approximation) is a sublinear randomized algorithm. Given a discrete signal S of length N, the algorithm finds a near-optimal B-term Sparse Representation R in time and space poly(B, log(N), log(delta),epsilon -1), such that ||S - R|| 2 ≤ (1 + epsilon)||S - R Ropt|| 2. Its sublinear time cost outperforms the superlinear O( N log N) time requirement of the famous Fast Fourier Transform (FFT). However, a straightforward implementation of the RAℓSFA in [31] turns out to be very slow. Thus, it is important to improve the algorithm for practical purpose.; This dissertation focuses on the improvement, implementation, and application of RAℓSFA.; In order to make the theoretical sketch practical, we introduce several new ideas to speed up the algorithm. Both rigorous and heuristic arguments are presented. Theoretically, our RAℓSFA achieves the near-optimal approximation with high probability in time poly(B) log( N) log(1/delta)/epsilon2. We also extend the algorithm to higher dimensional cases. Numerical examples show that our implementation is faster (by a factor of four thousand times) than original RAℓSFA. Furthermore, it already beats FFT for reasonably large N. The crossover point lies at N ≃ 70, 000 in one dimension, and at N ≃ 900 for data on a N x N grid in two dimensions for small B signals contaminated by noise.; In some real applications, it is desirable to reconstruct the sparse representation from incomplete data. There are two main difficulties caused by irregularly spaced data. For one thing, a uniformly spaced sample may not always be available as a subset of the data; for another, the success probability of the RAℓSFA relies heavily on the percentage of available data. This thesis proposed a new adapted sublinear RAℓSFA algorithm. It introduced a greedy technique and Lagrange interpolation to overcome the above problems.; One of the exciting applications of RAℓSFA is multiscale models. Typically, the solutions of these models have rapidly oscillating coefficients, with period proportional to a small parameter alpha. Chapter 4 presents the first study of a new sublinear spectral method with time cost O(|log alpha|poly(d)) per time step. It shows great potential in solving multiscale models fast, especially for small resolutions and high dimensions.; This is a joint work with Dr. Ingrid Daubechies. |
