压缩感知重构算法之基追踪（Basis Pursuit，BP）

除匹配追踪类贪婪迭代算法之外，压缩感知重构算法另一大类就是凸优化算法或最优化逼近方法，这类方法通过将非凸问题转化为凸问题求解找到信号的逼近，其中最常用的方法就是基追踪(Basis Pursuit, BP)，该方法提出使用1l范数替代0l范数来解决最优化问题，以便使用线性规划方法来求解[1]。本篇我们就来讲解基追踪方法。理解基追踪方法需要一定的最优化知识基础，可参见最优化方法分类中的内容。

1、l1范数和l0范数最小化的等价问题

在文献【2】的第4部分，较为详细的证明了1l范数与0l范数最小化在某条件下等价。证明过程是一个比较复杂的数学推导，这里尽量引用文献中的原文来说明。

首先，在文献【2】的4.1节，给出了(P1)问题，并给出了(P1)的线性规划等价形式(LP)，这个等价关系后面再详叙。

4.1 The Case 1p

In the case 1p, (1P) is a convex optimization problem. Write it out in an equivalent form, with

 being the optimization variable:

11()min||||.nPsubjecttoy

This can be formulated as a linear programming problem: let A be the n by 2m matrix

[]. The linear program

()min1,0TnzLPzsubjecttoAzyx.

has a solution *z, say, a vector in 2m which can be partitioned as ***[]zuv; then ***uv

solves 1()P. The reconstruction *1,ˆnx. This linear program is typically considered

computationally tractable. In fact, this problem has been studied in the signal analysis literature

under the name Basis Pursuit [7]; in that work, very large-scale underdetermined problems.

2、基追踪实现工具箱l1-MAGIC

若要谈基追踪方法的实现，就必须提到l1-MAGIC工具箱（工具箱主页：/~justin/l1magic/），在工具箱主页有介绍：L1-MAGIC is a collection

of MATLAB routines for solving the convex optimization programs central to compressive

sampling. The algorithms are based on standard interior-point methods, and are suitable for

large-scale problems.

另外，该工具箱专门有一个说明文档《l1-magic: Recovery of Sparse Signals via Convex

Programming》，可以在工具箱主页下载。

该工具箱一共解决了七个问题，其中第一个问题即是Basis Pursuit ：

Min-1l with equality constraints. The problem

11()min||||,PxsubjecttoAxb

also known as basis pursuit, finds the vector with smallest 1l norm

1||||:||iixx

that explains the observations b. As the results in [4, 6] show, if a sufficiently sparse 0x exists

such that 0Axb then 1()P will find it. When ,,xAbhave real-valued entries, 1()P can be

recast as an LP (this is discussed in detail in [10]). 工具箱中给出了专门对（1P）的代码，使用方法可参见l1eq_example.m, 说明文档3.1节也进行了介绍。

在附录中，给出了将（1P）问题转化为线性规划问题的过程，但这个似乎并不怎么容易看明白：

3 如何将(P1)转化为线性规划问题？

尽管在l1-MAGIC给出了一种基追踪的实现，但需要基于它的l1eq_pd.m文件，既然基追踪是用线性规划求解，那么就应该可以用MATLAB自带的linprog函数求解，究竟该如何将(P1)转化为标准的线性规划问题呢？我们来看文献【3】的介绍：

3 Basis Pursuit

We now discuss our approach to the problem of overcomplete representations. We assume

that the dictionary is overcomplete, so that there are in general many representations

s.

The principle of Basis Pursuit is to find a representation of the signal whose coefficients have

minimal 1l norm. formally, one solves the problem

1min||||asubjecttoas. (3.1)

From one point of view, (3.1) is very similar to the method of Frames (2.3): we are simply

replacing the 2l norm in (2.3) with the 1l norm. however, this apparently slight change has

major consequences. The method of Frames leads to a quadratic optimization problem with linear

equality constraints, and so involves essentially just the solution of a system of linear equations. In

contrast, Basis Pursuit requires the solutions of a convex, nonquadratic optimization problem,

which involves considerably more effort and sophistication.

3.1 Linear Programming

To explain the last comment, and the name Basis Pursuit, we develop a connection with linear

programming (LP).

The linear program in so-called standard form [7,16] is a constrained optimization problem

defined in terms of a variable mx by

min,0,TcxsubjecttoAxbx (3.2)

where Tcx is the objective function, Axb is a collection of equality constraints, and 0x

is a set of bounds. The main question is, which variables should be zero.

The Basis Pursuit problem (3.1) can be equivalently reformulated as a linear program in the

standard form (3.2) by making the following translations:

2;(,);(1,1);(,);.mpxuvcAbs

Hence, the solution of (3.4) can be obtained by solving an equivalent linear program. (The

equivalent of minimum 1l optimizations with linear programming has been known since the

1950’s; see[2]). The connection between Basis Pursuit and linear programming is useful in several

ways.

这里，文献【3】的转化说明跟文献【2】中4.1节的说明差不多，但对初学者来说仍然会有一定的困难，下面我们就以文献【3】中的符号为准来解读一下。

首先，式(3.1)中的变量a没有非负约束，所以要将a变为两个非负变量u和v的差auv，由于u可以大于也可以小于v，所以a可以是正的也可以是负的[4]。也就是说，约束条件as要变为()uvs，而这个还可以写为[,][;]uvs，更清晰的写法如下： []usv

然后，根据范数的定义，目标函数可进一点写为：

1||||||||iiiiiaauv

目标函数中有绝对值，怎么去掉呢？这里得看一下文献【5】：

对L1norm如何线性化的理解最主要的是要想明白为什么对单一元素的最小化，即min||x等价于以下的线性规划问题。

min,0yzyzxyz

现在假设以上的线性规划问题的最优解00,yz，并且000,0yz。这个时候，总可以找到一个很小的正数使得10100,0yyzz。而对于11,yz它们满足以上线性规划的所有约束，比如110000()yzyzyzx，但这组可行解却具有比00,yz更小的目标函数值，即002yz。这就证明了00,yz并不是最优解，从而导出矛盾。所以这一般的结论就是对于以上的线性规划问题，其最优解必须满足要吗0y，要吗0z，从而其最优目标值要吗是x，要吗是x，即||x。