壓縮感知還原演算法

壓縮感知(Compressive Sensing, CS)是一種新興的取樣方法，相比長久以來被使用的奈奎斯特取樣定理(Nyquist Sampling Theorem)，能更高效的方式採樣信號。壓縮感知最主要利用信號的稀疏性來尋找欠定線性系統的稀疏解，因此能從較少的取樣樣本中還原信號。近幾年有許多文獻提出了許多有效的算法，大多是透過迭代的方式找到係數並還原信號，相較同時找到最大係數的方式，能更精確的還原信號。

還原演算法

對於壓縮感知中的稀疏信號還原有很多不同類型的演算法，這些算法大致可以被分為六類，以下將詳細敘述各類型演算法的特色^[1]。

凸鬆弛(Convex Relaxation)

這類算法最主要透過線性規劃方式求解凸優化的問題來對信號進行還原。 雖然要精確地還原信號所需的測量數量很少，但是這些方法在計算上是較複雜的。主要代表的演算法有基追蹤(Basis Pursuit, BP)、抗噪基追蹤(Basis Pursuit De-noising, BPDN)、最小角度回歸(Least Angle Regression, LARS)。

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

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

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

這類算法主要是透過迭代的方式逐步找到答案來還原信號。這類型的演算法在每次迭代中，以貪婪的方式選擇傳感矩陣${\displaystyle \Theta }$ 中與${\displaystyle Y}$ 做內積最大的列，也就是選出與傳感矩陣中最相關的列，接著該列對${\displaystyle Y}$ 的貢獻將會從${\displaystyle Y}$ 中被減去，並且對相減之後的結果進行迭代，直到識別出正確的列集合。相比之下，最小平方誤差的方法則是在每次迭代中最小化誤差。這類演算法的優點在於運算複雜度低，還原速度快，常見的演算法有正交匹配追蹤(Orthogonal Matching Pursuit, OMP)、隨機梯度追蹤(Stochastic Gradient Pursuit,SGP)、正則化正交匹配追蹤(Regularized OMP)、壓縮採樣匹配追蹤(Compressive Sampling Matching Pursuit, CoSaMP)和子空間追蹤(Subspace Pursuit,SP)。

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

•  
  正交匹配追蹤(OMP)演算法

