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

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

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

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.

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.

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.