压缩感知

信号处理领域中的一个常见问题就是从一系列的采样中重建原本的信号。一般而言，未被采样的部分信号，是不可能重建出来的。然而通过借助对于信号（性质）的预先了解或合理假设，完美地通过一系列采样重建原信号就成为了可能。随着科学的发展，数学家们逐步增进了如何作出合理假设的能力，并慢慢了解到在何种情况下可将这些假设一般化、推广化。

信号处理领域中的一次较早的突破是奈奎斯特采样定理的提出。这一定理证明了若信号的最高频率小于采样频率的一半，便可完美地从采样结果中恢复原本信号，因此定义了采样定理取样频率的下限。这种数据获取模式先采样再压缩，需要大量的时间压缩和空间存储数据，这限制了高速信号处理的发展，也给硬件的实时处理带来了极大的挑战。

在2004年左右，Emmanuel Candès、陶哲轩和David Donoho证明了在已知信号稀疏性的情况下，可能凭借较采样定理所规定更少的采样数重建原信号，这一理论也是压缩感知的基石。

一般来说，一个常见的线性系统问题，有m个方程式, n个未知数，可以被定义如下：

在通讯系统之中，y是被收到的讯号，而s则是要被重建的讯号，一般来说会有以下两种情况：

1.，也就是说方程式的数量大于等于未知数的数量，这种情况发生的时候就可以利用最小平方法(least squares, LS)去求得最接近的解，求得的解如下：

是拟反矩阵(pseudo inverse matrix)。

2.，也就是未知数的数量比方程式的数量来的多，这个方程组就被称为欠定线性系统，一般而言有无数个解，因此我们无法使用最小平方法去求得要重建的讯号。

但是，如果这个欠定线性系统只有唯一一个稀疏解，那么我们可以利用压缩感知理论和方法来寻找这个解。值得注意的是，并不是所有欠定线性方程组都具有稀疏解。

举例来说，是一个欠定线性系统，我们会有无限多个解可以满足这个方程式，然而当我们加入稀疏性的特性之后，也就是说之间只有一个有值，另外一个必定为0，我们就可以很轻易地得到这个欠定线性系统的解为或是，这个就是压缩感知的最主要的精神所在。

从下图我们可以轻易地了解，当解具有稀疏的特性时，就可以从欠定线性系统有无限多组解的情况变成可以利用最小平方法找出解的情况。

当讯号具有稀疏的特性时，线性系统就可以从无限多组解的情况，变成有解的情况。

一个向量的稀疏性可以被定义如下：

也就是计算一个向量之中非零的个数，举例来说，如果，，因此目标的解就会变成如下：

希望能在非零个数越少的情况之下，找到最有可能的解。然而在实际中，最优化L0范数是一个NP难的问题，需要穷举s中非零值的所有排列可能，因而无法求解。通常采取的手段是对L1范数进行最优化求解，优化目标则变为：

或是使用匹配追踪系列算法、迭代阈值法以及专门处理二维图像问题的最小全变分法等求得次最优解的算法进行计算。

有限等距性质(RIP)是压缩还原算法中常常可以看见的名词，主要可以被用来分析还原算法的表现好坏。其定义如下：

其中的代表传感矩阵，代表的是信号能量，可以表示如下：

因此整个式子可以视为信号跟传感矩阵的相似程度，也就是做完转换后的能量，要被RIP限制住，而RIP要求。

在理论上，为了确保信号重建的准确度，需要令所采用的取样矩阵各行列之间相干性（coherence）尽量地低，且须矩阵元素（element）取值随机性尽量地高。

相干性(coherence)可以简单定义如下：

也就是取样矩阵任两个相异的行做内积后，取绝对值所产生的最大值，可以用来衡量信号重建的准确度。

而目前对于采样矩阵有下列几种选择可以使还原重建度有一定品质：

1. 对n个A的行向量在m维的单位半径球面上进行随机采样

   对任一个都采用相同独立的高斯分布N(0,)进行随机采样

   对任一个都采用如下式相同独立的分布进行随机采样

除了上述的可能，现在也已经证实任何一个sub-gaussian的分布，都可以成为一个很好的测量矩阵，也就是说具有很好的还原效果。

