匹配追踪

✍ dations ◷ 2025-05-26 07:34:18 #算法

匹配追踪(matching pursuit, MP)最早是时频分析的分析工具,目的是要将一已知讯号拆解成由许多被称作为原子讯号的加权总和,而且企图找到与原来讯号最接近的解。其中原子讯号为一极大的原子库中的元素。以数学式子表示可以得到:

其中, a n {\displaystyle a_{n}} 是权重, g γ n {\displaystyle g_{\gamma _{n}}} 是由字典 D {\displaystyle D} 中获得的原子讯号。

如同傅立叶级数将一讯号拆解成一系列的正弦波的相加,其中每个成分拥有不同的系数作为权重,其数学式子如下:

而匹配追踪也具有将讯号拆解成一系列原子相加的意涵,甚至可以使用匹配追踪去描述傅立叶级数,也就是原子库对应到的所有正弦函数的集合。

为了找到最符合原讯号的一组原子加权总合,如果对原子库进行所有组合的尝试过于耗费时间。在1993年由Mallat S和Zhang Z的论文中,提出了一个贪婪算法(Greedy Algorithm),并大幅降低找出近似解的时间。其作法首先在原子库中寻找与原讯号内积结果最大的原子 g γ n {\displaystyle g_{\gamma _{n}}} ,找到此讯号以及其内积结果 a n {\displaystyle a_{n}} 之后再将原讯号减掉 a n g γ n {\displaystyle a_{n}g_{\gamma _{n}}} 作为下一次重复运算的原始讯号,如此反复做下去即可得到一系列的 a n {\displaystyle a_{n}} 以及原子 g γ n {\displaystyle g_{\gamma _{n}}} ,直到达到停止条件为止,其详细的算法如下:

在信号处理的许多应用中,需要将信号分解为一群在时域和频域都具有良好局部性(集中在某一范围)的函数,这些函数称为时频原子(time-frequency atom)。

选择不同的时频原子时,分解方式的特性会有很大的差异。窗函数傅立叶转换(window Fourier transform)和小波转换(wavelet transform)都是时频信号分解的方法。

通常一个时频原子群可以由单一的窗函数 g ( t ) L 2 ( R ) {\displaystyle g(t)\in L^{2}(R)} 经过scale、translation和modulation产生,令 g ( t ) O ( 1 t 2 + 1 ) {\displaystyle g(t)\in O({\frac {1}{t^{2}+1}})} 为一个实数的连续可微函数,且限制 g = 1 {\displaystyle \|g\|=1} g ( t ) {\displaystyle g(t)} 的积分不为零、 g ( 0 ) 0 {\displaystyle g(0)\neq 0}

γ = ( s , u , ξ ) {\displaystyle \gamma =(s,u,\xi )} 表示scale参数 s ( s > 0 ) {\displaystyle s(s>0)} 、translation参数 u {\displaystyle u} 和modulation参数 ξ {\displaystyle \xi } ,定义 g γ ( t ) {\displaystyle g_{\gamma }(t)}

g γ ( t ) = 1 s g ( t u s ) e i ξ t {\displaystyle g_{\gamma }(t)={\frac {1}{\sqrt {s}}}g({\frac {t-u}{s}})e^{i\xi t}}

其中 γ {\displaystyle \gamma } 是集合 Γ = R + × R 2 {\displaystyle \Gamma =R^{+}\times R^{2}} 中的元素, 1 s {\displaystyle {\frac {1}{\sqrt {s}}}} 使得 g = 1 {\displaystyle \|g\|=1}

事实上,函数群 D = ( g γ ( t ) ) γ Γ {\displaystyle D={(g_{\gamma }(t))}_{\gamma \in \Gamma }} 含有许多冗余的元素,对于任何函数 f ( t ) {\displaystyle f(t)} ,更有效率的表示方法是,在原子 ( g γ n ( t ) ) n N {\displaystyle {(g_{\gamma _{n}}(t))}_{n\in N}} 中,只选取适当数量的子集合,其中 γ n = ( s n , u n , ξ n ) {\displaystyle \gamma _{n}=(s_{n},u_{n},\xi _{n})} ,则 f ( t ) {\displaystyle f(t)} 可以表示为

