Search

We investigate the optimization of multilayer perceptrons on symmetric data. We compare the strategy of constraining the architecture to be equivariant to that of using augmentation. We show that, under natural assumptions on the loss and non-linearities, the sets of equivariant stationary points are identical for the two strategies, and that the set of equivariant layers is invariant under the gradient flow for augmented models. Finally, we show that stationary points may be unstable for augmented training although they are stable for the equivariant models

We propose an adaptive refinement algorithm to solve total variation regularized measure optimization problems. The method iteratively constructs dyadic partitions of the unit cube based on i) the resolution of discretized dual problems and ii) on the detection of cells containing points that violate the dual constraints. The detection is based on upper-bounds on the dual certificate, in the spirit of branch-and-bound methods. The interest of this approach is that it avoids the use of heuristic approaches to find the maximizers of dual certificates. We prove the convergence of this approach under mild hypotheses and a linear convergence rate under additional non-degeneracy assumptions. These results are confirmed by simple numerical experiments.

Equivariance of linear neural network layers is well studied. In this work, we relax the equivariance condition to only be true in a projective sense. We propose a way to construct a projectively equivariant neural network through building a standard equivariant network where the linear group representations acting on each intermediate feature space are "multiplicatively modified lifts" of projective group representations. By theoretically studying the relation of projectively and linearly equivariant linear layers, we show that our approach is the most general possible when building a network out of linear layers. The theory is showcased in two simple experiments., v2: Significant rewrite. The title has been changed: "neural network" -> "network". More general description of projectively equivariant linear layers, with new proposed architectures, and a completely new accompanying experiment section, as a result

We characterize the class of image plane transformations which realize rigid camera motions and call these transformations `rigidity preserving'. In particular, 2D translations of pinhole images are not rigidity preserving. Hence, when using CNNs for 3D inference tasks, it can be beneficial to modify the inductive bias from equivariance towards translations to equivariance towards rigidity preserving transformations. We investigate how equivariance with respect to rigidity preserving transformations can be approximated in CNNs, and test our ideas on both 6D object pose estimation and visual localization. Experimentally, we improve on several competitive baselines., Comment: v2: Substantially revised version. Among other things, experiments with the PixLoc model added

The blind deconvolution problem amounts to reconstructing both a signal and a filter from the convolution of these two. It constitutes a prominent topic in mathematical and engineering literature. In this work, we analyze a sparse version of the problem: The filter $h\in \mathbb{R}^\mu$ is assumed to be $s$-sparse, and the signal $b \in \mathbb{R}^n$ is taken to be $\sigma$-sparse, both supports being unknown. We observe a convolution between the filter and a linear transformation of the signal. Motivated by practically important multi-user communication applications, we derive a recovery guarantee for the simultaneous demixing and deconvolution setting. We achieve efficient recovery by relaxing the problem to a hierarchical sparse recovery for which we can build on a flexible framework. At the same time, for this we pay the price of some sub-optimal guarantees compared to the number of free parameters of the problem. The signal model we consider is sufficiently general to capture many applications in a number of engineering fields. Despite their practical importance, we provide first rigorous performance guarantees for efficient and simple algorithms for the bi-sparse and generalized demixing setting. We complement our analytical results by presenting results of numerical simulations. We find evidence that the sub-optimal scaling $s^2\sigma \log(\mu)\log(n)$ of our derived sufficient condition is likely overly pessimistic and that the observed performance is better described by a scaling proportional to $ s\sigma$ up to log-factors., Comment: 6 pages, 5 figures

Compressed sensing is a paradigm within signal processing that provides the means for recovering structured signals from linear measurements in a highly efficient manner. Originally devised for the recovery of sparse signals, it has become clear that a similar methodology would also carry over to a wealth of other classes of structured signals. In this work, we provide an overview over the theory of compressed sensing for a particularly rich family of such signals, namely those of hierarchically structured signals. Examples of such signals are constituted by blocked vectors, with only few non-vanishing sparse blocks. We present recovery algorithms based on efficient hierarchical hard-thresholding. The algorithms are guaranteed to converge, in a stable fashion both with respect to measurement noise as well as to model mismatches, to the correct solution provided the measurement map acts isometrically restricted to the signal class. We then provide a series of results establishing the required condition for large classes of measurement ensembles. Building upon this machinery, we sketch practical applications of this framework in machine-type communications and quantum tomography., Comment: This book chapter is a report on findings within the DFG-funded priority program `Compressed Sensing in Information Processing' (CoSIP)

