壓縮感知

壓縮感知（英語：Compressed sensing或Compressive sensing），也被稱為壓縮採樣（英語：Compressive sampling）或稀疏採樣（英語：Sparse sampling），是一種尋找欠定線性方程組的稀疏解的技術。壓縮感知被應用於電子工程尤其是信號處理中，用於獲取和重構稀疏或可壓縮的信號。該方法利用信號本身或其線性變化域稀疏的特性，相較於奈奎斯特–香農採樣定理（英語：Nyquist–Shannon sampling theorem），能夠通過較少的測量數據（英語：measurements）重建出原始信號。得益於壓縮感知能夠在少量採樣次數的情況下大致重建出原始信號或圖像，其目前被廣泛運用於核磁共振、單像素成像、快照式光譜成像等需要在少量採樣的情況下重建信號的領域。

## 概述

信號處理領域中的一個常見問題就是從一系列的採樣中重建原本的信號。一般而言，未被採樣的部分信號，是不可能重建出來的。然而通過藉助對於信號（性質）的預先了解或合理假設，完美地通過一系列採樣重建原信號就成為了可能。

信號處理領域中的一次較早的突破是奈奎斯特–香農採樣定理的提出。這一定理證明了若信號的最高頻率小於採樣頻率的一半，便可完美地從採樣結果中恢復原本信號，因此定義了採樣定理取樣頻率的下限。這種數據獲取模式先採樣再壓縮，需要大量的時間壓縮和空間存儲數據，這限制了高速信號處理的發展，也給硬體的實時處理帶來了極大的挑戰。

在2004年左右，伊曼紐爾·坎德斯（英語：Emmanuel Candès）、戴維·多諾霍（英語：David Donoho）、Justin Romberg和陶哲軒（英語：Terence Tao）證明了在已知信號稀疏性的情況下，可能憑藉較採樣定理所規定更少的採樣數重建原信號，這一理論也是壓縮感知的基石。

## 問題定義

壓縮感知主要用於解決欠定線性方程問題。對於一個常見的線性方程問題，有$m$個方程式和 $n$個未知數，其用數學表達為$\mathbf{y}=\mathbf{\Phi}\mathbf{x},$其中$\mathbf{\Phi}\in \mathbb{R}^{m \times n}$, $\mathbf{x}\in \mathbb{R}^{n}$, $\mathbf{y}\in \mathbb{R}^{m}$。在通訊系統中，$\mathbf{y}$是被收到的訊號，而$\mathbf{x}$則是要被重建的訊號。若要依據該線性方程組對$\mathbf{x}$進行重建，則會出現兩種情況。

第一種情況，當$m\geq n$時，也就是說方程式的數量大於等於未知數的數量。這種情況下，除非矩陣$\mathbf{\Phi}$的秩小於$n$，否則並不是需要使用壓縮感知求解，而是直接利用最小平方法去求得最接近的解$\hat{\mathbf{x}}=\mathbf{\Phi}^\dagger \mathbf{y}$，其中$\ \mathbf{\Phi}^\dagger:=(\mathbf{\Phi}^T \mathbf{\Phi})^{-1} \mathbf{\Phi}^T$是矩陣$\mathbf{\Phi}$的穆爾-彭羅斯廣義逆矩陣（英語：Moore–Penrose pseudoinverse matrix）。

第二種情況，當$m< n$，也就是未知數的數量多於方程式的數量時，該欠定線性方程組是有無數個解的，因此無法使用最小平方法去求得要重建的訊號。

但是，如果這個欠定線性系統只有唯一一個稀疏解，那麼我們可以利用壓縮感知理論和方法來尋找這個解。值得注意的是，並不是所有欠定線性方程組都具有稀疏解。舉例來說，若一個線性方程組

$$\begin{cases}2=x_1+x_2 + x_3 + x_4 \\ 4 = x_1 + 2 x_2 + x_3 + x_4\end{cases}$$

或通過矩陣表示為

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

其是一個欠定線性系統，會有無限多個解可以滿足這個方程式，然而若加入該信號的稀疏限制條件：「$x_1,x_2, x_3, x_4$之間只有一個有值，其餘都是0」，便可以得到這個欠定線性系統的解為$\mathbf{x}=\begin{bmatrix}0,2, 0, 0\end{bmatrix}^T$，這個就是壓縮感知的最主要的精神所在：僅根據部分採樣數據，在已知信號的先驗條件（本例中為信號的稀疏性）情況下，亦可以重建出原始信號。

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

