BP问题介绍

基追踪不同于匹配追踪(Match Pursuit, MP)，描述的不是一种算法，而是一类问题。基追踪用来描述信号在过完备字典(Overcomplete Dictionary)下的稀疏表示(Sparse Representation, SR)¹。由于字典是过完备的，信号总能通过基的线性组合表达。此外，由于字典中的基一般不是线性无关的，所以信号在选定字典下的稀疏表示并不唯一。

稀疏性可以通过向量的$\ell_0$范数保证。这类问题称作$\ell_0$规约化($\ell_0$ Regularization)问题，表达如下：

$$
\underset{\alpha}{\arg\min}||\alpha||_0 \quad\text{s.t.}\quad \Phi\alpha=y
$$

式中，$y$为信号，$\alpha$为稀疏表示系数，$\Phi$为过完备字典，$||\alpha||_0=\#\{i|\alpha_i\ne0\}$为向量$\alpha$的$\ell_0$范数。但这类问题是NP-Hard问题，在计算和使用时并不方便。

使用$\ell_1$范数，也可保证系数的稀疏性，此时上述问题就变为了BP问题：

$$
\underset{\alpha}{\arg\min}||\alpha||_1 \quad\text{s.t.}\quad \Phi\alpha=y
$$

式中，$y$为信号，$\alpha$为稀疏表示系数，$\Phi$为过完备字典，$||\alpha||_1=\sum_i|\alpha_i|$为向量$\alpha$的$\ell_1$范数。

BP问题求解

在Chen的文章中，将BP转化为线性规划(Linear Programming, LP)问题解决。详细推导如下：

线性规划的一般形式如：
$$
\underset{x}{\arg\min} c^\mathrm{T}x \quad\text{s.t.}\quad \mathrm{A}x=b,\ x\ge0
$$

做变量代换$\alpha = u - v$，$u\ge0$，$v\ge0$，有：

$$
\begin{align*}
\Phi\alpha &= \Phi(u-v) \\
&= (\Phi,-\Phi)\times\left(\begin{array}{c} u \\ v\end{array}\right) \\
||\alpha||_1&=||u||_1+||v||_1 \\
&=\sum_i(u_i+v_i)
\end{align*}
$$