f ( t ) = n = + a n g γ n ( t ) {\displaystyle f(t)=\sum _{n=-\infty }^{+\infty }a_{n}g_{\gamma _{n}}(t)}

在窗函数傅立叶转换中,所有原子 g γ n {\displaystyle g_{\gamma _{n}}} 具有相同的scale参数 s n = s 0 {\displaystyle s_{n}=s_{0}} ,因此主要分布在一个大小为 s 0 {\displaystyle s_{0}} 倍数的区间内,由于上述特性,窗函数傅立叶转换无法准确地描述比 s 0 {\displaystyle s_{0}} 大许多或小许多的函数结构。

小波转换将信号分解为不同尺度的时频原子,称为小波(wavelet),小波群 ( g γ n ( t ) ) n N {\displaystyle {(g_{\gamma _{n}}(t))}_{n\in N}} 的建构方法是令 ξ n = ξ 0 / s n {\displaystyle \xi _{n}=\xi _{0}/s_{n}} ,其中 ξ 0 {\displaystyle \xi _{0}} 是一个常数。小波转换可以分析不同尺寸的信号成分,然而,受限于参数 ξ n {\displaystyle \xi _{n}} s n {\displaystyle s_{n}} 必须成反比的条件,小波转换的系数无法精准估计傅立叶转换后具有良好局部性的频率成分。

自适应时频分解(adaptive time-frequency decomposition)的目的是将信号展开到一组波形(waveform)上,这些波形选自一个数量庞大的冗余字典,而匹配追踪是能达到自适应分解的一种方法。

一个希尔伯特空间可表示为 L 2 ( R ) {\displaystyle L^{2}(R)} ,其组成的复数函数 f {\displaystyle f} 必须满足

f = + | f ( t ) | 2 d t < + {\displaystyle \|f\|=\int _{-\infty }^{+\infty }{|f(t)|}^{2}dt<+\infty }

H {\displaystyle H} 代表一个希尔伯特空间,则将“字典”定义为 H {\displaystyle H} 中的一个向量群 D = ( g γ ) γ Γ {\displaystyle D={(g_{\gamma })}_{\gamma \in \Gamma }} ,满足 g γ = 1 {\displaystyle \|g_{\gamma }\|=1} ,其中 γ {\displaystyle \gamma } 是集合 Γ = R + × R 2 {\displaystyle \Gamma =R^{+}\times R^{2}} 中的元素。 V {\displaystyle V} 代表字典向量的封闭线性生成空间(closed linear span),在空间 V {\displaystyle V} 中,集合 D {\displaystyle D} 之向量的有限线性展开(finite linear expansion)是稠密(dense)的,如果 V = H {\displaystyle V=H} ,则称此字典具有完备性(completeness)。对于“时频原子分解”段落所描述的字典, H = L 2 ( R ) {\displaystyle H=L^{2}(R)} ,在空间 L 2 ( R ) {\displaystyle L^{2}(R)} 中,时频分子的有限线性展开是稠密的,因此该字典具有完备性。

假设有一信号 f H {\displaystyle f\in H} ,欲将其线性展开到由集合 D {\displaystyle D} 中选出的一组向量上,使得结果最匹配原来的信号结构。匹配追踪的方法是连续地将 f {\displaystyle f} 以其在集合 D {\displaystyle D} 中元素的正交投影(orthogonal projection)近似。

g γ 0 D {\displaystyle g_{\gamma _{0}}\in D} ,向量 f {\displaystyle f} 可以被分解为

f = f , g γ 0 g γ 0 + R f {\displaystyle f=\langle f,g_{\gamma _{0}}\rangle g_{\gamma _{0}}+Rf}

