Compressed Sensing

压缩感知（Compressed Sensing，亦称压缩采样）是二十一世纪信号处理领域最具突破性的理论之一。该理论由数学家陶哲轩、坎德斯、罗姆伯格以及多诺霍等人在二零零六年前后系统建立。其最核心的洞见在于：当信号在某个变换域中表现出稀疏性，也就是大部分变换系数都等于零或者非常接近于零的时候，人们完全可以用远低于传统奈奎斯特-香农采样定理所要求的采样率来采集信号数据，然后利用数学优化方法近乎完美地重建出原始信号。这一理论的出现彻底颠覆了沿袭数十年的"先高速采样再将数据压缩"的两步处理范式，它将采样与压缩两个阶段有机地融合为一个单一过程，在医学核磁共振成像、雷达目标探测、无线通信系统、天文射电观测以及数据科学等众多领域引发了深远的技术变革。

1. 基本概念

1.1 稀疏性——压缩感知的信息论基础

压缩感知能够成立的第一个核心前提是信号必须具有稀疏性。所谓稀疏性，通俗来说就是指一个信号在某种合适的变换域中，它所包含的能量仅仅集中在很少的几个系数上面，而其余绝大部分系数都小到可以忽略不计。自然界中有大量信号天然具备这种稀疏结构。举例来说，一张风景照片在离散余弦变换域中，人眼能够感知到的视觉信息主要集中分布在低频部分，而高频细节部分的系数值通常非常微小；一段人的语音信号在傅里叶变换域中，能量仅占据有限的几个频率带，其余频带的能量接近于零；一张医学脑部断层扫描图像在小波变换域中也表现出高度稀疏的系数分布特征。从数学上来定义，如果一个长度为n的信号在变换后只有k个非零的表示系数，并且k远远小于n，那么人们就说这个信号是k稀疏的。稀疏性之所以如此关键，根本原因在于它揭示了信号真实信息含量的内在维度——虽然信号的表观长度是n，看上去需要n个数据点才能完整描述，但实际上它的有效自由度仅仅只有k。压缩感知的核心思想正是巧妙地利用了这种结构化的信息冗余，从而能够从远远少于n次的测量中成功恢复出原始信号。

1.2 测量过程与传统采样方式的对比

在传统的信号采集框架之下，人们必须严格遵循奈奎斯特-香农采样定理，以不低于信号最高频率两倍的速度进行采样，这样才能够保证在后续的处理过程中不会丢失任何信息。然而压缩感知采用了一种和传统做法完全不同的思路。它不是逐个时间点地去采集信号的幅度值，而是通过一个精心设计的测量矩阵将原始信号整体投影到一组维数较低的观测数据之上。具体来说，假设原始信号的长度是n，而我们想要进行的测量次数是m，并且m远远小于n，那么整个采集过程实际上就相当于从m个不同的线性投影当中去重构出原始的n维信号。这种做法相当于把数据压缩的步骤直接前置到了采样环节，也就是说在采样的同时就已经完成了压缩。测量矩阵中的每一个行向量都可以看作是一根探针，每一根探针从不同的角度对信号进行加权求和，而最终得到的观测向量则承载了所有这些综合信息的集合。由于测量次数m远远小于信号的长度n，这样得到的方程组是欠定的，也就是说在数学上存在无穷多个可能的解。压缩感知的理论魅力恰恰就体现在这里——它在严格的数学条件下证明，尽管方程组是欠定的，但是当信号具有稀疏性并且测量矩阵满足特定条件的时候，不仅可以从欠定系统中恢复出唯一的解，而且这个解对于测量噪声还具有很好的鲁棒性。

1.3 受限等距性质的重要意义

为了使得从欠定线性方程组中恢复稀疏解成为可能，测量矩阵必须满足一种被称为受限等距性质的数学条件。这个重要的条件是由坎德斯和陶哲轩共同提出来的。它的核心要求可以这样理解：测量矩阵必须能够近似地保持任意两个稀疏向量之间的欧几里德距离不发生严重变形。换句话说，测量这个过程不能把不同的稀疏信号给混淆掉——两个不同的稀疏信号经过同一个测量矩阵投影以后，它们的观测结果必须仍然能够被清楚地区分开来，而不能坍缩到几乎一模一样的观测值上面去。在实际应用中，最典型也是最常用的满足受限等距性质的测量矩阵有两种。第一种是高斯随机矩阵，这种矩阵的每一个元素都是独立地按照标准正态分布随机生成的。第二种是伯努利随机矩阵，这种矩阵的每一个元素以相等的概率取正一或者负一。这类随机矩阵之所以能够很好地满足受限等距性质，根本原因在于它们在高维空间中的方向分布是近似各向同性的，也就是说它们没有偏好任何一个特定的方向，因此任意一个稀疏向量在经过投影之后都能够以极高的概率保持原有的长度和方向关系。

