香港大学电机电子工程学系 高效计算方法研究小组 沙威 2008年11月20日 Email: wsha@eee.hku.hk
Personal Website: http://www.eee.hku.hk/~wsha
到了香港做博士后，我的研究领域继续锁定计算电磁学。我远离小波和计算时谐分析有很长的时间了。尽管如此，我仍然陆续收到一些年轻学者和工程人员的来信，和我探讨有关的问题。对这个领域，我在理论上几乎有很少的贡献，唯一可以拿出手的就是几篇网上发布的帖子和一些简单的入门级的代码。但是，从小波和其相关的理论学习中，我真正懂得了一些有趣的知识，并获益良多。我深切地感到越来越多的学者和工程师开始使用这个工具解决实际的问题，我也发现互联网上关于这方面的话题多了起来。但是，我们永远不能只停留在某个阶段，因为当今学术界的知识更新实在太快。就像我们学习了一代小波，就要学习二代小波；学习了二代小波，就要继续学习方向性小波（X-let）。我也是在某个特殊的巧合下不断地学习某方面的知识。就像最近，我的一个友人让我帮她看看“压缩传感”（Compressive Sensing）这个话题的时候，我的兴趣又一次来了。我花了一个星期，阅读文献、思考问题、编程序、直到写出今天的帖子。我希望这篇帖子，能对那些没进入且迫切想进入这个领域的学者和工程师有所帮助。并且，我也希望和我一个星期前一样，对这个信号处理学界的“一个大想法”（A Big Idea）丝毫不了解的人，可以尝试去了解它。我更希望，大家可以和我探讨这个问题，因为我到现在甚至不完全确定我对压缩传感的某些观点是否正确，尽管我的简单的不到50行的代码工作良好。在这个领域中，华裔数学家陶哲轩和斯坦福大学的统计
学家David Donoho教授做出了重要的贡献。在这个引言中，我用简单的关键字，给出我们为什么需要了解甚至是研究这个领域的原因。那是因为，我们从中可以学习到，下面的这些：矩阵分析、统计概率论、拓扑几何、优化与运筹学、泛函分析、时谐分析（傅里叶变换、小波变换、方向性小波变换、框架小波）、信号处理、图像处理等等。所以，我们有什么理由，拒绝这个有意思的东西呢？让我们开始吧。
传统思路——正交变换 对于一维的信号x∈R
N×1
，大多数情况下，信息是冗余的。我们可以通过正交变换的
H
H
方法来压缩它。正变换：y=Ψx，反变换x=Ψy。这里，ΨΨ
=ΨHΨ=I，Ψ∈CN×N，
I是单位矩阵。对于y∈CN×1，能量较x集中，本质上去除了x中的相关性。因此，我们只
保留K个较大的分量，而把其它N−K个置为零。通过反变换，我们能够近乎完美的重建原始信号。因为，那N−K个变换域系数的贡献，实在微乎其微。具有这样性质的信号被称为K“稀疏”（Sparsity）的。于是，我们有了如下编码解码的策略：
编码：构造Ψ，做正变换y=Ψx，保留y中最重要的K个分量，和其对应的位置。
ˆ=Ψyˆ。 解码：把K个分量放回到对应的位置，其它位置填0，构造Ψ，反变换x
HH
ˆ||2=||y−yˆ||2≤δ，δ是一个小而解码能否近乎得到原始信号呢？显然，我们希望||x−xˆ||2/||y||2≤δ。 的常数。但更有效的是用相对误差||y−y
但这种编码解码方法有些缺点：1、考虑到香农（Shannon）采样定理，为了获得很好的信号分辨率，采样间隔会很小，造成了原始信号长度会很长，因此变换过程会消耗很长的时间。2、K个需要保留的重要分量的位置，是随着信号的不同而不同的。因此，这种策略是“自适应”（Adaptive）的，且需要分配多余的空间存储这些位置。3、一旦在传输过程中K
个分量中的某几个丢失了，后果可想而知。如果我们制作一个音频设备，1将带来电力的消耗和用户的不满，2将带来存储空间的增加，3将带来较差的抗干扰能力。
新的思路——压缩传感 压缩传感（Compressive Sensing）是一个很有意思的新的方向。它也正成为信号处理领域的“A Big Idea”。对于信号x∈RMeasurement），s=Φx。Φ∈R
M×N
N×1
，我们可以找到它的M个线性测量（Liner
。这里，Φ的每一行可以看作是一个传感器（Sensor）,
它与信号相乘，拾取（Acquisition）了信号的一部分信息。拥有了这M个测量和Φ，我们就可以近乎完美的重构原始信号了。听起来“相当”传奇，事实上，它基于如下严格的数学最优化（Optimization）问题：
ˆ=s ˆ||0，且满足等式约束ΦΨy目标函数min||y
或者，可以写成
H
ˆ||2+λ||yˆ||0 min||s−ΦΨHy
ˆ，然后反变换，便可以得到时域的xˆ。公式中的2是我求解该最优化问题，得到变换域的y
ˆ中非零元素的个数。看起来很们熟悉的2-范数，而0是什么呢？是0-范数，也就是向量y
ˆ是待求的变换域向量，它是K稀疏的。使yˆ非零元素的个数尽量小，也就有道理，因为y
是保留了尽量少的重要的K个分量，显然这几个分量可以近乎完美重构x。我们回到传统的思路，这K个分量是我们在变换域“自适应”找的，而该优化算法也可以使我们找到这K个分量。
这就足够了吗？显然不行，我们仍然没有探讨测量矩阵Φ需要满足的性质。我们用极限分析法。如果我们把Φ构造成和Ψ极端相似（Coherence）的矩阵，也就是拿出Ψ的
H
⎛sM×1⎞
⎟ˆ，我们将得到yˆ=⎜前M行。用这个算法求y⎜0(N−M)×1⎟，这显然是错误的。也就是说，你
⎝⎠
强迫的认为前M个变换域分量是重要的。而事实是，重要的K个分量的位置我们事先是不知道的，是随着信号的不同而不同的。当然，你可以将Φ恰好构造成对应最重要分量的K行，
得到正确的结果。而这种的做法要付出的概率代价
1K
。也就是说，你必须穷举C次，才NKCN
能得到你想要的结果。但是，即使你有幸碰到了它，也并不能肯定这个结果就是对的。因此，我们选择Φ和Ψ极端不相似（Extremely Incoherence）。于是，Φ很大程度上和随机（Randomness）这个词相联系，它可以是满足高斯分布的白噪声矩阵，或贝努里分布的±1矩阵（也称作Noiselet）等等。除此之外，我们希望线性测量有稳定的能量性质：
H
ˆ||2||ΦΨHy1−δ≤≤1+δ，也就是它要保持K个重要分量的长度。综合上面的，我们有
ˆ||2||y
了如下编码解码的策略：
编码：构造Φ，生成测量s=Φx，保留s。
解码：构造同样的Φ，构造任一种正交变换Ψ，根据s重构x。
压缩传感的优势：1、非自适应（Non-Adaptive）的，一开始就可以传输长度较短的信号，甚至突破采样定理的极限。2、抗干扰，s中任何一项都是重要的，或者说不重要的。丢失了某几项，仍然可以完美重构。它的缺点：1、实际中，s的长度一般是重要分量长度的4倍，才能近乎完美重构。数学上更严格的，M≈4K或者M≥Klog2(
H
N
)。2、重构K
（恢复）算法是NP问题。即使将0-范数转化为1-范数，由于其不可微性（Indifferentiable），算法的计算复杂度仍然很高。它的应用前景广泛：低成本数码相机和音频采集设备；节电型音频和图像采集设备；天文（图像本身就稀疏，例如天空的星星）；网络；军事（用很简易
的摄像机随机记录场景，可以完全重构军事地图）；超宽带（雷达信号处理）。这里，值得指出的是，美国的工程学家已经设计出了实际的产品。
快速算法——正交匹配追踪 对于0-范数的优化问题，实际上是NP问题，就是在多项式时间内难以求解，甚至无法验证解的可靠性。于是，我们必须将0-范数换一下，变成1-范数。为什么不是2-范数呢，那样就会简单多了。毕竟2-范数的优化问题可以转化成2次型问题，而1-范数，
ˆ||1=∑|yˆi|，在0点处不可导，因此无论是梯度算法、矩阵求导等等手段都变得相形见||y
i
绌。因此，基于1-范数的优化算法需要特殊处理，且复杂度很高。下面我们来解释下为什么要用1-范数，而不是2-范数。我们令恢复（Recovery）矩阵T=ΦΨ，则等式约束可
H
ˆ=s。yˆ中未知数有N个，方程只有M个，且M< 两个元素待求）可认为它就是一条直线。而范数约束呢？0-范数是一个十字架，因此它的最外侧（范数的最小值）是4个点。所以其和直线的交点，必然在坐标轴上。也就是说，能使 ˆ产生更多的0，这正是我们想要的“稀疏”的结果。2范数是一个圆，因此它的最外侧边y 界和直线的交点（就是切线的概念），以压倒性的概率不在坐标轴上，除了直线的斜率恰好为0或者无穷大。其实直线的斜率恰好为0或者无穷大，是不可能的，因为Φ和Ψ极端两者相似，才会发生斜率恰好为0或者无穷大的情况（因不相似。只有Φ取Ψ的某一行时，此，你的胜算只有1/C2，但你不知道哪个是对的。）。依上所述，用2-范数优化的结果，使 1 H ˆ几乎没有0，这是我们不期望的。而1-范数是一个菱形，四个角都在坐标轴上，因此它和y 直线的交点以压倒性的概率落在坐标轴上。这就是我们要用1-范数的原因。事实上，p范它的外边界都向中心凹（Concave）。而p>1，外边界向外凸（Convex）。数满足，0≤p<1， 所以前者的外边界和直线的交点无疑落在坐标轴上。根据这个几何解释，我们可以将问题转化成： ˆ||2+λ||yˆ||1 min||s−Ty 这显然是一个非线性（Non-Linear）的凸（Convex）优化问题。 ˆ||1，在0点导数不众所周知，对于优化问题，我们一般用梯度的方法来求解。而对||y 存在，因为这个点正好位于两条直线的交点上，左右导数不相等。这也正是很多数学方法的考虑。像子梯度（Subgradient）法、平滑近似法（Smooth Approximation）等等。我们暂不谈这些方法，因为它需要特殊的数学背景。我们谈一谈工程领域最常用的正交匹配追踪法（Orthogonal Matching Pursuit）。它的思想本质上还是来自于这个K“稀疏”。我们绕了一圈，还是为了找这K个关键的分量。既然是关键，显然它的系数的绝对值应该比其它 ˆq在yˆ中对应的N−K个分量大得多。为了简单起见，我们先假设K=1，唯一非零元素y ˆ就是恢复矩阵T的第q列Tq与yˆ中的非零元素yˆq的乘积，ˆq=sq。位置在q。于是Ty即Tqy 且||s−sq||2/||s||2<δ。换句话说，T的第q列与s的相似程度最高，即 | 算出的Y，进 正好能与Tq正 交交。这也是为什么这个方法叫“正交”匹配追踪的意思了。而匹配，显然是你找到了最大的 | 个即可（但第一次找到的那列要排除，因为它已经保留了下来。）。于是，找到使 ˆq2⎞ˆq2⎞⎛y⎛y ⎟。这里，Tq1是我们第一次找到的那一列，Tq2是⎟⎜⎜||2最小的那个⎜||s−(Tq2,Tq1)⎜⎟ˆq1⎟ˆq1⎠⎠⎝y⎝yˆq2⎞⎛y ⎟被更新了，由原来ˆq=⎜。可以看出，y我们新找到的那一列（也要记住它的列号q2） ⎟⎜yˆ⎝q1⎠ ˆ中对应的位置了。的一个变成两个了，也就是我们找到两个在变换域最关键的元素和其在y 令Tq=Tq2,Tq1，余量rn又一次被写为：rn=s− () Tq。我们再一次看到了施密 特正交化的影子。继续上面的步骤，直至找到变换域所有K个最重要的分量。也就是说，正交匹配追踪的迭代次数m≥K。实际操作上只要满足||rn||2/||s||2<δ，迭代就可以中止了。最后，假设正交变换Ψ是傅里叶变换，我们来分析下计算复杂度。生成恢复矩阵T，采用FFT快速算法，需要计算复杂度O(MNlog2(N))；找到T中匹配的列向量需要 ˆq和rn需要O(m2M)次操作。考O(mNM)次操作，注意m是算法需要的迭代次数；求解y 虑到m~K，M~Klog2(N/K)，总计算复杂度可以控制在O(N[log2(N)])以下。到此为止，我们完成了压缩传感所有基础的理论和操作。 2 小结——压缩传感的特点 最后，让我们总结一下，压缩传感理论的关键字：稀疏（Sparsity）、不相关（Incoherence）、随机性（Randomness）、非自适应（Non-Adaptivity）、非线性（Non-Linearity）、不可微（Indifferentiability）。从这些词语可以看出，压缩传感理论是对传统理论的颠覆。这种颠覆最令人振奋的表现，就是它突破了香农采样定理的极限，能以随机采样的方式用更少的数据采样点（平均采样间隔低于采样定理的极限），来完美地恢复原始信号。科学也就是在对传统理论不断地颠覆和修正中才得以进步和发展。 为了大家更好的理解压缩传感，在我的个人网站上，给出了一个没有经过优化的简单的操作代码，希望对大家有所帮助。此外，由于此帖含有大量公式，我用了类似Latex的语法 敲出了它，一个更好阅读的pdf版本也放在了我的个人网页上。最后，如果阅读这篇帖子的人，试图转贴的话，请注明这篇帖子的出处和作者，以此作为对作者工作小小的肯定和支持。（程序和帖子的PDF版下载地址：http://www.eee.hku.hk/~wsha/Freecode/freecode.htm） 因篇幅问题不能全部显示，请点此查看更多更全内容