Jokar, Sadegh; Pfetsch, Marc E. Exact and approximate sparse solutions of underdetermined linear equations. (English) Zbl 1188.90213 SIAM J. Sci. Comput. 31, No. 1, 23-44 (2008). Summary: We empirically investigate the NP-hard problem of finding sparsest solutions to linear equation systems, i.e., solutions with as few nonzeros as possible. This problem has recently received considerable interest in the sparse approximation and signal processing literature. 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 six (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 so-called basis pursuit heuristic performs worse, compared to the other methods. Among the best heuristics are a method due to Mangasarian and one due to Chinneck. Cited in 10 Documents MSC: 90C27 Combinatorial optimization 90C59 Approximation methods and heuristics in mathematical programming Keywords:sparse representations; basis pursuit; orthogonal matching pursuit; maximum feasible subsystem problem Software:SCIP PDFBibTeX XMLCite \textit{S. Jokar} and \textit{M. E. Pfetsch}, SIAM J. Sci. Comput. 31, No. 1, 23--44 (2008; Zbl 1188.90213) Full Text: DOI Link