1.4 采样次数的理论下限

一个自然产生的问题是：为了能够可靠地重建信号，测量次数m到底需要多大才算足够？理论研究表明，测量次数m和信号的稀疏度k之间需要满足一个明确的数量关系。具体来说，m必须不小于k乘以n除以k的对数再乘以某个常数因子。这个关系简洁而深刻地揭示了压缩感知中几个关键变量之间的相互制约：稀疏度越高，需要的测量就越少；信号长度越长，需要的测量也会相应增加，但这种增加是对数级别的，因此非常缓慢。这一结论为实际系统中的参数设计提供了明确的数学指导，使得工程师可以针对具体的应用场景来合理选择测量次数。

2. 核心重建方法

2.1 一范数最小化与基追踪方法

有了低维的观测数据之后，接下来的任务就是从这些数据当中恢复出高维的稀疏信号。这个问题本质上就是在无穷多种可能的解当中找出最稀疏的那一个。最直接的数学表达方式是让非零系数的个数达到最小，也就是所谓的零范数最小化。然而不幸的是，零范数最小化问题在计算上属于NP难问题，对于实际应用中碰到的信号规模和维度来说几乎是不可能求解的，因为它需要穷举所有可能的非零系数位置组合。值得庆幸的是，坎德斯和陶哲轩做出了一个非常关键的理论贡献。他们严格证明，只要测量矩阵满足受限等距性质，那么那个难以求解的零范数问题就可以等价地松弛为最小化系数绝对值之和的问题，也就是所谓的一范数最小化。一范数最小化是一个凸优化问题，它有多种高效的算法可以用来求解，比如内点法和单纯形法。这种方法在学术文献中通常被称为基追踪。从几何的角度来看，一范数最小化之所以能够诱导稀疏性，原因在于一范数球的形状具有尖锐的顶点和棱边，当线性约束所确定的可行域和一范数球相交的时候，最优解往往恰好落在坐标轴上，这就对应着只有少数几个非零系数的稀疏解。

2.2 贪婪类重建算法

除了基追踪这一类凸优化方法之外，在工程实践中还有一类被称为贪婪算法的重建方法被广泛使用，其中最具代表性的是正交匹配追踪。这种算法的思路是采用迭代的方式逐步逼近信号的稀疏解。在每一步迭代当中，算法首先从测量矩阵中挑选出和当前残差相关系数最大的那个列向量，然后把这个列向量加入到支撑集当中，接着利用最小二乘法来求解信号在当前支撑集上的最优估计值，最后再用更新后的估计值重新计算残差。上述过程不断重复，直到满足预设的稀疏度要求或者是残差的数值足够小为止。和基追踪方法相比，正交匹配追踪的计算效率明显更高，因此特别适合用来处理高维的大规模信号。然而它也有自己的缺点，那就是当测量矩阵的条件不太好或者信号中含有噪声的时候，它的重建稳定性相对较弱，有时候会错误地选入不相关的原子，而且一旦选错，后续的迭代就很难再纠正过来。

2.3 迭代阈值类算法

迭代软阈值算法是另一类非常重要的重建方法。这种方法把稀疏重建问题分解成为两个交替执行的步骤。第一个步骤是梯度下降，也就是沿着最小二乘误差下降最快的方向去更新当前对信号的估计值。第二个步骤是软阈值操作，也就是把更新之后的结果朝着稀疏的方向进行收缩——对于那些绝对值小于某个阈值的系数，直接把它们设置为零；对于那些绝对值大于阈值的系数，则把它们的绝对值减去阈值。以上两个步骤交替进行，直到算法收敛到一个稳定的解为止。迭代软阈值算法的最大优势在于它的实现非常简单，而且每一次迭代所需要的计算量很小，因此非常适合用来处理超大规模的信号重建问题。不过它的收敛速度相对来说比较慢，而且阈值参数的选择对于最终的重建质量有着很大的影响，需要根据信号和噪声的特性来仔细地调节。

3. 主要应用领域

3.1 医学核磁共振成像

压缩感知在医学成像领域最引人瞩目的应用当属加速核磁共振成像。传统的核磁共振成像扫描速度主要受到空间频率域中k空间逐行扫描方式的限制，患者往往需要在扫描仪中长时间保持静止不动才能完成全部数据的采集。这不仅导致设备的检查效率偏低，而且对于那些因为各种原因难以保持静止的患者来说也是一种不小的挑战。压缩感知核磁共振成像利用了人体解剖图像在小波变换域中高度稀疏的特点，它只需要随机采集k空间中大约百分之十到百分之三十的相位编码线，然后通过一范数最优化算法就可以重建出高质量的断层诊断图像。这样一来，扫描时间就从传统的二十分钟左右大幅缩短到了三五分钟，不仅显著提升了患者在检查过程中的舒适度，还大大减少了呼吸运动、心脏搏动以及肠道蠕动所带来的运动伪影对图像质量造成的不良影响。