而上述矩阵之所以常被拿来使用，主要是因为皆已经被验证具有高机率性满足有限等距性质，也就是相干性非常低，因此使用此方式进行讯号取样后，仍可确保在信号具有足够稀疏性的前提下得到较佳的压缩感知重建效果。

且当使用上述矩阵时，只要讯号x的非零数目成下列关系，可以确保讯号倍被完美还原。

而C是一个根据不同情况而改变的常数。

但是在上述矩阵时，所需要的数据存储量过于庞大——每个矩阵元素都要单独记录，且数据类型一般为浮点数——这就促进了简化取样矩阵的研究；目前被提出的简化取样矩阵主要包括两种：结构简化采样矩阵与数值简化采样矩阵。

目前较常被使用的两种结构简化采样矩阵为循环矩阵与常对角矩阵

循环矩阵的形式为下式：

常对角矩阵的形式为下式：

，

其中。

可以发现到，若采用循环矩阵作为测量矩阵的话，我们只需要存取一列的矩阵元素；相反地，若使用常对角矩阵，除了第一列的矩阵元素外，需要额外储存第一行的矩阵元素。

但是经过实验发现，常对角矩阵的相干性是低于循环矩阵的，因此使用者可以依据自己的使用环境，来找到一个平衡点。

采用这两种矩阵进行压缩感知取样时，可以大幅降低储存成本，也为此算法的前端感测器大幅降低实现门槛。

数值简化采样矩阵普遍将原有的、按照高斯分布随机取值的采样矩阵元素以数值上更为简单的元素取代，但在分布上维持矩阵元素的分布随机性——即缩减了储存浮点数这一方面的成本。

一种较为基本的数值简化采样矩阵是0-1伯努利矩阵，其中的元素仅有0和1两种，分布模式为相同独立的伯努利分布（identical independent Bernoulli distribution）。

对于每一个矩阵元素，该分布的概率质量函数为：

压缩感知利用了很多信号中所存在的冗余（换言之，这些信号并非完全是噪声）。具体而言，很多信号都是“稀疏”的；在适当的表示域中，它们的很多系数都是等于或约等于零。

在信号获取阶段，压缩感知在信号并不稀疏的域对信号进行线性测量。

为了从线性测量中重构出原来的信号，压缩感知求解一个称为L1-范数正则化的最小二乘问题。从理论上可以证明，在某些条件下，这个正则化最小二乘问题的解正是原欠定线性系统的稀疏解。

基追踪（basis pursuit）是一种信号重建算法，被广泛地用于压缩感知领域，属于数学最优化问题的范畴，形式为。

其中s是n×1向量，表示输出（信号），y是m×1的测量向量，A是m×n的“转换矩阵”或称作“测量矩阵”，其中M < N。

基追踪常在需要完美满足欠定线性方程组系统中时被应用，且要求解在L₁基准下为最稀疏的。

若应用情景允许降低对完美恢复的要求，以换取更加稀疏的解s，降噪基追踪（basis pursuit denoising）更为适用。

匹配追踪（Matching pursuit）是一种稀疏近似运算，旨在找到多维数据在某个超完备字典（dictionary）上映射的“最佳匹配”。其基本的概念就是要用来自的函数组（称为基元，或atom）的加权和来表示希尔伯特空间上的信号：

其中表示被选取基元的序数，是每个基元的加权常数。对于固定的字典，匹配追踪会先找到与信号间内积最大的一个基元，再减去该基元带来的影响，然后重复找寻影响力次大的基元直到信号被较好地分解。

相较而言，以傅里叶级数表示的信号来说，字典是构建于正弦基函数之上的。信号处理领域中傅里叶分析的主要缺点就在于它只能提取出信号中常存的特征，而不能适应当前的分析目标信号。

若采用一组极端保险、带有大量冗余的字典，我们就能够找到可以完美匹配信号的函数组。在对信号进行编码与压缩时，最好是能够找到一组映射，使加权和中的大部分系数都接近零（具有“稀疏性”）。

正交匹配追踪(Orthogonal Matching Pursuit)是匹配追踪的特殊形式，正交匹配追踪的算法与匹配追踪相同，但是正交匹配追踪不会重复使用同一个基元来进行匹配，因此会比匹配追踪更快收敛。

