Eingang zum Volltext

Urheberrechtshinweis / Copyright notice

Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URL: http://opus.kobv.de/zib/volltexte/2007/948/

Jokar, Sadegh ; Pfetsch, Marc E.

Exact and Approximate Sparse Solutions of Underdetermined Linear Equations

pdf-Format:
Dokument 1.pdf (275 KB)
ps-Format:
Dokument 1.ps (967 KB)

Kurzfassung in Englisch

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.

Freie Schlagwörter (englisch): sparse representations , basis pursuit , orthogonal matching pursuit , maximum feasible subsystem problem
MSC - Klassifikation 90C59
MSC - Klassifikation 90C27
Abteilung: ZIB Allgemein
DDC-Sachgruppe: Allgemeines, Wissenschaft
Dokumentart: ZIB-Report
Schriftenreihe: ZIB-Report
Band Nummer: 07-05
Quelle: Appeared in: Applied Numerical Mathematics 60, No. 4 (2010), 452-472
Sprache: Englisch
Erstellungsjahr: 2007
Publikationsdatum: 06.03.2007
Bemerkung: printed version not available / keine gedruckte Version verfügbar

Metadatensuche | Volltextsuche | Browsen | Die neuesten Publikationen | Veröffentlichen
Fragen und Anregungen an bibliothek@zib.de