支持匹配追踪(Support Match Pursuit)算法

介绍

支持匹配追踪(SMP)算法由Etai Mor于2009年提出，是匹配追踪的一个变种，用以解决超声信号的稀疏分解问题，用于重叠回波(分层结构)效果良好。与MP不同，SMP在计算步骤中在字典(所有basis组合成的矩阵)中选取所有满足阈值条件的basis，再通过计算一个参数可选的支持(support)来更新余量和对应的分解系数，一方面保证分解系数的稀疏性，另一方面可以克服MP中每个basis分解系数只计算一次、不能很好表示超声信号的缺点。

流程

待分解的信号记作$y$，第$i$个basis记作$b_i$，稀疏系数向量记作$\Phi$，定义$D=[b_1 \cdots b_n]$，则算法可以表示为：

$$
\begin{aligned}
R^{(0)} &= y \\
\Phi^{(n)} &= D^\mathrm{T}R^{(n)} \\
I^{(n)} &= \{i\ |\ c_i^{(n)}\gt k||R^{(n)}y||2/N\} \\
R^{(n+1)} &= R^{(n)} - D{m(n)}\Phi^{(n)}_{m(n)} \\
m(n) &= \begin{cases}\underset{i,i\in I^{(n)}}{\arg\min} ||R^{(n)}-D_i\Phi^{(n)}i||\xi &\text{if }I^{(n)}\ne\emptyset \\
\underset{i}{\arg\max}\Phi_i^{(n)} &\text{if }I^{(n)}=\emptyset \\
\end{cases}
\end{aligned}
$$

式中：

$N$为向量$y$的长度
阈值项中的常量$k$，一般可取$2\le k\le 3$
支持项$0\le\xi\le1$，当$\xi=1$时，算法退化为MP。当$\xi\approx0$时，算法与理论支持(therotical support)相符¹。

算法终止条件可以选择$n$次迭代或$R^{(n)}<\epsilon$。

实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


% inputs:
% y: signal
% D: dictionary [b1 b2 ... bn]
% iter: number of iterations
% k: threshold argument k
% xi: support argument xi
% output:
% coef: coefficient vector \Phi
function coef = smp(y, D, iter, k, xi)
    R = y;
    coef = zeros(size(D, 2), 1);
    nD = vecnorm(D);
    D = D ./ nD;
    for i = 1:iter
        c = D' * R;
        thres = k * norm(R) / length(y);
        P = c(abs(c) > thres);
        if isempty(P)
            [~, m] = max(abs(c));
            coef(m) = c(m) / nD(indices(m));
            R = R - D(:, m) * c(m);
        else
            indices = 1:length(c);
            indices = indices(abs(c) > thres);
            RR = repmat(R, 1, length(P)) - D(:, indices) .* P';
            [~, m] = min(vecnorm(RR, xi));
            R = RR(:, m);
            coef(indices(m)) = P(m) / nD(indices(m));
        end
    end
end

效果

论文里的图片：

a和b为MP，c和d为SMP。

暂时没有明白含义 ↩︎

支持匹配追踪(Support Match Pursuit)算法

介绍

流程

实现

效果

相关内容