Servicenavigation

Detailseite

Zurück

Projekt Druckansicht

Sparse Exact and Approximate Recovery

Fachliche Zuordnung Mathematik
Förderung Förderung von 2010 bis 2015
Projektkennung Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 189141722
 
Erstellungsjahr 2014

Zusammenfassung der Projektergebnisse

The fundamental discovery that led to the tremendous research on sparse recovery over the past decade is that the NP-hard problem (1) can be solved efficiently under certain conditions. Thus, sparse recovery conditions under which (1) can be solved “efficiently”—i.e., by practical polynomial-time methods—are of huge importance to obtain exact or approximate sparse solutions in practice. While several such conditions are known, those that are easy to check (e.g., based on the notions of mutual coherence or the exact recovery condition) are often unsatisfactory w.r.t. the sparsity levels (i.e., the requirements are too strict) or can only be used for post-validation of a solution (i.e., not to provide a priori guarantees of successful sparse recovery). The more powerful sparse recovery conditions are based on the spark, restricted isometry property (RIP) or nullspace property (NSP). For all of these concepts, we showed that they are NP-hard to evaluate themselves; in case of the RIP, even in the strong sense. While this had been suspected for quite some time, proofs were missing until our work. The importance of the results was recognized by the “Best Student Paper” award at a major Compressed Sensing gathering, SPARS’13. The most popular approach to obtain sparse solutions is Basis Pursuit (2) (and its denoising variants). For this model, the strongest recovery guarantees are known, and a large number of different solution methods had been proposed over the last years. We contribute two further solution methods, ISAL1 from the important general class of projected subgradient methods (that we generalized to the ISA framework using adaptive approximate projections), and the sparse Kaczmarz method that utilizes Bregman projections, which both had not been considered for (2) before. Moreover, we devised an extensive numerical comparison, including the proposal of a large set of publicly available test problems, of various state-of-the-art 1-solvers with the aim of finding out if one of the many algorithms is superior. Our results indicate that some popular algorithms are overrated (there are better ones). Moreover, our solver ISAL1 is competitive in general. Furthermore, our heuristic optimality check (HOC) could improve the performance both in terms of solution accuracy and speed for many 1-solvers in the sparse recovery regime. The computational comparison can help selecting an algorithm, the testset allows for obtaining results with new methods that are directly comparable (to those of others), and our various tools for test instance construction should be useful to other researchers to create their own test problems with desired properties. Nevertheless, and not surprisingly, there are many open questions left. While the understanding of the basic properties have reached a mature level during the course of the project (and we think that we have contributed here), many variants and solution methods are still to be investigated. Indeed, compressed sensing still is a very active and interesting research area and is likely to remain so for the future.

Projektbezogene Publikationen (Auswahl)

 
 

Zusatzinformationen

© 2024 DFG Kontakt / Impressum / Datenschutz

Textvergrößerung und Kontrastanpassung