Title:  Fast Algorithms for Sampled Multiband Signals

Committee:

Dr. Mark Davenport, ECE, Chair , Advisor

Dr. Justin Romberg, ECE

Dr. James McClellan, ECE

Dr. Christopher Heil, Math

Dr. Michael Lacey, Math

Abstract: Over the past several years, computational power has grown tremendously. This has led to two trends in signal processing. First, signal processing problems are now posed and solved using linear algebra, instead of traditional methods such as filtering and Fourier transforms. Second, problems are dealing with increasingly large amounts of data. Applying tools from linear algebra to large scale problems requires the problem to have some type of low-dimensional structure which can be exploited to perform the computations efficiently. One common type of signal with a low-dimensional structure is a multiband signal, which has a sparsely supported Fourier transform. Transferring this low-dimensional structure from the continuous-time signal to the discrete-time samples requires care. Naive approaches involve using the FFT, which suffers from spectral leakage. A more suitable method to exploit this low-dimensional structure involves using the Slepian basis vectors, which are useful in many problems due to their time-frequency localization properties. However, prior to this research, no fast algorithms for working with the Slepian basis had been developed. As such, practitioners often overlooked the Slepian basis vectors for more computationally efficient tools, such as the FFT, even in problems for which the Slepian basis vectors are a more appropriate tool. In this thesis, we first study the mathematical properties of the Slepian basis, as well as the closely related discrete prolate spheroidal sequences and prolate spheroidal wave functions. We then use these mathematical properties to develop fast algorithms for working with the Slepian basis, a fast algorithm for reconstructing a multiband signal from nonuniform measurements, and a fast algorithm for reconstructing a multiband signal from compressed measurements. The runtime and memory requirements for all of our fast algorithms scale roughly linearly with the number of samples of the signal.