<image>

- 當訊號具有稀疏的特性時，線性系統就可以從無限多組解的情況，變成有解的情況。

因此，以下三個方面即為壓縮感知的主要研究重點：

- 採樣方式，即該如何對原始信號採樣
- 設計先驗，即如何預設某信號先驗條件
- 重建演算法，即如何根據採樣數據和先驗條件進行重建

## 採樣方式

在壓縮感知中，選取的採樣矩陣需要滿足有限等距性質(英語：Restricted Isometry Property, RIP)，其定義如下：

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

其中$0<\delta <1$。$\|\cdot \|_2$表示$\ell_2$範數，可用於計算信號能量。因此整個式子可以視為信號$\mathbf{x}$跟傳感矩陣$\mathbf{\Phi}$的相似程度，即做完轉換後的能量需要在合理範圍之內。

另外，在理論上，為了確保信號重建的準確度，需要令所採用的取樣矩陣各行列之間相干性儘量地低，且須矩陣元素取值隨機性儘量地高。

相干性可定義為$\mu\bigl(\mathbf{\Phi}\bigr):=\max_{l\neq m}\left \vert \phi_l^T\phi_m\right \vert$，即取樣矩陣任兩個相異的行做內積後，取絕對值所產生的最大值，可以用來衡量信號重建的準確度。

而目前對於採樣矩陣$\mathbf{\Phi}\in \mathbb{R} ^{m\times n}$，有下列幾種選擇可以使還原重建度有一定品質：

- 對$n$個$\mathbf{\Phi}$的行向量在$m$維的單位半徑球面上進行隨機採樣;
- 對任一個$\mathbf{\Phi}_{i,j}$都採用相同獨立的高斯分布$\mathcal{N}(0,1/m$)進行隨機採樣;
- 對任一個$\mathbf{\Phi}_{i,j}$都採用如下式相同獨立的分布進行隨機採樣$P(\mathbf{\Phi}_{i,j}=\pm1/\sqrt{m})=1/2$;

除了上述的可能，現在也已經證實任何一個亞高斯分布的矩陣也可以成為一個很好的測量矩陣，也就是說具有很好的還原效果。另外，隨著機器學習和深度學習的發展，一些測量矩陣也可以通過訓練的方式獲取。

然而，對於上述矩陣，其所需要的數據存儲量過於龐大——每個矩陣元素都要單獨記錄，且數據類型一般為浮點數——這就促進了簡化取樣矩陣的研究；目前被提出的簡化取樣矩陣主要包括兩種：結構簡化採樣矩陣與數值簡化採樣矩陣。

### 結構簡化採樣矩陣

目前較常被使用的兩種結構簡化採樣矩陣為循環矩陣與常對角矩陣

循環矩陣的形式為下式：

$$\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}$$

常對角矩陣的形式為下式：

$$\mathbf{\Phi} = \begin{bmatrix} <pre> \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} \\ </pre> \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）。

對於每一個矩陣元素，該分布的機率質量函數$f$為： $f(k;p) = \begin{cases} p & \text{if }k=1, \\[6pt] 1-p & \text {if }k=0.\end{cases}$

## 設計先驗

壓縮感知利用了很多信號中所存在的冗餘（換言之，這些信號並非完全是噪聲）。具體而言，很多信號都是「稀疏」的；在適當的表示域中，它們的很多係數都是等於或約等於零。

一個向量$\mathbf{x}$的稀疏性可以被定義為：

$\left \Vert\mathbf{x} \right \Vert_0 := \sum_i |x_i|^0$。

也就是計算一個向量之中非零的個數，舉例來說，如果$\mathbf{x}=\begin{bmatrix}0, 0, 1, 0, 1, 0, 0\end{bmatrix}^T$，則$\left \Vert \mathbf{x} \right \Vert_0=2$，因此目標的解就會變成如下：

$$\min_\mathbf{x}\|\mathbf{x}\|_0\ \quad \mbox{subject to} \quad \ \mathbf{y}=\mathbf{\Phi}\mathbf{x}$$