迭代阈值算法(Iterative Shrinkage-Thresholding Algorithm)是上述基于贪婪算法(Greedy Algorithm)之匹配追踪与正交匹配追踪的替代算法，迭代算法主要是透过不断的投影和取阈值来进行收敛，而他在每次迭代中，都还可以进行其他优化例如:Wigener 滤波，不仅可以降低运算复杂度，也可以提高还原品质。

正交匹配追踪是一个用来解决压缩感知问题的算法，在一定的复杂度之下有不错的表现，他背后最主要的想法是源自于贪婪算法(Greedy Algorithm)，以下将逐步解说。

首先这个问题被定义为：y=Ax，目标是要借由已知的y向量、A矩阵，来还原x向量，他会利用迭代的方式，逐步找出x向量当中最有可能是非零的位置。

一开始会有一个空集合，以及剩余的部分，每次迭代都会从找出一个A矩阵投影到剩余有最大值的位置，把这个位置加到之中，并从当中移除，最后再更新剩余。利用迭代的方式，不断地找出x向量当中最有可能非零的位置，直到达到算法停止条件。

正交匹配追踪算法

在正交匹配追踪算法的基础上，Needell等人提出了正则正交匹配追踪（Regularized Orthogonal Matching Pursuit,ROMP）算法对于所有满足约束等距性条件的矩阵和所有稀疏信号进行重构。之后，引入回溯思想的压缩采样匹配追踪（Compressive Sampling Matching Pursuit,CoSaMP）算法被提出。

在实际应用中，稀疏信号非零元素个数K往往是未知的，而上述的匹配追踪算法都是建立在稀疏度K已知的基础上，因此出现了对K自适应的稀疏自适应匹配追踪（Sparsity Adaptive Matching Pursuit,SAMP）算法，它通过固定步长来逐步逼近进行重建，可以在稀疏度K未知的情况下获得较好的重建效果。

迭代阈值算法是从Relaxation Method启发而来，Relaxation Method是用于解决具有稀疏性的线性系统。

在迭代阈值算法中，问题一样是被定义为：

而在此算法中，每一次的迭代主要分成两部分：1、寻找新的解。2、更新残值。第一阶段，主要是利用投影的方式找到更新的向量方向，再透过取阈值的方式来进行优化。

而是relaxation parameter，且。

而就是阈值函数(thresholding function)，主要就是为了使迭代的过程中，逐渐逼近具有稀疏性性质的解，而目前主要有两大类取阈值的方式：硬阈值函数(Hard Thresholding Function)与软阈值函数(Soft Thresholding Function)。

硬阈值函数就是将小于阈值(thr)的解，一律通通过滤成0。

而软阈值函数则是使用较为平滑的方式，将值逼近于稀疏性的解

，而是Indicator Function

而第二阶段，则是利用新算出来的来进行残差更新。

之后一直等到规定的循环数抵达即完成还原。

而此算法是Landweber iteration的变形，若我们没有加入阈值函数的话，就会收敛到。

压缩感知与包括欠定系统、群验、稀疏编码、复用、稀疏采样等。在成像科技领域，亦有许多技术如（编码孔与计算摄影学）与压缩感知相关。亦有许多在不同技术完成度下将压缩感知实现的案例。

压缩感知技术被用于手机摄像头传感器设计中。这一技术使得在获取图像时所耗费的能量大大降低，可达原先耗费的15分之一——当然，需要引入复杂的解压算法；这一运算可能会需要脱机状态下的预先安装、设置。

压缩感知亦被用于实现单像素摄影。贝尔实验室运用了这一技术，用无镜片单像素相机在栅格中随机选取的孔隙处拍照，以达到成像效果。随着拍照次数的逐渐增多，照片质量也会逐步提高；一般来说，这种技术较之传统的摄影成像技术仅仅需要一小部分的数据占用量，且能完全避免与镜片或聚焦相关的故障或失常；参见 。

压缩感知可被用于增加通过单幅全息图中所能得到的立体像素的数量改进全息摄影技术中的图像重建问题。在光学全息图或毫米波全息图采样率不足的情况下，这一技术也能够被用于图像检索以作出改善。

