Learning algorithms based on the Fourier transform attempt to learn functions by approximating the largest coefficients of their Fourier representations. Nearly all previous work in Fourier-based learning has been in the theoretical realm, where properties of the transform have made it possible to prove many interesting learnability results. The real-world usefulness of Fourier-based methods, however, has not been thoroughly explored. This thesis explores methods for the practical application of Fourier-based learning. The primary contribution of this thesis is a new search algorithm for finding the largest coefficients of a function's Fourier representation. Although the search space is exponentially large, empirical results demonstrate that only a small fraction of the space needs to be explored to find the largest coefficients. Furthermore, the algorithm is applicable to a much wider range of learning scenarios than previous approaches. Results of learning real-world problems with algorithms based on this search technique are also presented. The accuracies of the Fourier-based learning methods are not particularly impressive, however, and analysis and empirical results suggest why the Fourier representation may be a poor choice for typical real-world learning problems. Finally, this thesis shows that the search algorithm can be generalized to explore any basis of functions. Furthermore, it can search multiple bases simultaneously. This greatly enhances the learning techniques, and empirical results demonstrate significantly improved accuracy over the Fourier-based approach.



College and Department

Physical and Mathematical Sciences; Computer Science



Date Submitted


Document Type





machine learning, Fourier transform, basis functions, search