其中 R f {\displaystyle Rf} 是将 f {\displaystyle f} g γ 0 {\displaystyle g_{\gamma _{0}}} 的方向近似后的剩余向量(residual vector),由于 g γ 0 {\displaystyle g_{\gamma _{0}}} R f {\displaystyle Rf} 正交,可得下式

f 2 = | f , g γ 0 | 2 + R f 2 {\displaystyle {\|f\|}^{2}={|\langle f,g_{\gamma _{0}}\rangle |}^{2}+{\|Rf\|}^{2}}

为了最小化 R f {\displaystyle \|Rf\|} ,必须选取 g γ 0 D {\displaystyle g_{\gamma _{0}}\in D} 使得 | f , g γ 0 | {\displaystyle |\langle f,g_{\gamma _{0}}\rangle |} 最大化。在某些情况下,只能找到近似最佳的向量 g γ 0 {\displaystyle g_{\gamma _{0}}} ,符合

| f , g γ 0 | α   sup γ Γ | f , g γ | {\displaystyle |\langle f,g_{\gamma _{0}}\rangle |\geq \alpha \ {\underset {\g

相关

  • 乏燃料池乏核燃料是经受过辐射照射、使用过的核燃料,通常是由核电站的核反应堆产生。这种燃料无法继续维持核反应。乏核燃料中仍然包含有大量的放射性元素,因此具有放射性,如果不加以妥
  • 路易吉·伽伐尼路易吉·阿洛伊西奥·伽伐尼(意大利文:Luigi Aloisio Galvani, 拉丁文:Aloysius Galvani)1737年9月9日-1798年12月4日)是意大利医生、物理学家与哲学家,现代产科学的先驱者。他在意
  • 凯泽在物理学里,波数是波动的一种性质,定义为每 2π 长度的波长数量(即每单位长度的波长数量乘以 2π)。更明确地说,波数是每 2π 长度内,波动重复的次数(一个波动取同样相位的次
  • 罗马奥林匹克体育场罗马奥林匹克体育场(Stadio Olimpico di Roma,又名奥林匹高球场)是意大利罗马市最主要的体育场,也是意甲俱乐部罗马和拉齐奥的共用主场球场。罗马奥林匹克体育场为了一九六零年
  • 氯化铁氯化铁(FeCl3)又称三氯化铁,是三价铁的氯化物。它易潮解,在潮湿的空气会水解,溶于水时会释放大量热,并产生啡色的酸性溶液。这个溶液可蚀刻铜制的金属,甚至不锈钢。无水的氯化铁是
  • 南非语南非语(Afrikaans),字面意思为“非洲语”或“非洲的”,但发展是基于欧洲语言而来,为南非境内的白人种族阿非利卡人的主要语言。也有人将其中文名译为南非荷兰语、阿非利卡语、阿
  • 莉莉·艾尔伯莉莉·艾尔伯(丹麦语:Lili Elbe,1882年12月28日-1931年9月13日)是一位丹麦跨性别女性,也是世界上有纪录的最早接受性别重置手术者之一。艾尔伯出生时生理性别为男性,名叫埃纳·莫恩
  • 十日谈《十日谈》(Decameron )是意大利文艺复兴时期作家乔万尼·薄伽丘所著的一本写实主义短篇小说集。1348年繁华的佛罗伦萨发生一场残酷的瘟疫(黑死病),丧钟乱鸣,死了十多万人,在整个欧
  • 枣庄市枣庄市,简称枣,古称峄县,是中华人民共和国山东省下辖的地级市,位于山东省南部。市境东接临沂市,北、西两面邻济宁市,南界江苏省徐州市。地处黄淮平原腹地,山东丘陵西南边缘,西濒微山
  • 长征系列运载火箭长征系列运载火箭是中华人民共和国自行研制的航天运载工具,长征火箭从1965年开始研制,1970年“长征一号”运载火箭首次发射“东方红一号”卫星成功。目前,长征火箭有:长征一号、