压缩感知

压缩感知（英语：Compressed sensing或Compressive sensing ），也被称为压缩采样（英语：Compressive sampling）或稀疏采样（英语：Sparse sampling），是一种寻找欠定线性方程组的稀疏解的技术。压缩感知被应用于电子工程尤其是信号处理中，用于获取和重构稀疏或可压缩的信号。该方法利用信号本身或其线性变化域稀疏的特性，相较于奈奎斯特–香农采样定理（英语：Nyquist–Shannon sampling theorem），能够通过较少的测量数据（英语：measurements）重建出原始信号。得益于压缩感知能够在少量采样次数的情况下大致重建出原始信号或图像，其目前被广泛运用于核磁共振、单像素成像（英语：Single-pixel imaging）、快照式光谱成像（英语：Snapshot hyperspectral imaging）等需要在少量采样的情况下重建信号的领域。

概述

信号处理领域中的一个常见问题就是从一系列的采样中重建原本的信号。一般而言，未被采样的部分信号，是不可能重建出来的。然而通过借助对于信号（性质）的预先了解或合理假设，完美地通过一系列采样重建原信号就成为了可能。

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

在2004年左右，伊曼纽尔·坎德斯（英语：Emmanuel Candès）、戴维·多诺霍（英语：David Donoho）、Justin Romberg和陶哲轩（英语：Terence Tao）证明了在已知信号稀疏性的情况下，可能凭借较采样定理所规定更少的采样数重建原信号，这一理论也是压缩感知的基石。

问题定义

压缩感知主要用于解决欠定线性方程问题。对于一个常见的线性方程问题，有${\displaystyle m}$个方程式和 ${\displaystyle n}$个未知数，其用数学表达为${\displaystyle \mathbf {y} =\mathbf {\Phi } \mathbf {x} ,}$其中${\displaystyle \mathbf {\Phi } \in \mathbb {R} ^{m\times n}}$, ${\displaystyle \mathbf {x} \in \mathbb {R} ^{n}}$, ${\displaystyle \mathbf {y} \in \mathbb {R} ^{m}}$。在通信系统中，${\displaystyle \mathbf {y} }$是被收到的信号，而${\displaystyle \mathbf {x} }$则是要被重建的信号。若要依据该线性方程组对${\displaystyle \mathbf {x} }$进行重建，则会出现两种情况。

第一种情况，当${\displaystyle m\geq n}$时，也就是说方程式的数量大于等于未知数的数量。这种情况下，除非矩阵${\displaystyle \mathbf {\Phi } }$的秩小于${\displaystyle n}$，否则并不是需要使用压缩感知求解，而是直接利用最小平方法去求得最接近的解${\displaystyle {\hat {\mathbf {x} }}=\mathbf {\Phi } ^{\dagger }\mathbf {y} }$，其中${\displaystyle \ \mathbf {\Phi } ^{\dagger }:=(\mathbf {\Phi } ^{T}\mathbf {\Phi } )^{-1}\mathbf {\Phi } ^{T}}$是矩阵${\displaystyle \mathbf {\Phi } }$的穆尔-彭罗斯广义逆矩阵（英语：Moore–Penrose pseudoinverse matrix）。

第二种情况，当${\displaystyle m<n}$，也就是未知数的数量多于方程式的数量时，该欠定线性方程组是有无数个解的，因此无法使用最小平方法去求得要重建的信号。

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

${\displaystyle {\begin{cases}2=x_{1}+x_{2}+x_{3}+x_{4}\\4=x_{1}+2x_{2}+x_{3}+x_{4}\end{cases}}}$

或通过矩阵表示为

${\displaystyle {\begin{bmatrix}2\\4\end{bmatrix}}={\begin{bmatrix}1&1&1&1\\1&2&1&1\end{bmatrix}}\mathbf {x} }$

