|
abstract:
The lš-minimization problem min{ ||x||_1 : Ax=b } , also known as Basis Pursuit (BP), has become important in Compressed Sensing due to its ability to sometimes yield the sparsest solution of the underdetermined system Ax=b. In the past few years, a lot of new algorithms solving (BP) or some (possibly regularized) variant of it have been developed. We introduce a subgradient scheme which -- unlike typical projected subgradient methods -- is not required to maintain feasibility of the iterates throughout the algorithmic progress. Convergence of this method (ISML1) to an optimal feasible point for (BP) can be proven under certain reasonable assumptions. In the second part of the talk we will present results of a computational comparison of various state-of-the-art lš-solvers and our method. We also show how a new optimality check can speed up these solvers and at the same time dramatically improve the solution quality. (Joint work with D. Lorenz and M. Pfetsch) |
