壓縮感知還原演演算法

壓縮感知(Compressive Sensing, CS)是一種新興的取樣方法，相比長久以來被使用的奈奎斯特取樣定理(Nyquist Sampling Theorem)，能更高效的方式取樣訊號。壓縮感知最主要利用訊號的稀疏性來尋找欠定線性系統的稀疏解，因此能從較少的取樣樣本中還原訊號。近幾年有許多出了許多有效的演算法，大多是透過迭代的方式找到係數並還原訊號，相較同時找到最大係數的方式，能更精確的還原訊號。還原演演算法.對於壓縮感知中的稀疏訊號還原有很多不同型別的演演算法，這些演算法大致可以被分為六類，以下將詳細敘述各型別演演算法的特色。凸鬆弛(Convex Relaxation).這類演算法最主要透過線性規劃方式求解凸最佳化的問題來對訊號進行還原。 雖然要精確地還原訊號所需的測量數量很少，但是這些方法在計算上是較複雜的。主要代表的演演算法有基追蹤(Basis Pursuit, BP)、抗噪基追蹤(Basis Pursuit De-noising, BPDN)、最小角度回歸(Least Angle Regression, LARS)。基追蹤最佳化公式：formula_1抗噪基追蹤最佳化公式：formula_2貪婪迭代演演算法(Greedy Iterative Algorithm).這類演算法主要是透過迭代的方式逐步找到答案來還原訊號。這型別的演演算法在每次迭代中，以貪婪的方式選擇感測矩陣formula_3中與formula_4做內積最大的列，也就是選出與感測矩陣中最相關的列，接著該列對formula_4的貢獻將會從formula_4中被減去，並且對相減之後的結果進行迭代，直到識別出正確的列集合。相比之下，最小平方誤差的方法則是在每次迭代中最小化誤差。這類演演算法的優點在於運算複雜度低，還原速度快，常見的演演算法有正交匹配追蹤(Orthogonal Matching Pursuit, OMP)、隨機梯度追蹤(Stochastic Gradient Pursuit,SGP)、正則化正交匹配追蹤(Regularized OMP)、壓縮取樣匹配追蹤(Compressive Sampling Matching Pursuit, CoSaMP)和子空間追蹤(Subspace Pursuit,SP)。正交匹配追蹤(Orthogonal Matching Pursuit, OMP).一開始會有一個空集合formula_7，以及剩餘的部分formula_8，每次疊代都會從formula_9找出一個A矩陣投影到剩餘formula_10有最大值的位置，把這個位置加到formula_11之中，並從formula_12當中移除，最後再更新剩餘formula_13。利用疊代的方式，不斷地找出x向量當中最有可能非零的位置，直到達到演演算法停止條件。隨機梯度追蹤(Stochastic Gradient Pursuit,SGP).可視為是正交匹配追蹤的改良版，在面對雜訊的環境下也能更好地還原。整體演演算法都與正交匹配追蹤相同，除了用最小二乘法(least square,LS)那一項。最小二乘法可以用零強制線性均衡(zero forcing linear equalization,ZFLE)來實現：但是零強制線性均衡的缺點可以直接從上式看出，會造成放大雜訊的影響。為瞭解決雜訊的問題，可以利用最小均方誤差(minimum mean square error,MMSE)均衡器來最小化整體的誤差和零強制線性均衡相比，在反矩陣內部多增加了額外的項，可直接視為雜訊專案。雖然最小均方誤差方法的正交匹配追蹤更能夠對抗雜訊幹擾，但是formula_16和formula_17並不適用壓縮感知的眾多應用上，所以並不能直接套用在壓縮感知的還原演演算法上。因為最小均方(least mean square,LMS)在不斷地迭代後的平衡值會接近最小均方誤差，因此隨機梯度追蹤利用最小均方來取代最小二乘法。最小均方的迭代將根據預估誤差來調整support係數，而預估誤差可表示為：因此最小均方的梯度下降遞迴(gradient decent recursion)可以表示為：總結來說隨機梯度追蹤演演算法裡麵包含了兩個迭代迴圈。一個大的迭代是由正交匹配追蹤所形成，而小的迴圈則被大的迭代所包含，是由最小均方所形成，不斷地迭代來更新formula_21的值。壓縮取樣匹配追蹤(Compressive Sampling Matching Pursuit, CoSaMP).在進行該還原演演算法前需要額外的輸入引數-稀疏性數量K(訊號非零項的數量)。和一般的貪婪迭代演演算法一樣，整個還原過程同樣是由(1)匹配追蹤(找出內積最大的列)、(2)還原值估計(透過最大內積列來估計還原值)、(3)剩餘值(residual)更新(透過估計還原值來更新誤差)不停地迭代組成。和正交匹配追蹤不同的是正交匹配追蹤在每次迭代的匹配追蹤上只尋找並增加一個內積最大的列；而壓縮取樣匹配追蹤則在每次迭代的匹配追蹤上尋找並增加2K個內積最大的列。壓縮取樣匹配追蹤過程：引數定義：π為相關向量、r(t)為在第t次迭代的剩餘值(residual)、ω為在π裡面最大的值、Ω為support的集合子空間追蹤(Subspace Pursuit,SP).子空間追蹤還原演演算法和壓縮取樣匹配追蹤還原演演算法相似，它們之間只有三個主要的差別。利用剩餘值(residual)是否有在迭代過程在降低來當成迴圈終止條件，因此使得子空間追蹤收斂的速度比壓縮取樣匹配追蹤來的更快。迭代閾值演演算法(Iterative Thresholding Algorithm).相較於凸鬆弛演演算法，迭代方法在壓縮感知還原訊號的速度更快。對於這類演算法，主要透過過軟閾值或硬閾值來正確的重建訊號，而閾值的大小則會根據迭代次數進行調整。 最近提出了擴充套件匹配追蹤(Expander Matching Pursuits)、稀疏匹配追蹤(Sparse Matching Pursuit)和序列稀疏匹配追蹤(Sequential Sparse Matching Pursuits)，實現了近線性還原時間。組合/次線性演演算法(Combinatorial/Sublinear Algorithms).這類演算法透過分組測試來還原稀疏訊號。與凸鬆弛演演算法或貪婪演演算法相比，它們有高速和高效的好處，然而對於測量矩陣formula_38有特定模式稀疏的要求。代表性的演演算法有傅裡葉取樣演算法(Fourier Sampling Algorithm)和鍊式追蹤(Chaining Pursuits)。非凸最小化演演算法(Non Convex Minimization Algorithms).非凸區域性最小化技術透過用formula_39規範替換formula_40規範來從更少的測量中恢復CS訊號，其中formula_41。非凸最佳化主要應用於醫學影像斷層掃描、網路狀態推斷、資料串流壓縮。提出了許多使用這種技術的演演算法，例如聚焦欠定系統解法(Focal Underdetermined System Solution, FOCUSS)、迭代重新加權最小平方法(Iterative Re-weighted Least Squares)、稀疏貝葉斯學習演算法(Sparse Bayesian Learning Algorithms)、基於蒙特卡羅(Monte-Carlo based Algorithms)的演演算法。布里格曼迭代演演算法(Bregman Iterative Algorithm).這些演算法提供了一種解決最小化問題的簡單而有效的方法。出了一個新的想法，它透過布里格曼迭代正則化方法產生一系列無約束子問題給出約束問題的精確解。當應用於壓縮感知問題時，使用布里格曼的迭代方法能在四到六次的迭代中實現還原。與其他現有演演算法相比，這些演算法的計算速度特別吸引人。