壓縮感知

壓縮感知，是一種尋找的稀疏解的技術。壓縮感知被應用於電子工程尤其是訊號處理中，用於獲取和重構稀疏或可壓縮的訊號。這個方法利用訊號稀疏的特性，相較於奈奎斯特理論，得以從較少的測量值還原出原來整個欲得知的訊號。核磁共振就是一個可能使用此方法的應用。這一方法至少已經存在了四十年，由於、戴維·多諾霍、Justin Romberg和陶哲軒的工作，最近這個領域有了長足的發展。概覽.訊號處理領域中的一個常見問題就是從一系列的取樣中重建原本的訊號。一般而言，未被取樣的部分訊號，是不可能重建出來的。然而透過藉助對於訊號的預先了解或合理假設，完美地透過一系列取樣重建原訊號就成為了可能。隨著科學的發展，數學家們逐步增進了如何作出合理假設的能力，並慢慢了解到在何種情況下可將這些假設一般化、推廣化。訊號處理領域中的一次較早的突破是奈奎斯特取樣定理的提出。這一定理證明了若訊號的最高頻率小於取樣頻率的一半，便可完美地從取樣結果中恢復原本訊號，因此定義了取樣定理取樣頻率的下限。這種資料獲取模式先採樣再壓縮，需要大量的時間壓縮和空間儲存資料，這限制了高速訊號處理的發展，也給硬體的實時處理帶來了極大的挑戰。在2006年左右，、戴維·多諾霍、Justin Romberg和陶哲軒證明了在已知訊號稀疏性的情況下，可能憑藉較取樣定理所規定更少的取樣數重建原訊號，這一理論也是壓縮感知的基石。正交基展開來展開訊號。範例.傅立葉級數展開是正交基展開的方法:formula_1formula_2if formula_3Three-parameter atom expansion，Four-parameter atom (chirplet) expansion，PSWF 展開則是過完備的非正交基集展開的方法:formula_4formula_5 (t) 不構成一個完備的正交基集。分類.壓縮感知希望處理的問題是：假設 formula_6 組成一個過完備的非正交基集問題一.我們希望最小化 formula_7 ( formula_8 是 formula_9 範數， formula_7 意指formula_11 的值不為0 的個數)，使得：formula_12問題二.我們希望最小化 formula_7 ，使得：formula_14問題三.限制 formula_7 為 M，我們想要最小化：formula_16方法.方法一：匹配追蹤.原子：formula_17formula_18 [第1步]輸入：formula_19,初始化: formula_20[第2步]找到最小化formula_21的m[第3步]令 formula_22[第4步]formula_23[第5步]formula_24[第6步]檢查下列條件是否符合，若不符合，回到[第2步]；若符合，則進到[第7步]問題一:是否滿足 formula_25問題二:是否滿足 formula_26問題三:是否滿足formula_27[第7步] formula_28方法二:基追蹤.將 formula_29 範數改為 formula_30 範數formula_31問題一:我們想要最小化 formula_32 ，使得：formula_33問題二:我們想要最小化 formula_32 ，使得：formula_14問題三:令formula_36，我們想要最小化：formula_37問題定義.一般來說，一個常見的線性系統問題，有"m"個方程式, "n"個未知數，可以被定義如下：formula_38其中formula_39在通訊系統之中，"y"是被收到的訊號，而"s"則是要被重建的訊號，一般來說會有以下兩種情況：1.formula_40，也就是說方程式的數量大於等於未知數的數量，這種情況發生的時候就可以利用最小平方法去求得最接近的解，求得的解如下：formula_41其中formula_42是偽逆矩陣。2.formula_43，也就是未知數的數量比方程式的數量來的多，這個方程組就被稱為欠定線性系統，一般而言有無數個解，因此無法使用最小平方法去求得要重建的訊號。但是，如果這個欠定線性系統只有唯一一個稀疏解，那麼我們可以利用壓縮感知理論和方法來尋找這個解。值得注意的是，並不是所有欠定線性方程組都具有稀疏解。舉例來說，formula_44是一個欠定線性系統，會有無限多個解可以滿足這個方程式，然而若加入稀疏的限制條件：formula_45之間只有一個有值，其餘都是0；就可以很輕易地得到這個欠定線性系統的解為formula_46，這個就是壓縮感知的最主要的精神所在。從下圖可以輕易地瞭解，當解具有稀疏的特性時，就可以從欠定線性系統有無限多組解的情況變成可以利用最小平方法找出解的情況。稀疏性.一個向量的稀疏性可以被定義如下：formula_47的個數。也就是計算一個向量之中非零的個數，舉例來說，如果formula_48，formula_49，因此目標的解就會變成如下：formula_50希望能在非零個數越少的情況之下，找到最有可能的解。然而在實際中，最最佳化L0範數是一個NP難的問題，需要窮舉s中非零值的所有排列可能，因而無法求解。通常採取的手段是對L1範數進行最最佳化求解，最佳化目標則變為：formula_51或是使用匹配追蹤系列演算法、迭代閾值法以及專門處理二維影象問題的最小全變分法等求得次最優解的演算法進行計算。有限等距性質(Restricted Isometry Property, RIP).有限等距性質(RIP)是壓縮還原演演算法中常常可以看見的名詞，主要可以被用來分析還原演演算法的表現好壞。其定義如下：formula_52其中的formula_53代表感測矩陣，formula_54代表的是訊號能量，可以表示如下：formula_55因此整個式子可以視為訊號formula_56跟感測矩陣formula_53的相似程度，也就是做完轉換後的能量，要被RIP限制住，而RIP要求formula_58。取樣方法.在理論上，為了確保訊號重建的準確度，需要令所採用的取樣矩陣各行列之間相干性取值隨機性儘量地高。相干性(coherence)可以簡單定義如下：formula_59也就是取樣矩陣任兩個相異的行做內積後，取絕對值所產生的最大值，可以用來衡量訊號重建的準確度。而目前對於取樣矩陣formula_60有下列幾種選擇可以使還原重建度有一定品質：formula_64除了上述的可能，現在也已經證實任何一個sub-gaussian的分佈，都可以成為一個很好的測量矩陣，也就是說具有很好的還原效果。而上述矩陣之所以常被拿來使用，主要是因為皆已經被驗證具有高機率性滿足有限等距性質，也就是相干性非常低，因此使用此方式進行訊號取樣後，仍可確保在訊號具有足夠稀疏性的前提下得到較佳的壓縮感知重建效果。且當使用上述矩陣時，只要訊號x的非零數目成下列關係，可以確保訊號被完美還原。formula_65而C是一個根據不同情況而改變的常數。但是在上述矩陣時，所需要的資料儲存量過於龐大——每個矩陣元素都要單獨記錄，且資料型別一般為浮點數——這就促進了簡化取樣矩陣的研究；目前被提出的簡化取樣矩陣主要包括兩種：結構簡化取樣矩陣與數值簡化取樣矩陣。結構簡化取樣矩陣.目前較常被使用的兩種結構簡化取樣矩陣為迴圈矩陣與常對角矩陣迴圈矩陣的形式為下式：formula_66常對角矩陣的形式為下式：formula_67，其中formula_68。可以發現到，若採用迴圈矩陣作為測量矩陣的話，只需要存取一列的矩陣元素；相反地，若使用常對角矩陣，除了第一列的矩陣元素外，需要額外儲存第一行的矩陣元素。但是經過實驗發現，常對角矩陣的相干性是低於迴圈矩陣的，因此使用者可以依據自己的使用環境，來找到一個平衡點。採用這兩種矩陣進行壓縮感知取樣時，可以大幅降低儲存成本，也為此演算法的前端感測器大幅降低實現門檻。數值簡化取樣矩陣.數值簡化取樣矩陣普遍將原有的、按照高斯分佈隨機取值的取樣矩陣元素以數值上更為簡單的元素取代，但在分佈上維持矩陣元素的分佈隨機性——即縮減了儲存浮點數這一方面的成本。一種較為基本的數值簡化取樣矩陣是0-1伯努利矩陣，其中的元素僅有0和1兩種，分佈模式為相同獨立的伯努利分佈。對於每一個矩陣元素，該分佈的機率質量函式formula_69為： formula_70求解/重構方法.壓縮感知利用了很多訊號中所存在的冗餘。具體而言，很多訊號都是“稀疏”的；在適當的表示域中，它們的很多係數都是等於或約等於零。在訊號獲取階段，壓縮感知在訊號並不稀疏的域對訊號進行線性測量。為了從線性測量中重構出原來的訊號，壓縮感知求解一個稱為L1-範數正則化的最小二乘問題。從理論上可以證明，在某些條件下，這個正則化最小二乘問題的解正是原欠定線性系統的稀疏解。基追蹤.是一種訊號重建演演算法，被廣泛地用於壓縮感知領域，屬於數學最最佳化問題的範疇，形式為formula_71。其中s是n×1向量，表示輸出，"y"是m×1的測量向量，"H"是"m"×n的“轉換矩陣”或稱作“測量矩陣”，其中"M" &lt; "N"。基追蹤常在需要完美滿足欠定線性方程組系統中formula_72時被應用，且要求解在"L"1基準下為最稀疏的。若應用情景允許降低對完美恢復的要求，以換取更加稀疏的解"s"，更為適用。匹配追蹤.是一種稀疏近似運算，旨在找到多維資料在某個超完備字典的加權和來表示希爾伯特空間formula_76上的訊號formula_69：formula_78其中formula_79表示被選取基元的序數，formula_80是每個基元的加權常數。對於固定的字典，匹配追蹤會先找到與訊號間內積最大的一個基元，再減去該基元帶來的影響，然後重複找尋影響力次大的基元直到訊號被較好地分解。相較而言，以傅立葉級數表示的訊號來說，字典是構建於正弦基函式之上的。訊號處理領域中傅立葉分析的主要缺點就在於它只能提取出訊號中常存的特徵，而不能適應當前的分析目標訊號formula_69。若採用一組極端保險、帶有大量冗餘的字典，我們就能夠找到可以完美匹配訊號的formula_69函式組。在對訊號進行編碼與壓縮時，最好是能夠找到一組對映，使加權和中的大部分系數都接近零。正交匹配追蹤.正交匹配追蹤(Orthogonal Matching Pursuit)是匹配追蹤的特殊形式，正交匹配追蹤的演算法與匹配追蹤相同，但是正交匹配追蹤不會重複使用同一個基元來進行匹配，因此會比匹配追蹤更快收斂。迭代閾值演算法.迭代閾值演算法(Iterative Shrinkage-Thresholding Algorithm)是上述基於貪婪演演算法(Greedy Algorithm)之匹配追蹤與正交匹配追蹤的替代演算法，迭代演算法主要是透過不斷的投影和取閾值來進行收斂，而他在每次迭代中，都還可以進行其他最佳化例如:Wigener 濾波，不僅可以降低運算複雜度，也可以提高還原品質。正交匹配追蹤(Orthogonal Matching Pursuit).正交匹配追蹤是一個用來解決壓縮感知問題的演演算法，在一定的複雜度之下有不錯的表現，他背後最主要的想法是源自於貪婪演演算法(Greedy Algorithm)，以下將逐步解說。首先這個問題被定義為：y=Ax，目標是要藉由已知的y向量、A矩陣，來還原x向量，他會利用疊代的方式，逐步找出x向量當中最有可能是非零的位置。一開始會有一個空集合formula_83，以及剩餘的部分formula_84，每次疊代都會從formula_85找出一個A矩陣投影到剩餘formula_86有最大值的位置，把這個位置加到formula_87之中，並從formula_88當中移除，最後再更新剩餘formula_89。利用疊代的方式，不斷地找出x向量當中最有可能非零的位置，直到達到演演算法停止條件。在正交匹配追蹤演算法的基礎上，Needell等人提出了正則正交匹配追蹤演算法被提出。在實際應用中，稀疏訊號非零元素個數K往往是未知的，而上述的匹配追蹤演算法都是建立在稀疏度K已知的基礎上，因此出現了對K自適應的稀疏自適應匹配追蹤演算法，它透過固定步長來逐步逼近進行重建，可以在稀疏度K未知的情況下獲得較好的重建效果。迭代閾值演算法(Iterative Shrinkage-Thresholding Algorithm).迭代閾值演算法是從Relaxation Method啟發而來，Relaxation Method是用於解決具有稀疏性的線性系統。在迭代閾值演算法中，問題一樣是被定義為：formula_90而在此演算法中，每一次的迭代主要分成兩部分：1、尋找新的解formula_91。2、更新殘值formula_92。第一階段，主要是利用投影的方式找到更新的向量方向，再透過取閾值的方式來進行最佳化。formula_93而formula_94是relaxation parameter，且formula_95。而formula_96就是閾值函式(thresholding function)，主要就是為了使迭代的過程中，逐漸逼近具有稀疏性性質的解，而目前主要有兩大類取閾值的方式：硬閾值函式(Hard Thresholding Function)與軟閾值函式(Soft Thresholding Function)。硬閾值函式就是將小於閾值(thr)的解，一律通透過濾成0。formula_97而軟閾值函式則是使用較為平滑的方式，將值逼近於稀疏性的解formula_98，而formula_99是指示函式而第二階段，則是利用新算出來的formula_91來進行殘差更新。formula_101之後一直等到規定的迴圈數抵達即完成還原。而此演算法是Landweber iteration的變形，若沒有加入閾值函式的話，就會收斂到formula_102。稀疏性空間投影.壓縮感知還原演演算法包括整個壓縮感知都是建立在訊號有稀疏性上，但是並不是所有的訊號都天然具有稀疏性，例:聲音。那麼是否不具有稀疏性的訊號就不能使用壓縮感知呢？答案為並不是，天然不具有稀疏性的訊號還是能夠使用壓縮感知，只需要把該訊號投影到其他空間，其他該訊號有稀疏性的空間下，壓縮感知就可直接使用在該投影空間上。可以被定義如下：formula_103s:要被重建的訊號(原訊號)；ψ:投影矩陣，把非稀疏性訊號投影到稀疏性空間；z:非零項遠小於零項故原壓縮感知公式定義也隨之改變：formula_104所以可以把formula_105視為原本壓縮感知公式裡面的H，還原演演算法即可一樣使用。至於formula_106的選擇對於不同訊號來說有很多種，有離散餘弦變換(DCT) ,離散小波變換(DWT)，字典學習(Dictionary Learning)等。離散餘弦變換和離散小波變換.利用訊號經過這兩種變換後都會有稀疏性的特性，把這兩種變換變成矩陣形式，讓訊號直接投影到具有稀疏性的空間上。好處壞處字典學習.顧名思義即把formula_106當作一本要學習的字典，不斷的利用該訊號和還原演演算法後的結果做字典的更新，直到找到一個formula_106能夠把該訊號投影到稀疏性空間上。字典學習的流程：字典學習的演演算法有很多，較為常用的有Method of optimal directions(MOD)。好處壞處相關應用.壓縮感知與包括欠定系統、群驗、稀疏編碼、複用、稀疏取樣等。在成像科技領域，亦有許多技術如與壓縮感知相關。亦有許多在不同技術完成度下將壓縮感知實現的案例。攝影學.壓縮感知技術被用於手機攝像頭感測器設計中。這一技術使得在獲取影象時所耗費的能量大大降低，可達原先耗費的15分之一——當然，需要引入複雜的解壓演算法；這一運算可能會需要離線狀態下的預先安裝、設定。壓縮感知亦被用於實現單畫素攝影。貝爾實驗室運用了這一技術，用無鏡片單畫素相機在柵格中隨機選取的孔隙處拍照，以達到成像效果。隨著拍照次數的逐漸增多，照片質量也會逐步提高；一般來說，這種技術較之傳統的攝影成像技術僅僅需要一小部分的資料佔用量，且能完全避免與鏡片或聚焦相關的故障或失常； 。全息成像.壓縮感知可被用於增加透過單幅全息圖中所能得到的立體畫素的數量改進全息攝影技術中的影象重建問題。在光學全息圖或毫米波全息圖取樣率不足的情況下，這一技術也能夠被用於影象檢索以作出改善。面部識別.壓縮感知目前被用於面部識別應用之中，ngineers 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)的方式，來降低所需要的取樣次數，對於在時頻上有稀疏特性、寬頻的訊號特別適合，可以參考。網路診斷.壓縮感知在被用於旨在利於網路管理的網路診斷應用中時帶來了極佳成效。對網路延時的估計和網路擁塞的探知均可被歸納、建模為非定性的線性方程組系統，其中的引數矩陣正是所分析網路的路由選擇矩陣。此外，在網際網路情景中，網路路由矩陣常常能夠滿足壓縮感知技術所要求的幾個基本要素：低相關性、稀疏性及 。短紅外攝影.目前，基於壓縮感知技術的商用短紅外相機已被推出  。這些相機的光敏度大約從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)可以被視為一組加密後的鑰匙，能對訊號進行壓縮並同時加密，而不需要額外的運算，可以參考。