下载文档原格式
：稀疏表示的本质就是稀疏正规化约束下的信号分解。
提出一种改进的正交匹配追踪算法，使运算量较高的矩阵求逆运算转变为轻量级的向量运算或向量与矩阵的运算，可以加快逆矩阵和大矩阵乘积的求解主要介绍MP(Matching Pursuits)算法和OMP(Orthogonal Matching Pursuit)算法[1]，这两个算法虽然在90年代初就提出来了，但作为经典的算法，国内文献(可能有我没有搜索到)都仅描述了算法步骤和简单的应用，并未对其进行详尽的分析，国外的文献还是分析的很透彻，所以我结合自己的理解，来分析一下写到博客里，算作笔记。
1. 信号的稀疏表示(sparse representation of signals)给定一个过完备字典矩阵，其中它的每列表示一种原型信号的原子。
给定一个信号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 在本次迭代运算中最匹配的。
一种改进StOMP的Massive MIMO下行信道估计方法沈涛;刘紫燕【摘要】针对传统的压缩感知算法在大规模多输入多输出(Massive MIMO)系统下行信道估计中估计性能较差的问题,提出一种基于粒子群分段正交匹配追踪(PSO-StOMP)压缩感知算法.该算法在分段正交匹配追踪(StOMP)算法求解不同阈值的估计信道矩阵参数和归一化最小均方误差的基础上,利用粒子群(PSO)算法动态地搜索出Massive MIMO系统下行虚拟角域信道中最小均方误差对应的阈值,达到参数自适应的目的.仿真结果表明,当虚拟角域扩展角度发生变化时,PSO-StOMP算法能够自适应信道估计,提升信道估计精度.【期刊名称】《通信技术》【年(卷),期】2019(052)002【总页数】6页(P361-366)【关键词】大规模多输入多输出;信道估计;压缩感知;粒子群分段正交匹配追踪算法【作者】沈涛;刘紫燕【作者单位】贵州大学大数据与信息工程学院,贵州贵阳 550025;贵州大学大数据与信息工程学院,贵州贵阳 550025【正文语种】中文【中图分类】TN929.50 引言作为5G移动通信系统的关键技术之一，大规模多输入多输出（Massive Multi-Input Multi-Output， Massive MIMO）系统通过在基站端部署大量天线，可以有效提升数据传输速率和链路可靠性[1]。
在Massive MIMO系统中，上行链路的信号检测和下行链路的预编码均依赖准确的信道状态信息（Channel State Information，CSI）。
基于导频的信道估计原理简单、易于实现，因此得到了广泛研究[2]。
传统信道估计方案中，正交导频的开销正比于发射端的天线数目，Massive MIMO系统基站端部署数十至上百根天线，因此下行链路中导频会占用大量的系统资源用于信道估计。
在时分双工（Time Division Duplexing，TDD）模式下，可以利用TDD系统的信道互易性，通过对上行信道的CSI转置获得下行链路中的CSI。
正交匹配追踪算法omp原理
正交匹配追踪算法（Orthogonal Matching Pursuit，简称OMP）是一种用于稀疏重构的迭代算法，主要用于解决压缩感知问题。
其原理如下：
1. 稀疏表示假设：假设信号可以通过少量的原子（基底）的线性组合来表示，即稀疏表示。
2. 初始状态：设置初始残差为输入信号，初始解集为空集。
3. 原子选择：在目前残差中选择一个最适合代表残差的原子（基底）。
4. 矩阵变换：将原子调整为正交的形式，即正交化。
5. 正交投影：计算残差与正交基底的投影，得到投影系数。
6. 更新残差：使用投影系数更新残差。
7. 判断结束：如果残差的能量减少到一定程度，则认为重构已经足够准确，结束算法；否则，返回第3步进行下一个迭代。
8. 输出结果：返回最终的解集，其中每个元素对应一个原子。
OMP算法没有要求输入信号满足特定的分布条件，因此适用
于多种应用场景。
算法通过选择最适合的原子来逐步逼近信号，并且通过迭代追踪算法的方式，能够保证逐步收敛到最优解。
该算法的时间复杂度较低，且能在较短的时间内达到令人满意的重构质量。
探究机器学习中的正交匹配追踪算法机器学习（Machine Learning）是一门利用统计学和计算机科学等领域的技术，让计算机能够从数据中学习并自动改进性能的学科。
在机器学习中，正交匹配追踪算法（Orthogonal Matching Pursuit, 简称OMP）被广泛应用于特征选择、信号恢复和压缩感知等领域。
本文将探究机器学习中的正交匹配追踪算法，并分析其背后的原理和应用。
正交匹配追踪算法是一种迭代的贪心算法，通过选择最相关的特征来逼近目标信号。
其基本思想是在每一步选择与目标信号正交的原子（或特征），并计算其与残差之间的相关度。
算法根据相关度来选择下一个与残差最相关的特征，直到达到预设的迭代次数或达到预设的停止准则。
正交匹配追踪算法的优点在于能够通过稀疏表示来高效地恢复信号。
稀疏表示是指在表示一个信号时，只使用少数几个非零系数。
正交匹配追踪算法通过选择少数相关的特征，实现了对信号的高度压缩，从而在信号恢复和特征选择等任务中具有较好的性能表现。
在特征选择中，正交匹配追踪算法可以帮助我们从大量的特征中选择出最具代表性的子集。
通过选择与目标信号最相关的特征，我们可以去除冗余特征并减少特征维度，从而提高特征的判别性和分类效果。
这在许多领域中都有重要应用，例如基因表达数据中的基因筛选、图像识别中的特征选择等。
在信号恢复中，正交匹配追踪算法可以通过少数测量值来恢复出完整的信号。
这一应用领域在压缩感知（Compressed Sensing）中得到了广泛的研究和应用。
传统的信号采样和重建方法需要满足奈奎斯特（Nyquist）采样定理，即采样率至少是信号带宽的两倍。
而压缩感知则通过选择最相关的特征，可以在保证一定重建误差的情况下，大幅降低采样率并进行信号恢复。
正交匹配追踪算法在实际应用中也有一定的局限性。
首先，算法的运算复杂度较高，对大规模问题的求解可能会遇到困难。
其次，算法在处理噪声较大或特征高度相关的情况下可能失效。
基于正交匹配追踪的图像跟踪算法研究一、引言随着数字图像处理技术的不断发展，图像跟踪技术受到越来越多的关注。
其中一种最常用的技术是基于正交匹配追踪算法（orthogonal matching pursuit, OMP）的图像跟踪。
在本文中，我们将深入探讨这一算法在图像跟踪中的原理、优势以及应用。
二、基于OMP的图像跟踪算法原理正交匹配追踪算法是一种用于稀疏信号重构的方法，主要思想是在一个字典集合中，选取最少的原子，使得它们的加权线性组合等于原信号。
这个问题可以被看作是一个最小化残差的问题，在求解迭代过程中不断使用匹配追踪技术，将残差最小化，例如：1. 计算残差r = x - Dα；2. 找到字典中与r最匹配的向量d，并将其加入高度匹配字典A = [d1, d2, …, dk]中；3. 解最小二乘问题min||α||1 subject to r=Dα；4. 如果前k个原子能够重构原信号，那么就可以提前结束算法，否则，返回步骤1。
在图像跟踪中，字典一般是选取一组具有代表性的小波或字典基。
基于OMP的图像跟踪算法的主要优势是能够快速地找到一幅图像的最佳表示，并精确定位到目标区域。
它同时能够处理一些困难的跟踪场景，如部分目标遮挡、快速移动等。
三、基于OMP的图像跟踪算法的优势基于OMP的图像跟踪算法有如下的优势：1. 可以高效地利用字典和稀疏性质，实现图像跟踪；2. 对于噪声和部分遮挡等现象有较强的鲁棒性；3. 能够快速、准确地进行目标跟踪，适用于实时跟踪；4. 具备较好的可解释性。
值得注意的是，虽然基于OMP的图像跟踪算法具有很多优点，但其也存在一些缺陷，例如对于可见性差、静止目标等场景局限性大。
四、基于OMP的图像跟踪算法应用基于OMP的图像跟踪算法已应用于各种图像和视频分析任务。
例如，在行人跟踪、运动目标跟踪、人脸识别等方面都取得了不错的效果。
在行人跟踪方面，Wang等人提出了一种引导机制的基于OMP的跟踪方法。
基于改进型正交匹配追踪的TOFD重叠信号分离研究刘琨;罗福兴;杨克已;于刚【摘要】针对在使用超声衍射时差技术检测焊缝时,对于薄壁试件、近表面或尺寸较小的缺陷,各回波波形之间容易发生重叠和给波达时间的测量带来困难的问题,基于Gabor函数,对传统的正交匹配追踪算法的优化进行了研究,建立了超声TOFD 检测信号特征信号库.利用波形的相似性从特征信号库中选择了与检测信号相匹配的最优原子,实现了重叠信号分离以及检测信号稀疏化,设计了超声TOFD实验系统,并对带有人工缺陷的试块进行了相关实验验证.研究结果表明,该技术能够有效分离重叠信号并精确测量超声波波达时间,缺陷测量误差小于0.28 mm.【期刊名称】《机电工程》【年(卷),期】2016(033)010【总页数】6页(P1176-1181)【关键词】TOFD;重叠信号;波达时间;正交匹配追踪;稀疏技术【作者】刘琨;罗福兴;杨克已;于刚【作者单位】天津钢管集团股份有限公司,天津300301;杭州浙达精益机电技术股份有限公司,浙江杭州311121;浙江大学现代制造工程研究所,浙江杭州310027;浙江大学现代制造工程研究所,浙江杭州310027【正文语种】中文【中图分类】TG115.28;TH878超声波衍射时差技术(time of flight diffraction, TOFD)是一种在能源石化、冶金制造、交通航空等领域广泛应用的一种超声无损检测技术[1-2]，其基本原理为超声波衍射。
凭借高效率、高灵敏度、高精度和易于实现自动化等优点，该技术在无损检测领域尤其是焊缝检测中占用重要的地位。
1996年，美国推出的标准[3]规定，在特定情况下，超声TOFD检测技术可作为射线检测的替代。
近年来，超声TOFD技术发展迅速、应用日益广泛，在焊缝检测领域大有替代传统射线检测的趋势，日渐成为焊缝质量定量化评估的主要手段。
超声TOFD技术检测探头为一组纵波斜探头，一个为发射探头，一个为接收探头，两个探头的基本参数相同[4]。
一种改进的稀疏表示DOA估计算法赵宏伟;刘波;刘恒【摘要】稀疏表示波达方向（DOA）估计算法具有分辨力高等优点，但是对阵元个数要求高、低信噪比时估计性能恶化严重，不利于在实际系统中应用。
为此，提出一种基于实信号特点的稀疏表示波达方向估计算法。
首先，建立实值稀疏表示的DOA估计模型，能够将阵元数虚拟加倍；其次，利用正交三角分解对估计模型变型，从而改善低信噪比时的估计性能；最后，利用正交匹配追踪算法得到估计结果。
仿真实验结果表明，相对传统稀疏表示算法，具有更低的估计误差和更好的实时性，在实际工程中应用前景广阔。
%Though the direction of arrival (DOA) estimation with sparse representation has high resolution, its computational load is too much and is not suitable for real-time processing in practical system. A DOA estimation algorithm with sparse representation based on the property of real signal sources is proposed to settle the problem. First, the corresponding DOA model is constructed and the numbers of available sensors is doubled based on the array data model of real signals. Then, the orthogonal triangular (QR) decomposition is used to improve the estimation performance at low SNR. Finally, the direction estimation was obtained by orthogonal matching pursuit algorithm. The results of simulation experiments show that the proposed algorithm is suitable for real-time processing and has low estimation error. Therefore, there is much application prospect in practical system engineering.【期刊名称】《电子设计工程》【年(卷),期】2016(024)009【总页数】4页(P133-135,143)【关键词】波达方向估计;稀疏表示;正交三角分解;正交匹配追踪【作者】赵宏伟;刘波;刘恒【作者单位】西安空间无线电技术研究所陕西西安 710100;西安空间无线电技术研究所陕西西安 710100;西安空间无线电技术研究所陕西西安 710100【正文语种】中文【中图分类】TN911波达方向（Direction of Arrival，DOA）估计技术是阵列信号处理领域的研究重点之一，能够实现空间中多个目标信号的高分辨定位，在雷达、通信、导航等领域有着广泛的应用［1-2］。
第10卷 第5期信 息 与 电 子 工 程 Vo1．10，No．52012年10月 INFORMATION AND ELECTRONIC ENGINEERING Oct．，2012 文章编号：1672-2892(2012)05-0579-05一种改进的用于稀疏表示的正交匹配追踪算法王燕霞，张 弓(南京航空航天大学 电子信息工程学院，江苏 南京 210016)摘 要：稀疏表示理论在军事目标识别、雷达目标参数估计等领域应用越来越广，而目标信号的稀疏表示通常不唯一，因此产生了大量的稀疏表示算法。
本文基于现有稀疏表示算法的研究，提出一种改进的正交匹配追踪(OMP)算法。
首先采用非线性下降的阈值更快速地选择原子，确定备选原子集，提高了算法速度；其次用正则化的二次筛选剔除备选原子集中能量较低的原子，保证了算法精确度；并设置迭代停止条件实现算法的稀疏度自适应。
实验结果表明，本文算法可以实现稀疏表示求解精确度和速度上的平衡，求解速度比基追踪(BP)算法快，精确度比OMP 、正则化OMP(ROMP)、基于自适应OMP 回溯(BAOMP)算法高。
关键词：过完备字典；稀疏表示；正交匹配追踪；正则化 中图分类号：TN850.6；TP753 文献标识码：AAn improved orthogonal matching pursuit algorithm for sparse representationWANG Yan -xia，ZHANG Gong(College of Electronics and Information Engineering，Nanjing University of Aeronautics and Astronautics，Nanjing Jiangsu 210016，China)Abstract：Usually sparse representation of signal is not unique, which results in a large number of sparse representation algorithms. An improved Orthogonal Matching Pursuit(OMP) algorithm is proposed. The atoms are selected more quickly with nonlinear decline threshold and the set of alternative atoms is determined, which improves the algorithm speed. Regularized secondary screening can remove lower -energy atoms from the alternative atoms set to ensure the accuracy. A stop condition for iteration is preset to realize the adaptive sparsity of new algorithm. Simulation results show that, the improved algorithm can keep a balance between accuracy and speed for sparse solving with a faster speed than Basis Pursuit(BP) algorithm and a higher accuracy than OMP, Regularized OMP(ROMP) and Backtracking -based Adaptive OMP(BAOMP) algorithms.Key words：over -complete dictionary；sparse representation；orthogonal matching pursuit；regularized稀疏表示理论在军事目标识别[1]、雷达目标参数估计[2]等领域的应用越来越广，2010年Vishal 和Nasser 等人基于科曼奇族前视红外数据库将稀疏表示用于军事目标的识别，稀疏求解的结果表明算法取得了较好的识别效果[1]。
对于稀疏表示理论应用于各种目标信号处理来说，信号的表示应该能对自身不同性质，以及各性质间的差异提供明确信息，这就促进了信号在基于大量波形的过完备字典上的分解[1]。
然而过完备库中的波形数远远超过信号的维数，因此它对给定信号的表示不是唯一的，由此产生了信号处理工作中大量的稀疏表示算法。
基于过完备字典的稀疏表示起源于20世纪90年代，Mallat 和Zhang 首次提出了匹配追踪(Matching Pursuit ，MP)算法来解决该稀疏分解问题[3−4]，通常这些算法可以分为3类：基于p l 范数正则化的方法、迭代收缩算法和贪婪追踪算法。
基于p l 范数正则化的方法通过求解在重构条件下系数的p l 范数最小化来寻找稀疏解，此类比较典型的算法有基追踪(BP)[5]；迭代收缩算法首先要获得系数的初始集，然后迭代修正获得稀疏表示，早期的这类方法有噪声整形(Noise Shaping ，NS)[6]等；贪婪追踪算法力求从字典中选取与余量最匹配的原子作为信号的近似表示，并通过减去与该原子相关的分量来更新余量，此类算法研究的成果较多，典型的有MP [5],OMP [7],ROMP [8]及BAOMP [9]等。
收稿日期：2011-12-14；修回日期：2012-02-09580 信 息 与 电 子 工 程 第10卷BP 算法是稀疏表示的有效近似，是一种全局优化算法，但是线性规划的计算复杂度比较大，因此在实际应用中通常不选择该算法实现稀疏求解；NS 所设置的阈值是线性递减的，于是就需要预设一个阈值数组，然而阈值数组长度的选择是个不确定问题，数组过长则增加了迭代的次数，数组过短则降低了抑制噪声的能力，而且该算法降噪效果不好[4]；作为贪婪算法，匹配追踪类算法的主要思想是从过完备字典中选择最匹配的原子，如何实现原子的快速精确选择是备受关注的问题。
1 稀疏表示理论基于冗余字典的稀疏表示就是在一部过完备字典中能够找到一组最佳原子的线性组合最好的表示信号[10]。
设y 是长度为n 的原始信号，给定一个集合：12[,,,]N M M ×=∈Φ"\ϕϕϕ (1)其元素i ϕ是维数为N 的矢量，若N M ，则称集合Φ为过完备字典，其元素称为原子(或基函数)。
对于任意给定的信号N y ∈\都可以表示成原子i ϕ的叠加：1Mi i i ===∑y f Φf ϕ (2)式中f 为信号在过完备字典下的稀疏表示系数矢量。
鉴于字典的冗余性，矢量i ϕ不再是线性独立的，因此上式中信号y 的表示不是唯一的，而过完备稀疏表示就是从所有可能的表示中找出分解系数最为稀疏的一个。
由于N M ，该求解过程是一个病态的求解问题，通常对信号的过完备稀疏求解建立如下模型：2min , s.t. fδ−fy Φ≤ (3)匹配追踪类算法用于该模型的稀疏求解具有一定的稳定性[11]，主要思想是通过迭代来计算y 的支撑，文献[3]中首次提出MP 算法，它将信号分解为冗余字典中部分原子的线性扩张，然而该算法中信号在已选定原子集合上的投影是非正交的，使得收敛需要经过较多次迭代；OMP [7]算法在MP 的基础上，通过递归地对已选择原子集合进行正交化，保证了迭代的最优性，使得迭代次数减小，但正交化过程也带来了计算复杂性的增加；为进一步提高迭代速度，Needell D 和Vershynin D 提出了正则化的正交匹配追踪(ROMP)[8]算法，该方法挑选多个原子作为候选集，然后从候选集中按照正则化原则挑选出部分原子将其并入最终的支撑集；然而OMP,ROMP 都需已知信号的稀疏度，实际应用中信号的稀疏度往往未知，于是Thong T Do 等人提出了对稀疏度自适应的稀疏自适应匹配追踪算法(Sparsity Adaptive Matching Pursuit ，SAMP)[12]，通过设置一个可变补偿，逐步对信号稀疏度进行估计，SAMP 中自适应的过程对步长要求比较苛刻，步长太小则增加了迭代次数，降低了稀疏求解速度。
BAOMP [9]算法比OMP,ROMP 等具有更稀疏的信号重构和近似性能，但对于不同的信号，BAOMP 算法所设置的前向阈值和后向阈值也不同，不具有普适性。
在正交匹配追踪算法基础上，可使用非线性下降的阈值自适应地确定原子个数，将这些原子作为备选原子集，利用正则化方法对备选原子集做二次筛选，保留能量较大的原子加入原子支撑集，保证了算法稀疏求解的精度，并设置迭代停止条件实现算法对稀疏度的自适应。
2 阈值非线性下降的正则化正交匹配追踪算法文献[8]提出的ROMP 算法对所有满足RIP 条件的矩阵和稀疏信号都可以精确重建，对于稀疏度为K 的信号，若余量与字典的相关系数为1M ×∈g \，选出其中K 个最大的相关系数存入候选集J ，将J 分成若干组，对于任意一个分组Λ，若满足所有的,i j ∈Λ，式(4)都成立：2,,i j i j ∈g g Λ≤ (4) 则选择能量最大的一组子集Λ作为最终的索引值集，选取该索引值集对应的原子集ΛΦ，根据最小二乘法计算信号逼近ˆf 及余量newr 的更新： 2ˆarg min =−Λf y Φf (5)new ˆf=−Λr y Φ (6) ROMP 算法的基本步骤如下：1) 设置初始余量0=r f ，0ˆ0=f ，索引值集合0=∅Λ，估计信号稀疏度为K ，迭代次数初始值1m =；第5期 王燕霞等：一种改进的用于稀疏表示的正交匹配追踪算法 5812) 计算冗余字典与余量的乘积1T n n −=P Φr ，求最大的K 个索引值，并根据式(4)确定最终索引值集合n Λ及对应的原子集ΛΦ；3) 用式(5)计算信号逼近ˆf ，并根据式(6)更新余量newr ； 4) 判断是否满足迭代终止条件2K Λ≥，若不满足，1m m =+，转步骤2)继续迭代计算。
ROMP 算法能保证没有入选支撑集的原子的能量一定远小于最终支撑集中原子的能量，是一种简单有效的原子筛选方法，最多经过K 次迭代便可以精确重建信号。
然而该算法需预估信号的稀疏度，这个问题利用SAMP 算法可解决，但是初始步长的设置是个难题。
文献[6]提出一种噪声修正(NS)算法，该算法在迭代过程中利用阈值的设置剔除较小的系数，并通过正交互补空间映射来修正较大的系数以弥补误差，所设置的阈值是线性递减的，于是就需要预设一个阈值数组，数组维数是个不确定问题，而且该方法降噪效果比较差[4]。
