如果对压缩感知没有概念的同学可以去看看我的上一篇文章：压缩感知基本概念

基追踪算法

我们考虑下面的问题：

$Ax=b$

其中$x\in R^n,b\in R^m,A\in R^{m\times n},m<<n$,实际上，这个问题是存在无穷多解的，但是对于压缩感知而言，我们需要的是稀疏解，所以我们需要将问题转化成

$min||x||_0 \quad s.t.\quad Ax=b$

但是我们不难发现，这是一个NP-hard问题，但是在这类问题中，我们可以将$||x||_1与||x||_0$等价看待，由于$||x||_1$是连续的，对于我们来说就可以更好地进行求解。但是，还有一个问题，$l_2$范数比$l_1$范数更好求解，那么我们可以通过求解$min||x||_2$来求解问题嘛，很明显，这是不行的，因为$l_2$范数会破坏数据的稀疏性，所以求解的出来的那个解对于我们来说是没有用的，简单点说就是$l_2$范数的解空间是与球相切的，它的解在坐标轴上是非稀疏的（有点粗略，不明白的可以去各大wiki上学学范数）。

求解

线性规划问题

一个比较基础方法就是将问题转化成线性规划问题。

首先我们再明确一下我们的问题：

$min||x||_1 \quad s.t.\quad Ax=b$

那么我们首先将$x$定义成两个非负变量的差：

$x=u-v,u,v\geq 0$

那么我们可以发现在这个顶一下$x$中的元素可以是正也可以是负，那么我们的原等式可以重写为：

$[A,-A][u,v]^T=b$

也就是：

$||x||_1=\sum _{i=1}^n|x_i|=\sum _{i=1}^n|u_i-v_i|$

所以我们就需要求解下列问题

$\begin{cases} min\sum (u+v)\\ u-v=x\\ u,v\geq0 \end{cases}$

我们再定义$y=[u,v]^T\in R^{2n}$,那么我们就可以得到一个较为标准的线性方程：

$\begin{cases} min\quad ey\\ [A,-A]y=b\\ y\geq 0 \end{cases}$

其中e为1行2n列元素全为 1 的向量。

具体代码如下：

function [ alpha ] = bpalg( Phi,b )
% 使用BP思想计算稀疏系数
%phi就是上文中对应的A，alpha就是我们还原的压缩系数，其他定义一致
    n = size(Phi, 2);%取phi的列数
    e = ones(1,2 * n);
    A = [Phi, -Phi];
    lb = zeros(1,2 * n);
    y = linprog(0.5*e,[],[],A,b,lb,[])
    alpha = y(1 : n) - y(n + 1 : 2 * n);

end

利用非光滑凸优化问题的最优性理论(还没搞懂)

对于等式约束，我们引入Lagrangian乘子$v\in R^m$,则Lagrangian函数为：

$L(x,v)=||x||_1+V^T(Ax-b)$

参考文献：

稀疏优化L1范数最小化问题求解之基追踪准则(Basis Pursuit)——原理及其Python实现-CSDN博客

Basis Pursuit, LASSO, TV - 知乎 (zhihu.com)

基追踪及其实现_atomic decomposition by basis pursuit-CSDN博客

未完待续……