-
压缩感知重构算法之基追踪（
Basis Pursuit
，
BP
）
除匹配追踪类贪婪迭代算法之外，
压缩感知重构算法另一大类就是凸优化算法或
最优化
逼近方法，
这类方法通过将非凸问题转化为凸问题求解找
到信号的逼近，
其中最常用的方法
就是基追踪
< br>(Basis
Pursuit,
BP)
，该方法提出使用
l
1
范数
替代
l
0
范数来解决最优化问题，以便
使用线性规划方法来求解
[1]
。本篇
我们就来讲解基追踪方法。理解基追踪方法需要一定的
最优化知识基础，可参见最优化方
法分类中的内容。
1
、
l1
范数和
l0
范数最小化
的等价问题
在文献【
2
】的第
4
部分，较为详细的证明了
< br>l
1
范数与
l
< br>0
范数最小化在某条件下等价。
证明过程是一个比较复杂
的数学推导，这里尽量引用文献中的原文来说明。
首先，在文
献【
2
】的
4.1
节，给出了
(P1)
问题，并给出了
(P1)
的线性规划等价形式
(LP)
，
这个等价关系后面再详叙。
4.1 The Case
p
?
1
In the case
p
?
1
,
(
P
1
) is a convex
optimization problem. Write it out in an
equivalent form, with
?
being the optimization variable:
(
P
1
)
min
||
?
||
1
subject
to
?
?
?
y
n
.
?
This
can
be
formulated
as
a
linear
programming
problem:
let
A
be
the
n
by
2
m
matrix
[
?
< br>?
?
]
. The
linear program
(
LP
)
min1
T
z
subject
to
Az
?
y
n
,
x
?
0
.
z
has a solution
z
*
, say, a vector
in
?
2
m
which can be partitioned as
z
*
?
[
u<
/p>
*
v
*
]
; then
?
*
?
u
*
?
v<
/p>
*
?
1,
n
?
?
?
*
.
This
linear
program
is
typically
considered
solves
(
P
< br>1
)
.
The
reconstruction
x
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
若
要
谈
基
追
踪
方
法
的
实
现
，
就
必
< br>须
提
到
l1-MAGIC
工
具
箱
（
工
具
箱
主
页
：
/~justin/l1magic/
）
，在工具箱主页有介绍：
L1-MAGIC
is a collection
of
MA
TLAB
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
P
rogramming
》
，可以在工具箱主页下载。
该工具箱一共解决了七个问题，其中第一个问题即是
Basis
Pursuit
：
Min-
l
1
with equality constraints. The problem
(
P
1
)
min
||
x
||
1
subject
to
Ax
?
b
,
also known as basis pursuit, finds
the vector with smallest
l
1
norm
|
?
:
x
i
|
|
|
|
x
1
|
?
i
that explains the observations
b
. As the results in [4, 6]
show, if a sufficiently sparse
x
0
exists
such
that
Ax
0
?
b<
/p>
then
(
P
1
)
will
find
it.
When
x
,
A
,
b
have
real-valued
entries,
(
P
1
)
can
be
recast
as an LP (this is discussed in detail in [10]).
工具箱中给出了专门对（
P
1
）的代码，使用方法可参见
l1eq_example.m,
说明文档
3.1
节也进行了介绍。
< br>
在附录中，给出了将（
P
1<
/p>
）问题转化为线性规划问题的过程，但这个似乎并不怎么容
易看明
白：
3
如何将
(P1)
转化为线性规划问题？
尽管在
l1-MAGIC
给出了一种基
追踪的实现，但需要基于它的
l1eq_pd.m
文件，既然基
追踪是用线性规划求解，
那么就应该可以用
MATLAB
自带的
linprog
函数求解，
究竟该如何
将
(P1)<
/p>
转化为标准的线性规划问题呢？我们来看文献【
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
?
?
?
?
?<
/p>
?
?
.
The
principle of Basis Pursuit is to find a
representation of the signal whose coefficients
have
minimal
l
1
norm. formally, one solves the problem
min
||
a
||
1
subject
to
?
a
?
s
.
(3.1)
From one point of
view, (3.1) is very similar to the method of
Frames (2.3): we are simply
replacing
the
l
2
norm
in
(2.3)
with
the
l
1
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
x
?
?
m
by
min
c
T
x
subject
< br>to
Ax
?
b
< br>,
x
?
0,
(3.2)
where
c
T
x
is
the
objective
function,
Ax
?
b
is
a
collection
of
equality
constraints,
and
x
?
0
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:
m
?
2
p
;
x
?
(
u
,
v
);
c
?
(1,1);
A
?
(
?
,
??
);
b
?
s
.
Hence,
the
solution
of
(3.4)
can
be
obtained
by
solving
an
equivalent
linear
program.
(The
equivalent
of
minimum
l
1
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
的差
a
?
u
?
v
，由于
u
可以大于也可以小于
v
，所以
a
可以是正的也可以是负的
[4]
。也就是说，
约束条件
?
a
?
s
要变为
?
(
u
?
v
)<
/p>
?
s
，
而这个还
可以写为
[
?
,
??
][
u
;
v
]
?
s
，
更清晰的写法如下：
-
-
-
-
-
-
-
-
-
上一篇：人文英语4形考任务单元自测1
下一篇：对口高职升学英语词汇表..