，其是一个欠定线性系统，会有无限多个解可以满足这个方程式，然而若加入该信号的稀疏限制条件：“${\displaystyle x_{1},x_{2},x_{3},x_{4}}$之间只有一个有值，其余都是0”，便可以得到这个欠定线性系统的解为${\displaystyle \mathbf {x} ={\begin{bmatrix}0,2,0,0\end{bmatrix}}^{T}}$，这个就是压缩感知的最主要的精神所在：仅根据部分采样数据，在已知信号的先验条件（本例中为信号的稀疏性）情况下，亦可以重建出原始信号。

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

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

因此，以下三个方面即为压缩感知的主要研究重点：

1. 采样方式，即该如何对原始信号采样
2. 设计先验，即如何预设某信号先验条件
3. 重建算法，即如何根据采样数据和先验条件进行重建

采样方式

在压缩感知中，选取的采样矩阵需要满足有限等距性质(英语：Restricted Isometry Property, RIP)，其定义如下：

${\displaystyle (1-\delta )\|\mathbf {x} \|_{2}^{2}\leq \|\mathbf {\Phi } \mathbf {x} \|_{2}^{2}\leq (1+\delta )\|\mathbf {x} \|_{2}^{2}}$

其中${\displaystyle 0<\delta <1}$。${\displaystyle \|\cdot \|_{2}}$表示${\displaystyle \ell _{2}}$范数，可用于计算信号能量。因此整个式子可以视为信号${\displaystyle \mathbf {x} }$跟传感矩阵${\displaystyle \mathbf {\Phi } }$的相似程度，即做完转换后的能量需要在合理范围之内。

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

相干性可定义为${\displaystyle \mu {\bigl (}\mathbf {\Phi } {\bigr )}:=\max _{l\neq m}\left\vert \phi _{l}^{T}\phi _{m}\right\vert }$，即取样矩阵任两个相异的行做内积后，取绝对值所产生的最大值，可以用来衡量信号重建的准确度。

而目前对于采样矩阵${\displaystyle \mathbf {\Phi } \in \mathbb {R} ^{m\times n}}$，有下列几种选择可以使还原重建度有一定质量：

1. 对${\displaystyle n}$个${\displaystyle \mathbf {\Phi } }$的行向量在${\displaystyle m}$维的单位半径球面上进行随机采样;
2. 对任一个${\displaystyle \mathbf {\Phi } _{i,j}}$都采用相同独立的高斯分布${\displaystyle {\mathcal {N}}(0,1/m}$)进行随机采样;
3. 对任一个${\displaystyle \mathbf {\Phi } _{i,j}}$都采用如下式相同独立的分布进行随机采样${\displaystyle P(\mathbf {\Phi } _{i,j}=\pm 1/{\sqrt {m}})=1/2}$;

除了上述的可能，现在也已经证实任何一个亚高斯分布的矩阵也可以成为一个很好的测量矩阵，也就是说具有很好的还原效果。另外，随着机器学习和深度学习的发展，一些测量矩阵也可以通过训练的方式获取^[1]。

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

结构简化采样矩阵

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

循环矩阵的形式为下式：

${\displaystyle \mathbf {\Phi } ={\begin{bmatrix}\phi _{1}&\phi _{2}&\phi _{3}&\dots &\phi _{n}\\\phi _{n}&\phi _{1}&\phi _{2}&&\phi _{n-1}\\\phi _{n-1}&\phi _{n}&\phi _{1}&&\phi _{n-2}\\\vdots &&&\ddots &\vdots \\\phi _{n-m+2}&\phi _{n-m+3}&\phi _{n-m+4}&\dots &\phi _{n-m+1}\end{bmatrix}}}$

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

