Sparse Exact and Approximate Recovery
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)
- Visualization of astronomical nebulae via distributed multi-GPU compressed sensing tomography. IEEE Transactions on Visualization and Computer Graphics, 18(12):2188–2197, 2012
Stephan Wenger, Marco Ament, Stefan Guthe, Dirk A. Lorenz, Andreas M. Tillmann, Daniel Weiskopf, and Marcus Magnor
(Siehe online unter https://doi.org/10.1109/TVCG.2012.281) - Computational Aspects of Compressed Sensing. Doctoral dissertation, TU Darmstadt, September 2013. Date of Thesis Defense: December 16, 2013. PDF Server RWTH Aachen, XIX, 230 S.
Andreas M. Tillmann
- Computing and analyzing recoverable supports for sparse reconstruction
Christian Kruschel and Dirk A. Lorenz
- Constructing test instances for basis pursuit denoising. IEEE Transactions on Signal Processing, 61(5):1210–1214, 2013
Dirk A. Lorenz
(Siehe online unter https://doi.org/10.1109/TSP.2012.2236322) - An infeasible-point subgradient method using adaptive approximate projections. Computational Optimization and Applications, 57(2):271–306, 2014
Dirk A. Lorenz, Marc E. Pfetsch, and Andreas M. Tillmann
(Siehe online unter https://doi.org/10.1007/s10589-013-9602-3) - Geometrical Interpretations and Algorithmic Verification of Exact Solutions in Compressed Sensing. Doctoral dissertation, TU Braunschweig, 2014
Christian Kruschel
- The computational complexity of the restricted isometry property, the nullspace property, and related concepts in compressed sensing. IEEE Transactions on Information Theory, 60(2):1248–1259, 2014
Andreas M. Tillmann and Marc E. Pfetsch
(Siehe online unter https://dx.doi.org/10.1109/TIT.2013.2290112) - The linearized Bregman method via split feasibility problems: Analysis and generalizations. SIAM Journal on Imaging Sciences, 2(7), 2014
Dirk A. Lorenz, Frank Schöpfer, and Stephan Wenger
(Siehe online unter https://dx.doi.org/10.1137/130936269) - Solving basis pursuit: Heuristic optimality check and solver comparison. ACM Transactions on Mathematical Software, Volume 41 Issue 2, January 2015, Article No. 8
Dirk A. Lorenz, Marc E. Pfetsch, and Andreas M. Tillmann
(Siehe online unter https://doi.org/10.1145/2689662)
