壓縮感知

概覽

訊號處理領域中的一個常見問題就是從一系列的採樣中重建原本的訊號。一般而言，未被採樣的部分訊號，是不可能重建出來的。然而通過藉助對於訊號（性質）的預先了解或合理假設，完美地通過一系列採樣重建原訊號就成為了可能。隨著科學的發展，數學家們逐步增進了如何作出合理假設的能力，並慢慢了解到在何種情況下可將這些假設一般化、推廣化。
訊號處理領域中的一次較早的突破是奈奎斯特採樣定理的提出。這一定理證明了若訊號的最高頻率小於採樣頻率的一半，便可完美地從採樣結果中恢復原本訊號，因此定義了採樣定理取樣頻率的下限。這種資料取得模式先採樣再壓縮，需要大量的時間壓縮和空間儲存資料，這限制了高速訊號處理的發展，也給硬體的即時處理帶來了極大的挑戰。
在2004年左右，Emmanuel Candès、陶哲軒和David Donoho證明了在已知訊號稀疏性的情況下，可能憑藉較採樣定理所規定更少的採樣數重建原訊號，這一理論也是壓縮感知的基石。

問題定義

一般來說，一個常見的線性系統問題，有m個方程式, n個未知數，可以被定義如下：
其中
在通訊系統之中，y是被收到的訊號，而s則是要被重建的訊號，一般來說會有以下兩種情況：
1.，也就是說方程式的數量大於等於未知數的數量，這種情況發生的時候就可以利用最小平方法去求得最接近的解，求得的解如下：
其中是偽逆矩陣。
2.，也就是未知數的數量比方程式的數量來的多，這個方程組就被稱為欠定線性系統，一般而言有無數個解，因此我們無法使用最小平方法去求得要重建的訊號。
但是，如果這個欠定線性系統只有唯一一個稀疏解，那麼我們可以利用壓縮感知理論和方法來尋找這個解。值得注意的是，並不是所有欠定線性方程組都具有稀疏解。
舉例來說，是一個欠定線性系統，我們會有無限多個解可以滿足這個方程式，然而當我們加入稀疏性的特性之後，也就是說之間只有一個有值，另外一個必定為0，我們就可以很輕易地得到這個欠定線性系統的解為或是，這個就是壓縮感知的最主要的精神所在。

從下圖我們可以輕易地了解，當解具有稀疏的特性時，就可以從欠定線性系統有無限多組解的情況變成可以利用最小平方法找出解的情況。

稀疏性

一個向量的稀疏性可以被定義如下：
的個數。
也就是計算一個向量之中非零的個數，舉例來說，如果，，因此目標的解就會變成如下：
希望能在非零個數越少的情況之下，找到最有可能的解。然而在實際中，最佳化L0範數是一個NP難的問題，需要窮舉s中非零值的所有排列可能，因而無法求解。通常採取的手段是對L1範數進行最佳化求解，最佳化目標則變為：
或是使用匹配追蹤系列演算法、疊代閾值法以及專門處理二維圖像問題的最小全變分法等求得次最佳解的演算法進行計算。

有限等距性質(Restricted Isometry Property, RIP)

有限等距性質(RIP)是壓縮還原演算法中常常可以看見的名詞，主要可以被用來分析還原演算法的表現好壞。其定義如下：
其中的代表傳感矩陣，代表的是訊號能量，可以表示如下：
因此整個式子可以視為訊號跟傳感矩陣的相似程度，也就是做完轉換後的能量，要被RIP限制住，而RIP要求。

結構簡化採樣矩陣

目前較常被使用的兩種結構簡化採樣矩陣為循環矩陣與常對角矩陣
循環矩陣的形式為下式：
常對角矩陣的形式為下式：
，
其中。
可以發現到，若採用循環矩陣作為測量矩陣的話，我們只需要存取一列的矩陣元素；相反地，若使用常對角矩陣，除了第一列的矩陣元素外，需要額外儲存第一行的矩陣元素。
但是經過實驗發現，常對角矩陣的相干性是低於循環矩陣的，因此使用者可以依據自己的使用環境，來找到一個平衡點。
採用這兩種矩陣進行壓縮感知取樣時，可以大幅降低儲存成本，也為此演算法的前端感測器大幅降低實現門檻。

數值簡化採樣矩陣

