Ewout van den Berg
Guest Ph.D. Student with Uri Ascher and Michael Friedlander, Department of Computer Science
A current problem in signal processing is to find the sparsest representation
of a vector b in terms of columns of an m × n matrix
A with n >> m. That is,
|
minx ||x||0
subject to
Ax = b
|
(1)
|
where ||x||0 is a pseudo-norm defined by
|{i|xi ≠ 0}|.
This problem, being combinatorial in nature is prohibitively expensive to solve.
However, recent results have shown that the same solution can be obtained by solving
|
minx ||x||1
subject to
Ax = b
|
(2)
|
provided b = Ax0 for some sufficiently sparse x0.
In this talk we consider the linear program (LP) formulation of (2)
and discuss the use of primal-dual interior-point methods to solve it. In
particular, we compare the behaviour of a number of different indicator functions,
their use in finite termination of the interior-point algorithms,
and their applicability with respect to different types of vectors x0.
