Skip to content

Sub-Linear Methods

The major goal in this work is the identification of sparse signals in time commensurate with the number of terms in the signal. That is, given a wide swath of the spectrum (a large bandwidth) and knowledge that there are only a small number of signals in this spectrum to identify, our goal is to identify these signals  as efficiently as possible. This problem arises in many contexts.  For example, consider personalized medicine. This area suffers from having a large amount of high dimensional data. The data one wants to bring together for identifying treatment is large: genomics data, health care records for patient outcomes, family medical history and the area where someone lives. However, we are looking for a few significant signals in all this data, meaning that the signal is sparse. This is also happening in the traditional sciences, where reams of sensor data are easy to obtain but difficult to analyze.  Take for example The Large Synoptic Survey Telescope project. This work will give vast amounts of data describing the universe around us, but now the key is how to analyze this high dimensional data. Methods need to be developed for identifying sparse signals in this high dimensional data so that we can identify relationships in the data and learn more about the universe around us. As a third example, consider scientific computing at the exascale. Here, we will be able to explore problems we have never been able to tackle, but we are left with the issue of dealing with exabytes of data that are too expensive to store long term. We need novel methods of compression and signal identification so as to only store the meaningful information within these data sets.  

We have been working on this problem for several years. Our approach has been to develop a sub-linear Fast Fourier Transform. This methodology has been developed for continuous signals for both noisy and high dimensional data. We are working on extending these methods to discreet data using key ideas from nonuniform FFTs.  

Select Papers

  • D. Lawlor, Y. Wang, and A.J. Christlieb, "Adaptive Sub-Linear Time Fourier Algorithms'', Advances in Adaptive Data Analysis, 5(01), 2013
  • D. Lawlor, Y. Wang, and A.J. Christlieb, "A Multiscale Sub-linear Time Fourier Algorithm for Noisy Data'', Applied Computational Harmonic Analysis,  40(3), 553--574, 2016
  • B.Choi, A.J. Christlieb, Y. Wang, "Multi-dimensional Sublinear Sparse Fourier Algorithm",  submitted/on arXiv
  • S. Merhi, R. Zhang, M. Iwen, A.J. Christlieb, "A New Class of Fully Discrete Sparse Fourier Transforms: Faster Stable Implementations with Guarantees" submitted/on arXiv