因此取$A=(\Phi,-\Phi)$，$b=y$，$c^\mathrm{T} = (\mathbf{1},\mathbf{1})$，即可将BP问题转化为LP问题，求解后：
$$
\alpha_i = x_i - x_{i+\#\alpha}
$$

可以实现如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


% inputs:
% y: signal
% B: dictionary
% output:
% alpha: coefficient vector \alpha
function alpha = bp(y, Phi)
    c = ones(1, length(Phi) * 2);
    x = optimvar('x', length(Phi) * 2, 1);
    prob = optimproblem;
    prob.Objective = c * x;
    prob.Constraints.cons = [Phi, -Phi] * x == y;

    sol = solve(prob);
    
    alpha = sol.x(1:end/2) - sol.x(end/2+1:end);
end

BP问题中由于约束$\Phi\alpha=y$的存在，字典的完备性必须保证(任意信号一定能够表示为字典中向量的线性组合)，否则无法满足约束条件，问题不可解。当问题可解时，重构的信号一定和原信号完全一致。

BPDN问题介绍

当信号含有噪声或不关注的成分时，一般希望分解重构后的信号将这些成分去除。借鉴BP的思想，提出基追踪降噪(Basis Pursuit Denoise, BPDN)问题。信号$y=s+n$，$n$为噪声，在给定的字典$\Phi$下，BPDN得到的重构满足：

$$
y=\Phi\alpha+r
$$

$r$为BPDN重构的余量，这种方法得到的是原信号的稀疏近似²。

BPDN问题构造如下：

$$
\underset{\alpha}{\arg\min}\frac{1}{2}||y-\Phi\alpha||_2^2 + \mathrm{\lambda}||\alpha||_1
$$

与BP问题相比没有约束项。该式总是可解的，且解是$\mathrm{\lambda}$的函数$\alpha(\mathrm{\lambda})$。

类似于BP问题，BPDN问题可以转化为扰动线性规划(Perturbed Linear Programming, PLP)问题解决。这里不做详细推导。做代换$\mathrm{A}=(\Phi,-\Phi)$，$b=y$，$c=\mathrm{\lambda}(\mathbf{1},\mathbf{1})$, $x=(u,v)$，$\alpha = u - v$，$u\ge0$，$v\ge0$，可以得到PLP问题：

$$
\underset{x,p}{\arg\min}c^\mathrm{T}x+\frac{1}{2}||p||^2 \quad\text{s.t.}\quad \mathrm{A}x+\delta p=b, x\ge0, \delta=1
$$

PLP本质上是一个二次规划(Quadratic Programming, QP)问题。因此BPDN也可转化为QP问题求解。例如标准的边界约束二次规划(Bound-Constrained Quadratic Programming, BCQP)问题，如下：

$$
\underset{z}{\arg\min}c^\mathrm{T}z+\frac{1}{2}z^\mathrm{T}Bz \quad\text{s.t.}\quad z\ge 0
$$

参考链接: https://blog.csdn.net/jbb0523/article/details/52013669
类似BP，做代换$\alpha = u - v$，$u\ge0$，$v\ge0$，并定义$G = (\Phi,-\Phi)$，$z = \left(\begin{array}{c}u\\v\end{array}\right)$有：

$$
\begin{align*}
||y-\Phi\alpha||_2^2 &= ||y-Gz||_2^2 \\
&= (y-Gz)^\mathrm{T}(y-Gz) \\
&= y^\mathrm{T}(y-Gz) - (Gz)^\mathrm{T}(y-Gz) \\
&= y^\mathrm{T}y - y^\mathrm{T}Gz - z^\mathrm{T}G^\mathrm{T}y + z^\mathrm{T}G^\mathrm{T}Gz \\
\end{align*}
$$

因为$y^\mathrm{T}Gz$是标量，有$y^\mathrm{T}Gz = (y^\mathrm{T}Gz)^\mathrm{T} = z^\mathrm{T}G^\mathrm{T}y$，所以：

$$
\begin{align*}
||y-\Phi\alpha||_2^2 &= y^\mathrm{T}y - z^\mathrm{T}G^\mathrm{T}Gz - 2y^\mathrm{T}Gz\\
&= y^\mathrm{T}y + z^\mathrm{T}G^\mathrm{T}Gz - 2(y^\mathrm{T}\Phi, -y^\mathrm{T}\Phi)z
\end{align*}
$$

与BP类似，有：

$$
||\alpha||_1=\sum_i(u_i+v_i)=(\mathbf{1},\mathbf{1})z
$$

取：

$$
\begin{align*}
B &= G^\mathrm{T}G =\left(\begin{array}{rr}\Phi^\mathrm{T}\Phi & -\Phi^\mathrm{T}\Phi \\ -\Phi^\mathrm{T}\Phi & \Phi^\mathrm{T}\Phi\end{array}\right)\\
c^\mathrm{T} &= \mathrm{\lambda}(\mathbf{1},\mathbf{1})- (y^\mathrm{T}\Phi, -y^\mathrm{T}\Phi)z = (\mathrm{\lambda}\mathbf{1} - y^\mathrm{T}\Phi,\mathrm{\lambda}\mathbf{1} + y^\mathrm{T}\Phi)
\end{align*}
$$

有：

$$
\begin{align*}
\frac{1}{2}||y-\Phi\alpha||_2^2 + \mathrm{\lambda}||\alpha||_1
&= \frac{1}{2}[y^\mathrm{T}y + z^\mathrm{T}G^\mathrm{T}Gz - 2(y^\mathrm{T}\Phi, -y^\mathrm{T}\Phi)z] + \mathrm{\lambda}(\mathbf{1},\mathbf{1})z \\
&= \frac{1}{2}y^\mathrm{T}y + \frac{1}{2}z^\mathrm{T}Bz + [\mathrm{\lambda}(\mathbf{1},\mathbf{1}) -(y^\mathrm{T}\Phi, -y^\mathrm{T}\Phi)]z \\
&= c^\mathrm{T}z + \frac{1}{2}z^\mathrm{T}Bz + \frac{1}{2}y^\mathrm{T}y
\end{align*}
$$

由于$y^\mathrm{T}y$是常量，在求解中可以直接忽略。BPDN问题即转化为BCQP问题，同样的，求解后有：

$$
\alpha_i = z_i - z_{i+\#\alpha}
$$

BPDN可以实现如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


% inputs:
% y: signal
% B: dictionary
% lambda: parameter
% output:
% alpha: coefficient vector \alpha
function alpha = bpdn(y, Phi, lambda)
    n = size(Phi, 2);
    b = y' * Phi;
    c = lambda * ones(1, 2*n) + [-b, b];
    B = [Phi' * Phi, -Phi' * Phi; -Phi' * Phi, Phi' * Phi];
    lb = zeros(2*n, 1);
    z0 = quadprog(B, c', [], [], [], [], lb, [], []);
    alpha = z0(1:n) - z0(n+1:2*n);
end

λ取值问题

在chen的文章中，有：

$$
\mathrm{\lambda} = \sigma\sqrt{2\log (p)}
$$
式中，$p$为字典中基的数目，$\sigma$为噪声成分的强度。

在hua的文章中中，有：

$$
\mathrm{\lambda} = \frac{1}{10}max|\Phi^\mathrm{T}y|
$$

fan的文章中探讨了不同$\mathrm{\lambda}$对结果的影响，在文中的应用场合下，最后选择了$\mathrm{\lambda}=11$。

BPDN问题的其他形式

BPDN问题与下列问题在一定条件下是等价的：
$$
\begin{aligned}
\text{QCLP:}\quad\underset{\alpha}{\arg\min}||\alpha||_1 \quad\text{s.t.}\quad ||y-\Phi\alpha||_2^2\le\epsilon \\
\text{QP:}\quad\underset{\alpha}{\arg\min}||y-\Phi\alpha||_2^2 \quad\text{s.t.}\quad ||\alpha||_1\le t
\end{aligned}
$$

讨论

BPDN问题和机器学习/统计学中的最小绝对值收敛和选择算子(Least Absolute Shrinkage and Selection Operator, LASSO)有密切联系，问题的基本形式一致。
BP类的问题和凸优化(Convex Optimization)密切相关。这类问题的求解复杂度比MP类的算法高很多。
此类问题也称作$\ell_1$或$\ell_p$问题，l1 magic工具箱及其相关的研究可以用来深入学习此类问题。

TO BE CONTINUED…

注意这里是表示。此外，另一个常见术语缩写SSR = Signal Sparse Representation，~~而不是Super Super Rare~~。 ↩︎
注意这里是近似，有别于上述的表示。 ↩︎

基追踪(Basis Pursuit, BP)