數值簡化採樣矩陣普遍將原有的、按照高斯分布隨機取值的採樣矩陣元素以數值上更為簡單的元素取代，但在分布上維持矩陣元素的分布隨機性——即縮減了儲存浮點數這一方面的成本。
一種較為基本的數值簡化採樣矩陣是0-1伯努利矩陣，其中的元素僅有0和1兩種，分布模式為相同獨立的伯努利分布（identical independent Bernoulli distribution）。
對於每一個矩陣元素，該分布的概率品質函式為：

求解/重構方法

壓縮感知利用了很多訊號中所存在的冗餘（換言之，這些訊號並非完全是噪聲）。具體而言，很多訊號都是「稀疏」的；在適當的表示域中，它們的很多係數都是等於或約等於零。 
在訊號取得階段，壓縮感知在訊號並不稀疏的域對訊號進行線性測量。
為了從線性測量中重構出原來的訊號，壓縮感知求解一個稱為L1-範數正規化的最小二乘問題。從理論上可以證明，在某些條件下，這個正規化最小二乘問題的解正是原欠定線性系統的稀疏解。

基追蹤

基追蹤（basis pursuit）是一種訊號重建演算法，被廣泛地用於壓縮感知領域，屬於數學最佳化問題的範疇，形式為。
其中s是n×1向量，表示輸出（訊號），y是m×1的測量向量，H是m×n的「轉換矩陣」或稱作「測量矩陣」，其中M < N。
基追蹤常在需要完美滿足欠定線性方程組系統中時被應用，且要求解在L₁基準下為最稀疏的。
若應用情景允許降低對完美恢復的要求，以換取更加稀疏的解s，降噪基追蹤（basis pursuit denoising）更為適用。

匹配追蹤

匹配追蹤（Matching pursuit）是一種稀疏近似運算，旨在找到多維資料在某個超完備字典（dictionary）上對映的「最佳匹配」。其基本的概念就是要用來自的函式組（稱為基元，或atom）的加權和來表示希爾伯特空間上的訊號：
其中表示被選取基元的序數，是每個基元的加權常數。對於固定的字典，匹配追蹤會先找到與訊號間內積最大的一個基元，再減去該基元帶來的影響，然後重複找尋影響力次大的基元直到訊號被較好地分解。
相較而言，以傅立葉級數表示的訊號來說，字典是構建於正弦基函式之上的。訊號處理領域中傅立葉分析的主要缺點就在於它只能提取出訊號中常存的特徵，而不能適應目前的分析目標訊號。
若採用一組極端保險、帶有大量冗餘的字典，我們就能夠找到可以完美匹配訊號的函式組。在對訊號進行編碼與壓縮時，最好是能夠找到一組對映，使加權和中的大部分係數都接近零（具有「稀疏性」）。

正交匹配追蹤

正交匹配追蹤(Orthogonal Matching Pursuit)是匹配追蹤的特殊形式，正交匹配追蹤的演算法與匹配追蹤相同，但是正交匹配追蹤不會重複使用同一個基元來進行匹配，因此會比匹配追蹤更快收斂。

疊代閾值演算法

疊代閾值演算法(Iterative Shrinkage-Thresholding Algorithm)是上述基於貪婪演算法(Greedy Algorithm)之匹配追蹤與正交匹配追蹤的替代演算法，疊代演算法主要是透過不斷的投影和取閾值來進行收斂，而他在每次疊代中，都還可以進行其他最佳化例如:Wigener 濾波，不僅可以降低運算複雜度，也可以提高還原品質。

正交匹配追蹤(Orthogonal Matching Pursuit)

