压缩感知还原演算法

压缩感知(Compressive Sensing, CS)是一种新兴的取样方法，相比长久以来被使用的奈奎斯特取样定理(Nyquist Sampling Theorem)，能更高效的方式采样信号。压缩感知最主要利用信号的稀疏性来寻找欠定线性系统的稀疏解，因此能从较少的取样样本中还原信号。近几年有许多文献提出了许多有效的算法，大多是透过迭代的方式找到系数并还原信号，相较同时找到最大系数的方式，能更精确的还原信号。

还原演算法

对于压缩感知中的稀疏信号还原有很多不同类型的演算法，这些算法大致可以被分为六类，以下将详细叙述各类型演算法的特色^[1]。

凸松弛(Convex Relaxation)

这类算法最主要透过线性规划方式求解凸优化的问题来对信号进行还原。虽然要精确地还原信号所需的测量数量很少，但是这些方法在计算上是较复杂的。主要代表的演算法有基追踪(Basis Pursuit, BP)、抗噪基追踪(Basis Pursuit De-noising, BPDN)、最小角度回归(Least Angle Regression, LARS)。

基追踪优化公式： $\min _{x}\|x\|_{1}\quad {\mbox{subject to}}\quad y=Ax.$

抗噪基追踪优化公式： $\min _{x}{\frac {1}{2}}\|y-Ax\|_{2}^{2}+\lambda \|x\|_{1},$

贪婪迭代演算法(Greedy Iterative Algorithm)

这类算法主要是透过迭代的方式逐步找到答案来还原信号。这类型的演算法在每次迭代中，以贪婪的方式选择传感矩阵 $\Theta$ 中与 $Y$ 做内积最大的列，也就是选出与传感矩阵中最相关的列，接著该列对 $Y$ 的贡献将会从 $Y$ 中被减去，并且对相减之后的结果进行迭代，直到识别出正确的列集合。相比之下，最小平方误差的方法则是在每次迭代中最小化误差。这类演算法的优点在于运算复杂度低，还原速度快，常见的演算法有正交匹配追踪(Orthogonal Matching Pursuit, OMP)、随机梯度追踪(Stochastic Gradient Pursuit,SGP)、正则化正交匹配追踪(Regularized OMP)、压缩采样匹配追踪(Compressive Sampling Matching Pursuit, CoSaMP)和子空间追踪(Subspace Pursuit,SP)。

正交匹配追踪(Orthogonal Matching Pursuit, OMP)

正交匹配追踪(OMP)演算法

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

随机梯度追踪(Stochastic Gradient Pursuit,SGP)

可视为是正交匹配追踪的改良版，在面对杂讯的环境下也能更好地还原。整体演算法都与正交匹配追踪相同，除了用最小二乘法(least square,LS)那一项。

最小二乘法可以用零强制线性均衡(zero forcing linear equalization,ZFLE)来实现：

$x_{ZF}=A_{\Omega }^{\dagger }y=A_{\Omega }^{\dagger }(Ax+n)=x+A_{\Omega }^{T}(A_{\Omega }A_{\Omega }^{T})^{-1}n$ ,n为杂讯

但是零强制线性均衡的缺点可以直接从上式看出，会造成放大杂讯的影响。为了解决杂讯的问题，可以利用最小均方误差(minimum mean square error,MMSE)均衡器来最小化整体的误差

$x_{MMSE}=A_{\Omega }^{T}(A_{\Omega }A_{\Omega }^{T}+{\frac {\sigma _{n}^{2}}{\sigma _{x|\Omega }^{2}}}I)^{-1}y$

和零强制线性均衡相比，在反矩阵内部多增加了额外的项，可直接视为杂讯项目。虽然最小均方误差方法的正交匹配追踪^[2]更能够对抗杂讯干扰，但是 ${\sigma _{x|\Omega }^{2}}$ 和 ${\sigma _{n}^{2}}$ 并不适用压缩感知的众多应用上，所以并不能直接套用在压缩感知的还原演算法上。

因为最小均方(least mean square,LMS)在不断地迭代后的平衡值会接近最小均方误差，因此随机梯度追踪利用最小均方来取代最小二乘法。最小均方的迭代将根据预估误差来调整support系数，而预估误差可表示为：

$e_{\lambda }=y_{\lambda }-{\tilde {A_{\lambda }}}{\tilde {x_{\lambda }}}$

因此最小均方的梯度下降递归(gradient decent recursion)可以表示为：

${\tilde {x}}_{\lambda +1}={\tilde {x}}_{\lambda }+\mu e_{\lambda }A_{\Omega }^{T}$ ， $\mu$ 为step size

总结来说随机梯度追踪演算法里面包含了两个迭代循环。一个大的迭代是由正交匹配追踪所形成，而小的循环则被大的迭代所包含，是由最小均方所形成，不断地迭代来更新 ${\tilde {x}}_{\lambda }$ 的值。

压缩采样匹配追踪(Compressive Sampling Matching Pursuit, CoSaMP)

在进行该还原演算法前需要额外的输入参数-稀疏性数量K(信号非零项的数量)。和一般的贪婪迭代演算法一样，整个还原过程同样是由(1)匹配追踪(找出内积最大的列)、(2)还原值估计(通过最大内积列来估计还原值)、(3)剩馀值(residual)更新(通过估计还原值来更新误差)不停地迭代组成。

和正交匹配追踪不同的是正交匹配追踪在每次迭代的匹配追踪上只寻找并增加一个内积最大的列；而压缩采样匹配追踪则在每次迭代的匹配追踪上寻找并增加2K个内积最大的列。