一開始會有一個空集合${\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向量當中最有可能非零的位置，直到達到演算法停止條件。

隨機梯度追蹤(Stochastic Gradient Pursuit,SGP)

可視為是正交匹配追蹤的改良版，在面對雜訊的環境下也能更好地還原。整體演算法都與正交匹配追蹤相同，除了用最小二乘法(least square,LS)那一項。

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

• ${\displaystyle 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)均衡器來最小化整體的誤差

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

和零强制线性均衡相比，在反矩陣內部多增加了額外的項，可直接視為雜訊項目。雖然最小均方误差方法的正交匹配追蹤^[2]更能夠對抗雜訊干擾，但是${\displaystyle {\sigma _{x|\Omega }^{2}}}$ 和${\displaystyle {\sigma _{n}^{2}}}$ 並不適用壓縮感知的眾多應用上，所以並不能直接套用在壓縮感知的還原演算法上。

因為最小均方(least mean square,LMS)在不斷地迭代後的平衡值會接近最小均方误差，因此隨機梯度追蹤利用最小均方來取代最小二乘法。最小均方的迭代將根據預估誤差來調整support係數，而預估誤差可表示為：

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

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

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

總結來說隨機梯度追蹤演算法裡面包含了兩個迭代循環。一個大的迭代是由正交匹配追蹤所形成，而小的循環則被大的迭代所包含，是由最小均方所形成，不斷地迭代來更新${\displaystyle {\tilde {x}}_{\lambda }}$ 的值。

壓縮採樣匹配追蹤(Compressive Sampling Matching Pursuit, CoSaMP)

在進行該還原演算法前需要額外的輸入參數-稀疏性數量K(信號非零項的數量)。和一般的貪婪迭代演算法一樣，整個還原過程同樣是由(1)匹配追蹤(找出內積最大的列)、(2)還原值估計(通過最大內積列來估計還原值)、(3)剩餘值(residual)更新(通過估計還原值來更新誤差)不停地迭代組成。

和正交匹配追蹤不同的是正交匹配追蹤在每次迭代的匹配追蹤上只尋找並增加一個內積最大的列；而壓縮採樣匹配追蹤則在每次迭代的匹配追蹤上尋找並增加2K個內積最大的列。

壓縮採樣匹配追蹤過程：

參數定義：π為相關向量、r(t)為在第t次迭代的剩餘值(residual)、ω為在π裡面最大的值、Ω為support的集合

1. 初始化，${\displaystyle x(0)=0_{Px1},r(0)=y,\Omega (0)=\emptyset ,t=0}$ 
2. 計算相關向量π
   • π = |${\displaystyle A^{T}}$ r(t)|
3. 從相關向量π裡面尋找出2K個最高correlation值的supports
   • ω ${\displaystyle \equiv }$ ${\displaystyle {\underset {\omega \in [P]}{\arg max}}}$ x{ | π(ω) | }
4. 把找到的support加入support 集合裡面
   • Ω = Ω ᑌ supp(T(π,2K))，T(π,2K)為在π裡面2K個最高的值、supp(T(π,2K))為T(π,2K)的索引集合
   • 因為初始Ω裡面含有K個supports，所以在經過3.後的Ω裡面將含有2K至3K個supports
5. 挑出需要運算的矩陣A
   • ${\displaystyle A_{\Omega }}$ = {${\displaystyle {\vec {\theta _{j}}}|j\in \Omega }$ }，${\displaystyle {\vec {\theta _{j}}}}$ 為第j列的矩陣A
6. 利用最小二乘法(least square,LS)計算出${\displaystyle x_{i|\Omega }(t+1)}$ 
   • ${\displaystyle x_{i|\Omega }(t+1)}$  = ${\displaystyle A_{\Omega }^{\dagger }y=(A_{\Omega }^{T}A_{\Omega })^{-1}A_{\Omega }^{T}y}$  ,${\displaystyle x_{i|\Omega ^{C}}(t+1)}$ = 0
7. 以每一列絕對值的大小排列Ω裡面的每一列，並只保留前K個最大的supports，把剩餘的刪去
   • Ω = supp${\displaystyle (T(|x_{i|\Omega }(t+1)|,K))}$ ，${\displaystyle x_{i|\Omega ^{C}}(t+1)}$ = 0
8. 剩餘值(residual)更新
   • r(t+1) = y - Ax(t+1)
9. 如達到終止條件，結束該還原，返還x(t)；否則回到1.繼續。
   • 終止條件： ${\displaystyle (\lVert r(t)\rVert _{2}\leq THR)}$ 或者 (t=${\displaystyle Iter_{max}}$ )

子空間追蹤(Subspace Pursuit,SP)

子空間追蹤還原演算法和壓縮採樣匹配追蹤還原演算法相似，它們之間只有三個主要的差別。

1. 只從相關向量π裡面尋找出K個最高correlation值的supports，而不是K個。
   • Ω = Ω ᑌ supp(T(π,K))
2. 在把K個supports移除過後，再進行一次最小二乘法，讓預估計算的值更精準。
3. 終止條件的更改。因為壓縮採樣匹配追蹤還原演算法需要額外定義的THR來當做終止條件，故子空間追蹤用前一次迭代的剩餘值(residual)來取代THR。
   • ${\displaystyle \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)

這類算法通過分組測試來還原稀疏信號。與凸鬆弛演算法或貪婪演算法相比，它們有高速和高效的好處，然而對於測量矩陣${\displaystyle \Phi }$ 有特定模式稀疏的要求。代表性的演算法有傅里葉採樣算法(Fourier Sampling Algorithm)和鍊式追蹤(Chaining Pursuits)。

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

非凸局部最小化技術通過用${\displaystyle l_{p}}$ 規範替換${\displaystyle l_{1}}$ 規範來從更少的測量中恢復CS信號，其中${\displaystyle 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]

種類	演算法	複雜度	最小測量次數
凸鬆弛	基追踪	${\displaystyle O(n^{3})}$	${\displaystyle O(s\log n)}$
貪婪迭代演算法	正交匹配追踪	${\displaystyle O(smn)}$	${\displaystyle O(s\log n)}$
	正則化正交匹配追踪	${\displaystyle O(smn)}$	${\displaystyle O(s\log ^{2}n)}$
	壓縮採樣匹配追踪	${\displaystyle O(mn)}$	${\displaystyle O(s\log n)}$
迭代閾值演算法	擴展匹配追踪	${\displaystyle O(n\log(n/s))}$	${\displaystyle O(n\log(n/s))}$
組合/次線性演算法	鍊式追踪	${\displaystyle O(s\log ^{2}n\log ^{2}s)}$	${\displaystyle O(s\log ^{2}n)}$

參考資料

1. Qaisar, S.; Bilal, R. M.; Iqbal, W.; Naureen, M.; Lee, S. Compressive sensing: From theory to applications, a survey. Journal of Communications and Networks. October 2013, 15 (5): 443–456 [2017-12-19]. ISSN 1229-2370. doi:10.1109/JCN.2013.000083. （原始内容于2018-11-28）. 
2. Sparrer, S.; Fischer, R.F.H. MMSE-based version of OMP for recovery of discrete-valued sparse signals. Electronics Letters. 2016-01-08, 52 (1): 75–77. ISSN 0013-5194. doi:10.1049/el.2015.0924. 
3. Yin, W.; Osher, S.; Goldfarb, D.; Darbon, J. Bregman Iterative Algorithms for $\ell_1$-Minimization with Applications to Compressed Sensing. SIAM Journal on Imaging Sciences. 2008-01-01, 1 (1): 143–168. doi:10.1137/070703983.