压缩感知目前被用于面部识别应用之中，参见。

压缩感知也被应用在医疗影像上，特别是核磁共振成像(Magnetic Resonance Imaging, MRI)，具有稀疏的特性，因此能使用压缩感知的技术。在过去核磁共振成像会因为物理学、生理学上的限制，而有扫描时间较长的问题，如今压缩感知利用核磁共振成像具有的稀疏特性，来改善成像品质以及降低所需要量测数量，能有效缩短核磁共振的扫描时间，近期相关的压缩感知算法也被广为讨论，可以参见 、 与，其中涉及的重建方法包括ISTA、FISTA、SISTA等。

一般来说地震成像既不稀疏，也不可压缩，具有高维度、大面积的特性，因此会耗费大量的量测以及运算时间，所以希望能降低取样的次数，同时能保有原本的品质。因此有人利用压缩感知技术将取样以及编码同时进行，来达到降低维度的目的，最后再透过压缩感知的还原算法进行还原，可以参考。

在通讯系统当中会遇到高带宽的问题，因此会需要较高的取样频率，然而其中的信号可能含有的资讯是远小于带宽的，因此就会浪费软、硬件的资源来进行取样。所以有人提出用类比信息转换(Analog-to-Information Converter, AIC)取代类比数位转换(Analog-to-Digital Converter, ADC)，利用随机解调(Random Demodulation)的方式，来降低所需要的取样次数，对于在时频上有稀疏特性、宽频的信号特别适合，可以参考。

压缩感知在被用于旨在利于网络管理的网络诊断应用中时带来了极佳成效。对网络延时的估计和网络拥塞的探知均可被归纳、建模为非定性的线性方程组系统，其中的参数矩阵正是所分析网络的路由选择矩阵。此外，在互联网情景中，网络路由矩阵常常能够满足压缩感知技术所要求的几个基本要素：低相关性、稀疏性及（可能的）R.I.P条件，请参见 。

目前，基于压缩感知技术的商用短红外相机已被推出 。这些相机的光敏度大约从0.9µm到1.7µm，在上述波段上，人类的肉眼是无效的。

随着通讯要求的带宽越来越大，因此可用的频带从微波(Microwave)转到毫米波(mmWave)的频段，虽然可用的带宽增加，然而会受到更严重的通道衰减，所以波束成型的技术被提出，结合天线阵列来对抗通道衰减的效应。然而大量的天线阵列会使得做通道估测的复杂度上升，传统的做法是使用最小平方法(Least Square, LS)来进行通道估测，不过有人发现通道具有稀疏的特性，因此提出了利用压缩感知的技术，进行压缩通道估测(Compressed Channel Estimation, CCS)，相较最小平方法，不仅复杂度降低，还能达到更低的错误率以及延迟性。

利用压缩感知理论可以恢复出稀疏信号的特性，压缩感知理论被广泛应用于波达方向估计(Direction of Arrival,DOA)中。基于压缩感知的波达方向估计中将信号源矩阵看作是一个稀疏矩阵，在已知采样矩阵和阵列流形矩阵为前提下，对稀疏信号源矩阵进行重构以获得被测量信号源的波达方向。使用这种方法，不仅避免了传统波达方向估计中需要计算复杂协方差矩阵的步骤，同时还对空间中的相干信号源有着很好的性能。

在物联网的情境之下，装置的数量会大幅增加，然而因为资源有限，所以用来辨别装置的展频码(m)会少于装置的数量(n)，因此会使得整个系统变成欠定的线性系统，然而这些装置大部分的时候都是处于休息、监测的状态，并不会一直传送讯息给基地台，因此就有了稀疏的性质，利用压缩感知的技术就能分辨出处于活动状态的装置，并解出其所传送的讯号。

压缩感知算法天生就具有加密的性质，因为要重建原本信号的话，必须要知道采样矩阵才能进重建。因此现今也有许多加密的研究关注于压缩感知算法，因为虚拟乱数传感矩阵(Pseudo-random Sensing Matrix)可以被视为一组加密后的钥匙，能对信号进行压缩并同时加密，而不需要额外的运算，可以参考。