Profile

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.

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.

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.

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.

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.

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.

• 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/)

• the test images from the paper
• a document with lots of result tables of supplementary numerical experiments

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.

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.

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.

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.

• 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))

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.

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.

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

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.