${\displaystyle \mathbf {\Phi } ={\begin{bmatrix}\phi _{0}&\phi _{-1}&\phi _{-2}&\ldots &\ldots &\phi _{-n+1}\\\phi _{1}&\phi _{0}&\phi _{-1}&\ddots &&\vdots \\\phi _{2}&\phi _{1}&\ddots &\ddots &\ddots &\vdots \\\vdots &\ddots &\ddots &\ddots &\phi _{m-n-1}&\phi _{m-n-2}\\\vdots &&\ddots &\phi _{m-n+1}&\phi _{m-n}&\phi _{m-n-1}\\\phi _{m-1}&\ldots &\ldots &\phi _{m-n+2}&\phi _{m-n+1}&\phi _{m-n}\end{bmatrix}}}$

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

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

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

数值简化采样矩阵

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

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

对于每一个矩阵元素，该分布的概率质量函数${\displaystyle f}$为： ${\displaystyle f(k;p)={\begin{cases}p&{\text{if }}k=1,\\[6pt]1-p&{\text{if }}k=0.\end{cases}}}$

设计先验

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

一个向量${\displaystyle \mathbf {x} }$的稀疏性可以被定义为：

${\displaystyle \left\Vert \mathbf {x} \right\Vert _{0}:=\sum _{i}|x_{i}|^{0}}$。

也就是计算一个向量之中非零的个数，举例来说，如果${\displaystyle \mathbf {x} ={\begin{bmatrix}0,0,1,0,1,0,0\end{bmatrix}}^{T}}$，则${\displaystyle \left\Vert \mathbf {x} \right\Vert _{0}=2}$，因此目标的解就会变成如下：

${\displaystyle \min _{\mathbf {x} }\|\mathbf {x} \|_{0}\ \quad {\mbox{subject to}}\quad \ \mathbf {y} =\mathbf {\Phi } \mathbf {x} }$

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

${\displaystyle \min _{\mathbf {x} }\|\mathbf {x} \|_{1}\ \quad {\mbox{subject to}}\quad \ \mathbf {y} =\mathbf {\Phi } \mathbf {x} }$

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

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

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

重建算法

基追踪

基追踪（英语：Basis Pursuit，BP）是一种信号重建算法，被广泛地用于压缩感知领域，属于数学最优化问题的范畴，形式为${\displaystyle \min _{\mathbf {x} }\|\mathbf {x} \|_{1}\quad {\mbox{subject to}}\quad \mathbf {y} =\mathbf {\Phi } \mathbf {x} }$。

基追踪常在需要完美满足欠定线性方程组系统中${\displaystyle \mathbf {y} =\mathbf {\Phi } \mathbf {x} }$时被应用，且要求解在${\displaystyle \ell _{1}}$范数下为最稀疏的。

若应用情景允许降低对完美恢复的要求，以换取更加稀疏的解${\displaystyle \mathbf {x} }$，降噪基追踪（英语：basis pursuit denoising）更为适用。

匹配追踪

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

${\displaystyle f(t)=\sum _{n=0}^{+\infty }a_{n}g_{\gamma _{n}}(t)}$

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

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

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

正交匹配追踪

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

迭代阈值算法

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

深度学习方法

随着深度学习的发展，一些方法^[2]直接通过神经网络学习从${\displaystyle \mathbf {y} }$到${\displaystyle \mathbf {x} }$的映射函数，从而实现压缩感知重建。

特别地，一些深度学习方法结合了上述的传统迭代算法，从而使得重建质量更高，重建过程更具可解释性。这类方法被称为深度展开网络（英文：Deep Unfolding Network）。例如，ISTA-Net^[3]将ISTA算法展开，并且用神经网络替代ISTA算法中的阈值收缩步骤；DMP-DUN^[4]提出基于AMP算法的DMP算法，从而能够利用扩散模型的先验知识实现重建。

相关应用

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

X射线晶体学

压缩感知在X射线晶体学中的应用主要体现在相位恢复问题的研究上。相位恢复在X射线晶体结构分析中至关重要，因为晶体结构与其X射线衍射效应之间存在傅里叶转换关系。传统方法中，仅能获得衍射强度的振幅信息，缺乏相位信息，这使得直接重建晶体结构变得困难。

