关键词：稀疏信号；算法；压缩传感；离散傅立叶变换
摘 要：In this thesis, we consider the problem of computing a sparse Discrete-Fourier-Transform of a high-dimensional signal from its timedomain samples, as a representative example of compressed-sensing problems. We use this problem to investigate the tradeo between the number of measurements, noise robustness, and the computational complexity of the recovery algorithm in compressed sensing problems.