基追踪降噪（Basis Pursuit De-Noising, BPDN）

先介绍下软阈值（Soft Thresholding）的概念：

求解如下优化问题：

将上述目标函数展开即为

即转化为了求解N个如下的独立函数的优化问题：

对上述函数求导

令导数等于0

等号两边都有x，需要进一步分情况讨论，推导过程见https://www.cnblogs.com/wlzy/p/7966525.html

讨论之后综合多种情况，f(x)的最小值为：

即当参数b小于\lambda/2 时，x=b+\lambda/2 时，f(x)取到最小值，当|b| 小于\lambda/2时，x=0取到最小值，b大于\lambda/2时，x=b-\lambda/2取到最小。

个人理解，之所以称之为软阈值，因为\lambda为参数而非固定的常值，取值范围随着\lambda的变动而变动。

将上式中的b视为变量，λ/2视为阈值，上式即为软阈值(Soft Thresholding)的公式。

即若要解决优化问题

只需要调用soft(B, λ/2)即可

可以发现，软阈值解决的优化问题和基追踪降噪问题很像，但并不一样，而且需要格外说明的是，软阈值并能不解决基追踪降噪问题。

基追踪（Basis Pursuit，BP）

通过将非凸问题转化为凸优化问题求解找到信号的逼近。

基本思想是由于零范数具有非凸性，故而将优化问题中的零范数转化为一范数求解的优化算法。

由文献Donoho D L.Compressedsensing[J]. IEEE Transactions on information theory, 2006, 52(4):1289-1306. (Available at: http://www.signallake.com/innovation/CompressedSensing091604.pdf)的4.1节较为详细的证明了零范数和一范数的最小化在某种条件下是等价的。

L1范数最小化是通过用L1范数来近似0范数，取1而不取1/2,2/3或者其他值，是因为1范数最小化是凸优化问题，可以将求解过程转化成有一个线性规划问题。L1最小范数下最优化问题又称为基追踪(BP)，常用实现算法有：内点法和梯度投影法。内点法速度慢，但得到的结果十分准确：而梯度投影法速度快，但没有内点法得到的结果准确 。

如何将一范数问题转化为标准的线性规划问题求解：

式中的变量a没有非负约束，所以要将a变为两个非负变量u和v的差a=u-v，由于u可以大于也可以小于v，所以a可以是正的也可以是负的。也就是说，约束条件Φa=s要变为Φ(u-v)=s，而这个还可以写为[Φ,-Φ][u;v]=s。

此时约束条件已经符合线性规划的非负性的要求，需要进一步考虑如何将目标函数变为我们想要的形式。

基追踪降噪（Basis Pursuit DeNoising，BPDN）

为了使基追踪能够适应有噪声的数据，提出了基追踪降噪：

我们假定数据具有如下的形式：

其中z是标准的高斯白噪声， \sigma是噪声等级，s是去噪后的clean signal，在上述式子中，y是已知的，s是未知的

未完待续。