压缩传感引论

《压缩传感引论》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、“压缩传感”引论香港大学电机电子工程学系高效计算方法研究小组沙威2008年11月20日Email:wsha@eee.hku.hkPersonalWebsite:http://www.eee.hku.hk/~wsha到了香港做博士后，我的研究领域继续锁定计算电磁学。我远离小波和计算时谐分析有很长的时间了。尽管如此，我仍然陆续收到一些年轻学者和工程人员的来信，和我探讨有关的问题。对这个领域，我在理论上几乎有很少的贡献，唯一可以拿出手的就是几篇网上发布的帖子和一些简单的入门级的代码。但是，从小波和其相关的理论学习中，我真正懂得了一些有趣的知识，并获益良多

2、。我深切地感到越来越多的学者和工程师开始使用这个工具解决实际的问题，我也发现互联网上关于这方面的话题多了起来。但是，我们永远不能只停留在某个阶段，因为当今学术界的知识更新实在太快。就像我们学习了一代小波，就要学习二代小波；学习了二代小波，就要继续学习方向性小波（X-let）。我也是在某个特殊的巧合下不断地学习某方面的知识。就像最近，我的一个友人让我帮她看看“压缩传感”（CompressiveSensing）这个话题的时候，我的兴趣又一次来了。我花了一个星期，阅读文献、思考问题、编程序、直到写出今天的帖子。我希望这篇帖子，能对那些没进入且迫切想进入这

3、个领域的学者和工程师有所帮助。并且，我也希望和我一个星期前一样，对这个信号处理学界的“一个大想法”（ABigIdea）丝毫不了解的人，可以尝试去了解它。我更希望，大家可以和我探讨这个问题，因为我到现在甚至不完全确定我对压缩传感的某些观点是否正确，尽管我的简单的不到50行的代码工作良好。在这个领域中，华裔数学家陶哲轩和斯坦福大学的统计学家DavidDonoho教授做出了重要的贡献。在这个引言中，我用简单的关键字，给出我们为什么需要了解甚至是研究这个领域的原因。那是因为，我们从中可以学习到，下面的这些：矩阵分析、统计概率论、拓扑几何、优化与运筹学、泛函

4、分析、时谐分析（傅里叶变换、小波变换、方向性小波变换、框架小波）、信号处理、图像处理等等。所以，我们有什么理由，拒绝这个有意思的东西呢？让我们开始吧。传统思路——正交变换N×1对于一维的信号x∈R，大多数情况下，信息是冗余的。我们可以通过正交变换的HHHN×N方法来压缩它。正变换：y=Ψx，反变换x=Ψy。这里，ΨΨ=ΨΨ=I，Ψ∈C，N×1I是单位矩阵。对于y∈C，能量较x集中，本质上去除了x中的相关性。因此，我们只保留K个较大的分量，而把其它N−K个置为零。通过反变换，我们能够近乎完美的重建原始信号。因为，那N−K个变换域系数的贡献，实在微乎其

5、微。具有这样性质的信号被称为K“稀疏”（Sparsity）的。于是，我们有了如下编码解码的策略：编码：构造Ψ，做正变换y=Ψx，保留y中最重要的K个分量，和其对应的位置。HH解码：把K个分量放回到对应的位置，其它位置填0，构造Ψ，反变换xˆ=Ψyˆ。而解码能否近乎得到原始信号呢？显然，我们希望

6、

7、x−xˆ

8、

9、=

10、

11、y−yˆ

12、

13、≤δ，δ是一个小22的常数。但更有效的是用相对误差

14、

15、y−yˆ

16、

17、/

18、

19、y

20、

21、≤δ。22但这种编码解码方法有些缺点：1、考虑到香农（Shannon）采样定理，为了获得很好的信号分辨率，采样间隔会很小，造成了原始信号长度会很长，

22、因此变换过程会消耗很长的时间。2、K个需要保留的重要分量的位置，是随着信号的不同而不同的。因此，这种策略是“自适应”（Adaptive）的，且需要分配多余的空间存储这些位置。3、一旦在传输过程中K个分量中的某几个丢失了，后果可想而知。如果我们制作一个音频设备，1将带来电力的消耗和用户的不满，2将带来存储空间的增加，3将带来较差的抗干扰能力。新的思路——压缩传感压缩传感（CompressiveSensing）是一个很有意思的新的方向。它也正成为信号处理N×1领域的“ABigIdea”。对于信号x∈R，我们可以找到它的M个线性测量（LinerM×NMe

23、asurement），s=Φx。Φ∈R。这里，Φ的每一行可以看作是一个传感器（Sensor）,它与信号相乘，拾取（Acquisition）了信号的一部分信息。拥有了这M个测量和Φ，我们就可以近乎完美的重构原始信号了。听起来“相当”传奇，事实上，它基于如下严格的数学最优化（Optimization）问题：H目标函数min

24、

25、yˆ

26、

27、，且满足等式约束ΦΨyˆ=s0或者，可以写成Hmin

28、

29、s−ΦΨyˆ

30、

31、+λ

32、

33、yˆ

34、

35、20求解该最优化问题，得到变换域的yˆ，然后反变换，便可以得到时域的xˆ。公式中的2是我们熟悉的2-范数，而0是什么呢？是0-范数，也

36、就是向量yˆ中非零元素的个数。看起来很有道理，因为yˆ是待求的变换域向量，它是K稀疏的。使yˆ非零元素的个数尽量小，也就是