Date of Award


Document Type


Degree Name

Master of Science (MS)

Legacy Department

Mathematical Science


Gao, Shuhong

Committee Member

Khan , Taufiquar R

Committee Member

Sun , Xiaoqian


Compressive sensing is a novel paradigm for acquiring signals and has a wide range of applications. The basic assumption is that one can recover a sparse or compressible signal from far fewer measurements than traditional methods. The difficulty lies in the construction of efficient recovery algorithms. In this thesis, we review two main approaches for solving the sparse recovery problem in compressive sensing: l1-minimization methods and greedy methods. Our contribution is that we look at compressive sensing from a different point of view by connecting it with sparse interpolation. We introduce a new algorithm for compressive sensing called generalized eigenvalues (GE). GE uses the first m consecutive rows of discrete Fourier matrix as its measurement matrix. GE solves for the support of a sparse signal directly by considering generalized eigenvalues of Hankel systems. Under Fourier measurements, we compare GE with iterated hard thresholding (IHT) that is one of the state-of-the-art greedy algorithms. Our experiment shows that GE has a much higher probability of success than IHT when the number of measurements is small while GE is a bit more sensitive for signals with clustered entries. To address this problem, we give some observations from the experiment that suggests GE can be potentially improved by taking adaptive Fourier measurements. In addition, most greedy algorithms assume that the sparsity k is known. As sparsity depends on the signal and we may not be able to know the sparsity unless we have some prior information about the signal. However, GE doesn't need any prior information on the sparsity and can determine the sparsity by simply computing the rank of the Hankel system.