匹配追踪

✍ dations ◷ 2025-07-27 20:07:52 #算法

匹配追踪(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

相关

  • TRH促甲状腺激素释放激素简称甲促素释素(thyrotropin-releasing hormone、TRH),是由下丘脑(Hypothalamus)所制造的肽类激素(Peptide Hormone),能够调节脑下垂体前叶分泌促甲状腺激素(甲
  • 黹部,为汉字索引中的部首之一,康熙字典214个部首中的第二百〇四个(十二划的则为第四个)。就繁体和简体中文中,黹部归于十二划部首。黹部只以左方为部字。且无其他部首可用者将部
  • 丹吉尔丹吉尔(柏柏尔语:ⵜⴰⵏⵊⴰ;阿拉伯语:طنچة‎;转写:Tanja;西班牙语:Tánger;法语:Tanger),又译坦几亚,是北非国家摩洛哥北部的一个滨海城市,在直布罗陀海峡西面的入口,与大西洋及地中
  • 列夫·托尔斯泰列夫·尼古拉耶维奇·托尔斯泰(俄语:Лев Николаевич Толстой,拉丁化:Lev Nikolayevich Tolstoy;1828年9月9日(儒略历8月28日)—1910年11月20日(儒略历11月7日)),俄
  • span title=感觉器 class=rt-commentedTextS/spanATC代码S(感觉器)是解剖学治疗学及化学分类系统的一个分类,这是由世界卫生组织药物统计方法整合中心(The WHO Collaborating Centre for Drug Statistics Methodology)所制定的药
  • 刮胡子剃毛,主要指用剃刀剃去人的毛发等的行为。由于剃毛只能剃去表皮以上的毛发,因此毛发会于短期内长出来,因此剃毛的效果不太好。
  • 诺盖尔鸟诺盖尔鸟(学名Noguerornis)是一类反鸟亚纲鸟类。它们生存于约1亿3000万年前的白垩纪早期,其化石是在西班牙发现。
  • 赫斯特国际集团赫斯特国际集团(Hearst Corporation)是总部建在美国纽约市的出版界巨头,它的创始人是报业大亨威廉·赫斯特(William Randolph Hearst,1863年4月29日-1951年8月14日)。集团在1935年
  • 越南现代史年表越南现代史年表是1945年以后的越南历史年表。
  • 洛阳牡丹花会中国洛阳牡丹文化节是由中国文化部和河南省人民政府每年春季主办的以洛阳牡丹为主题的文化旅游类节会,其前身是洛阳牡丹花会,是中国四大名会之一。自1982年洛阳市政府将牡丹定