匹配追蹤

匹配追蹤(matching pursuit, MP)最早是時頻分析的分析工具，目的是要將一已知訊號拆解成由許多被稱作為原子訊號的加權總和，而且企圖找到與原來訊號最接近的解。其中原子訊號為一極大的原子庫中的元素。以數學式子表示可以得到：formula_1其中，formula_2是權重，formula_3是由字典formula_4中獲得的原子訊號。如同傅立葉級數將一訊號拆解成一系列的正弦波的相加，其中每個成分擁有不同的係數作為權重，其數學式子如下：formula_5而匹配追蹤也具有將訊號拆解成一系列原子相加的意涵，甚至可以使用匹配追蹤去描述傅立葉級數，也就是原子庫對應到的所有正弦函式的集合。演演算法.為了找到最符合原訊號的一組原子加權總合，如果對原子庫進行所有組合的嘗試過於耗費時間。在1993年由Mallat S和Zhang Z的論文[1]中，提出了一個貪婪演演算法，並大幅降低找出近似解的時間。其作法首先在原子庫中尋找與原訊號內積結果最大的原子formula_3，找到此訊號以及其內積結果formula_2之後再將原訊號減掉formula_8作為下一次重複運算的原始訊號，如此反覆做下去即可得到一系列的formula_2以及原子formula_3，直到達到停止條件為止，其詳細的演演算法如下：輸入：Signal: formula_11, dictionary formula_4.輸出：List of coefficients: formula_13.初始化：formula_14;formula_15;重複：尋找 formula_16 具有最大內積 formula_17;formula_18;formula_19;formula_20;直到達到停止條件時頻原子分解(time-frequency atom decomposition).在訊號處理的許多應用中，需要將訊號分解為一群在時域和頻域都具有良好區域性性(集中在某一範圍)的函式，這些函式稱為時頻原子(time-frequency atom)。選擇不同的時頻原子時，分解方式的特性會有很大的差異。窗函式傅立葉轉換(window Fourier transform)和小波轉換(wavelet transform)都是時頻訊號分解的方法。通常一個時頻原子群可以由單一的窗函式formula_22經過scale、translation和modulation產生，令formula_23為一個實數的連續可微函式，且限制formula_24、formula_25的積分不為零、formula_26。以formula_27表示scale引數formula_28、translation引數formula_29和modulation引數formula_30，定義formula_31為formula_32其中formula_33是集合formula_34中的元素，formula_35使得formula_24。事實上，函式群formula_37含有許多冗餘的元素，對於任何函式formula_11，更有效率的表示方法是，在原子formula_39中，只選取適當數量的子集合，其中formula_40，則formula_11可以表示為formula_42在窗函式傅立葉轉換中，所有原子formula_3具有相同的scale引數formula_44，因此主要分佈在一個大小為formula_45倍數的區間內，由於上述特性，窗函式傅立葉轉換無法準確地描述比formula_45大許多或小許多的函式結構。小波轉換將訊號分解為不同尺度的時頻原子，稱為小波(wavelet)，小波群formula_39的建構方法是令formula_48 ，其中formula_49是一個常數。小波轉換可以分析不同尺寸的訊號成分，然而，受限於引數formula_50和formula_51必須成反比的條件，小波轉換的係數無法精準估計傅立葉轉換後具有良好區域性性的頻率成分。希爾伯特空間(Hilbert space)的匹配追蹤.自適應時頻分解(adaptive time-frequency decomposition)的目的是將訊號展開到一組波形(waveform)上，這些波形選自一個數量龐大的冗餘字典，而匹配追蹤是能達到自適應分解的一種方法。一個希爾伯特空間可表示為formula_52，其組成的複數函式formula_53必須滿足formula_54令formula_55代表一個希爾伯特空間，則將「字典」定義為formula_55中的一個向量群formula_57，滿足formula_58，其中formula_33是集合formula_34中的元素。formula_61代表字典向量的封閉線性生成空間(closed linear span)，在空間formula_61中，集合formula_4之向量的有限線性展開(finite linear expansion)是稠密(dense)的，如果formula_64，則稱此字典具有完備性(completeness)。對於「時頻原子分解」段落所描述的字典，formula_65，在空間formula_52中，時頻分子的有限線性展開是稠密的，因此該字典具有完備性。假設有一訊號formula_67，欲將其線性展開到由集合formula_4中選出的一組向量上，使得結果最匹配原來的訊號結構。匹配追蹤的方法是連續地將formula_53以其在集合formula_4中元素的正交投影(orthogonal projection)近似。令formula_71，向量formula_53可以被分解為formula_73其中formula_74是將formula_53以formula_76的方向近似後的剩餘向量(residual vector)，由於formula_76和formula_74正交，可得下式formula_79為了最小化formula_80，必須選取formula_71使得formula_82最大化。在某些情況下，只能找到近似最佳的向量formula_76，符合formula_84其中formula_85，在選擇向量formula_76時，並非隨機選擇，而是由一個選擇函式formula_87決定。重複上述步驟，疊代地將剩餘向量formula_74投影到集合formula_4中最匹配formula_74的向量，並將formula_74分解。匹配追蹤的步驟可以由數學歸納法來表示formula_99剩餘向量formula_94被分解為formula_101由於formula_3和formula_103正交，可得下式formula_104當分解到第formula_105次時，formula_53被分解為formula_107formula_108被分解為formula_109此公式具有能量守恆的意義，原來的向量formula_53被分解為許多字典中元素的總和。有限空間的匹配追蹤.當訊號存在的空間formula_55具有有限的維度formula_112時，匹配追蹤方法會有特殊的特性。在字典formula_4中，可能含有無限多的元素，假設此字典具有完備性，此時可以用一種有效率的匹配追蹤方法，剩餘向量的範數(norm)會以指數方式下降。當字典含有非常多冗餘的元素時，要尋找和剩餘向量最匹配的向量，通常可以只限制在一個子字典formula_114中尋找，假設formula_115是一個包含於formula_116的有限索引集，使得對於所有訊號formula_67，滿足formula_118依據formula_115的大小和字典formula_4的冗餘程度，集合formula_115可以比formula_116小許多。以數學歸納法表示此處的匹配追蹤方法formula_128為了從字典中找到一個比formula_127更匹配formula_53的元素，可以利用牛頓法(Newton’s method)，在formula_116中尋找formula_132的鄰近索引formula_133，使得內積達到區域性最大值，在此情況下，可以得出下式formula_134在此處，選擇函式formula_87與希爾伯特空間中的匹配追蹤不同，必須進行二次搜尋。在選出一個formula_127後，必須計算新的剩餘向量formula_103和任何formula_138的內積，更新公式如下formula_139由於先前的計算已經得到formula_140和formula_141，因此上式的更新只需要計算formula_142。對於一個給定的訊號formula_53，要對其剩餘向量分解多少次，決定於要求的精準度formula_144，重複的次數為能夠滿足下式的最小值formula_145formula_146根據能量守恆，此公式等價於formula_147由於在此方法中，每一次重覆計算時，並沒有計算剩餘向量formula_94，因此只根據上式來判斷是否達到停止分解的條件。重複次數formula_145決定於formula_150的下降速率，依據訊號的不同，formula_145可以有很大的變化，但在一般情況下，formula_145會比空間formula_55的維度formula_112小很多。應用.匹配追蹤演演算法的靈活性和效率在訊號處理領域中越來越重要，尤其在以下幾種領域中更有其重要的應用：在視訊編碼和影像壓縮上，對於運動的影像估計和補償，在提出新的原子庫或是擴充套件的演演算法之後，有相當的改良。在影像辨識和形狀辨認上，匹配追蹤演演算法的稀疏性對於同樣具有稀疏性的影象提供新的研究方向。另外在音樂、語音方面，最早即在時頻分析上作為MP演演算法研究物件。壓縮感知[1] S. G. Mallat and Z. Zhang, "Matching pursuits with time-frequency dictionaries," in IEEE Transactions on Signal Processing, vol. 41, no. 12, pp. 3397-3415, Dec 1993.[2] Jian-Jiun Ding, Time frequency analysis and wavelet transform class note,the Department of Electrical Engineering, National Taiwan University (NTU), Taipei, Taiwan, 2012.[3] B. Torresani, "Wavelets associated with representations of the affine Weyl-Heisenberg group," 1. Math. Physics, vol. 32, pp. 1273-1279, May 1991.