正交匹配追蹤是一個用來解決壓縮感知問題的演算法，在一定的複雜度之下有不錯的表現，他背後最主要的想法是源自於貪婪演算法(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未知的情況下獲得較好的重建效果。

疊代閾值演算法(Iterative Shrinkage-Thresholding Algorithm)

疊代閾值演算法是從Relaxation Method啟發而來，Relaxation Method是用於解決具有稀疏性的線性系統。

在疊代閾值演算法中，問題一樣是被定義為：
而在此演算法中，每一次的疊代主要分成兩部分：1、尋找新的解。2、更新殘值。
第一階段，主要是利用投影的方式找到更新的向量方向，再透過取閾值的方式來進行最佳化。
而是relaxation parameter，且。
而就是閾值函式(thresholding function)，主要就是為了使疊代的過程中，逐漸逼近具有稀疏性性質的解，而目前主要有兩大類取閾值的方式：硬閾值函式(Hard Thresholding Function)與軟閾值函式(Soft Thresholding Function)。

硬閾值函式就是將小於閾值(thr)的解，一律通通過濾成0。
而軟閾值函式則是使用較為平滑的方式，將值逼近於稀疏性的解
，而是Indicator Function
而第二階段，則是利用新算出來的來進行殘差更新。
之後一直等到規定的迴圈數抵達即完成還原。
而此演算法是Landweber iteration的變形，若我們沒有加入閾值函式的話，就會收斂到。

稀疏性空間投影

壓縮感知還原演算法包括整個壓縮感知都是建立在訊號有稀疏性上，但是並不是所有的訊號都天然具有稀疏性，例:聲音。那麼是否不具有稀疏性的訊號就不能使用壓縮感知呢？答案為並不是，天然不具有稀疏性的訊號還是能夠使用壓縮感知，只需要把該訊號投影到其他空間，其他該訊號有稀疏性的空間下，壓縮感知就可直接使用在該投影空間上。可以被定義如下：
s:要被重建的訊號(原訊號)；ψ:投影矩陣，把非稀疏性訊號投影到稀疏性空間；z:非零項遠小於零項
故原壓縮感知公式定義也隨之改變：
所以可以把視為原本壓縮感知公式裡面的H，還原演算法即可一樣使用。
至於的選擇對於不同訊號來說有很多種，有離散餘弦變換(DCT) ,離散小波變換(DWT)，字典學習(Dictionary Learning)等。

相關應用

壓縮感知與包括欠定系統、群驗、稀疏編碼、復用、稀疏採樣等。在成像科技領域，亦有許多技術如（編碼孔與計算攝影學）與壓縮感知相關。亦有許多在不同技術完成度下將壓縮感知實現的案例。

攝影學

壓縮感知技術被用於手機網路攝影機感測器設計中。這一技術使得在取得圖像時所耗費的能量大大降低，可達原先耗費的15分之一——當然，需要引入複雜的解壓演算法；這一運算可能會需要離線狀態下的預先安裝、設定。
壓縮感知亦被用於實現單像素攝影。貝爾實驗室運用了這一技術，用無鏡片單像素相機在柵格中隨機選取的孔隙處拍照，以達到成像效果。隨著拍照次數的逐漸增多，相片品質也會逐步提高；一般來說，這種技術較之傳統的攝影成像技術僅僅需要一小部分的資料占用量，且能完全避免與鏡片或聚焦相關的故障或失常；參見 。

全像成像

壓縮感知可被用於增加通過單幅全像圖中所能得到的立體像素的數量改進全像攝影技術中的圖像重建問題。在光學全像圖或毫米波全像圖取樣率不足的情況下，這一技術也能夠被用於圖像檢索以作出改善。

面部辨識

壓縮感知目前被用於面部辨識應用之中，參見Engineers Test Highly Accurate Face Recognition。

核磁共振成像

壓縮感知也被應用在醫療影像上，特別是核磁共振成像(Magnetic Resonance Imaging, MRI)，具有稀疏的特性，因此能使用壓縮感知的技術。在過去核磁共振成像會因為物理學、生理學上的限制，而有掃描時間較長的問題，如今壓縮感知利用核磁共振成像具有的稀疏特性，來改善成像品質以及降低所需要量測數量，能有效縮短核磁共振的掃描時間，近期相關的壓縮感知演算法也被廣為討論，可以參見 、 與，其中涉及的重建方法包括ISTA、FISTA、SISTA等。

地震成像

一般來說地震成像既不稀疏，也不可壓縮，具有高維度、大面積的特性，因此會耗費大量的量測以及運算時間，所以希望能降低取樣的次數，同時能保有原本的品質。因此有人利用壓縮感知技術將取樣以及編碼同時進行，來達到降低維度的目的，最後再透過壓縮感知的還原演算法進行還原，可以參考。

類比資訊轉換(Analog-to-Information Converter, AIC)

在通訊系統當中會遇到高頻寬的問題，因此會需要較高的取樣頻率，然而其中的訊號可能含有的資訊是遠小於頻寬的，因此就會浪費軟、硬體的資源來進行取樣。所以有人提出用類比資訊轉換(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)可以被視為一組加密後的鑰匙，能對訊號進行壓縮並同時加密，而不需要額外的運算，可以參考。