One-bit compressed sensing and fast binary embeddings

Stollenwerk, Alexander; Rauhut, Holger; Dirksen, Sjoerd

doi:10.18154/RWTH-2020-00296

One-bit compressed sensing and fast binary embeddings = 1-Bit komprimierte Erfassung und schnelle binäre Einbettungen

Stollenwerk, Alexander^RWTH*

2019 & 2020

Verantwortlichkeitsangabevorgelegt von Alexander Stollenwerk, M.Sc.

ImpressumAachen 2019

Umfang1 Online-Ressource (136 Seiten) : Illustrationen

Dissertation, RWTH Aachen University, 2019

Veröffentlicht auf dem Publikationsserver der RWTH Aachen University 2020

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Dirksen, Sjoerd (Thesis advisor)^RWTH* ; Rauhut, Holger (Thesis advisor)^RWTH*

Tag der mündlichen Prüfung/Habilitation
2019-12-11

Online
DOI: 10.18154/RWTH-2020-00296
URL: https://publications.rwth-aachen.de/record/775859/files/775859.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
Gaussian circulant matrices (frei) ; binary dimensionality reduction (frei) ; fast Johnson-Lindenstrauss transforms (frei) ; hinge loss minimization (frei) ; one-bit compressed sensing (frei)

Thematische Einordnung (Klassifikation)
DDC: 510

Kurzfassung
Der Schwerpunkt dieser Dissertation liegt auf zwei verwandten Problemen aus der Datenwissenschaft: Rekonstruktion von strukturierten hochdimensionalen Vektoren aus wenigen binären Messungen, sowie Entwicklung rechenzeiteffizienter binärer Einbettungsmethoden. Während das erste Problem im Bereich compressed sensing studiert wird, fällt das zweite Problem in einen Forschungsbereich der sich allgemeiner mit Dimensionsreduktion befasst. Beide Probleme verbindet nicht nur die gemeinsame Annahme, dass die betrachteten Datenvektoren eine niedrigdimensionale Struktur besitzen, welche auf empirischen Beobachtungen in zahlreichen Anwendungen basiert, sondern zudem wird auch eine geometrische Verbindung zwischen beiden Problemen offenkundig wenn man die betrachteten binären Einbettungsabbildungen, beziehungsweise Abtastungsabbildungen als von Hyperebenenzerteilungen induziert betrachtet. Als Folge daraus werden in beiden Forschungsfeldern ähnliche Komplexitätsmaße, sowie ähnliche mathematische Methoden verwendet. Bezüglich des Problems der Signalrekonstruktion aus binären Messungen analysieren wir die Rekonstruktionsperformance eines spezifischen konvexen Rekonstruktionsprogrammes welches wir „Hinge Loss Minimierung“ nennen. Das Programm basiert auf der Methode der empirischen Risikominimierung unter Nebenbedingung, wobei die hinge loss Funktion zur Berechnung des „Risikos“ beziehungsweise des „Verlustes“ verwendet wird. Während dieses Programm erfolgreich bei Klassifizierungsproblemen eingesetzt wird, ist kaum erforscht ob man damit auch einen spezifischen Signalvektor rekonstruieren kann. Eine Hauptschwierigkeit liegt darin, dass die hinge loss Funktion nur stückweise linear ist. Gewissermaßen ist ihre „Krümmungsenergie“ in einem einzigen Punkt konzentriert. Dies unterscheidet die hinge loss Funktion von anderen häufig betrachteten Verlustfunktionen im Bereich der Signalrekonstruktion, wie zum Beispiel der quadratischen oder der logistischen Verlustfunktion, die zumindest lokal stark konvex sind. Dennoch zeigen unsere Rekonstruktionsresultate, dass Signalrekonstruktion mit dem Programm „Hinge Loss Minimierung“ bereits unter relativ schwachen Annahmen über das betrachtete Signalmodell möglich ist, und zwar auch in Situationen in denen starkes Rauschen den Quantisierungsvorgang stört. Um rechenzeiteffiziente binäre Einbettungsmethoden zu entwickeln, betrachten wir Abbildungen die zunächst jeden Vektor linear in einen niedrigdimensionalen euklidischen Raum einbetten, und diesen dann vermöge der komponentenweise angewandten Vorzeichenfunktion quantisieren. Genauer zeigen wir, dass Abbildungen dieses Typs, bei der die lineare Transformation durch eine Konstruktion aus gaußschen zirkulanten Matrizen gegeben wird, dafür verwendet werden können Winkelabstände zwischen Vektoren zu erhalten. Falls man zusätzlich künstliches Rauschen vor dem Quantisierungsschritt hinzufügt, dann können Abbildungen dieser Art auch dazu verwendet werden euklidische Abstände zwischen Vektoren zu erhalten. Diese Einbettungsabbildungen können effizient berechnet werden, d.h., jeder Vektor kann in log-linearer Zeit eingebettet werden, und bei der Einbettung von endlichen Mengen wird (fast) die kleinstmöglich erreichbare Einbettungsdimension angenommen. Zuletzt zeigen wir, dass auch unendliche, allerdings niedrig-komplexe und beschränkte Datenmengen effizient eingebettet werden können, sodass dabei alle paarweisen Euklidischen Abstände annähernd erhalten bleiben. Die dafür verwendeten Transformationen sind sogenannte gedämpfte gaußsche zirkulante binäre Einbettungsabbildungen.

The focus of this dissertation lies on two related problems from data science: estimation of structured high-dimensional vectors from few binary measurements, and the design of computationally efficient binary embedding methods. While the former problem is more broadly studied in the field of compressed sensing, the latter task belongs to the field of dimensionality reduction. Both problems are linked by the joint assumption, inspired by empirical observations in numerous applications, that the data vectors considered exhibit some type of low-complexity structure. Furthermore, there is a geometric connection between both problems, which becomes apparent when visualizing the considered binary embedding, respectively sensing maps as being induced by hyperplane tessellations of the data set. As a consequence, not only the considered complexity measures are the same, but also the applied theoretical tools are very similar. For the task of signal estimation from binary measurements we investigate the recovery performance of a specific convex reconstruction program, called hinge loss minimization. The program is based on constrained empirical risk minimization and uses the hinge loss function as a data fidelity term. While successfully applied in classifications tasks, the program's ability to estimate a specific signal vector is only poorly understood. A major difficulty is that the hinge loss is just piecewise linear, so that its “curvature energy” is concentrated in a single point. This is substantially different from other popular loss functions considered in signal estimation, e.g., the square or logistic loss, which are at least locally strongly convex. Still, our reconstruction results show that signal estimation from one-bit measurements via hinge loss minimization is feasible under fairly general signal model conditions and even in the presence of strong noise that corrupts the quantization process. Regarding the task of fast binary dimensionality reduction, we consider embedding maps that first linearly map a vector to a lower-dimensional Euclidean space and then quantize the embedded vector by taking the sign component-wise. More specifically, we show that such maps, where the linear transformation is given by a construction involving Gaussian circulant matrices, can be used for the task of preserving pairwise angular distances between data vectors. Further, by additionally adding designed noise prior to the quantization step, these binary maps induced by Gaussian circulant matrices also succeed at the task of preserving Euclidean distances. The embedding maps can be computed efficiently, meaning that every vector can be embedded in near-linear time, and for finite sets the maps (almost) attain the minimal embedding dimension possible. Finally, we show that by considering so-called dithered Gaussian circulant binary embeddings, also infinite, but low-complexity and bounded data sets can be efficiently embedded, in such a way that all pairwise Euclidean distances are approximately preserved.

OpenAccess:
PDF
(additional files)