# 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

I am a PostDoc at the Visual Computing Institute and the Chair of Operations Research (see my homepage there) , and head the "Data" unit of the profile area CompSE (Computational Science and Engineering) of RWTH Aachen University. I received my doctoral degree from TU Darmstadt in December 2013, and was an interim/visiting professor of mathematical optimization at TU Braunschweig in winter 2014/15. I am one of the organizers of the Workshop on Optimization, Machine Learning and Data Science, taking place at TU Braunschweig April 12-13, 2018.

My research interests focus on theoretical and practical aspects of optimization and complexity theory in areas like compressed sensing, signal and image processing, machine learning, operations research, and (discrete) geometrical problems. I am affiliated with the project "EXPRESS – EXploiting structure in comPREssed Sensing using Side constraints" within the DFG priority program CoSIP ("Compressed Sensing in Information Processing", SPP 1798). I am also the principal investigator of the project "Efficient exact maximum-likelihood decoding and minimum-distance computation for binary linear codes" funded by the RWTH ERS StartUp/DFG Excellence Initiative.

You can also find me on Google Scholar and on Research Gate.

## Presentations

### Title

SPARS 2019    Poster    Structured Discrete Shape Approximation
SPARS 2019    Poster    Exact Recovery of Partially Sparse Signals
EURO 2019    Invited Talk    Airplane Boarding: Complexity, Approximation and Exact Solution
ISMP 2018    Invited Talk    Spark-MIP: Mixed-Integer Programming for the (Vector) Matroid Girth Problem
SPARS 2017    Talk    Computing the Spark of a Matrix
SPARS 2017    Poster    L1-HOUDINI: A New Homotopy Method for L1-Minimization
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

## Structured Discrete Shape Approximation: Theoretical Complexity and Practical Algorithm

Andreas Tillmann, Leif Kobbelt
preprint, submitted for publication

We consider the problem of approximating a two-dimensional shape contour (or curve segment) using discrete assembly systems, which allow to build geometric structures based on limited sets of node and edge types subject to edge length and orientation restrictions. We show that already deciding feasibility of such approximation problems is NP-hard, and remains intractable even for very simple setups. We then devise an algorithmic framework that combines shape sampling with exact cardinality-minimization to obtain good approximations using few components. As a particular application and showcase example, we discuss approximating shape contours using the classical Zometool construction kit and provide promising computational results, demonstrating that our algorithm is capable of obtaining good shape representations within reasonable time, in spite of the problem's general intractability. We conclude the paper with an outlook on possible extensions of the developed methodology, in particular regarding 3D shape approximation tasks.

Code available per request.

## Computing the Spark: Mixed-Integer Programming for the (Vector) Matroid Girth Problem

Andreas Tillmann
Computational Optimization and Applications

We investigate the NP-hard problem of computing the spark of a matrix (i.e., the smallest number of linearly dependent columns), a key parameter in compressed sensing and sparse signal recovery. To that end, we identify polynomially solvable special cases, gather upper and lower bounding procedures, and propose several exact (mixed-)integer programming models and linear programming heuristics. In particular, we develop a branch-and-cut scheme to determine the girth of a matroid, focussing on the vector matroid case, for which the girth is precisely the spark of the representation matrix. Extensive numerical experiments demonstrate the effectiveness of our specialized algorithms compared to general-purpose black-box solvers applied to several mixed-integer programming models.

Code and test instances available per request; will become directly available on this page in the near future.
» Show BibTeX

@article{Tillmann2019,
author = {Andreas M. Tillmann},
title = {{Computing the Spark: Mixed-Integer Programming\\for the (Vector) Matroid Girth Problem}},
journal = {{Computational Optimization and Applications}},
volume = {to appear},
year = {2019}
}

## Joint Antenna Selection and Phase-Only Beam Using Mixed-Integer Nonlinear Programming

Tobias Fischer, Ganapati Hegde, Frederic Matter, Marius Pesavento, Marc Pfetsch, Andreas Tillmann
Proc. WSA (ITG Workshop on Smart Antennas) 2018

In this paper, we consider the problem of joint antenna selection and analog beamformer design in a downlink single-group multicast network. Our objective is to reduce the hardware requirement by minimizing the number of required phase shifters at the transmitter while fulfilling given quality of constraints. We formulate the problem as an L0 minimization problem and devise a novel branch-and-cut based algorithm to solve the formulated mixed-integer nonlinear program optimally. We also propose a suboptimal heuristic algorithm to solve the above problem with a low computational complexity. Furthermore, the performance of the suboptimal method is evaluated against the developed optimal method, which serves as a benchmark.

» Show BibTeX

@inproceedings{FischerHedgeMatterPesaventoPfetschTillmann2018,
author = {T. Fischer and G. Hedge and F. Matter and M. Pesavento and M. E. Pfetsch and A. M. Tillmann},
title = {{Joint Antenna Selection and Phase-Only Beam Using Mixed-Integer Nonlinear Programming}},
booktitle = {{Proc. WSA 2018}},
pages = {},
year = {2018},
note = {to appear}
}

## A Primal-Dual Homotopy Algorithm for L1-Minimization with L-infinity-Constraints

Christoph Brauer, Dirk Lorenz, Andreas Tillmann
Computational Optimization and Applications

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

@article{BrauerLorenzTillmann2018,
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}},
journal = {{Computational Optimization and Applications}},
volume = {70},
number = {2},
pages = {443--478},
note = {DOI:10.1007/s10589-018-9983-4},
year = {2018}
}

## Sparse Recovery with Integrality Constraints

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}
}

## DOLPHIn -- Dictionary Learning for Phase Retrieval

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}
}

## Dictionary Learning from Phaseless Measurements

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}
}

## Equivalence of Linear Programming and Basis Pursuit

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}
}

## On the Computational Intractability of Exact and Approximate Dictionary Learning,

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}
}

## Solving Basis Pursuit: Heuristic Optimality Check and Solver Comparison

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}
}

## Projection Onto The Cosparse Set is NP-Hard

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},
journal = {{Computational Optimization and Applications}},
volume = {57},
number = {2},
pages = {271--306},
year = {2014},
note = {DOI: 10.1007/s10589-013-9602-3}
}

## The Computational Complexity of the Restricted Isometry Property, the Nullspace Property, and Related Concepts in Compressed Sensing

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}
}

## Computational Aspects of Compressed Sensing

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},
year = {2013}
}

## Visualization of Astronomical Nebulae via Distributed Multi-GPU Compressed Sensing Tomography

Stephan Wenger, Marco Ament, Stefan Guthe, Dirk Lorenz, Andreas Tillmann, Daniel Weiskopf, Marcus Magnor
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}
}