为解决这一问题，有学者将压缩感知应用于相位恢复，提出了压缩相位恢复(Compressive phase retrieval)。该方法利用信号的稀疏性，通过较少的测量数据成功回复原始信号。在随机傅里叶转换模型下，仅需少量随机的傅里叶测量，即可恢复稀疏信号。

此外，压缩感知还被用于提升X射线成像的分辨率和稳定性，尤其是将压缩感知与深度学习相结合的创新方法，进一步优化了图像重建的效果。

摄影学

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

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

全息成像

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

面部识别

压缩感知目前被用于面部识别应用之中，参见Engineers Test Highly Accurate Face Recognition （页面存档备份，存于互联网档案馆）。

核磁共振成像

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

地震成像

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

模拟信息转换(Analog-to-Information Converter, AIC)

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

网络诊断

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

短红外摄影

目前，基于压缩感知技术的商用短红外相机已被推出[6] （页面存档备份，存于互联网档案馆） 。这些相机的光敏度大约从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)可以被视为一组加密后的钥匙，能对信号进行压缩并同时加密，而不需要额外的运算，可以参考^[7]。

示例

正交基展开

正交基展开采用的是完全正交基（英语：complete and orthogonal basis set）来进行展开，而压缩感知采用的是过完备的非正交基集（英语：over-complete and non-orthogonal basis set）来展开信号。

傅立叶级数展开是正交基展开（orthogonal basis expansion）的方法:

${\displaystyle x(t)\approx \sum _{m=1}^{M}a_{m}\exp(j2\pi f_{m}t)}$

${\displaystyle \int \exp(j2\pi f_{m}t){\overline {\exp(j2\pi f_{n}t)}}\mathrm {d} t=0,}$if ${\displaystyle f_{m}\neq f_{n}}$

Three-parameter atom expansion，Four-parameter atom (chirplet) expansion，

PSWF 展开则是过完备的非正交基集展开（over-complete and non-orthogonal basis expansion）的方法:

${\displaystyle x(t)\approx \sum a_{t0,f0,{\displaystyle \sigma }}\phi _{t0,f0,{\sigma }}(t)}$

${\displaystyle {\displaystyle \phi }_{t0,f0,{\displaystyle \sigma }}}$ (t) 不构成一个完备的正交基集。

分类

压缩感知希望处理的问题是：

假设 ${\displaystyle b_{0}(t),b_{1}(t),b_{2}(t),b_{3}(t),\cdots }$ 组成一个过完备的非正交基集

问题一

我们希望最小化 ${\displaystyle ||c||_{0}}$ ( ${\displaystyle \lVert \cdot \rVert _{0}}$ 是 ${\displaystyle L_{0}}$ 范数， ${\displaystyle ||c||_{0}}$ 意指${\displaystyle c_{m}}$ 的值不为0 的个数)，使得：

${\displaystyle x(t)\approx \sum _{m}c_{m}b_{m}(t)}$

问题二

我们希望最小化 ${\displaystyle ||c||_{0}}$ ，使得：

${\displaystyle \int (x(t)-\sum _{m}c_{m}b_{m}(t))^{2}\mathrm {d} t<{\text{threshold}}}$

问题三

限制 ${\displaystyle ||c||_{0}}$ 为 M，我们想要最小化：

${\displaystyle \int (x(t)-\sum _{m}c_{m}b_{m}(t))^{2}\mathrm {d} t}$

匹配追踪

原子：${\displaystyle b_{m}(t),m=1,2,3,\cdots }$

${\displaystyle \left|\int b_{m}(t)b_{m}^{*}(t)\mathrm {d} t\right|=1}$ （归一化）

[第1步]输入：${\displaystyle x(t)}$,初始化: ${\displaystyle n=0,x_{r}(t)=x(t)}$

[第2步]找到最小化${\displaystyle \left|\int x_{r}(t)b_{m}^{*}(t)\mathrm {d} t\right|}$的m