希望能在非零個數越少的情況之下，找到最有可能的解。然而在實際中，最優化$\ell_0$範數是一個NP難的問題，需要窮舉$\mathbf{x}$中非零值的所有排列可能，因而無法求解。通常採取的手段是對$\ell_1$範數進行最優化求解，優化目標則變為：

$$\min_\mathbf{x}\|\mathbf{x}\|_1\ \quad \mbox{subject to} \quad \ \mathbf{y}=\mathbf{\Phi}\mathbf{x}$$

在信號獲取階段，壓縮感知在信號並不稀疏的域對信號進行線性測量。

為了從線性測量中重構出原來的信號，壓縮感知求解$\ell_1$範數正則化的最小二乘問題。從理論上可以證明，在某些條件下，這個正則化最小二乘問題的解正是原欠定線性系統的稀疏解。

或是使用匹配追蹤系列演算法、迭代閾值法以及專門處理二維圖像問題的最小全變分法等求得次最優解的演算法進行計算。

## 重建演算法

### 基追蹤

基追蹤（英語：Basis Pursuit，BP）是一種信號重建演演算法，被廣泛地用於壓縮感知領域，屬於數學最優化問題的範疇，形式為$\min_\mathbf{x} \|\mathbf{x}\|_1 \quad \mbox{subject to} \quad \mathbf{y} = \mathbf{\Phi}\mathbf{x}$。

基追蹤常在需要完美滿足欠定線性方程組系統中$\mathbf{y} = \mathbf{\Phi}\mathbf{x}$時被應用，且要求解在$\ell_1$範數下為最稀疏的。

若應用情景允許降低對完美恢復的要求，以換取更加稀疏的解$\mathbf{x}$，降噪基追蹤（英語：basis pursuit denoising）更為適用。

### 匹配追蹤

匹配追蹤是一種稀疏近似運算，旨在找到多維數據在某個超完備字典（dictionary）$D$上映射的「最佳匹配」。其基本的概念就是要用來自$D$的函數組$g_{\gamma_n}$（稱為基元，或atom）的加權和來表示希爾伯特空間$H$上的信號$f$：

$$f(t) = \sum_{n=0}^{+\infty} a_n g_{\gamma_n}(t)$$

其中$n$表示被選取基元的序數，$a_n$是每個基元的加權常數。對於固定的字典，匹配追蹤會先找到與信號間內積最大的一個基元，再減去該基元帶來的影響，然後重複找尋影響力次大的基元直到信號被較好地分解。

相較而言，以傅立葉級數表示的信號來說，字典是構建於正弦基函數之上的。信號處理領域中傅立葉分析的主要缺點就在於它只能提取出信號中常存的特徵，而不能適應當前的分析目標信號$f$。

若採用一組極端保險、帶有大量冗餘的字典，我們就能夠找到可以完美匹配信號的$f$函數組。在對信號進行編碼與壓縮時，最好是能夠找到一組映射，使加權和中的大部分係數都接近零（具有「稀疏性」）。

### 正交匹配追蹤

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

### 迭代閾值演算法

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

### 深度學習方法

隨著深度學習的發展，一些方法直接通過神經網路學習從$\mathbf{y}$到$\mathbf{x}$的映射函數，從而實現壓縮感知重建。

特別地，一些深度學習方法結合了上述的傳統迭代演算法，從而使得重建質量更高，重建過程更具可解釋性。這類方法被稱為深度展開網路（英文：Deep Unfolding Network）。例如，ISTA-Net將ISTA演算法展開，並且用神經網路替代ISTA演算法中的閾值收縮步驟；DMP-DUN提出基於AMP演算法的DMP演算法，從而能夠利用擴散模型的先驗知識實現重建。

## 相關應用

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

### X射線晶體學

壓縮感知在X射線晶體學中的應用主要體現在相位回復問題的研究上。相位回復在X射線晶體結構分析中至關重要，因為晶體結構與其X射線繞射效應之間存在傅里葉轉換關係。傳統方法中，僅能獲得繞射強度的振幅資訊，缺乏相位資訊，這使得直接重建晶體結構變得困難。

