可能第壹個與稀疏信號恢復相關的算法是由法國數學家Prony提出的。這種被稱為Prony方法的稀疏信號恢復方法可以通過求解特征值問題從少量等距樣本中估計稀疏三角多項式的非零振幅和相應頻率。最早采用基於L1範數最小化的稀疏約束的人是B. Logan。他發現，如果數據足夠稀疏，可以通過最小化L1範數從欠采樣樣本中有效恢復頻率稀疏信號。D. Donoho和B.Logan是信號處理領域的先驅，他們采用L1範數最小化稀疏約束。然而，地球物理學家早在20世紀70年代和80年代就開始使用L1範數最小化來分析地震反射信號。20世紀90年代，稀疏重構方法被提出用於從欠采樣非等距樣本中恢復稀疏傅裏葉譜。同時，稀疏信號處理方法也被引入到圖像處理中。在統計學中，使用L1範數和相關方法進行模型選擇的問題也同時開始。
基於上述理論，壓縮感知創造性地將L1範數最小化的稀疏約束與隨機矩陣相結合，以獲得最佳的稀疏信號重構性能。
壓縮感知基於信號的可壓縮性，通過對低維空間、低分辨率和低奈奎斯特采樣數據的不相關觀測實現對高維信號的感知，豐富了信號恢復的優化策略，極大地促進了數學理論與工程應用的結合。它是傳統信息論的延伸，但它超越了傳統壓縮理論，成為壹個全新的分支。它誕生至今只有五年時間，但其影響力已經席卷了大多數應用科學。