壓縮感知

壓縮感知（Compressed sensing），也被稱為壓縮採樣（Compressive sampling）或稀疏採樣（Sparse sampling），是一種尋找欠定線性系統（英語：Underdetermined system）的稀疏解的技術。壓縮感知被應用於電子工程尤其是信號處理中，用於獲取和重構稀疏或可壓縮的信號。這個方法利用訊號稀疏的特性，相較於奈奎斯特理論，得以從較少的測量值還原出原來整個欲得知的訊號。核磁共振就是一個可能使用此方法的應用。這一方法至少已經存在了四十年，由於Emmanuel Candès（英語：Emmanuel Candès）、戴維·多諾霍、Justin Romberg和陶哲軒的工作，最近這個領域有了長足的發展。

概覽

信號處理領域中的一個常見問題就是從一系列的採樣中重建原本的信號。一般而言，未被採樣的部分信號，是不可能重建出來的。然而通過藉助對於信號（性質）的預先了解或合理假設，完美地通過一系列採樣重建原信號就成為了可能。隨着科學的發展，數學家們逐步增進了如何作出合理假設的能力，並慢慢了解到在何種情況下可將這些假設一般化、推廣化。

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

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

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

範例

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

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

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

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

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

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

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

分類

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

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

問題一

我們希望最小化 ${\displaystyle ||c||_{0}}$ ( ${\displaystyle \lVert \cdot \rVert _{0}}$ 是 ${\displaystyle L_{0}}$ 範數， ${\displaystyle ||c||_{0}}$ 意指${\displaystyle c_{m}}$ 的值不為0 的個數)，使得：

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

問題二

我們希望最小化 ${\displaystyle ||c||_{0}}$ ，使得：

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

問題三

限制 ${\displaystyle ||c||_{0}}$ 為 M，我們想要最小化：

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

方法

方法一：匹配追蹤（貪心算法）

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

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

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

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

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

[第4步]${\displaystyle x_{r}(t)=x_{r}(t)-u_{n}{\displaystyle \phi }_{n}(t)}$

[第5步]${\displaystyle n=n+1}$

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

問題一:是否滿足 ${\displaystyle x_{r}(t)=0}$

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

問題三:是否滿足${\displaystyle n=M}$

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

方法二:基追蹤（Basis Pursuit）

將 ${\displaystyle L_{0}}$ 範數改為 ${\displaystyle L_{1}}$ 範數

${\displaystyle \lVert c\rVert _{1}=|c|_{0}+|c|_{1}+|c|_{2}+......}$

問題一:

我們想要最小化 ${\displaystyle ||c||_{1}}$ ，使得：

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

問題二:

我們想要最小化 ${\displaystyle ||c||_{1}}$ ，使得：

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

問題三:

令${\displaystyle \lVert c\rVert _{1}\leq M}$，我們想要最小化：

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

問題定義

一般來說，一個常見的線性系統問題，有m個方程式, n個未知數，可以被定義如下：

${\displaystyle y=Hs,}$其中${\displaystyle H\in \Re ^{m\times n},s\in \Re ^{n\times 1},y\in \Re ^{m\times 1}}$

在通訊系統之中，y是被收到的訊號，而s則是要被重建的訊號，一般來說會有以下兩種情況：

1.${\displaystyle m\geq n}$，也就是說方程式的數量大於等於未知數的數量，這種情況發生的時候就可以利用最小平方法去求得最接近的解，求得的解如下：

${\displaystyle s^{*}=(H^{T}H)^{-1}H^{T}y=H^{\dagger }y,}$其中${\displaystyle \ H^{\dagger }=(H^{T}H)^{-1}H^{T}}$是偽逆矩陣。

2.${\displaystyle m<n}$，也就是未知數的數量比方程式的數量來的多，這個方程組就被稱為欠定線性系統，一般而言有無數個解，因此無法使用最小平方法去求得要重建的訊號。

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

