Profile

Dr. Andreas Tillmann
Room 108
Phone: +49 241 8021806
Fax: +49 241 8022899
Email: andreas.tillmann@cs.rwth-aachen.de
Office hours: by appointment

--more info coming soon--



Presentations

Event
Type
Title
The Aussois C.O.W. 2017   Talk   Sparse Signal Reconstruction with Integrality Constraints
DWCAA 2016   Invited Talk   Exploiting hidden sparsity for image reconstruction from nonlinear measurements
Data Science meets Optimization 2016   Invited Talk   New Applications of Sparsity-Based Learning
ICASSP 2016   Poster   Dictionary Learning from Phaseless Measurements
CSA 2015   Poster   Dictionary Learning for Phase Retrieval
ISMP 2015   Invited Talk    Branch & Cut Methods for Exact Sparse Recovery
SPARS 2015   Poster   Heuristic Optimality Checks for Noise-Aware Sparse Recovery by L1-Minimization
GAMM 2015   Invited Talk   Computational Aspects of Sparse Recovery
Sparse Tomographic Reconstruction 2015   Invited Talk   Computational Aspects of Sparse Recovery
ICASSP 2014   Poster   Projection onto the Cosparse Set is NP-hard
SPARS 2013   Poster   Projection onto the k-Cosparse Set is NP-hard
SPARS 2013   Talk   The Computational Complexity of Spark, RIP, and NSP (Highlight Talk)
MATHEON-W. Sparse Representation [...] 2012   Invited Talk   Branch & Cut for L0-Minimization
ISMP 2012   Invited Talk   Heuristic Optimality Check and Computational Solver Comparison for Basis Pursuit
SIAM Conf. on Applied Linear Algebra 2012   Invited Talk   Solving Basis Pursuit
SPARS 2011   Poster   An Infeasible-Point Subgradient Algorithm and a Computational Solver Comparison for l1-Minimization
SIAM Conf. on Optimization 2011   Poster   An Infeasible-Point Subgradient Method Using Approximate Projections
CSSIP 2010   Talk   An Infeasible-Point Subgradient Method and Computational Comparison for L1-Minimization


Publications


Christoph Brauer, Dirk Lorenz, Andreas Tillmann
(submitted)

In this paper we propose a primal-dual homotopy method for L1-minimization problems with infinity norm constraints in the context of sparse reconstruction. The natural homotopy parameter is the value of the bound for the constraints and we show that there exists a piecewise linear solution path with finitely many break points for the primal problem and a respective piecewise constant path for the dual problem. We show that by solving a small linear program, one can jump to the next primal break point and then, solving another small linear program, a new optimal dual solution is calculated which enables the next such jump in the subsequent iteration. Using a theorem of the alternative, we show that the method never gets stuck and indeed calculates the whole path in a finite number of steps. Numerical experiments demonstrate the effectiveness of our algorithm. In many cases, our method significantly outperforms commercial LP solvers; this is possible since our approach employs a sequence of considerably simpler auxiliary linear programs that can be solved efficiently with specialized active-set strategies.



Matlab-Code and test instances for our method can be found below.
» Show BibTeX
@misc{BrauerLorenzTillmann2016, author = {C. Brauer and D. A. Lorenz and A. M. Tillmann}, title = {{A Primal-Dual Homotopy Algorithm for $\ell_1$-Minimization with $\ell_\infty$-Constraints}}, howpublished = {arXiv:1610.10022 [math.OC]}, month = {October}, year = {2016} }





Jan-Hendrik Lange, Marc Pfetsch, Bianca Seib, Andreas Tillmann
(submitted)

In this paper, we investigate conditions for the unique recoverability of sparse integer-valued signals from few linear measurements. Both the objective of minimizing the number of nonzero components, the so-called L0-norm, as well as its popular substitute, the L1-norm, are covered. Furthermore, integer constraints and possible bounds on the variables are investigated. Our results show that the additional prior knowledge of signal integrality allows for recovering more signals than what can be guaranteed by the established recovery conditions from (continuous) compressed sensing. Moreover, even though the considered problems are NP-hard in general (even with an L1-objective), we investigate testing the L0-recovery conditions via some numerical experiments; it turns out that the corresponding problems are quite hard to solve in practice. However, medium-sized instances of L0- and L1-minimization with binary variables can be solved exactly within reasonable time.

