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

example obama
压缩感知问题源自稀疏表示问题,两者的本质都是要在一定的约束条件下求得欠定方程的最稀疏解。Donoho在这个领域功不可没,也是压缩感知研究领域具有奠基性工作的人物。压缩感知的发现是个传说,2004年加州理工学院教授(现在在斯坦福)的Emmanuel Candes,Donoho的学生,在研究Shepp-Logan Phantom图像,这是医学图像处理领域用来进行仿真测试的标准模拟图像。Candes检查的图像质量非常差,充满了噪声,他想到一种名叫L1-minimization的数学算法能去除掉噪声条纹,结果算法真的起作用了,而且他发现在图像变干净的同时,图像的细节出人意料得完美,简直就像变魔术一样。

“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频率的限制。

compressed sensing

最后收集了一些压缩感知的资料,要狂补数学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. 松鼠会科普文章:压缩感知与单像素照相机填补空缺——压缩感知