舉例來說，${\displaystyle 2=s_{1}+s_{2}+s_{3}+s_{4},4=s_{1}+2s_{2}+s_{3}+s_{4}}$是一個欠定線性系統，會有無限多個解可以滿足這個方程式，然而若加入稀疏的限制條件：${\displaystyle s_{1},s_{2},s_{3},s_{4}}$之間只有一個有值，其餘都是0；就可以很輕易地得到這個欠定線性系統的解為${\displaystyle {\bigl (}0,2,0,0{\bigr )}}$，這個就是壓縮感知的最主要的精神所在。

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

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

稀疏性

一個向量的稀疏性可以被定義如下：

${\displaystyle \left\Vert s\right\Vert _{0}=\{i:s_{i}\neq 0\}}$的個數。

也就是計算一個向量之中非零的個數，舉例來說，如果${\displaystyle s=[0\ 0\ 1\ 0\ 1\ 0\ 0]}$，${\displaystyle \left\Vert s\right\Vert _{0}=2}$，因此目標的解就會變成如下：

${\displaystyle s^{*}=\arg \min \|s\|_{0}\ ,s.t.\ y=Hs}$

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

${\displaystyle s^{*}=\arg \min \|s\|_{1}\ ,s.t.\ y=Hs}$

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

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

有限等距性質(RIP)是壓縮還原演算法中常常可以看見的名詞，主要可以被用來分析還原演算法的表現好壞。其定義如下：

${\displaystyle (1-\delta )\left\Vert s\right\Vert _{l_{2}}^{2}\leq \left\Vert Hs\right\Vert _{l_{2}}^{2}\leq (1+\delta )\left\Vert s\right\Vert _{l_{2}}^{2}}$

其中的${\displaystyle H}$代表傳感矩陣，${\displaystyle l_{2}}$代表的是信號能量，可以表示如下：

${\displaystyle \left\Vert x\right\Vert _{l_{2}}^{2}=\sum _{i=1}^{N}\left\vert x_{i}\right\vert ^{2}}$

因此整個式子可以視為信號${\displaystyle s}$跟傳感矩陣${\displaystyle H}$的相似程度，也就是做完轉換後的能量，要被RIP限制住，而RIP要求${\displaystyle 0<\delta <1}$。

取樣方法

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

相干性(coherence)可以簡單定義如下：

${\displaystyle \mu {\bigl (}H{\bigr )}=\max _{l\neq m}\left\vert \phi _{l}^{T}\phi _{m}\right\vert }$

也就是取樣矩陣任兩個相異的行做內積後，取絕對值所產生的最大值，可以用來衡量信號重建的準確度。

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

1. 對n個A的行向量在m維的單位半徑球面上進行隨機採樣
2. 對任一個${\displaystyle A_{i,j}}$都採用相同獨立的高斯分布N(0,${\displaystyle {\frac {1}{m}}}$)進行隨機採樣
3. 對任一個${\displaystyle A_{i,j}}$都採用如下式相同獨立的分布進行隨機採樣

${\displaystyle P(A_{i,j}=\pm {\frac {1}{\sqrt {m}}})={\frac {1}{2}}}$

除了上述的可能，現在也已經證實任何一個sub-gaussian的分布，都可以成為一個很好的測量矩陣，也就是說具有很好的還原效果。

而上述矩陣之所以常被拿來使用，主要是因為皆已經被驗證具有高機率性滿足有限等距性質，也就是相干性非常低，因此使用此方式進行訊號取樣後，仍可確保在信號具有足夠稀疏性的前提下得到較佳的壓縮感知重建效果。

且當使用上述矩陣時，只要訊號x的非零數目成下列關係，可以確保訊號被完美還原。

${\displaystyle m\geq C\times S\log({\frac {n}{S}})}$

而C是一個根據不同情況而改變的常數。

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

結構簡化採樣矩陣

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

循環矩陣的形式為下式：