The problem of wideband massive MIMO channel estimation is considered. Targeting for low complexity algorithms as well as small training overhead, a compressive sensing (CS) approach is pursued. Unfortunately, due to the Kronecker-type sensing (measurement) matrix corresponding to this setup, application of standard CS algorithms and analysis methodology does not apply. By recognizing that the channel possesses a special structure, termed hierarchical sparsity, we propose an efficient algorithm that explicitly takes into account this property. In addition, by extending the standard CS analysis methodology to hierarchical sparse vectors, we provide a rigorous analysis of the algorithm performance in terms of estimation error as well as number of pilot subcarriers required to achieve it. Small training overhead, in turn, means higher number of supported users in a cell and potentially improved pilot decontamination. We believe, that this is the first paper that draws a rigorous connection between the hierarchical framework and Kronecker measurements. Numerical results verify the advantage of employing the proposed approach in this setting instead of standard CS algorithms., 8 pages, 5 figures

This thesis treats regularization techniques of inverse problems using TV- and atomic norms. In the first part of the thesis, the two concepts are connected, making a unified treatment in the rest of the thesis possible. Concretely, it is proven that for reasonable dictionaries, atomic norms can be calculated with the help of TV -minimization, and that the TV -norm can be considered as an atomic norm with respect to a special dictionary in a Hilbert space. The theory is formulated in an infinite-dimensional setting - finite dimensional examples are however also included as subcases. In the following chapter, a result on the structure of solutions of TV -regularized problems is proven. Formulated and proven in an abstract setting, it states that in most cases, there will exist sparse solutions of the TV -regularized problems. In the chapter thereafter, exact recovery guarantees are discussed. The main aim of that chapter is to provide a link between TV -minimization and atomic norm-minimization with respect to certain dictionaries in so-called reproducible Kernel Hilbert spaces. These results are then applied to produce recovery guarantees for measurement models not previously treated in the literature. In the chapter thereafter, the framework of soft recovery is developed. A method is presented to prove approximate support recovery guarantees. This is first formulated in a very general manner, and then applied to numerous examples. New results on the recoverability of large peaks in standard, finite dimensional dictionary sparse recovery is proven, as well as soft recovery guarantees for several different types of superresolution problems. In the final chapter, methods for numerical resolution of infinite dimensional TV-regularized problems are discussed. The main novel finding is a connection between grid discretization of the TV -regularized problem and linearization of the operator used to probe the signal., Diese Doktorarbeit behandelt Regularisierungstechniken für inverse Probleme, die TV- und atomische Normen verwenden. Im ersten Tail der Arbeit werden die beiden Konzepte verbunden, so dass eine einheitliche Behandlung in den weiteren Teilen der Arbeit möglich ist. Konkret wird bewiesen dass atomische Norme für vernünftige Dictionaries mittels TV-minimierung berechnet werden können, und dass die TV-Norm als eine atomische Norm bezüglich eines bestimmten Dictionary in einem Hilbertraum aufgefasst werden kann. Die Theorie wird in einem unendlichdimensionalen Rahmen formuliert, endlichdimensionale Beispiele sind allerdings auch als Spezialfälle inkludiert. Im darauffolgenden Kapitel wird ein Resultat zur Struktur von Lösungen von TV-regularisierte Probleme bewiesen. Das Resultat wird in einem abstrakten Rahmen formuliert und bewiesen, und sagt aus, dass es in den meisten Fällen dünn besetzte Lösungen existieren. Im Kapitel danach werden exakte Rekonstruktionsgarantien diskutiert. Das Hauptzeil dieses Kapitels ist es, eine Verbindung zwischen TV-Minimierung und atomische Norm-Minimierung bezüglich bestimmte Dictionaries in sogenannten Reproducing Kernel-Hilberträume herzustelen. Diese Resultate werden danach verwendet, um Rekonstruktionsgarantien zu erzeugen für Messmodelle, die bisher nicht betrachtet wurden. Im nächsten Kapitel wird das Konzept der sanften Rekonstruktion entwickelt. Es wird eine Methode vorgestellt, die verwendet werden kann, um approximative Trägerrekonstruktionsgarantien zu beweisen. Diese wird zunächst in einer sehr allgemeinen Form formuliert, und anschließend an mehreren Beispielen appliziert. Es werden sowohl eue Resultate zur Rekonstruktionsmöglichkeit von große Komponenten in endlichdimensionale Dictionary-dünn-besetzte Signale, als auch sanfte Rekonstruktionsgarantien für mehrere Arten von Superresolutionsprobleme bewiesen. Im letzten Kapitel werden Methode zur numerischen Lösung von unendlichdimensionale TV-regularisierte Probleme diskutiert. Das hauptsächliche neue Erkenntnis ist die Herstellung einer Verbindung zwischen Gitterdiskretizierung vom TV-regularisierten Problem und eine Linearisierung des Operators, die für die Messung der Signale verwendet wird.

