Final presentation of the master thesis
Utilization of Sparsity Awareness in the Simplex Algorithm
Thomas Leichtle (Supervisor: Henning Zörlein)

Monday, June 2, 2014, 4:00 pm
Uni West, Room 43.2.101

The principle of Compressed Sensing can be described as the problem of finding the sparsest solution to an underdetermined linear system of equations. In order to solve this generally intractable problem, several approaches have been proposed in the past. The well-known Basis Pursuit approach applies a convex $\ell_1$-relaxation and transforms the underdetermined system of equations into a so called linear program. These special optimization problems can be solved efficiently by several algorithms, e.g. by the Simplex algorithm. However, due to the necessary convex relaxation, the found solution is not necessarily always the sparsest. Sparse solutions occur at so called degenerated corners in the Simplex algorithm.
The objective of this thesis is to implement the Simplex algorithm and to investigate the possibility of utilizing degenerated corners as indicator for sparse solutions. The resulting sparsity aware Simplex algorithm should obtain the desired sparse solution more often than the conventional convex relaxation approach. Within this thesis, it should be investigated by numerical evaluations to which extend the sparsity awareness can be utilized and at which computational costs.