2.3.2　字典學習

由于冗余字典中原子個數可遠高于信號長度，因此可從字典中尋找原子的最佳線性組合來逼近信號，獲得稀疏的表示系數。但是在冗余字典表示中，表示并不是唯一的。例如，圖2-5中，x=［3　2　0　0］T也是一個可行的稀疏解。因此，要獲得基于冗余字典的稀疏表示，需要解決兩個方面的問題：一是給定一組目標信號，如何獲得最佳的原子，并構造得到字典，即字典設計問題；二是對于任意一個信號，如何從這個字典中挑選出最優的一種原子組合來表示信號，即原子選擇問題。

1. 字典設計

字典設計需要解決的問題是如何設計字典D，使得對于給定的一系列信號{y_i，i=1，2，…，N}，利用y=Dx得到的表示x是稀疏的。當前，主流字典設計方法可以大致歸結為以下兩類[8]：

·第一類方法：分析法。根據信號的先驗知識來構建字典，如傅里葉、DCT、小波、曲波、帶波、仿型波、復小波、方向波、組波等。用分析法構建字典相對簡單，且結構特征明顯，計算量小。然而，使用該類方法需要有一定的信號先驗知識[9]。

·第二類方法：學習法。這種方法無須信號先驗信息，直接對信號樣本進行訓練得到字典。相比分析法，學習法得到的字典可帶來更好的信號匹配度，得到更優的稀疏化效果。

由于分析法需要先驗知識，對于成分復雜的信號或時變信號，無法保證較好的稀疏化效果。因此，目前更多地采用學習法進行字典構造。

對于一系列待訓練信號{y_i，i=1，2，…，N}，字典學習的目標是通過訓練尋找字典D，使得字典原子與訓練信號相適應，從而使得信號在其上的分解系數x_i盡量稀疏。若將待訓練信號和分解系數分別組成矩陣Y，X，上述問題可表示為

式中，ε表示逼近誤差。如果采用稀疏效果作為約束條件，則字典學習問題還可表述為

若將約束條件抽象化，更一般地可將式（2-4）記為

式中，G（X）表示訓練過程中對分解系數X的約束條件。

2. 原子選擇

原子選擇需要解決在給定冗余字典D的條件下，從滿足y=Dx的多種可能表示x中找到最優的表示，這里的最優通常指的是最稀疏的，也就是在表示y時，用到的原子數最少。

由于D的行數N遠小于列數M，y=Dx的求解屬于欠定方程組求解問題，一般情況下無法得到確定解。然而基于信號稀疏的前提，該問題可以轉化為稀疏約束條件下的優化問題：

即滿足約束條件的l_p范數（p≥0）最稀疏矢量為最優解。

在l_p范數稀疏的約束下尋找方程組的解，可看作求解矢量所在的超平面與l_p范數張成的曲面的交點，且交點應位于坐標軸上以保證解最為稀疏。此處超平面不與任意坐標平面平行。如圖2-3所示，當p=0時，超平面與退化后的曲面形成的切點易落在坐標軸上，因此加入l₀范數稀疏的約束可以實現信號重構；類似地，對于0<p≤1的情況，超平面和曲面都容易尋找到落在坐標軸上的切點，因此在這些稀疏約束下都能找到式（2-6）的解；當p>1時（例如p=2），曲面是“凸”的，超平面與曲面的切點以絕對的大概率不落在坐標軸上，因此無法保證估計到稀疏信號。綜合起來，當0≤p≤1時，在l_p范數稀疏的約束下都可以對欠定方程組進行求解，進而得到稀疏解。

由于采用信號的非零元素個數（即l₀范數）判斷其稀疏性最為直觀，研究者最初選擇l₀范數約束對欠定方程進行求解。然而，這需要列出x中所有非零項位置的種可能的線性組合，才能得到最優解。因此采用l₀范數求解式（2-4）屬于NP難問題[10]。若選擇0<p<1，由l_p范數的定義，計算較為復雜，因此更多地考慮采用l₁范數約束進行求解。

許多算法都利用了l₁范數最小來求解最稀疏解的思想，它們屬于凸松弛算法類別，基追蹤（Basis Pursuit，BP）算法是其代表，有效性已得到了充分的理論證明[11]，但其全局搜索策略的計算復雜度較大，人們進而考慮采用貪婪算法來求解局部最優。這種思想促生了匹配追蹤（Matching Pursuit，MP）算法[1]及其一系列改進算法，如正交匹配追蹤（Orthogonal Matching Pursuit，OMP）[12]等。另一種貪婪算法的求解思路是對信號進行結構化采樣，由分組測試快速獲得信號的表示，如子空間追蹤（Subspace Pursuit，SP）、迭代硬閾值法（Iterative Hard Thresholding，IHT）[13]等就是其中的代表。這類算法在計算復雜度上較凸優化算法低，然而在理論完備性上還有所欠缺[14]。圖2-6給出了已有原子選擇算法比較詳細的分類。

作為一種典型的自然信號，聲音信號中也包含著大量冗余。如何通過字典學習找到語音、音頻信號的稀疏表示，也引起了很多研究人員的關注。例如，文獻［15］結合稀疏多尺度改進型DCT（MDCT）對音頻進行建模，降低了編碼比特率；文獻［16］用特定源字典對音樂進行稀疏分解，實現了樂-噪分離；文獻［17］結合語音信號設計了貪婪自適應字典訓練方法，實現了語音增強。隨著研究的推進，利用冗余字典對語音進行稀疏表示將在更多的應用中發揮作用。