In this paper we develop a general theory of compressed sensing for analog signals, in close similarity to prior results for vectors in finite dimensional spaces that are sparse in a given orthonormal basis. The signals are modeled by functions in a reproducing kernel Hilbert space. Sparsity is defined as the minimal number of terms in expansions based on the kernel functions. Minimizing this number is under certain conditions equivalent to minimizing an atomic norm, the pre-dual of the supremum norm for functions in the Hilbert space. The norm minimizer is shown to exist based on a compactness argument. Recovery based on minimizing the atomic norm is robust and stable, so it provides controllable accuracy for recovery when the signal is only approximately sparse and the measurement is corrupted by noise. As applications of the theory, we include results on the recovery of sparse bandlimited functions and functions that have a sparse inverse short-time Fourier transform.

The estimation of direction of arrivals with help of $TV$-minimization is studied. Contrary to prior work in this direction, which has only considered certain antenna placement designs, we consider general antenna geometries. Applying the soft-recovery framework, we are able to derive a theoretic guarantee for a certain direction of arrival to be approximately recovered. We discuss the impact of the recovery guarantee for a few concrete antenna designs. Additionally, numerical simulations supporting the findings of the theoretical part are performed.

We propose a scheme utilizing ideas from infinite dimensional compressed sensing for thermal source localization. Using the soft recovery framework of one of the authors, we provide rigorous theoretical guarantees for the recovery performance. In particular, we extend the framework in order to also include noisy measurements. Further, we conduct numerical experiments, showing that our proposed method has strong performance, in a wide range of settings. These include scenarios with few sensors, off-grid source positioning and high noise levels, both in one and two dimensions.

This paper describes a dual certificate condition on a linear measurement operator $A$ (defined on a Hilbert space $\mathcal{H}$ and having finite-dimensional range) which guarantees that an atomic norm minimization, in a certain sense, will be able to approximately recover a structured signal $v_0 \in \mathcal{H}$ from measurements $Av_0$. Put very streamlined, the condition implies that peaks in a sparse decomposition of $v_0$ are close the the support of the atomic decomposition of the solution $v^*$. The condition applies in a relatively general context - in particular, the space $\mathcal{H}$ can be infinite-dimensional. The abstract framework is applied to several concrete examples, one example being super-resolution. In this process, several novel results which are interesting on its own are obtained.

This article provides a new type of analysis of a compressed-sensing based technique for recovering column-sparse matrices, namely minimization of the $\ell_{1,2}$-norm. Rather than providing conditions on the measurement matrix which guarantees the solution of the program to be exactly equal to the ground truth signal (which already has been thoroughly investigated), it presents a condition which guarantees that the solution is approximately equal to the ground truth. Soft recovery statements of this kind are to the best knowledge of the author a novelty in Compressed Sensing. Apart from the theoretical analysis, we present two heuristic proposes how this property of the $\ell_{1,2}$-program can be utilized to design algorithms for recovery of matrices which are sparse and have low rank at the same time.

The suboptimal performance of wavelets with regard to the approximation of multivariate data gave rise to new representation systems, specifically designed for data with anisotropic features. Some prominent examples of these are given by ridgelets, curvelets, and shearlets, to name a few. The great variety of such so-called directional systems motivated the search for a common framework, which unites many under one roof and enables a simultaneous analysis, for example with respect to approximation properties. Building on the concept of parabolic molecules, the recently introduced framework of $\alpha$-molecules does in fact include the previous mentioned systems. Until now however it is confined to the bivariate setting, whereas nowadays one often deals with higher dimensional data. This motivates the extension of this unifying theory to dimensions larger than 2, put forward in this work. In particular, we generalize the central result that the cross-Gramian of any two systems of $\alpha$-molecules will to some extent be localized. As an exemplary application, we investigate the sparse approximation of video signals, which are instances of 3D data. The multivariate theory allows us to derive almost optimal approximation rates for a large class of representation systems.

The suboptimal performance of wavelets with regard to the approximation of multivariate data gave rise to new representation systems, specifically designed for data with anisotropic features. Some prominent examples of these are given by ridgelets, curvelets, and shearlets, to name a few. The great variety of such so-called directional systems motivated the search for a common framework, which unites many under one roof and enables a simultaneous analysis, for example with respect to approximation properties. Building on the concept of parabolic molecules, the recently introduced framework of $��$-molecules does in fact include the previous mentioned systems. Until now however it is confined to the bivariate setting, whereas nowadays one often deals with higher dimensional data. This motivates the extension of this unifying theory to dimensions larger than 2, put forward in this work. In particular, we generalize the central result that the cross-Gramian of any two systems of $��$-molecules will to some extent be localized. As an exemplary application, we investigate the sparse approximation of video signals, which are instances of 3D data. The multivariate theory allows us to derive almost optimal approximation rates for a large class of representation systems.