Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
  • Treffer 19 von 63
Zurück zur Trefferliste

Exact and Approximate Sparse Solutions of Underdetermined Linear Equations

Zitieren Sie bitte immer diese URN: urn:nbn:de:0297-zib-9488
  • 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.

Volltext Dateien herunterladen

Metadaten exportieren

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar Statistik - Anzahl der Zugriffe auf das Dokument
Metadaten
Verfasserangaben:Sadegh Jokar, Marc PfetschORCiD
Dokumentart:ZIB-Report
Freies Schlagwort / Tag:basis pursuit; maximum feasible subsystem problem; orthogonal matching pursuit; sparse representations
MSC-Klassifikation:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C59 Approximation methods and heuristics
Datum der Erstveröffentlichung:06.03.2007
Schriftenreihe (Bandnummer):ZIB-Report (07-05)
ZIB-Reportnummer:07-05
Verlagspublikation:Appeared in: Applied Numerical Mathematics 60, No. 4 (2010), 452-472
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.