最近看到两个两个大牛的毕业论文里有压缩感知的(Compressed Sensing, CS)概念,才知道压缩感知是近10年来极为热门的学术大坑。

“It was as if you gave me the first three digits of a 10-digit bank account number — and then I was able to guess the next seven,” he says. He tried rerunning the experiment on different kinds of phantom images; they resolved perfectly every time.
Emmanuel Candes后来向加州大学洛杉矶分校的同事陶哲轩介绍了自己的发现,陶哲轩是世界上搞调和分析的顶尖高手之一,于是陶哲轩、Emmanuel Candes和Donoho神牛们完善了理论,联手挖出了Compressed Sensing的大坑。
传统信号或者图像采样一般采用奈奎斯特-香农采样定理(Nyquist–Shannon sampling theorem):即采样频率至少要大于模拟信号频率最大值(那奎斯特采样频率)的二倍,才能保证模拟信号在数字化过程中信息没有损失。在很多的应用场合,如医学成像、模式识别、无线通信等领域,高采样率带来的问题成为了制约信号获取、存储、传输及处理等信号与信息处理领域进一步发展的瓶颈。科学松鼠会一篇文章很好地介绍了压缩感知的应用背景:
压缩感知和数据压缩不同,经典的数据压缩技术是从数据本身的特性出发,寻找并剔除数据中隐含的冗余度,从而达到压缩的目的。这样的压缩有两个特点:第一、它是发生在数据已经被完整采集到之后;第二、它本身需要复杂的算法来完成。相较而言,解码过程反而一般来说在计算上比较简单。
但是压缩和解压缩的不对称性正好同人们的需求是相反的。在大多数情况下,采集并处理数据的设备,往往是廉价、省电、计算能力较低的便携设备。而负责处理(即解压缩)信息的过程往往在更高计算能力的大型计算机上进行。也就是说,我们是在用廉价节能的设备来处理复杂的计算任务,而用大型高效的设备处理相对简单的计算任务。
压缩感知可以解决这样的矛盾,从尽量少的数据中提取尽量多的信息:如果数码相机镜头收集到了大量的数据,然后在压缩时丢弃掉90%的数据,何不一开始收集数据就丢弃那90%的数据,直接采集去除冗余的信息,不仅可以省去了压缩的麻烦还能节省电量和空间。类似的在医学上,压缩感知可以显著减少断层扫描(CT)或磁共振成像(MRI)测量次数。
所以压缩感知理论是信号处理领域一次颠覆性的飞跃,它提出了一种新的信号采集或者测量方式:在信号满足稀疏性假设的前提下,可以以低于Nyquist标准对其采样,并且有一种算法可以足够精确地恢复出原始信号,即信号的采集可以突破Nyquist频率的限制。

最后收集了一些压缩感知的资料,要狂补数学TT:
1. Rice大学的Compressive Sensing Resources,最权威最全面的Compressive Sensing资源主页
2. An Introduction to Compressed Sensing,Emmanuel Candes在斯坦福的课程
3. Emmanuel Candes教授“21世纪计算”大会演讲:压缩感知,信号采集的重大突破
4. 陶哲轩的compressive sensing课程
5. Igor Carron收集的Compressive Sensing: The Big Picture, Compressed Sensing Listing, Compressive Sensing Videos, Compressive Sensing Codes
6. cvchina压缩感知的系列文章,包括CMU关于Compressive sensing的课件
7. 松鼠会科普文章:压缩感知与单像素照相机,填补空缺——压缩感知