Signal Separation with A Priori Knowledge Using Sparse Representation - Advances in Heuristic Signal Processing and Applications - page 313

2. w k (Γ k ) † y ; =

3. r k Γ k w k ; = y −

1.
These greedy algorithms (MP and OLS) are proposed to build up iteratively a
signal representation by selecting the atom that maximally improves the represen-
tation at each iteration. They are easily implemented, converge quickly, and have
good approximation properties. However, there is no guarantee that they compute
sparse representations. Only under some conditions, they can be used to compute
sparse (or nearly sparse) representations [ 22 ]. A drawback of these algorithms ap-
plied to sparse representation is their greediness. It is possible to construct signal
representation problems where, because of the greediness, an atom that is not part
of the optimal sparse representation is selected; as a result, many of the subsequent
atoms selected simply compensate for the poor initial selection [ 14 ]. This shortcom-
ing motivated the development of basis pursuit algorithm, which succeeds on these
problems.

4. k = k +

14.2.2.2 Algorithms Based on Norm Minimization

As searching for the minimum l 0 -norm is an intractable problem, the researchers
consider using methods based on other norm minimizations to find approximate
solutions to Eq. ( 14.3 ). The l 1 -norm minimization and iteratively reweighted norm
minimization are two commonly used alternatives to the l 0 -norm minimization.
(A) Basis pursuit
The principle of basis pursuit (BP) proposed in [ 4 ] is to find signal representa-
tions whose coefficients have minimal l 1 -norm. The resulting representations are
sparse in the l 0 -norm sense under certain conditions [ 8 ]. Formally, BP solves the
following problem

min
w

w 1 subject to y = Dw . (14.4)

The basis pursuit problem of Eq. ( 14.4 ) can be equivalently reformulated as a
linear program (LP) which is the problem of finding a vector q that minimizes a
linear function f T q subject to linear constraints such that one or more of the fol-
lowing hold: Aq < b , A eq . q

b eq , l ≤ q ≤ u . A tremendous amount of work has
been done on the solution of linear programs. For solving a BP optimization prob-
lem, the algorithm from the LP literature can be considered as a candidate. In [ 4 ],
the BP-simplex and BP-interior, which are respectively based on the simplex and
interior-point algorithms, were described to solve a BP optimization problem.
In [ 4 ], the BP is also adapted to the case of noisy data. Take data of the form

=

x = y + e (14.5)

into consideration, where x is the observed signal vector, y is the clean signal vector,
and e is a Gaussian noise. For finding the sparse representation of the clean signal