[第3步]令 ${\displaystyle \phi _{n}(t)=b_{m}(t),u_{n}=\int x_{r}(t)b_{m}^{*}(t)\mathrm {d} t}$

[第4步]${\displaystyle x_{r}(t)=x_{r}(t)-u_{n}{\displaystyle \phi }_{n}(t)}$

[第5步]${\displaystyle n=n+1}$

[第6步]检查下列条件是否符合，若不符合，回到[第2步]；若符合，则进到[第7步]

问题一:是否满足 ${\displaystyle x_{r}(t)=0}$

问题二:是否满足 ${\displaystyle \int x_{r}^{2}(t)\mathrm {d} t<{\text{threshold}}}$

问题三:是否满足${\displaystyle n=M}$

[第7步] ${\displaystyle x(t)\approx \sum _{m}u_{m}{\displaystyle \phi }_{m}(t)}$

基追踪（Basis Pursuit）

将 ${\displaystyle L_{0}}$ 范数改为 ${\displaystyle L_{1}}$ 范数

${\displaystyle \lVert c\rVert _{1}=|c|_{0}+|c|_{1}+|c|_{2}+......}$

问题一:

我们想要最小化 ${\displaystyle ||c||_{1}}$ ，使得：

${\displaystyle x(t)\approx \sum _{m}c_{m}b_{m}(t)}$

问题二:

我们想要最小化 ${\displaystyle ||c||_{1}}$ ，使得：

${\displaystyle \int (x(t)-\sum _{m}c_{m}b_{m}(t))^{2}\mathrm {d} t<{\text{threshold}}}$

问题三:

令${\displaystyle \lVert c\rVert _{1}\leq M}$，我们想要最小化：

${\displaystyle \int (x(t)-\sum _{m}c_{m}b_{m}(t))^{2}\mathrm {d} t}$

正交匹配追踪(Orthogonal Matching Pursuit)

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

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

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

• 
  正交匹配追踪算法

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

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

迭代阈值算法(Iterative Shrinkage-Thresholding Algorithm)

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

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

${\displaystyle \min \|x\|_{1}\ \ subject\ to\ y=Ax}$

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

${\displaystyle x^{t+1}=\eta _{thr}(x^{t}+{\mathcal {K}}\times (A^{T}r^{t}))}$

而${\displaystyle {\mathcal {K}}}$是relaxation parameter，且${\displaystyle {\mathcal {K}}\in (0,1)}$。

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

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

${\displaystyle \eta _{thr}^{H}(x)={\begin{cases}x,{\text{if }}|x|>thr\\0,{\text{otherwise}}\end{cases}}}$

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

${\displaystyle \eta _{thr}^{S}(x)=\operatorname {sgn}(x)(|x|-thr)_{+}{\text{, where }}(z)_{+}=z\times \mathbb {I} (z\geq 0)}$，而${\displaystyle \mathbb {I} (.)}$是指示函数

而第二阶段，则是利用新算出来的${\displaystyle x^{t+1}}$来进行残差更新。

${\displaystyle r^{t+1}=y-Ax^{t+1}}$

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

而此算法是Landweber iteration的变形，若没有加入阈值函数的话，就会收敛到${\displaystyle \min \|y-Ax\|_{2}^{2}}$。

稀疏性空间投影

压缩感知还原算法包括整个压缩感知都是建立在信号有稀疏性上，但是并不是所有的信号都天然具有稀疏性，例:声音。那么是否不具有稀疏性的信号就不能使用压缩感知呢？答案为并不是，天然不具有稀疏性的信号还是能够使用压缩感知，只需要把该信号投影到其他空间，其他该信号有稀疏性的空间下，压缩感知就可直接使用在该投影空间上。可以被定义如下：

${\displaystyle s=\psi z,where\ \psi \in \Re ^{n\times k},z\in \Re ^{k\times 1},s\in \Re ^{n\times 1}}$

s:要被重建的信号(原信号)；ψ:投影矩阵，把非稀疏性信号投影到稀疏性空间；z:非零项远小于零项

