Institute for Analysis and Algebra Research Group Optimization DFG

SPEAR  –   Sparse Exact and Approximate Recovery


This research project deals with the problem to recover a sparse solution of an underdetermined linear (equality) system. This topic has many applications and is a very active research area. It is located at the border between analysis and combinatorial optimization. The main goal of our project is to obtain a better understanding of the conditions under which (efficiently) finding such a sparse solution, i.e., recovery, is possible. Our project is characterized by both theoretical and computational aspects as well as the interplay of continuous and discrete methods.

The SPEAR project is a collaboration of the Research Group Optimization (RGO) at the TU Darmstadt and the Institute for Analysis and Algebra (IAA) at the TU Braunschweig. The project is funded by a DFG research grant. Project period: 2011 – 2014.
Project members:
Publications
Papers:
  • An Infeasible-Point Subgradient Method Using Adaptive Approximate Projections
    Dirk A. Lorenz, Marc E. Pfetsch, and Andreas M. Tillmann.
    Computational Optimization and Applications 57(2), 2014, pp. 271–306,
    DOI 10.1007/s10589-013-9602-3
  • Constructing test instances for Basis Pursuit Denoising
    Dirk A. Lorenz.
    IEEE Transactions on Signal Processing 61(5), 2013, pp. 1210–1214.
    DOI 10.1109/TSP.2012.2236322
    Code to reproduce the figures is here.
  • Solving Basis Pursuit: Heuristic Optimality Check and Solver Comparison
    Dirk A. Lorenz, Marc E. Pfetsch, and Andreas M. Tillmann.
    To appear in ACM Transactions on Mathematical Software, 2014.
    Optimization Online E-Print ID 2011-07-3100
    A detailed table of numerical results can be found here. A list of the test set instances is here. Code to produce figures and tables, and result data files are here; see also this HOC Demo (cf. Fig. 10).
  • The Computational Complexity of the Restricted Isometry Property, the Nullspace Property, and Related Concepts in Compressed Sensing
    Marc E. Pfetsch and Andreas M. Tillmann.
    IEEE Transactions on Information Theory 60(2), 2014, pp. 1248–1259,
    DOI 10.1109/TIT.2013.2290112
    Preprint: arXiv:1205.2081. A preliminary version achieved the Best Student Paper Award at SPARS'13.
  • Visualization of Astronomical Nebulae via Distributed Multi-GPU Compressed Sensing Tomography
    Stephan Wenger, Marco Ament, Stefan Guthe, Dirk A. Lorenz, Andreas M. Tillmann, Daniel Weiskopf, and Marcus Magnor.
    IEEE Transactions on Visualization and Computer Graphics 18(12), 2012, pp. 2188–2197.
    DOI 10.1109/TVCG.2012.281
  • Projection Onto The Cosparse Set is NP-hard
    Andreas M. Tillmann, Rémi Gribonval, and Marc E. Pfetsch.
    Proceedings of ICASSP 2014, pp. 7148–7152. DOI 10.1109/ICASSP.2014.6854987
  • Computing and Analyzing Recoverable Supports for Sparse Reconstruction
    Christian Kruschel and Dirk A. Lorenz. Submitted. September 2013.
    arXiv:1309.2460
    Code to reproduce the figures is here.
 
Talks & Presentations:
  • Geometrical Insights To Sparse Recovery via Minimally Redundant Matrices
    Christian Kruschel. AIP 13 (Advances in Mathematical Image Processing), 09/30 - 02/10/2013 @ Annweiler, Germany.
  • The Computational Complexity of Spark, RIP, and NSP
    Andreas M. Tillmann. SPARS 13 (Signal Processing with Adaptive Sparse Structured Representations), 07/08 - 07/11/2013 @ Lausanne, Switzerland. Best Student Paper Award
    The slides can be found here.
  • Heuristic Optimality Check and Computational Solver Comparison for Basis Pursuit
    Andreas M. Tillmann. ISMP 2012 (21st International Symposium on Mathematical Programming), 08/19 - 08/24/2012 @ Berlin, Germany.
    The slides can be found here.
  • Solving Basis Pursuit
    Andreas M. Tillmann. SIAM LA12 (SIAM Conference on Applied Linear Algebra), 06/18 - 06/22/2012 @ Valencia, Spain.
    The slides can be found here.
  • Constructing Test Instances With Prescribed Properties for Sparsity Problems
    Christian Kruschel. SIAM LA12 (SIAM Conference on Applied Linear Algebra), 06/18 - 06/22/2012 @ Valencia, Spain.
  • Branch & Cut for L0-Minimization
    Andreas M. Tillmann. Matheon Workshop (Sparse Representation of Functions: Analytic and Computational Aspects), 12/10 - 12/14/2012 @ Berlin, Germany.
    The slides can be found here.
  • Constructing Test Instances for Sparse Recovery Algorithms
    Christian Kruschel. SIAM IS12 (SIAM Conference on Imaging Science), 05/20 - 05/22/2012 @ Philadelphia, PA, USA.
    The slides can be found here.
  • Basis pursuit denoising: Exact test instances and exact recovery for ill-posed problems
    Dirk A. Lorenz. Dagstuhl Workshop on Sparse Representations and Efficient Sensing of Data, 01/30 - 02/04/2011 @ Schloss Dagstuhl, Germany.
    The slides can be found here.
  • An Infeasible-Point Subgradient Method and Computational Comparison for l1-Minimization
    Andreas M. Tillmann. CSSIP10 (Workshop on Compressed Sensing, Sparsity and Inverse Problems), 09/06 - 09/07/2010 @ TU Braunschweig, Germany.
  • An Infeasible-Point Subgradient Method Using Approximate Projections
    Andreas M. Tillmann. SIAM OP11 (SIAM Conference on Optimization), 05/16 - 05/19/2011 @ Darmstadtium, Darmstadt, Germany.
    The poster can be found here.
  • An Infeasible-Point Subgradient Algorithm and a Computational Solver Comparison for l1-Minimization
    Andreas M. Tillmann. SPARS 11 (Signal Processing with Adaptive Sparse Structured Representations), 06/27 - 06/30/2011 @ RCPE Edinburgh, UK.
    The poster can be found here.
Software
L1 Test Pack A Matlab package to generate test instances for L1-minimization problems
(Version 1.2 of 04/12/2012).
find_sign_pattern A Matlab program that, given a matrix and sparsity level, computes a support and sign pattern such that any vector conforming to these is a unique Basis Pursuit solution.
HOC Suite A Matlab package containing code for Heuristic Optimality Checks (HOCs) for Basis Pursuit, Basis Pursuit Denoising, and L1-Regularized Least-Squares. HOC can improve speed and accuracy of existing solvers for these problems (see README file for details, and results in "Solving Basis Pursuit" paper along with this HOC Demo for BP).
(Version 1.0 of 09/30/2013).
ISAL1 A Matlab implementation of the Infeasible-Point Subgradient Algorithm for Basis Pursuit;
the latest version includes prototype code (ISAL1bpdn) for BP Denoising as well.
(Version 1.00 of 09/30/2013 — current release)
(The "Solving Basis Pursuit" paper used Version 0.91 of 10/08/2012).
L1-Testset (ascii) The testset we used in our L1-solver comparison as ascii-files, accompanied by Matlab routines for data handling.
(Size of zip-file: 313MB)
L1-Testset (mat) The testset we used in our L1-solver comparison as Matlab binary files.
(Size of zip-file: 1GB)
      Related Links:
      last update: 08/11/2014