${\displaystyle A={\begin{bmatrix}a_{1}&a_{2}&a_{3}&\dots &a_{n}\\a_{n}&a_{1}&a_{2}&&a_{n-1}\\a_{n-1}&a_{n}&a_{1}&&a_{n-2}\\\vdots &&&\ddots &\vdots \\a_{n-m+2}&a_{n-m+3}&a_{n-m+4}&\dots &a_{n-m+1}\end{bmatrix}}}$

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

${\displaystyle A={\begin{bmatrix}a_{0}&a_{-1}&a_{-2}&\ldots &\ldots &a_{-n+1}\\a_{1}&a_{0}&a_{-1}&\ddots &&\vdots \\a_{2}&a_{1}&\ddots &\ddots &\ddots &\vdots \\\vdots &\ddots &\ddots &\ddots &a_{m-n-1}&a_{m-n-2}\\\vdots &&\ddots &a_{m-n+1}&a_{m-n}&a_{m-n-1}\\a_{m-1}&\ldots &\ldots &a_{m-n+2}&a_{m-n+1}&a_{m-n}\end{bmatrix}}}$，

其中${\displaystyle A_{i,j}=A_{i+1,j+1}=a_{i-j}.\ }$。

可以發現到，若採用循環矩陣作為測量矩陣的話，只需要存取一列的矩陣元素；相反地，若使用常對角矩陣，除了第一列的矩陣元素外，需要額外儲存第一行的矩陣元素。

但是經過實驗發現，常對角矩陣的相干性是低於循環矩陣的，因此使用者可以依據自己的使用環境，來找到一個平衡點。

採用這兩種矩陣進行壓縮感知取樣時，可以大幅降低儲存成本，也為此算法的前端感測器大幅降低實現門檻。

數值簡化採樣矩陣

數值簡化採樣矩陣普遍將原有的、按照高斯分布隨機取值的採樣矩陣元素以數值上更為簡單的元素取代，但在分布上維持矩陣元素的分布隨機性——即縮減了儲存浮點數這一方面的成本。

一種較為基本的數值簡化採樣矩陣是0-1伯努利矩陣，其中的元素僅有0和1兩種，分布模式為相同獨立的伯努利分布（identical independent Bernoulli distribution）。

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

求解/重構方法

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

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

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

基追蹤

基追蹤（英語：basis pursuit）是一種信號重建演算法，被廣泛地用於壓縮感知領域，屬於數學最優化問題的範疇，形式為${\displaystyle \min _{s}\|s\|_{1}\quad {\mbox{subject to}}\quad y=Hs}$。

其中s是n×1向量，表示輸出（信號），y是m×1的測量向量，H是m×n的「轉換矩陣」或稱作「測量矩陣」，其中M < N。

基追蹤常在需要完美滿足欠定線性方程組系統中${\displaystyle y=Hs}$時被應用，且要求解在L₁基準下為最稀疏的。

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

匹配追蹤

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

${\displaystyle f(t)=\sum _{n=0}^{+\infty }a_{n}g_{\gamma _{n}}(t)}$

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

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

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

正交匹配追蹤

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

迭代閾值算法

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

正交匹配追蹤(Orthogonal Matching Pursuit)

正交匹配追蹤是一個用來解決壓縮感知問題的演算法，在一定的複雜度之下有不錯的表現，他背後最主要的想法是源自於貪婪演算法(Greedy Algorithm)，以下將逐步解說。

首先這個問題被定義為：y=Ax，目標是要藉由已知的y向量、A矩陣，來還原x向量，他會利用疊代的方式，逐步找出x向量當中最有可能是非零的位置。

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

• 
  正交匹配追蹤演算法

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

在迭代閾值算法中，問題一樣是被定義為：

${\displaystyle \min \|x\|_{1}\ \ subject\ to\ y=Ax}$

而在此算法中，每一次的迭代主要分成兩部分：1、尋找新的解${\displaystyle x^{t+1}}$。2、更新殘值${\displaystyle r^{t}}$。 第一階段，主要是利用投影的方式找到更新的向量方向，再透過取閾值的方式來進行優化。

