4.2. 匹配追踪¶
4.2.1. 什么是匹配追踪¶
匹配追踪 (Matching Pursuit , MP) 最初被提出来是用于信号的稀疏分解 [9], 匹配追踪在很多领域中有应用, 匹配追踪用于量子模拟 [1].
4.2.2. 匹配追踪算法¶
匹配追踪算法步骤见算法1.
注解
算法1: 匹配追踪算法步骤
输入: 列归一化过完备字典矩阵 \({\bm A} \in {\mathbb R}^{m \times n}\), 待分解信号 \({\bm y}\in {\mathbb R}^{m \times 1}\), 稀疏度 \(K\), 容忍残差模值 \(\epsilon\)
输出: 稀疏分解系数 \(\hat{\bm x} \in {\mathbb R}^{n\times 1}\), 索引集合 \({\mathbb I} \subset {\mathbb U} = \{1,2,\cdots,n\}\), 待分解信号近似 \(\hat{\bm y}\) 和残差向量 \({\bm r} = {\bm y} - \hat{\bm y}\)
Step1: 初始化稀疏信号 \({\bm x}_{0} = {\bm 0}\), 残差 \({\bm r}_{0} = {\bm y} - \bm{A}{\bm x}_0 = {\bm y}\), 索引集合(支撑) \({\mathbb I}_{0} = \empty\), 迭代计数器 \(k = 1\).
Step2: 选择与残差最相关的原子, 即求解索引 \(\lambda_k\) 满足优化问题
Step3: 更新索引集 \({\mathbb I}_{k} = {\mathbb I}_{k-1} \cup {i_k}\)
Step4: 更新稀疏分解系数 \(x[i_k] = {\langle {\bm A}_{i_k}, {\bm r}_{k-1} \rangle} = {\bm A}_{i_k}^T{\bm r}_{k-1}\)
Step5: 计算新的残差 \({\bm r}_{k} = {\bm r}_{k-1} - {\bm A}_{i_k}x[i_k]\)
Step6: 更新迭代计数器 \(k = k + 1\) 若 \(k<K\) 且 \(||{\bm r}||_2 < \epsilon\) , 重复 Step2 至 Step6, 否则停止迭代, 转 Step7.
Step7: 输出 \(\hat{\bm x} = \bm{x}\), \(\hat{\bm y} = \hat{\bm y}_{k}\), \({\bm r} = {\bm r}_k\). 其中, \(\hat{\bm x}\) 在位置 \({\mathbb I}_k\) 处非零.