為解決這一問題，有學者將壓縮感知應用於相位回復，提出了壓縮相位回復(Compressive phase retrieval)。該方法利用訊號的稀疏性，通過較少的測量數據成功回復原始訊號。在隨機傅里葉轉換模型下，僅需少量隨機的傅里葉測量，即可回復稀疏訊號。

此外，壓縮感知還被用於提升X射線成像的解析度和穩定性，尤其是將壓縮感知與深度學習相結合的創新方法，進一步優化了圖像重建的效果。

### 攝影學

壓縮感知技術被用於手機攝像頭傳感器設計中。這一技術使得在獲取圖像時所耗費的能量大大降低，可達原先耗費的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)可以被視為一組加密後的鑰匙，能對信號進行壓縮並同時加密，而不需要額外的運算，可以參考。

## 範例

### 正交基展開

正交基展開採用的是完全正交基（英語：complete and orthogonal basis set）來進行展開，而壓縮感知採用的是過完備的非正交基集（英語：over-complete and non-orthogonal basis set）來展開訊號。

傅立葉級數展開是正交基展開（orthogonal basis expansion）的方法:

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

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

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

PSWF 展開則是過完備的非正交基集展開（over-complete and non-orthogonal basis expansion）的方法:

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

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

#### 分類

壓縮感知希望處理的問題是：

假設 $b_{0}(t), b_{1}(t), b_{2}(t), b_{3}(t), \cdots$ 組成一個過完備的非正交基集

##### 問題一

我們希望最小化 $||c||_0$ ( $\lVert \cdot \rVert_0$ 是 $L_0$ 範數， $||c||_0$ 意指$c_m$ 的值不為0 的個數)，使得：

$$x(t) \approx <pre> \sum _{m} c_{m}b_{m}(t)$$

##### 問題二

我們希望最小化 $||c||_0$，使得：

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

##### 問題三

限制 $||c||_0$ 為 M，我們想要最小化：

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

### 匹配追蹤

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

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

第1步輸入：$x(t)$,初始化: $n = 0, x_{r}(t) = x(t)$

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

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

第4步$x_r(t) = x_r(t) - u_n {\displaystyle \phi}_n (t)$

第5步$n = n + 1$

第6步檢查下列條件是否符合，若不符合，回到第2步；若符合，則進到第7步

問題一:是否滿足 $x_r(t) = 0$

問題二:是否滿足 $\int x_{r}^{2}(t)\mathrm {d} t < \text{threshold}$

問題三:是否滿足$n = M$

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

### 基追蹤（Basis Pursuit）

將 $L_0$ 範數改為 $L_1$ 範數

$$\lVert c \rVert _1 = |c|_0 + |c|_1 + |c|_2 + ......$$

問題一:

我們想要最小化 $||c||_1$，使得：

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

問題二:

我們想要最小化 $||c||_1$，使得：

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

問題三:

令$\lVert c \rVert_1 \le M$，我們想要最小化：

$$\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向量當中最有可能是非零的位置。

一開始會有一個空集合$\Lambda_0$，以及剩餘的部分$r_0$，每次疊代都會從$\overline{\Lambda{_{l-1}}}$找出一個A矩陣投影到剩餘$r_{l-1}$有最大值的位置，把這個位置加到$\Lambda_l$之中，並從$\overline{\Lambda{_{l}}}$當中移除，最後再更新剩餘$r_{l}$。利用疊代的方式，不斷地找出x向量當中最有可能非零的位置，直到達到演演算法停止條件。

<image>

- 正交匹配追蹤演演算法

在正交匹配追蹤演算法的基礎上，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是用於解決具有稀疏性的線性系統。

在迭代閾值演算法中，問題一樣是被定義為：$\min \|x\|_1\ \ subject\ to\ y=Ax$而在此演算法中，每一次的迭代主要分成兩部分：1、尋找新的解$x^{t+1}$。2、更新殘值$r^t$。

第一階段，主要是利用投影的方式找到更新的向量方向，再透過取閾值的方式來進行優化。$x^{t+1}=\eta_{thr}(x^t+\mathcal{K}\times(A^Tr^t))$而$\mathcal{K}$是relaxation parameter，且$\mathcal{K}\in(0,1)$。

