主要内容

匹配追踪算法

冗余字典与稀疏性

要在一个特定的基中表示一个信号，需要找到该基中唯一的一组膨胀系数。虽然在基中，特别是在正交基中表示信号有许多优点，但也有缺点。

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

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

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

字典中的非线性近似

定义一个字典作为信号空间的单位范数基本构建块的集合。这些单位范数向量称为原子. 如果字典的原子跨越整个信号空间，则字典为完成．

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

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

x ＝ ∑ k α k ϕ k

一个重要的问题是是否存在最好的对。一种直觉上令人满意的选择最好的表示法是选择φk产生与信号最大的内积（绝对值）。例如，最好的单φs manbetx 845k是

最大值 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 sqrt（3）/2；-1/sqrt（2）-1/sqrt（2）]；x=[11/2]；

    计算信号和字典原子之间的内积（标量）。s manbetx 845

    scalars manbetx 845products=字典'*x；

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

    通过减去信号的正交投影得到残差(1 /√(2);1 /√(2))接下来，计算剩余（新信号）与剩余字典原子的内积。不需要包括s manbetx 845(1 /√(2);1 /√(2))因为残差通过构造与向量正交。

    残差=x-scalarproductss manbetx 845（3）*字典（：，3）；scalarproducts=字典（：，1:2）'*残差；

    得到了绝对值最大的标量积[1;0]．字典中最好的两个原子来自两次迭代(1 /√(2);1 /√(2))和[1;0]．如果对剩余部分进行迭代，可以看到输出不再与所选的第一个原子正交。换句话说，该算法引入了一个与所选第一个原子张成的空间不正交的组件。这一事实以及与趋同相关的复杂性，支持了趋同正交匹配追踪(OMP)。

    正交匹配追踪

    在正交匹配追踪（OMP）中，残差始终与已选择原子的跨度正交。这就导致了一种新方法的收敛性d-维向量d步骤。

    从概念上讲，可以通过使用Gram Schmidt创建一组正交原子来实现这一点。对于一组正交原子，你可以看到d-维向量，你最多可以找到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 ］

      这被称为虚弱的匹配追踪。

      小波工具箱文档

      万博1manbetx

      尝试MATLAB, Si万博1manbetxmulink和其他产品s manbetx 845

      现在受审