給定壹個過完備字典矩陣，其中它的每列表示壹種原型信號的原子。給定壹個信號y，它可以被表示成這些原子的稀疏線性組合。信號 y 可以被表達為 y = Dx ，或者。 字典矩陣中所謂過完備性，指的是原子的個數遠遠大於信號y的長度(其長度很顯然是n)，即n<<k。
2.MP算法(匹配追蹤算法)
2.1 算法描述
作為對信號進行稀疏分解的方法之壹，將信號在完備字典庫上進行分解。
假定被表示的信號為y，其長度為n。假定H表示Hilbert空間，在這個空間H裏，由壹組向量構成字典矩陣D，其中每個向量可以稱為原子(atom)，其長度與被表示信號 y 的長度n相同，而且這些向量已作為歸壹化處理，即|，也就是單位向量長度為1。MP算法的基本思想：從字典矩陣D（也稱為過完備原子庫中），選擇壹個與信號 y 最匹配的原子(也就是某列)，構建壹個稀疏逼近，並求出信號殘差，然後繼續選擇與信號殘差最匹配的原子，反復叠代，信號y可以由這些原子來線性和，再加上最後的殘差值來表示。很顯然，如果殘差值在可以忽略的範圍內，則信號y就是這些原子的線性組合。如果選擇與信號y最匹配的原子？如何構建稀疏逼近並求殘差？如何進行叠代？我們來詳細介紹使用MP進行信號分解的步驟：[1] 計算信號 y 與字典矩陣中每列(原子)的內積，選擇絕對值最大的壹個原子，它就是與信號 y 在本次叠代運算中最匹配的。用專業術語來描述：令信號，從字典矩陣中選擇壹個最為匹配的原子，滿足，r0 表示壹個字典矩陣的列索引。這樣，信號 y 就被分解為在最匹配原子的垂直投影分量和殘值兩部分，即：。[2]對殘值R1f進行步驟[1]同樣的分解，那麽第K步可以得到.