${\displaystyle x^{t+1}=\eta _{thr}(x^{t}+{\mathcal {K}}\times (A^{T}r^{t}))}$

而${\displaystyle {\mathcal {K}}}$是relaxation parameter，且${\displaystyle {\mathcal {K}}\in (0,1)}$。

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

硬閾值函數就是將小於閾值(thr)的解，一律通通過濾成0。

${\displaystyle \eta _{thr}^{H}(x)={\begin{cases}x,{\text{if }}|x|>thr\\0,{\text{otherwise}}\end{cases}}}$

而軟閾值函數則是使用較為平滑的方式，將值逼近於稀疏性的解

${\displaystyle \eta _{thr}^{S}(x)=\operatorname {sgn}(x)(|x|-thr)_{+}{\text{, where }}(z)_{+}=z\times \mathbb {I} (z\geq 0)}$，而${\displaystyle \mathbb {I} (.)}$是指示函數

而第二階段，則是利用新算出來的${\displaystyle x^{t+1}}$來進行殘差更新。

${\displaystyle r^{t+1}=y-Ax^{t+1}}$

之後一直等到規定的迴圈數抵達即完成還原。

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

稀疏性空間投影

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

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

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

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

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

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

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

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

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

好處

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

壞處

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

字典學習

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

字典學習的流程：

1. 設定字典學習的學習次數(Iter)
2. 收集一定量(L筆)要學習的資料s,組成S = [s₁, s₂, ... ,s_L]
3. 固定${\displaystyle \psi }$，利用還原演算法找出每一筆資料的z，組成Z = [z₁, z₂, ... ,z_L]
   • ${\displaystyle {\underset {c}{min}}}$||S - ${\displaystyle \psi }$Z|${\displaystyle |_{F}^{2}}$ s.t. ||z_i||₀ < K_th ${\displaystyle \forall }$i
4. 固定Z， 利用3.所得之Z來更新字典
   • 當Z固定時，定義誤差e_i = s_i - ${\displaystyle \psi }$z_i，組成E = [e₁, e₂, ... ,e_L]
   • 所以整體的均方誤差為 ||E|${\displaystyle |_{F}^{2}}$= || [e₁, e₂, ... ,e_L] |${\displaystyle |_{F}^{2}}$ = || S - ${\displaystyle \psi }$Z|${\displaystyle |_{F}^{2}}$
   • 在Z固定下使得E最小，將得到關係式 (S - ${\displaystyle \psi }$Z)Z^T = 0
   • => ${\displaystyle \psi }$= SZ^T(ZZ^T)^-1
5. 檢查Z上面是否已經有稀疏性，如有則結束學習；如沒有則回到3.直到達到學習的次數

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

好處

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

壞處

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

相關應用

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

攝影學

壓縮感知技術被用於手機攝像頭傳感器設計中。這一技術使得在獲取圖像時所耗費的能量大大降低，可達原先耗費的15分之一——當然，需要引入複雜的解壓算法；這一運算可能會需要脫機狀態下的預先安裝、設置。

壓縮感知亦被用於實現單像素攝影。貝爾實驗室運用了這一技術，用無鏡片單像素相機在柵格中隨機選取的孔隙處拍照，以達到成像效果。隨着拍照次數的逐漸增多，照片質量也會逐步提高；一般來說，這種技術較之傳統的攝影成像技術僅僅需要一小部分的數據占用量，且能完全避免與鏡片或聚焦相關的故障或失常；參見[1] （頁面存檔備份，存於網際網路檔案館） 。

全息成像

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

面部識別

壓縮感知目前被用於面部識別應用之中，參見Engineers Test Highly Accurate Face Recognition （頁面存檔備份，存於網際網路檔案館）。

核磁共振成像

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

地震成像

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

類比信息轉換(Analog-to-Information Converter, AIC)

