主要内容

匹配追踪算法

冗余字典和稀疏性

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

基提供稀疏表示的能力取决于信号特征与基向量特征的匹配程度。例如，平滑的连续信号在傅立叶基中稀疏表示，而脉冲则不是。具有孤立不连续的平滑信号用小波基稀疏表示。然而，小波基不能有效地表示傅立叶变换高频支持较窄的信号。金宝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 0;1/2倍根号(3)/ 2;1 /√(2)1 /√(2)];X = [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) *词典(:,3);scalar下载188bet金宝搏products =字典(:1:2)*残余;

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

    正交匹配追踪

    在正交匹配追踪(OMP)中，残差总是与已选原子的跨度正交。这使得a收敛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 ］

      这被称为弱匹配的追求。

      小波工具箱文档

      金宝app

      尝试MATLAB, Si金宝appmulink和其他产品下载188bet金宝搏

      得到审判现在