Sparsity Aware Simplex Algorithms for Sparse Recovery
Conference: SCC 2015 - 10th International ITG Conference on Systems, Communications and Coding
02/02/2015 - 02/05/2015 at Hamburg, Germany
Pages: 5Language: englishTyp: PDFPersonal VDE Members are entitled to a 10% discount on this title
Zoerlein, Henning; Leichtle, Thomas; Bossert, Martin (Institute of Communications Engineering, Ulm University, 89081 Ulm, Germany)
Since it is NP-hard to find an optimal solution to the sparse recovery problem, suboptimal approaches are considered. The well known Basis Pursuit is a possible convex relaxation and widely used for sparse recovery. The resulting linear optimization problem can be solved with the help of the simplex algorithm. By utilizing degenerated corners, usually avoided in conventional approaches, sparsity aware variants of the simplex algorithm are introduced in this paper. The variants resemble possible trade-offs between potential reconstruction improvements and increased complexity. The improved recovery capability is evaluated by numerical simulations.