Marc
Pfetsch
Title:
Exact support minimum solutions to underdetermined linear
equations
Abstract:
This talk deals with the NP-hard problem to find solutions to
systems
of underdetermined linear equations that have the smallest number of
nonzeros. In the recent years this problem attracted considerable
interest in the signal processing literature, motivated by results
saying that under appropriate conditions on the system, such a support
minimum solution can be found efficiently by LP methods. We present an
empirical investigation of these results using a branch-and-cut
algorithm for the related maximum feasible subsystem problem. We
furthermore study the behavior of several heuristics for this problem.