PIMS/CSC Research Seminar: Mark Iwen

Compressive sensing in its most practical form aims to recover a function that exhibits sparsity in a given basis from as few function samples as possible. One of the fundamental results of compressive sensing tells us that $O(s \log^4 N)$ samples suffice in order to robustly and efficiently recover any function that is a linear combination of $s$ arbitrary elements from a given bounded orthonormal set of size $N > s$. Furthermore, the associated recovery algorithms (e.g., Basis Pursuit via convex optimization methods) are efficient in practice, running in just polynomial-in-$N$ time. However, when $N$ is very large (e.g., if the domain of the given function is high-dimensional), even these runtimes may become infeasible. If the orthonormal basis above is Fourier, then the sparse recovery problem above can also be solved using Sparse Fourier Transform (SFT) techniques. Though these methods aim to solve the same problem, they have a different focus. Principally, they aim to reduce the runtime of the recovery algorithm as much as absolutely possible, and are willing to sample the function a bit more often than a compressive sensing method might in order to achieve that objective. By doing so, one can indeed achieve similar recovery guarantees to Basis Pursuit, but with radically reduced runtimes that depend only logarithmically on $N$.

However, SFTs are highly adapted to the special properties of the Fourier basis, making their extension to other orthonormal bases difficult. In this talk we will present a general framework that can be used in order to construct a highly efficient SFT algorithm. The framework abstracts many of the components required for SFT design in an attempt to simplify the application of SFT ideas to other basis choices.

Extension of arbitrary SFTs to the Chebyshev and Legendre polynomial bases will also be discussed.