Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-8394
Main Title: The Mismatch Principle and L1-analysis compressed sensing
Subtitle: a unified approach to estimation under large model uncertainties and structural constraints
Translated Title: Das Mismatch-Prinzip und L1-Analysis Compressed Sensing
Translated Subtitle: ein vereinheitlichter Ansatz für Schätzungen unter großen Modellunsicherheiten und strukturierten Nebenbedingungen
Author(s): Genzel, Martin
Advisor(s): Kutyniok, Gitta
Referee(s): Kutyniok, Gitta
Rauhut, Holger
Vershynin, Roman
Granting Institution: Technische Universität Berlin
Type: Doctoral Thesis
Language Code: en
Abstract: This thesis contributes to several mathematical aspects and problems at the interface of statistical learning theory and signal processing. Although based on a common theoretical foundation, the main results of this thesis can be divided into two major topics of independent interest. The first one deals with the estimation capacity of the generalized Lasso, i.e., least squares minimization combined with a (convex) structural constraint. These types of estimators were originally developed for noisy linear regression and related tasks; but beyond that traditional scope, this part of the thesis provides evidence that their outcome is still robust against model misspecifications and large uncertainties, such as unknown non-linear distortions of the output variable or strongly correlated input variables. At the heart of the associated statistical analysis stands the Mismatch Principle, which is a simple recipe to systematically derive performance guarantees for the generalized Lasso with arbitrary sub-Gaussian data. A key goal in this context is to ensure that an estimation procedure is not only accurate but also yields interpretable results. The common strategy of statistical learning theory, however, does not always comply with this wish for interpretability. This concern is of particular importance for semi-parametric observation models where one is typically interested in a certain set of unknown parameters, rather than predicting the value of the output variable. In that regard, the Mismatch Principle provides a useful refinement, allowing us to analyze quantitatively whether the generalized Lasso is capable of solving a specific parameter estimation problem or not. The benefits of the proposed approach are demonstrated in a variety of popular model cases, most notably, single-index models and variable selection. Furthermore, these examples are also relevant to recent advances in quantized and distributed compressed sensing. The second subject of this thesis is devoted to the problem of robust signal estimation from undersampled noisy sub-Gaussian measurements under the assumption of an analysis prior. Based on generalized sparsity parameters, a non-uniform recovery guarantee for the Analysis Basis Pursuit is established in this part, enabling for accurate predictions of its sample complexity. The corresponding bounds on the number of required samples do explicitly depend on the Gram matrix of the analysis operator and therefore particularly take account of its mutual coherence structure. These findings defy conventional wisdom in previous compressed sensing research which suggests that the sparsity of the analysis coefficients is the crucial performance indicator to be studied. In fact, this common conception is not valid in many situations of practical interest, for instance, when using a redundant (multilevel) frame as sparsifying transform. By extensive numerical experiments, it is demonstrated that, in contrast, the proposed theoretical sampling-rate bounds can reliably predict the reconstruction capability of various types of analysis operators, such as redundant Haar wavelets systems, total variation, or random frames. Apart from that, the presented results do naturally extend to stable recovery, which allows for handling signal vectors whose coefficient sequence is only compressible but not exactly sparse. While these two topics rely on quite different model assumptions and therefore seem rather unrelated at first sight, they actually have a common mathematical basis: Using tools from geometric functional analysis and recent advances in empirical process theory, a series of general estimation guarantees is established, which enables a unified treatment of both above-mentioned problem situations. In the first place, these results serve as technical preliminaries, but due to their generality, they may be of interest in their own right as well. Indeed, the underlying proof techniques are very amenable to extensions and refinements, giving rise to further applications that go beyond the scope of this thesis.
Die vorliegende Dissertation untersucht mehrere mathematische Aspekte und Problemstellungen an der Schnittstelle der Gebiete des statistischen Lernens und der Signalverarbeitung. Obwohl die Hauptergebnisse dieser Arbeit auf den gleichen theoretischen Grundlagen beruhen, lassen sie sich in zwei größere Themenbereiche aufgliedern, die von eigenständigem Interesse sind. Der erste Teil beschäftigt sich mit der Schätzfähigkeit des verallgemeinerten Lasso, d.h. mit der Methode der kleinsten Quadrate unter einer (konvexen) strukturgebenden Nebenbedingung. Derartige Methoden wurden ursprünglich für lineare Regression und verwandte Aufgaben entwickelt. Über diesen traditionellen Anwendungsbereich hinausgehend wird in diesem Teil der Arbeit ein Nachweis dafür erbracht, dass ihre Schätzergebnisse auch äußerst robust gegenüber Modellfehlspezifikationen und großen Unsicherheiten sind, beispielsweise bei unbekannten nichtlinearen Verzerrungen der Ausgabevariable oder stark korrelierten Eingabegrößen. Im Fokus der damit verbundenen statistischen Analyse steht die Entwicklung des Mismatch-Prinzips, welches eine systematische Herleitung von Fehlerschranken für das verallgemeinerte Lasso mit beliebigen sub-Gaußschen Daten erlaubt. Ein wesentliches Ziel in diesem Zusammenhang ist es, sicherzustellen, dass ein Schätzverfahren nicht nur akkurate, sondern auch interpretierbare Ergebnisse liefert. Es wird sich jedoch zeigen, dass die übliche Vorgehensweise im Bereich des statistischen Lernens nicht immer diesem Wunsch nach Interpretierbarkeit nachkommt. Dieser Aspekt ist vor allen Dingen für die Untersuchung von semiparametrischen Beobachtungsmodellen relevant, bei der die Schätzung von bestimmten unbekannten Parametern häufig den Vorrang vor einer genauen Prognose für die Ausgabevariable besitzt. In dieser Hinsicht stellt das Mismatch-Prinzip eine nützliche Verfeinerung dar, welche quantitative Aussagen darüber ermöglicht, ob das verallgemeinerte Lasso ein bestimmtes Parameterschätzproblem lösen kann oder nicht. Der Nutzen dieser Vorgehensweise wird anhand einer Reihe von populären Beispielmodellen verdeutlicht, insbesondere für den Fall von Single-Index-Modellen und das Variable-Selection-Problem. Darüber hinaus sind diese Resultate auch in Hinblick auf jüngste Fortschritte im Bereich des quantisierten und verteilten Compressed Sensing von Bedeutung. Der zweite Teil der Arbeit widmet sich der Aufgabe von Signalschätzungen aus stark unterabgetasteten sub-Gaußschen Messungen mit additivem Rauschen unter der Annahme eines Analysis-Modells. Mit Hilfe von verallgemeinerten Sparsity-Parametern wird in diesem Teil eine nicht-uniforme Rekonstruktionsgarantie für den Analysis-Basis-Pursuit Algorithmus hergeleitet, die eine zuverlässige Vorhersage von dessen Stichprobenkomplexität ermöglicht. Die daraus resultierenden Schranken für die Anzahl der benötigten Messungen hängen explizit von der Gramschen Matrix des Analysis-Operators ab und ziehen damit insbesondere dessen Kohärenzstruktur in Betracht. Die vorgestellten Resultate widersprechen der bislang üblichen Auffassung in der Compressed-Sensing-Forschung, wonach die Sparsity der Analysis-Koeffizienten die entscheidende Kenngröße eines Rekonstruktionsproblems darstellt. Diese einfache Grundregel verliert in vielen praktischen Szenarien jedoch ihre Gültigkeit, wie zum Beispiel bei der Verwendung von redundanten (mehrskaligen) Frames. Im Gegensatz dazu wird mit einer Reihe von numerischen Experimenten nachgewiesen, dass die gezeigten theoretischen Schranken hinsichtlich der Stichprobengröße die Rekonstruktionsfähigkeit vieler Arten von Analysis-Operatoren angemessen widerspiegeln, z.B. für redundante Haar-Wavelet-Systeme, Totalvariation oder zufällige Frames. Abgesehen davon lassen sich diese Ergebnisse auch auf den Fall stabiler Rekonstruierbarkeit übertragen, wodurch Signalvektoren betrachtet werden dürfen, deren Analysis-Koeffizienten zwar komprimierbar, aber nicht exakt sparse sind. Während die beiden Hauptteile dieser Dissertation auf unterschiedlichen Modellannahmen beruhen und auf den ersten Blick kein Zusammenhang zu bestehen scheint, so haben sie jedoch den gleichen mathematischen Ursprung: Unter Verwendung von Techniken aus der geometrischen Funktionalanalysis sowie jüngsten Ergebnissen aus der Theorie empirischer Prozesse werden mehrere allgemeine Fehlerschranken für die untersuchten Schätzer gezeigt, welche eine einheitliche Behandlung der beiden oben genannten Problemstellungen ermöglichen. In erster Linie bilden diese Resultate eine technische Grundlage, aber aufgrund ihrer Allgemeingültigkeit kommt ihnen ebenfalls eine eigenständige Bedeutung zu. Von den zugrunde liegenden Beweistechniken darf erwartet werden, dass sie den Ausgangspunkt für Erweiterungen und Verfeinerungen bilden können und somit den Weg für weitere Anwendungen eröffnen, die über den Rahmen dieser Arbeit hinausgehen.
URI: https://depositonce.tu-berlin.de/handle/11303/9321
http://dx.doi.org/10.14279/depositonce-8394
Exam Date: 28-Mar-2019
Issue Date: 2019
Date Available: 8-May-2019
DDC Class: 519 Wahrscheinlichkeiten, angewandte Mathematik
Subject(s): statistical learning
parameter estimation
Lasso
orthogonality principle
semi-parametric models
compressed sensing
cosparse modeling
analysis sparsity
L1-analysis basis pursuit
redundant frames
statistisches Lernen
Schätztheorie
Orthogonalitätsprinzip
semiparametrische Modelle
Cosparse-Modellierung
License: https://creativecommons.org/licenses/by/4.0/
Appears in Collections:Inst. Mathematik » Publications

Files in This Item:
File Description SizeFormat 
genzel_martin.pdf3.94 MBAdobe PDFThumbnail
View/Open


This item is licensed under a Creative Commons License Creative Commons