故原压缩感知公式定义也随之改变：

${\displaystyle y=Hs=H\psi z=\Theta z,\,where\,\Theta \in \Re ^{m\times k}}$

所以可以把${\displaystyle \Theta }$视为原本压缩感知公式里面的H，还原算法即可一样使用。

至于${\displaystyle \psi }$的选择对于不同信号来说有很多种，有离散余弦变换(DCT) ,离散小波变换(DWT)，字典学习(Dictionary Learning)等。

离散余弦变换和离散小波变换

利用信号经过这两种变换后都会有稀疏性的特性，把这两种变换变成矩阵形式，让信号直接投影到具有稀疏性的空间上。

好处

1. 不需要特别针对信号做不同${\displaystyle \psi }$的选择，对于绝大部分信号可以直接使用。
2. 并不需要前处理，可以直接使用。

坏处

1. 限制了原信号的维度，必须满足n = ${\displaystyle 2^{x}}$,x为任意正整数。
2. 因为通用所有信号，故经过压缩感知还原算法后还原的信号质量较差。

字典学习

顾名思义即把${\displaystyle \psi }$当作一本要学习的字典，不断的利用该信号和还原算法后的结果做字典的更新，直到找到一个${\displaystyle \psi }$能够把该信号投影到稀疏性空间上。

字典学习的流程：

1. 设置字典学习的学习次数(Iter)
2. 收集一定量(L笔)要学习的资料s,组成S = [s₁, s₂, ... ,s_L]
3. 固定${\displaystyle \psi }$，利用还原算法找出每一笔资料的z，组成Z = [z₁, z₂, ... ,z_L]
   • ${\displaystyle {\underset {c}{min}}}$||S - ${\displaystyle \psi }$Z|${\displaystyle |_{F}^{2}}$ s.t. ||z_i||₀ < K_th ${\displaystyle \forall }$i
4. 固定Z， 利用3.所得之Z来更新字典
   • 当Z固定时，定义误差e_i = s_i - ${\displaystyle \psi }$z_i，组成E = [e₁, e₂, ... ,e_L]
   • 所以整体的均方误差为 ||E|${\displaystyle |_{F}^{2}}$= || [e₁, e₂, ... ,e_L] |${\displaystyle |_{F}^{2}}$ = || S - ${\displaystyle \psi }$Z|${\displaystyle |_{F}^{2}}$
   • 在Z固定下使得E最小，将得到关系式 (S - ${\displaystyle \psi }$Z)Z^T = 0
   • => ${\displaystyle \psi }$= SZ^T(ZZ^T)^-1
5. 检查Z上面是否已经有稀疏性，如有则结束学习；如没有则回到3.直到达到学习的次数

字典学习的算法有很多，较为常用的有Method of optimal directions(MOD^[8])。

好处

1. 因为针对该种类信号做学习，故还原后的质量较好。
2. 对原信号的维度并没有任何限制。

坏处

1. 需要事前收集该种类的信号做学习，不能未学习直接使用。
2. 因为针对该种类信号做学习，故直接使用在不同种类信号效果较差/不适用。

外部链接

• "The Fundamentals of Compressive Sensing" Part 1 （页面存档备份，存于互联网档案馆）, Part 2 （页面存档备份，存于互联网档案馆） and Part 3 （页面存档备份，存于互联网档案馆）: video tutorial by Mark Davenport, Georgia Tech. at SigView, the IEEE Signal Processing Society Tutorial Library.
• Using Math to Turn Lo-Res Datasets Into Hi-Res Samples （页面存档备份，存于互联网档案馆） Wired Magazine article
• Compressive Sensing Resources at Rice University.
• Compressed Sensing Makes Every Pixel Count （页面存档备份，存于互联网档案馆） – article in the AMS What's Happening in the Mathematical Sciences series
• Wiki on sparse reconstruction. [2014-06-24]. （原始内容存档于2015-05-04）.