主要内容

匹配追踪算法

冗余字典和稀疏性

用一种特殊的基表示一个信号，需要找到该基中唯一的展开式系数集。虽然用基表示信号有很多优点，尤其是正交基，但也有缺点。

基提供稀疏表示的能力取决于信号特征与基向量特征的匹配程度。例如，平滑连续信号以傅里叶基稀疏表示，而脉冲信号则不是。用小波基稀疏表示具有孤立不连续的光滑信号。然而，小波基不能有效地表示傅里叶变换具有狭窄的高频支持的信号。金宝app

现实世界的信号通常包含禁止在任何单一基上进行稀疏表示的特征。对于这些信号，您希望能够从一个集合中选择向量，而不限于单个基。因为你想要确保你可以表示空间中的每一个向量字典你选择的向量必须张成空间。然而，因为集合不局限于单个基，所以字典不是线性无关的。

因为字典中的向量不是线性无关的集合，所以字典中的信号表示不是唯一的。然而，通过创建冗余字典，您可以在一组向量中扩展信号，以适应信号的时间频率或时间尺度特征。您可以自由地创建由几个碱基的并集组成的字典。例如，你可以为平方可积函数空间构成一组基，它由小波包基和局部余弦基组成。小波包基能很好地适应不同频率区间内表现不同的信号。局部余弦基可以很好地适应在不同时间间隔具有不同行为的信号。从这些基中选择向量的能力极大地提高了稀疏表示具有不同特征的信号的能力。

字典中的非线性逼近

定义一个字典作为信号空间的单元规范基本构建块的集合。这些单位范数向量叫做原子．如果字典中的原子横跨整个信号空间，则字典为完整的．

如果字典原子形成线性相关的集合，则字典为冗余．在大多数匹配追踪应用中，字典都是完整冗余的。

让{φk}表示字典的原子。假设字典是完整且冗余的。没有一种独特的方法可以将来自空间的信号表示为原子的线性组合。

x ＝ ∑ k α k ϕ k

一个重要的问题是是否存在最好的道路一种直观上令人满意的选择方法最好的表示是选择φk产生与信号的最大内积(绝对值)。下载188bet金宝搏比如，最好单φk是

马克斯 k | < x ， ϕ k > |

对于单位范数原子，哪个是φ张成的子空间上标量投影的大小k．

核心问题是匹配的追求是如何选择最优的呢米-在字典中展开信号的项。

基本匹配追求

让Φ将原子字典表示为一个N × M矩阵，其中M>N。如果完整的冗余字典为信号空间形成一个框架，则可以使用框架运算符获得最小的L2范数展开系数向量。

Φ __ ＝ Φ ＊ （ Φ Φ ＊ ） − 1

然而，由框架算子返回的系数向量并不保持稀疏性。如果信号在字典中是稀疏的，用标准帧算子得到的展开系数通常不反映这种稀疏性。信号在字典中的稀疏性是您通常希望保留的特性。匹配追踪直接解决了稀疏性保存问题。

匹配追踪是一种贪婪算法，它在一个完整的冗余字典中计算信号的最佳非线性逼近。匹配追踪逐步对信号建立稀疏逼近序列。让Φ={φk｝表示单位范数原子的字典。让f做你的信号。

  1. 从定义开始R0f＝f

  2. 通过从字典中选择使内积绝对值最大的原子来开始匹配追求R0f＝f．用φ表示那个原子p．

  3. 形成残差R1f通过减去的正交投影R0f在φ所张成的空间上p．

    R 1 f ＝ R 0 f − 〈 R 0 f ， ϕ p 〉 ϕ p

  4. 在残差上重复步骤2和3进行迭代。

    R 米 + 1 f ＝ R 米 f − 〈 R 米 f ， ϕ k 〉 ϕ k

  5. 当达到某个指定的停止条件时，停止算法。

    6. 在非正交的(或基本)匹配追求时，字典原子不是相互正交的向量。因此，从先前的残差中减去随后的残差可以引入与先前包含的原子的跨度不正交的成分。

    为了说明这一点，请考虑以下示例。本例并不打算给出一个可行的匹配追踪算法。

    考虑下面的欧几里得2-空间字典。这本字典是一个等范框架。

    ｛ （ 1 0 ） ， （ 1 / 2 3. / 2 ） ， （ − 1 / 2 − 1 / 2 ） ｝

    假设你有以下信号。

    （ 1 1 / 2 ）

    下图说明了这个示例。字典原子是红色的。信号向量用蓝色表示。

    在MATLAB中构造该字典和信号®．

    字典= [10;1/2倍根号(3)/ 2;1 /√(2)1 /√(2)];X = [1 1/2]';

    计算信号和字典原子之间的内(标量)积。下载188bet金宝搏

    Scalar下载188bet金宝搏products =字典'*x;

    绝对值中最大的标量积出现在信号和之间(1 /√(2);1 /√(2))．这很清楚，因为两个向量之间的夹角几乎是π弧度。

    通过减去信号在上面的正交投影形成残差(1 /√(2);1 /√(2))从信号。接下来，计算残差(新信号)与剩余字典原子的内积。下载188bet金宝搏没有必要包含(1 /√(2);1 /√(2))因为残差是正交于这个向量的。

    残差= x-scalarproduct下载188bet金宝搏s(3)*dictionary(:，3);Scalar下载188bet金宝搏products = dictionary(:，1:2)'*残差;

    求绝对值上最大的标量积(1, 0)．来自两次迭代的字典中最好的两个原子是(1 /√(2);1 /√(2))和(1, 0)．如果对残差进行迭代，可以看到输出不再与所选择的第一个原子正交。换句话说，该算法引入了一个与所选的第一个原子的跨度不正交的组件。这一事实以及与收敛相关的复杂情况支持正交匹配追踪(OMP)。

    正交匹配追踪

    在正交匹配追踪(OMP)中，残差始终与所选原子的跨度正交。这导致了a的收敛d最大为-维向量d步骤。

    从概念上讲，你可以使用Gram-Schmidt来创建一个标准正交的原子集合。对于一个标准正交的原子集合，你可以看到ad-维向量，你最多可以找到d正交的方向。

    OMP算法为:

    1. 用f．初始化残差R0f＝f．

    2. 选择使内积的绝对值最大的原子R0f＝f．用φ表示那个原子p．

    3. 形成一个矩阵，Φ，以先前选择的原子为列。的列张成的空间上定义正交投影算子Φ．

      P ＝ Φ （ Φ ＊ Φ ） − 1 Φ ＊

    4. 对残差应用正交投影算子。

    5. 更新残留信息。

      R 米 + 1 f ＝ （ 我 − P ） R 米 f

      我是单位矩阵。

      正交匹配追踪确保了先前选择的原子跨度中的成分不会在后续步骤中引入。

      弱正交匹配追踪

      将所选原子使内积绝对值最大的准则放宽到一个不那么严格的准则，在计算上是有效的。

      | 〈 x ， ϕ p 〉 | ≥ α 马克斯 k | 〈 x ， ϕ k 〉 | ， α ∈ （ 0 ， 1 ］

      这被称为弱匹配的追求。