傅里葉變換是計算信號頻域表示的最基本工具之一。它在信號處理、通信、音頻和視頻壓縮、醫(yī)學(xué)成像、基因組學(xué)、天文學(xué)以及許多領(lǐng)域中發(fā)揮著核心作用。由于其廣泛使用，傅里葉變換的快速算法能使大量應(yīng)用受益。目前的最快算法是快速傅里葉變換（FFT），它在接近線性的時間內(nèi)運(yùn)行，使其成為很多領(lǐng)域不可或缺的工具。然而，今天，特別是對于大數(shù)據(jù)問題，F(xiàn)FT算法的運(yùn)行速度還是趕不上需求量。因此，在次線性時間內(nèi)運(yùn)行的更快的算法，即甚至不采樣所有數(shù)據(jù)點(diǎn)，已經(jīng)變得必要。本書通過開發(fā)稀疏傅里葉變換算法來解決上述問題。本書的研究內(nèi)容曾獲得2016年美國計算機(jī)協(xié)會（ACM）的年度最佳博士論文獎。