压缩采样匹配追踪过程：

参数定义：π为相关向量、r(t)为在第t次迭代的剩馀值(residual)、ω为在π里面最大的值、Ω为support的集合

初始化， $x(0)=0_{Px1},r(0)=y,\Omega (0)=\emptyset ,t=0$
计算相关向量π
- π = | $A^{T}$ r(t)|
从相关向量π里面寻找出2K个最高correlation值的supports
- ω $\equiv$ ${\underset {\omega \in [P]}{\arg max}}$ x{ | π(ω) | }
把找到的support加入support 集合里面
- Ω = Ω ᑌ supp(T(π,2K))，T(π,2K)为在π里面2K个最高的值、supp(T(π,2K))为T(π,2K)的索引集合
- 因为初始Ω里面含有K个supports，所以在经过3.后的Ω里面将含有2K至3K个supports
挑出需要运算的矩阵A
- $A_{\Omega }$ = { ${\vec {\theta _{j}}}|j\in \Omega$ }， ${\vec {\theta _{j}}}$ 为第j列的矩阵A
利用最小二乘法(least square,LS)计算出 $x_{i|\Omega }(t+1)$
- $x_{i|\Omega }(t+1)$ = $A_{\Omega }^{\dagger }y=(A_{\Omega }^{T}A_{\Omega })^{-1}A_{\Omega }^{T}y$ , $x_{i|\Omega ^{C}}(t+1)$ = 0
以每一列绝对值的大小排列Ω里面的每一列，并只保留前K个最大的supports，把剩馀的删去
- Ω = supp $(T(|x_{i|\Omega }(t+1)|,K))$ ， $x_{i|\Omega ^{C}}(t+1)$ = 0
剩馀值(residual)更新
- r(t+1) = y - Ax(t+1)
如达到终止条件，结束该还原，返还x(t)；否则回到1.继续。
- 终止条件： $(\lVert r(t)\rVert _{2}\leq THR)$ 或者 (t= $Iter_{max}$ )

子空间追踪(Subspace Pursuit,SP)

子空间追踪还原演算法和压缩采样匹配追踪还原演算法相似，它们之间只有三个主要的差别。

只从相关向量π里面寻找出K个最高correlation值的supports，而不是K个。
- Ω = Ω ᑌ supp(T(π,K))
在把K个supports移除过后，再进行一次最小二乘法，让预估计算的值更精准。
终止条件的更改。因为压缩采样匹配追踪还原演算法需要额外定义的THR来当做终止条件，故子空间追踪用前一次迭代的剩馀值(residual)来取代THR。
- $\lVert r_{past}\rVert _{2}\leq \lVert r\rVert _{2}$

利用剩馀值(residual)是否有在迭代过程在降低来当成循环终止条件，因此使得子空间追踪收敛的速度比压缩采样匹配追踪来的更快。

迭代阈值演算法(Iterative Thresholding Algorithm)

相较于凸松弛演算法，迭代方法在压缩感知还原信号的速度更快。对于这类算法，主要透过过软阈值或硬阈值来正确的重建信号，而阈值的大小则会根据迭代次数进行调整。最近提出了扩展匹配追踪(Expander Matching Pursuits)、稀疏匹配追踪(Sparse Matching Pursuit)和序列稀疏匹配追踪(Sequential Sparse Matching Pursuits)，实现了近线性还原时间。

组合/次线性演算法(Combinatorial/Sublinear Algorithms)

这类算法通过分组测试来还原稀疏信号。与凸松弛演算法或贪婪演算法相比，它们有高速和高效的好处，然而对于测量矩阵 $\Phi$ 有特定模式稀疏的要求。代表性的演算法有傅里叶采样算法(Fourier Sampling Algorithm)和炼式追踪(Chaining Pursuits)。

非凸最小化演算法(Non Convex Minimization Algorithms)

非凸局部最小化技术通过用 $l_{p}$ 规范替换 $l_{1}$ 规范来从更少的测量中恢复CS信号，其中 $p\leq 1$ 。非凸优化主要应用于医学影像断层扫描、网络状态推断、资料串流压缩。文献中提出了许多使用这种技术的演算法，例如聚焦欠定系统解法(Focal Underdetermined System Solution, FOCUSS)、迭代重新加权最小平方法(Iterative Re-weighted Least Squares)、稀疏贝叶斯学习算法(Sparse Bayesian Learning Algorithms)、基于蒙特卡罗(Monte-Carlo based Algorithms)的演算法。

布里格曼迭代演算法(Bregman Iterative Algorithm)

这些算法提供了一种解决最小化问题的简单而有效的方法。文献^[3]给出了一个新的想法，它透过布里格曼迭代正则化方法产生一系列无约束子问题给出约束问题的精确解。当应用于压缩感知问题时，使用布里格曼的迭代方法能在四到六次的迭代中实现还原。与其他现有演算法相比，这些算法的计算速度特别吸引人。

复杂度比较

**各类型压缩感知还原演算法复杂度比较^[1]**
种类	演算法	复杂度	最小测量次数
凸松弛	基追踪	$O(n^{3})$	$O(s\log n)$
贪婪迭代演算法	正交匹配追踪	$O(smn)$	$O(s\log n)$
	正则化正交匹配追踪	$O(smn)$	$O(s\log ^{2}n)$
	压缩采样匹配追踪	$O(mn)$	$O(s\log n)$
迭代阈值演算法	扩展匹配追踪	$O(n\log(n/s))$	$O(n\log(n/s))$
组合/次线性演算法	炼式追踪	$O(s\log ^{2}n\log ^{2}s)$	$O(s\log ^{2}n)$