One-bit compressed sensing and fast binary embeddings

• 1-Bit komprimierte Erfassung und schnelle binäre Einbettungen

Stollenwerk, Alexander; Dirksen, Sjoerd (Thesis advisor); Rauhut, Holger (Thesis advisor)

Aachen (2019, 2020)
Doktorarbeit

Dissertation, RWTH Aachen University, 2019

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.

Einrichtungen

• Fachgruppe Mathematik [110000]
• Lehrstuhl für Mathematik der Informationsverarbeitung [114510]