OMP算法

3.1 算法描述

OMP算法的改进之处在于：在分解的每一步对所选择的全部原子进行正交化处理，这使得在精度要求相同的情况下，OMP算法的收敛速度更快。

那么在每一步中如何对所选择的全部原子进行正交化处理呢？在正式描述OMP算法前，先看一点基础思想。

先看一个 k 阶模型，表示信号 f 经过 k 步分解后的情况，似乎很眼熟，但要注意它与MP算法不同之处，它的残值与前面每个分量正交，这就是为什么这个算法多了一个正交的原因，MP中仅与最近选出的的那一项正交。

(1)

k 1 阶模型如下：

(2)

应用 k 1阶模型减去k 阶模型，得到如下：

(3)

我们知道，字典矩阵D的原子是非正交的，引入一个辅助模型，它是表示对前k个项的依赖，描述如下：

(4)

和前面描述类似，在span(x1, ...xk)之一上的正交投影操作，后面的项是残值。这个关系用数学符号描述：

请注意，这里的 a 和 b 的上标表示第 k 步时的取值。

将(4)带入(3)中，有：

（5）

如果一下两个式子成立，(5)必然成立。

(6)

(7)

令，有

其中。

ak的值是由求法很简单，通过对(7)左右两边添加作内积消减得到：

后边的第二项因为它们正交，所以为0，所以可以得出ak的第一部分。对于，在（4）左右两边中与作内积，可以得到ak的第二部分。

对于(4)，可以求出，求的步骤请参见参考文件的计算细节部分。为什么这里不提，因为后面会介绍更简单的方法来计算。

3.2

通过(7)，由于与正交，将两个残值移到右边后求二范的平方，并将ak的值代入可以得到：

可见每一次残差比上一次残差小，可见是收敛的。

3.3 算法步骤

整个OMP算法的步骤如下：

由于有了上面的来龙去脉，这个算法就相当好理解了。

到这里还不算完，后来OMP的迭代运算用另外一种方法可以计算得知，有位同学的论文[2]描述就非常好，我就直接引用进来：

对比中英文描述，本质都是一样，只是有细微的差别。这里顺便贴出网一哥们写的OMP算法的代码，源出处不得而知，共享给大家。

再贴另外一个洋牛paper[3]中关于OMP的描述，之所以引入，是因为它描述的非常严谨，但是也有点苦涩难懂，不过有了上面的基础，就容易多了。

它的描述中的Sweep步骤就是寻找与当前残差最大的内积时列在字典矩阵D中的索引，它的这个步骤描述说明为什么要选择内积最大的以及如何选择。

它的算法步骤Update Provisional Solution中求很简单，就是在 b = Ax 已知 A和b求x， 在x的最小二范就是A的伪逆与b相乘，即：2100433B

bm摆线马达共六大系列，可完全替代进口伊顿J2K、J6K；丹佛斯DANFOSS，OMP、OMR、OMS、OMV、OMT等系列，同时亦可替换国产BM1、BM2、BM3、BM4、BM5/2X、BM6/6X等系产品 。

本项目在国内外土木工程结构健康监测领域首先开展了数据压缩采样的研究，研究了数据稀疏分解的正交匹配追踪（OMP）算法，获得信号的稀疏表示；由于结构振动响应信号具有稀疏性，因此研究了结构动力响应数据的压缩采样；研究了结构健康监测声发射数据压缩采样的OMP算法；为增加无线传感器数据传输的鲁棒性，提出了基于压缩采样技术的结构健康监测无线传感器网络数据丢失的恢复方法，并将算法嵌入到美国UIUC大学B.F. Spencer教授研制的Imote2无线传感器里。考虑测量噪声，提出了Bayesian压缩采样方法。并进一步将压缩采样方法扩展用于具有稀疏解的系统识别反问题，提出了基于压缩采样理论与子结构灵敏度分析的结构损伤识别方法。研究成果采用山东滨州黄河公路大桥、哈尔滨松浦大桥以及国家游泳中心等现场监测数据进行了验证，取得好的结果。项目研究成果可用于结构健康监测的数据压缩，无线传感器和传感网络的数据鲁棒传输，具有稀疏解的系统识别问题。为土木工程结构健康监测数据分析与处理的发展提供了新的思路，具有重要的理论意义和实际价值。 2100433B

随着科学的发展和信息时代的到来，为了满足消费者的多种需求，金永（Kumyoung）科技凭借着雄厚的技术实力，成功研制出了新一代多媒体点播系统OMP（Orange Multimedia Player）、IMP(Internet Multimedia Player)。金永多媒体点播系统基于系统安全性、成本适中性、性能稳定性、使用便捷性、质量优越性、维护方便性六个方面而开发研制成功的。全系统由网络连接的计算机自动管理，无需碟机，亦无人员操作，极大地提高经营效率。该系统彻底解决了电脑电歌机系统的一些关键性问题，如数据传输的瓶颈、安全备份、数据流的控制等问题。完美的音乐与先进的点播系统技术相结合，使金永成为世界一流的KTV设备供应商。

金永正在扩大服务范围，提供以原音和数码技术进行再创作的所有服务。自2004年起，本公司的子公司综合金永的音乐资源，以移动增值的形式提供图片、铃声、手机卡拉OK等服务，并扩大到MP-3、MTV原音原唱原画面等所有与音乐有关的内容, 通过有线、无线(On-line、 Off-line)等各种媒体形式与听众见面。2100433B