TY - GEN A1 - Jokar, Sadegh A1 - Pfetsch, Marc T1 - Exact and Approximate Sparse Solutions of Underdetermined Linear Equations N2 - In this paper, we empirically investigate the NP-hard problem of finding sparse solutions to linear equation systems, i.e., solutions with as few nonzeros as possible. This problem has received considerable interest in the sparse approximation and signal processing literature, recently. We use a branch-and-cut approach via the maximum feasible subsystem problem to compute optimal solutions for small instances and investigate the uniqueness of the optimal solutions. We furthermore discuss five (modifications of) heuristics for this problem that appear in different parts of the literature. For small instances, the exact optimal solutions allow us to evaluate the quality of the heuristics, while for larger instances we compare their relative performance. One outcome is that the basis pursuit heuristic performs worse, compared to the other methods. Among the best heuristics are a method due to Mangasarian and a bilinear approach. T3 - ZIB-Report - 07-05 KW - sparse representations KW - basis pursuit KW - orthogonal matching pursuit KW - maximum feasible subsystem problem Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9488 ER - TY - GEN A1 - Pfetsch, Marc T1 - A Branch-And-Cut for the Maximum Feasible Subsystem Problem N2 - We present a branch-and-cut algorithm for the NP-hard maximum feasible subsystem problem: For a given infeasible linear inequality system, determine a feasible subsystem containing as many inequalities as possible. The complementary problem, where one has to remove as few inequalities as possible in order to render the system feasible, can be formulated as a set covering problem. The rows of this formulation correspond to irreducible infeasible subsystems, which can be exponentially many. The main issue of a branch-and-cut algorithm for MaxFS is to efficiently find such infeasible subsystems. We present three heuristics for the corresponding NP-hard separation problem and discuss further cutting planes. This paper contains an extensive computational study of our implementation on a variety of instances arising in a number of applications. T3 - ZIB-Report - 05-46 KW - infeasible linear inequality system KW - irreducible infeasible subsystem KW - (IIS) maximum feasible subsystem problem KW - minimum IIS-cover KW - branch-and-cut Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8797 ER -