在通訊系統當中會遇到高頻寬的問題，因此會需要較高的取樣頻率，然而其中的信號可能含有的資訊是遠小於頻寬的，因此就會浪費軟、硬體的資源來進行取樣。所以有人提出用類比信息轉換(Analog-to-Information Converter, AIC)取代類比數位轉換(Analog-to-Digital Converter, ADC)，利用隨機解調(Random Demodulation)的方式，來降低所需要的取樣次數，對於在時頻上有稀疏特性、寬頻的信號特別適合，可以參考^[3]。

網絡診斷

壓縮感知在被用於旨在利於網絡管理的網絡診斷應用中時帶來了極佳成效。對網絡延時的估計和網絡擁塞的探知均可被歸納、建模為非定性的線性方程組系統，其中的參數矩陣正是所分析網絡的路由選擇矩陣。此外，在互聯網情景中，網絡路由矩陣常常能夠滿足壓縮感知技術所要求的幾個基本要素：低相關性、稀疏性及（可能的）R.I.P條件，請參見[5] （頁面存檔備份，存於網際網路檔案館） 。

短紅外攝影

目前，基於壓縮感知技術的商用短紅外相機已被推出[6] （頁面存檔備份，存於網際網路檔案館） 。這些相機的光敏度大約從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)可以被視為一組加密後的鑰匙，能對信號進行壓縮並同時加密，而不需要額外的運算，可以參考^[4]。

參考資料

• Candès, E.J., & Wakin, M.B., An Introduction To Compressive Sampling, IEEE Signal Processing Magazine, V.21, March 2008
• J. Choi et al., "Compressive Sensing for Wireless Communications: Useful Tips and Tricks", IEEE Commun. Survey and Tutorials.
• C. Bockelmann, H. F. Schepker, and A. Dekorsy, "Compressive sensing based multi‐user detection for machine‐to‐machine communication," Transactions on Emerging Telecommunications Technologies, vol. 24, no. 4, pp. 389-400, 2013.
• F. Monsees, C. Bockelmann, D. Wubben, and A. Dekorsy, "Sparsity aware multiuser detection for machine to machine communication," 2012 IEEE Globecom Workshops, Anaheim, CA, 2012, pp. 3-7.
• Shen Q, Liu W, Cui W, et al. "Underdetermined DOA Estimation Under the Compressive Sensing Framework: A Review". IEEE Access, 2016: 8865-8878.
• Jian-Jiun Ding, 「Time Frequency Analysis and Wavelet Transforms 」, NTU, 2021.

外部連結

• "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
• Wiki on sparse reconstruction. [2014-06-24]. （原始內容存檔於2015-05-04）.

1. Engan, K.; Aase, S.O.; Hakon Husoy, J. Method of optimal directions for frame design. 1999 IEEE International Conference on Acoustics, Speech, and Signal Processing. Proceedings. ICASSP99 (Cat. No.99CH36258) (IEEE). 1999. ISBN 0780350413. doi:10.1109/icassp.1999.760624.
2. Hennenfent, Gilles; Herrmann, Felix J. Simply denoise: Wavefield reconstruction via jittered undersampling. GEOPHYSICS: V19–V28. [2017-12-16]. doi:10.1190/1.2841038. （原始內容存檔於2018-06-09）.
3. Laska, J. N.; Kirolos, S.; Duarte, M. F.; Ragheb, T. S.; Baraniuk, R. G.; Massoud, Y. Theory and Implementation of an Analog-to-Information Converter using Random Demodulation. 2007 IEEE International Symposium on Circuits and Systems. May 2007: 1959–1962. doi:10.1109/ISCAS.2007.378360.
4. Orsdemir, A.; Altun, H. O.; Sharma, G.; Bocko, M. F. On the security and robustness of encryption via compressed sensing. MILCOM 2008 - 2008 IEEE Military Communications Conference. November 2008: 1–7 [2017-12-16]. doi:10.1109/MILCOM.2008.4753187. （原始內容存檔於2021-02-24）.