BP问题介绍#
基追踪不同于匹配追踪(Match Pursuit, MP),描述的不是一种算法,而是一类问题。基追踪用来描述信号在过完备字典(Overcomplete Dictionary)下的稀疏表示(Sparse Representation, SR)1。由于字典是过完备的,信号总能通过基的线性组合表达。此外,由于字典中的基一般不是线性无关的,所以信号在选定字典下的稀疏表示并不唯一。
稀疏性可以通过向量的$\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} $$可以实现如下:
| |
BP问题中由于约束$\Phi\alpha=y$的存在,字典的完备性必须保证(任意信号一定能够表示为字典中向量的线性组合),否则无法满足约束条件,问题不可解。当问题可解时,重构的信号一定和原信号完全一致。
BPDN问题介绍#
当信号含有噪声或不关注的成分时,一般希望分解重构后的信号将这些成分去除。借鉴BP的思想,提出基追踪降噪(Basis Pursuit Denoise, BPDN)问题。信号$y=s+n$,$n$为噪声,在给定的字典$\Phi$下,BPDN得到的重构满足:
$$ y=\Phi\alpha+r $$$r$为BPDN重构的余量,这种方法得到的是原信号的稀疏近似2。
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 $$点击查看BPDN转化为BCQP的推导过程
参考链接: 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可以实现如下:
| |
λ取值问题#
在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工具箱及其相关的研究可以用来深入学习此类问题。