3.2 雷达探测与无线通信

在雷达探测这个领域当中，回波信号在时间和频率所构成的平面上的目标分布通常是非常稀疏的——广阔的探测空间内通常只存在少数几个反射目标，其余绝大部分区域都是没有回波的空白背景。压缩感知雷达正是利用了这一稀疏性特征，它可以发射宽频带但是低占空比的稀疏波形脉冲，同时在接收端以远远低于传统奈奎斯特速率的采样率对回波信号进行模数转换，却仍然能够非常精确地完成测距和测速的任务。这样做的好处不仅在降低雷达系统对高速模数转换器的依赖，同时也大大减少了数据存储和数据传输的压力。模拟-信息转换器进一步把压缩感知的思想推广到了一般模拟信号的直接采集当中——它采用随机解调器或者是随机采样器在很低的采样率下去捕获宽带信号，为认知无线电和超宽带通信系统提供了一种低功耗的信号采样解决方案。

3.3 天文观测与数据科学

射电天文学中的干涉成像是压缩感知在早期就展现出巨大价值的领域。射电望远镜阵列的基线分布在地球自转的作用下，在空间频率域中形成的是稀疏而且不均匀的覆盖轨迹。传统的傅里叶变换方法很难从这种稀疏而且不完整的数据当中重建出高质量的星体图像。压缩感知则利用天文图像在小波基下的稀疏表示，从稀疏的空间频率覆盖数据当中成功地恢复出了具有高动态范围和低旁瓣伪影的天体图像，在脉冲星观测和黑洞事件视界成像当中都发挥了极为重要的作用。在计算机视觉领域当中，图像去噪、图像修复、图像超分辨率重建以及视频压缩感知等方向，稀疏先验模型已经成为不可或缺的标准工具。此外，压缩感知的基本思想还进一步渗透到了基因数据分析、无线传感器网络和物联网等领域当中，为那些在有限资源条件下需要高效数据采集的场景提供了坚实的理论基础。

4. 局限性与前沿发展

压缩感知当然不是一种放之四海而皆准的万能方案，它本身也存在若干不容忽视的局限性。第一个局限是重建过程通常需要求解大规模的凸优化问题，计算成本远远高于传统的线性重建方法，因此在那些对实时性有严格要求的应用场景当中仍然面临不小的挑战。第二个局限是信号在变换域中的稀疏程度并不能事先百分之百地得到保证——对于那些纹理非常复杂或者随机性很强的信号来说，稀疏性假设可能并不充分成立，重建的质量也会随之明显下降。第三个局限是理想的受限等距测量矩阵在硬件实现过程中会遇到实际困难——完全随机的测量模式在光学系统、电磁传感器和模拟电路当中往往很难精确地实现出来，这给实际系统的设计增加了额外的硬件复杂度和开发成本。

近几年以来，深度学习方法和压缩感知的深度融合开辟了令人兴奋的新研究方向。研究者们设计出了一种将传统迭代优化算法的每一步都展开为神经网络层的网络架构，比如把迭代软阈值算法展开之后得到的深度网络以及把交替方向乘子法展开之后得到的网络。这些深度网络可以利用大量的训练数据去学习最优的变换基和阈值参数，从而在极低的测量数下实现了比纯优化方法更加优越的重建效果。生成对抗网络和变分自编码器也被用来当作信号的自然先验模型——通过让模型去学习自然信号的内在流形分布，替代传统的手工设计稀疏变换，进一步提升了压缩感知在极低采样率条件下的重建鲁棒性和图像质量。一比特压缩感知是另一个非常活跃的研究方向，它把测量值的量化过程推向了极致——每一个观测值仅仅保留正或者负的符号信息，在这种极端条件下去研究信号重建的理论极限和实用算法。分布式压缩感知则重点关注多传感器网络的应用场景，它利用多个测量信号之间共同分享的稀疏模式来实现联合重建，从而进一步降低了整套系统的数据采集成本和通信带宽需求。

5. 总结

压缩感知可以被视为二十一世纪信息科学领域中最具里程碑意义的理论贡献之一。它通过严格而优雅的数学工具，充分利用信号内部隐藏的稀疏结构，有力地回答了如何从远远少于传统理论所要求的信息量中精确重建信号这样一个根本性的科学问题。从更加宏观的视角来看，压缩感知的革命性不仅仅体现在采样效率获得了数量级的提升，更重要的是它重新定义了人们对采样本质的理解——它将信息获取的约束条件从信号带宽的限制转移到了信号内部结构之上。随着硬件计算能力的持续进步和深度学习方法的不断注入，压缩感知正在从学术研究的实验室走向临床诊断设备、通信基站和空间探测器的实际部署，为现代信息处理系统的设计提供了一种全新的范式选择。