» Show BibTeX
@misc{LangePfetschSeibTillmann2016, author = {J.-H. Lange and M. E. Pfetsch and B. M. Seib and A. M. Tillmann}, title = {{Sparse Recovery with Integrality Constraints}}, howpublished = {arXiv:1608.08678 [cs.IT]}, month = {August}, year = {2016} }





Andreas Tillmann, Yonina Eldar, Julien Mairal
IEEE Transactions on Signal Processing

We propose a new algorithm to learn a dictionary for reconstructing and sparsely encoding signals from measurements without phase. Specifically, we consider the task of estimating a two-dimensional image from squared-magnitude measurements of a complex-valued linear transformation of the original image. Several recent phase retrieval algorithms exploit underlying sparsity of the unknown signal in order to improve recovery performance. In this work, we consider such a sparse signal prior in the context of phase retrieval, when the sparsifying dictionary is not known in advance. Our algorithm jointly reconstructs the unknown signal-possibly corrupted by noise-and learns a dictionary such that each patch of the estimated image can be sparsely represented. Numerical experiments demonstrate that our approach can obtain significantly better reconstructions for phase retrieval problems with noise than methods that cannot exploit such “hidden” sparsity. Moreover, on the theoretical side, we provide a convergence result for our method.



Accompanying software to be found below:
  • DOLPHIn - Matlab implementation of the dictionary learning method for 2D noisy (sparse) phase retrieval. (Version 1.10 of 07/25/2016; requires SPAMS package obtainable from http://spams-devel.gforge.inria.fr/)
Moreover, below you can also find
  • the test images from the paper
  • a document with lots of result tables of supplementary numerical experiments
» Show BibTeX
@article{TillmannEldarMairal2016b, author = {A. M. Tillmann and Y. C. Eldar and J. Mairal}, title = {{DOLPHIn -- Dictionary Learning for Phase Retrieval}}, journal = {{IEEE Transactions on Signal Processing}}, volume = {64}, number = {24}, pages = {6485--6500}, year = {2016}, note = {DOI: 10.1109/TSP.2016.2607180} }





Andreas Tillmann, Yonina Eldar, Julien Mairal
International Conference on Acoustics, Speech and Signal Processing (ICASSP)

We propose a new algorithm to learn a dictionary along with sparse representations from signal measurements without phase. Specifically, we consider the task of reconstructing a two-dimensional image from squared-magnitude measurements of a complex-valued linear transformation of the original image. Several recent phase retrieval algorithms exploit underlying sparsity of the unknown signal in order to improve recovery performance. In this work, we consider sparse phase retrieval when the sparsifying dictionary is not known in advance, and we learn a dictionary such that each patch of the reconstructed image can be sparsely represented. Our numerical experiments demonstrate that our proposed scheme can obtain significantly better reconstructions for noisy phase retrieval problems than methods that cannot exploit such "hidden" sparsity.

» Show BibTeX
@inproceedings{TillmannEldarMairal2016a, author = {A. M. Tillmann and Y. C. Eldar and J. Mairal}, title = {{Dictionary Learning from Phaseless Measurements}}, booktitle = {{Proc. ICASSP 2016}}, pages = {4702--4706}, year = {2016}, note = {DOI: 10.1109/ICASSP.2016.7472569} }





Andreas Tillmann
GAMM 86th Annual Scientific Conference

In this note, we show that linear programming and the prominent Basis Pursuit problem (i.e., minimizing the L1-norm of a vector x subject to an underdetermined linear equation system Ax = b) are theoretically equivalent, and briefly discuss possible ramifications regarding computational complexity and practical applicability.

» Show BibTeX
@inproceedings{Tillmann2015, author = {A. M. Tillmann}, title = {{Equivalence of Linear Programming and Basis Pursuit}}, booktitle = {{PAMM (Proceedings in Applied Mathematics and Mechanics}}, volume = {15}, number = {1}, pages = {735--738}, year = {2015}, note = {DOI: 10.1002/PAMM.201510351} }





Andreas Tillmann
IEEE Signal Processing Letters

The efficient sparse coding and reconstruction of signal vectors via linear observations has received a tremendous amount of attention over the last decade. In this context, the automated learning of a suitable basis or overcomplete dictionary from training data sets of certain signal classes for use in sparse representations has turned out to be of particular importance regarding practical signal processing applications. Most popular dictionary learning algorithms involve NP-hard sparse recovery problems in each iteration, which may give some indication about the complexity of dictionary learning but does not constitute an actual proof of computational intractability. In this technical note, we show that learning a dictionary with which a given set of training signals can be represented as sparsely as possible is indeed NP-hard. Moreover, we also establish hardness of approximating the solution to within large factors of the optimal sparsity level. Furthermore, we give NP-hardness and non-approximability results for a recent dictionary learning variation called the sensor permutation problem. Along the way, we also obtain a new non-approximability result for the classical sparse recovery problem from compressed sensing.

» Show BibTeX
@article{Tillmann2015, author = {A. M. Tillmann}, title = {{On the Computational Intractability of Exact and Approximate Dictionary Learning}}, journal = {{IEEE Signal Processing Letters}}, volume = {22}, number = {1}, pages = {45--49}, year = {2015}, note = {DOI: 10.1109/LSP.2014.2345761} }





Dirk Lorenz, Marc Pfetsch, Andreas Tillmann
ACM Transactions on Mathematical Software

The problem of finding a minimum L1-norm solution to an underdetermined linear system is an important problem in compressed sensing, where it is also known as basis pursuit. We propose a heuristic optimality check as a general tool for L1-minimization, which often allows for early termination by “guessing” a primal-dual optimal pair based on an approximate support. Moreover, we provide an extensive numerical comparison of various state-of-the-art L1-solvers that have been proposed during the last decade, on a large test set with a variety of explicitly given matrices and several right-hand sides per matrix reflecting different levels of solution difficulty. The results, as well as improvements by the proposed heuristic optimality check, are analyzed in detail to provide an answer to the question which algorithm is the best.



Accompanying software to be found below:
  • HOC-Suite - 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 the paper, along with the HOC Demo for BP). (Version 1.0 of 09/30/2013).
  • ISAL1 - Matlab implementation of the Infeasible-Point Subgradient Algorithm for Basis Pursuit; also includes prototype code (ISAL1bpdn) for BP Denoising. (Version 1.00 of 09/30/2013 – current release; the paper used Version 0.91 of 10/08/2012).
  • L1-Testset - The testset we used for our L1-solver comparison as ascii- or Matlab binary files, accompanied by Matlab routines for data handling. (Size of zip-files: 313MB (ascii), 1GB (mat))
Moreover, an overview of updated computational results (as of April 2016) is also available below.
» Show BibTeX
@article{LorenzPfetschTillmann2015, author = {D. A. Lorenz and M. E. Pfetsch and A. M. Tillmann}, title = {{Solving Basis Pursuit: Heuristic Optimality Check and Solver Comparison}}, journal = {{ACM Transactions on Mathematical Software}}, volume = {41}, number = {2}, pages = {Art. No. 8}, year = {2015}, note = {DOI: 10.1145/2689662} }





Andreas Tillmann, Rémi Gribonval, Marc Pfetsch
International Conference on Acoustics, Speech and Signal Processing (ICASSP)

The computational complexity of a problem arising in the context of sparse optimization is considered, namely, the projection onto the set of k-cosparse vectors w.r.t. some given matrix M. It is shown that this projection problem is (strongly) NP-hard, even in the special cases in which the matrix M contains only ternary or bipolar coefficients. Interestingly, this is in contrast to the projection onto the set of k-sparse vectors, which is trivially solved by keeping only the k largest coefficients.

» Show BibTeX
@inproceedings{TillmannGribonvalPfetsch2014, author = {A. M. Tillmann and R. Gribonval and M. E. Pfetsch}, title = {{Projection Onto The Cosparse Set is NP-Hard}}, booktitle = {{Proc. ICASSP 2014}}, pages = {7148--7152}, year = {2014}, note = {DOI: 10.1109/ICASSP.2014.6854987} }





Dirk Lorenz, Marc Pfetsch, Andreas Tillmann
Computational Optimization and Applications

We propose a new subgradient method for the minimization of nonsmooth convex functions over a convex set. To speed up computations we use adaptive approximate projections only requiring to move within a certain distance of the exact projections (which decreases in the course of the algorithm). In particular, the iterates in our method can be infeasible throughout the whole procedure. Nevertheless, we provide conditions which ensure convergence to an optimal feasible point under suitable assumptions. One convergence result deals with step size sequences that are fixed a priori. Two other results handle dynamic Polyak-type step sizes depending on a lower or upper estimate of the optimal objective function value, respectively. Additionally, we briefly sketch two applications: Optimization with convex chance constraints, and finding the minimum L1-norm solution to an underdetermined linear system, an important problem in Compressed Sensing.

» Show BibTeX
@article{LorenzPfetschTillmann2014, author = {D. A. Lorenz and M. E. Pfetsch and A. M. Tillmann}, title = {{An infeasible-point subgradient method using adaptive approximate projections}}, journal = {{Computational Optimization and Applications}}, volume = {57}, number = {2}, pages = {271--306}, year = {2014}, note = {DOI: 10.1007/s10589-013-9602-3} }





Andreas Tillmann, Marc Pfetsch
IEEE Transactions on Information Theory

This paper deals with the computational complexity of conditions which guarantee that the NP-hard problem of finding the sparsest solution to an underdetermined linear system can be solved by efficient algorithms. In the literature, several such conditions have been introduced. The most well-known ones are the mutual coherence, the restricted isometry property (RIP), and the nullspace property (NSP). While evaluating the mutual coherence of a given matrix is easy, it has been suspected for some time that evaluating RIP and NSP is computationally intractable in general. We confirm these conjectures by showing that for a given matrix A and positive integer k, computing the best constants for which the RIP or NSP hold is, in general, NP-hard. These results are based on the fact that determining the spark of a matrix is NP-hard, which is also established in this paper. Furthermore, we also give several complexity statements about problems related to the above concepts.



A preliminary version of this work won the Best Student Paper Award at SPARS'13.
» Show BibTeX
@article{TillmannPfetsch2014, author = {A. M. Tillmann and M. E. Pfetsch}, title = {{The Computational Complexity of the Restricted Isometry Property, the Nullspace Property, and Related Concepts in Compressed Sensing}}, journal = {{IEEE Transactions on Information Theory}}, volume = {60}, number = {2}, pages = {1248--1259}, year = {2014}, note = {DOI: 10.1109/TIT.2013.2290112} }





Andreas Tillmann
Doctoral Dissertation

A central task in the novel field of Compressed Sensing is sparse recovery, i.e., finding the sparsest exact or approximate solution to an underdetermined linear equation system. Over the past decade, several conditions have been identified under which this generally intractable problem can be solved efficiently.

In this thesis, we investigate the computational complexity of ubiquitous sparse recovery conditions based on the spark, the restricted isometry property and the nullspace property of the sensing matrix. Furthermore, we provide an extensive numerical comparison of various state-of-the-art solvers for the most popular sparse recovery approach, the Basis Pursuit (L1-norm minimization) model, and demonstrate how a novel heuristic optimality check can significantly improve both speed and accuracy of most solvers. In addition, we introduce a new subgradient algorithm involving adaptive approximate projections for general nonsmooth convex constrained optimization and discuss its application to Basis Pursuit and variants.

» Show BibTeX
@misc{Tillmann2013, author = {A. M. Tillmann}, title = {{Computational Aspects of Compressed Sensing}}, howpublished = {Doctoral Dissertation}, school = {TU Darmstadt, Germany}, year = {2013} }





Stephan Wenger, Marco Ament, Stefan Guthe, Dirk Lorenz, Andreas Tillmann, Daniel Weiskopf, Marcus Magnot
IEEE Transactions on Visualization and Computer Graphics

The 3D visualization of astronomical nebulae is a challenging problem since only a single 2D projection is observable from our fixed vantage point on Earth. We attempt to generate plausible and realistic looking volumetric visualizations via a tomographic approach that exploits the spherical or axial symmetry prevalent in some relevant types of nebulae. Different types of symmetry can be implemented by using different randomized distributions of virtual cameras. Our approach is based on an iterative compressed sensing reconstruction algorithm that we extend with support for position-dependent volumetric regularization and linear equality constraints. We present a distributed multi-GPU implementation that is capable of reconstructing high-resolution datasets from arbitrary projections. Its robustness and scalability are demonstrated for astronomical imagery from the Hubble Space Telescope. The resulting volumetric data is visualized using direct volume rendering. Compared to previous approaches, our method preserves a much higher amount of detail and visual variety in the 3D visualization, especially for objects with only approximate symmetry.

» Show BibTeX
@article{WengerAmentGutheLorenzTillmannWeiskopfMagnor2012, author = {S. Wenger and M. Ament and S. Guthe and D. A. Lorenz and A. M. Tillmann and D. Weiskopf and M. Magnor}, title = {{Visualization of Astronomical Nebulae via Distributed Multi-GPU Compressed Sensing Tomography}}, journal = {{IEEE Transactions on Visualization and Computer Graphics}}, volume = {18}, number = {12}, pages = {2188--2197}, year = {2012}, note = {DOI: 10.1109/TVCG.2012.281} }




Disclaimer Home Visual Computing institute RWTH Aachen University