而$\eta_{thr}(.)$就是閾值函數(thresholding function)，主要就是為了使迭代的過程中，逐漸逼近具有稀疏性性質的解，而目前主要有兩大類取閾值的方式：硬閾值函數(Hard Thresholding Function)與軟閾值函數(Soft Thresholding Function)。

硬閾值函數就是將小於閾值(thr)的解，一律通通過濾成0。$\eta_{thr}^H(x)=\begin{cases} x, \text{if }|x|>thr\\0,\text{otherwise} \end{cases}$而軟閾值函數則是使用較為平滑的方式，將值逼近於稀疏性的解$\eta_{thr}^S(x)=\sgn(x)(|x|-thr)_+\text{, where }(z)_+=z\times\mathbb{I}(z\geq0)$，而$\mathbb{I}(.)$是指示函數而第二階段，則是利用新算出來的$x^{t+1}$來進行殘差更新。$r^{t+1}=y-Ax^{t+1}$之後一直等到規定的迴圈數抵達即完成還原。

而此演算法是Landweber iteration的變形，若沒有加入閾值函數的話，就會收斂到$\min \|y-Ax\|_2^2$。

### 稀疏性空間投影

壓縮感知還原演演算法包括整個壓縮感知都是建立在信號有稀疏性上，但是並不是所有的信號都天然具有稀疏性，例:聲音。那麼是否不具有稀疏性的信號就不能使用壓縮感知呢？答案為並不是，天然不具有稀疏性的信號還是能夠使用壓縮感知，只需要把該信號投影到其他空間，其他該信號有稀疏性的空間下，壓縮感知就可直接使用在該投影空間上。可以被定義如下：

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

s:要被重建的訊號(原信號)；ψ:投影矩陣，把非稀疏性信號投影到稀疏性空間；z:非零項遠小於零項

<image>

故原壓縮感知公式定義也隨之改變：

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

所以可以把$\Theta$視為原本壓縮感知公式裡面的H，還原演演算法即可一樣使用。

至於$\psi$的選擇對於不同信號來說有很多種，有離散餘弦變換(DCT) ,離散小波變換(DWT)，字典學習(Dictionary Learning)等。

#### 離散餘弦變換和離散小波變換

利用信號經過這兩種變換後都會有稀疏性的特性，把這兩種變換變成矩陣形式，讓信號直接投影到具有稀疏性的空間上。

好處

- 不需要特別針對信號做不同$\psi$的選擇，對於絕大部分信號可以直接使用。
- 並不需要前處理，可以直接使用。

壞處

- 限制了原信號的維度，必須滿足n = $2^x$,x為任意正整數。
- 因為通用所有信號，故經過壓縮感知還原演演算法後還原的信號品質較差。

#### 字典學習

顧名思義即把$\psi$當作一本要學習的字典，不斷的利用該信號和還原演演算法後的結果做字典的更新，直到找到一個$\psi$能夠把該信號投影到稀疏性空間上。

<image>

字典學習的流程：

- 設定字典學習的學習次數(Iter)
- 收集一定量(L筆)要學習的資料s,組成S = s1, s2, ... ,sL
- 固定$\psi$，利用還原演演算法找出每一筆資料的z，組成Z = z1, z2, ... ,zL
- $\underset{c}{min}$

$|_F^2$ s.t.

zi

0 < Kth $\forall$i

- 固定Z，利用3.所得之Z來更新字典
- 當Z固定時，定義誤差ei = si - $\psi$zi，組成E = e1, e2, ... ,eL
- 所以整體的均方誤差為

$|_F^2$=

e1, e2, ... ,eL |$|_F^2$ =

$|_F^2$

- 在Z固定下使得E最小，將得到關係式 (S - $\psi$Z)ZT = 0
- => $\psi$= SZT(ZZT)-1
- 檢查Z上面是否已經有稀疏性，如有則結束學習；如沒有則回到3.直到達到學習的次數

字典學習的演演算法有很多，較為常用的有Method of optimal directions(MOD)。

好處

- 因為針對該種類信號做學習，故還原後的品質較好。
- 對原信號的維度並沒有任何限制。

壞處

- 需要事前收集該種類的信號做學習，不能未學習直接使用。
- 因為針對該種類信號做學習，故直接使用在不同種類信號效果較差/不適用。

## 外部連結

- "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