信号处理领域的利器-压缩感知

随着信息量的不断增多，数据的采集、传输和存储设备正面临着日益严峻的压力;同时数据处理过程中也会伴随着信息泄露的风险，一部分数据的丢失都有可能威胁生命和财产的安全，而如今数据泄露已经屡见不鲜。因此在大数据时代，人们亟需寻找一种新的数据处理方式来降低信息处理过程中数据泄露风险，同时也释放内存、传感器等硬件设备的压力。

压缩感知理论是在这样的背景下产生的一种新兴的信号采集和编解码理论。该理论指出，不管是何种类型的信号，其在原始域或者某些变换域中，总是存在稀疏或者可压缩的表示，在传输过程中可用远低于传统奈奎斯特采样的线性投影值，实现对信号的准确或者高概率重建。

这一理论带来了信号采样理论的变革，对于信息安全也有重要的意义。学者将压缩感知应用至图像的加密与传输、信息的安全编码技术、信息的安全存储、无线传感器网络的数据采集之中，有很多的信息处理以及信息安全领域学者对压缩感知产生了较浓厚的研究兴趣。本文首先简单介绍压缩感知的诞生，然后扼要地介绍一下理论内容和一些应用方法，最后结合实际谈一谈目前一些比较成功的应用。

一.压缩感知的起源

“压缩感知”思想最早出现在一篇2000年左右的博士论文《Near-Optimal Signal Recovery From Random Projections》[1]中。它的发现可以说是一次意外，当时加州理工学院教授Emmanuel Candès在研究名叫Shepp-Logan Phantom的图像，这种标准图像常被计算机科学家和工程师用来测试图像还原算法。检查的图像质量非常差，充满了噪声，他使用了L-1范数最小化的数学算法来去除噪声条纹，结果算法真的起了作用。这种算法是将一个NP难问题转化为一个凸优化问题，也将压缩感知的思想充分的体现：通过对信号不完备观测后通过优化算法来高概率还原信号(如图1所示)。“就像给出10位银行卡账号的前三位，我就能猜出后七位一样，并且，屡试不爽。”这就是压缩感知思想的开端。

图1 加入各种噪声后的图像还原图

后来，Candès与陶哲轩进行了交流，陶哲轩也开始思考这个问题，上述交流成为第一篇关于压缩感知论文的基础。另外一位奠基人是Donoho，他的一篇代表作《Compressed sensing》[2]可以说是第一篇较为完整系统地阐述压缩感知原理以及推导的论文。

以上这些都是压缩感知的起源。

二.压缩感知理论内容以及获取和求解方法

压缩感知理论本身的含义为“通过对信号的高度不完备线性测量的高精确重建[3]”，在该理论框架下，采样速率不再取决于信号的带宽，而在很大程度上取决于两个基本准则：稀疏性和非相关性。

压缩感知理论

主要包括三部分：

(1)信号的稀疏表示;

(2)设计测量矩阵，要在降低维数的同时保证原始信号x的信息损失最小;

(3)设计信号恢复算法，利用M个观测值无失真地恢复出长度为N的原始信号。

理论依据[4](主要由陶哲轩以及Candès推导和证明)

(1)设长度为N的信号X在某个正交基Ψ上是K-稀疏的(即含有k个非零值);

(2)如果能找到一个与Ψ不相关(不相干)的观测基Φ;

(3)用观测基Φ观测原信号得到长度M的一维测量值M个观测值Y，K

(4)那么就可以利用各种优化方法从观测值Y中高概率恢复X。

压缩感知高概率重构信号方法流程如下图2所示：

图2 压缩感知信号恢复流程图

数学表达

压缩感知方程为：y=Φx=ΦΨs=Θs。(图3)

其中设x为长度为N的一维信号，稀疏度为k(即含有k个非零值)，y为长度为M的一维测量值，Φ为观测矩阵，Ψ为稀疏基，s为稀疏系数。

然后将原来的测量矩阵Φ变换为Θ=ΦΨ，解出s的逼近值s’，则原信号x’ = Ψs’。

图3 压缩感知方程表示图

压缩感知获取和求解方法

压缩感知在应用时主要存在两个问题：

问题1：如何设计观测矩阵和信号的稀疏基从而获取到较好地观测值，求解方法如下表1：

表1 压缩感知获取策略表

问题2：如何有效地进行信号的重构即求出压缩感知方程中信号x的近似解。求解方法如下图4所示：

图4 压缩感知信号重构方法

三.压缩感知的应用领域和应用事例

压缩传感技术是压缩感知理论的应用之一。它是一种抽象的数学概念，最初用在图像处理之中，并逐步扩展应用到成像以外的许多领域。