热门问题
时间线
聊天
视角
匹配追求过程
来自维基百科,自由的百科全书
Remove ads
匹配追求,是一个将高复杂度的信号以较简单的讯号来近似的过程,也就是在多维空间中,将高维度的资讯投影到较低维度的生成空间,借此降低一个信号所需的展开项目。
![]() | 此条目包含过多行话或专业术语,可能需要简化或提出进一步解释。 (2018年1月8日) |
![]() | 此条目包含指南或教学内容。 (2018年1月8日) |
简单来说,就是用尽可能少的基元,进行线性组合来逼近原讯号。
一个有N个基元的近似讯号为
其为各基元的权重。而与原讯号的近似误差为,表示为
匹配追求并不会赋予子空间的每个基元一个权重,意即有些基底会舍弃不用,借此降低所需空间,相反的,匹配追求会基于贪婪演算法,尽可能的用较少的基元,来降低误差。核心思想为自子空间中选择一个和讯号内积值最大的基元,将基元乘上适当的权重并从原讯号中减去,接著再次进行以上二步骤。以此往复实行运算,直到原讯号被解析,也就是近似误差趋近于0。
Remove ads
压缩感知
现假设有一组基元源自于字典,这组组成一个过完备性(Over-complete)、非正交集合。
压缩感知的问题在此即为:
Remove ads
能不能找到最小的(不为0的个数,),使得近似讯号等于。
Remove ads
很明显的,自然界中讯号大多只能以近似方式逼近,因此改为求
然而,这个最佳化问题是NP困难,无法在线性多项式时间内找到解答,因此使用匹配追求的近似解来求解。
Remove ads
演算法
輸入: 原訊號 輸出: 所需權重 與其對應的基元 初始化: 反覆: 尋找 使得內積 最大 令 令 直到中止條件發生: 問題一: 問題二: 問題三: 結束
Remove ads
基底追求(Basis Pursuit)
有鉴于匹配追求的限制条件以及贪婪演算法在特定情况上造成不适当的基元选择,S.S.Chen等人于1998年提出的基底追求。[1]若将匹配追求想成,从一个"空"的集合中,在每次迭代中慢慢增加一个基元来构成近似讯号,基底追求则可以想成,从一个完整的基元集合,慢慢减少基元数量。
现假设有一组基元源自于字典,这组组成一个过完备性(Over-complete)、非正交集合。不同于匹配追求,将原先所求的0级范数(),改为求其绝对值。
在此情况下,基底追求对于压缩感知问题的解法亦能细分为三大问题:
Remove ads
能不能找到最小的,使得近似讯号等于。
Remove ads
同理,自然界中讯号大多只能以近似方式逼近,因此改为求
这个最佳化问题依旧是NP困难,因此可使用基底追求的近似解来求解。
Remove ads
相关型态
- where
近似讯号是的特例,由三个基元组合而成,每个基元由决定在时间轴上的中心位置,决定在频率轴上的中心位置,以及由选择缩放尺度的大小。
由于 是非正交集合, 需要透过匹配追求来求得。
Four-Parameter Atoms(Chirplet) [2]
- where
近似讯号是的特例,由四个基元组合而成,每个基元由决定在时间轴上的中心位置,决定在频率轴上的中心位置,以及选择缩放尺度的大小和控制啁啾率。
同理,由于 是非正交集合, 需要透过匹配追求来求得。
参考资料
1. Jian-Jiun Ding, Time frequency analysis and wavelet transform class note, Department of Electrical Engineering, National Taiwan University (NTU), Taipei, Taiwan, 2017.
外部链接
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads