Optimierung, Modelle & Algorithmen für Dictionary Learning

Ob es die 300 Millionen hochgeladener Fotos auf Facebook pro Tag sind, die 800GB pro Sekunde, die der Large Hadron Collider aufzeichnet, oder die 320.000GB pro Sekunde, die er nicht aufzeichnen kann, eines ist klar, wir sind im Zeitalter der großen Datenvolumen angelangt. Im vergangenen Jahr etwa ist die Menge der weltweit vorhandenen Daten auf schätzungsweise 2,8 ZB = 2.800 Milliarden GB gestiegen, und während man annimmt, dass 23% dieser Daten nützlich sind, wenn analysiert, ist nur 1% auch tatsächlich analysiert. Wie sollen wir also mit diesen Datenmengen und den damit verbundenen Herausforderungen umgehen? Auf der Seite der Signalverarbeitung basieren einige der vielversprechendsten Strategien auf dem Schlüsselkonzept der dünnen Besetzung (sparsity), d.h., der geringen Komplexität sogar hochdimensionaler Daten, sobald diese in einem geeigneten Representationssystem (dictionary) dargestellt werden. Dieses Projekt befasst sich mit der grundlegenden Frage, wie man für eine gegebene Datenklasse automatisch ein Representationssystem lernen kann, das dünn besetzte Darstellung erlaubt, auch bekannt als dictionary learning oder sparse coding. Es zielt darauf ab, ein tieferes theoretisches Verständnis für dictionary learning zu liefern und auf dessen Grundlage stabile und effiziente Lernalgorithmen für hochdimensionale Daten zu entwickeln. Um dieses Ziel zu erreichen, werden insbesondere die folgenden Themen behandelt werden. Optimierung: Die bisher vielversprechendsten Strategien für dictionary learning basieren auf Optimierung. Unter Vorgabe geeigneter dünn besetzter Modelle für die Signale, werden wir die lokalen und globalen Identifizierungseigenschaften mehrerer klassischer und neuer Optimierungsprobleme untersuchen. Modelle: Über die derzeit verwendeten, isotropen dünn besetzten Koeffizientenmodelle hinausgehend, werden wir realistische Modelle entwickeln, die auch die Modellierung von strukturiert dünn besetzten Daten geeignet sind. Darüber hinaus werden wir Lernprobleme konzipieren und analysieren, die eine Identifizierung des Representationssystem gemeinsam mit (unabhängig von) den zugrunde liegenden Strukturen erlauben. (Randomisierte) Algorithmen: Eine grundlegende Herausforderung in dictionary learning ist die hohe Dimensionalität des Lernproblems an sich. Daher werden wir untersuchen, wie die Komplexität der Lernens über Johnson-Lindenstrauss Einbettungen und Divide & Conquer Strategien reduziert werden kann. Analysis Dictionary Learning: Analyse co-sparsity wurde kürzlich als Erfolg versprechende Alternative zur Synthese sparsity eingeführt. Wir werden analysis dictionary learning durch einen Ansatz parallel zu synthesis dictionary learning studieren, d.h. Formulierung von Optimierungsproblemen, Untersuchungen zur Identifizierbarkeit unter Vorgabe zufälliger co-sparser Signalmodelle und Entwicklung von effizienten (randomisierten) Algorithmen. Anwendungen: In enger Zusammenarbeit mit unseren (inter)nationalen wissenschaftlichen Partnern werden wir die entwickelten Strategien auf hochdimensionale Probleme anwenden, die nicht mit derzeit verfügbaren dictionary learning Schemata behandelt werden können, z.B. Mikroskopie, sound tracing, audio inpainting, Magnetresonanztomographie oder akustische Wahrnehmung.

Das Ziel von Dictionary Learning ist für eine Klasse von Signalen automatisch ein Repräsentationssystem (=Dictionary) zu finden, das erlaubt alle diese Signale kompakt darzustellen. Eines der Hauptziele des Projekts war Algorithmen für Dictionary Learning zu entwickeln, die auf echten und synthetischen Daten sinnvolle Ergebnisse liefern und für die theoretische Aussagen zur Konvergenz gemacht werden können. Zu den schönsten Projektergebnissen zählen ein Dictionary Learning Algorithmus, der ohne Angabe von Parametern wie Dictionary-Größe oder Kompaktheit der Darstellung vernünftige Ergebnisse auf Bilddaten liefert und das richtige Ergebnis auf synthetischen Daten. Weiters führte es zur ersten bzw. verbesserten Charakterisierung des Konvergenzradius für die bekannten Dictionary Learning Algorithmen MOD bzw. ODL auch bekannt als approximative K- SVD. Diese stellt gleichzeitig auch das erste theoretische Ergebnis für Dictionary Learning unter Annahme eines natürlichen Signalmodels dar, in dem verschiedene Dictionary-Elemente verschieden oft verwendet werden. Zu guter Letzt finden sich unter den weiteren Resultaten des Projekts: einfach anzuwendende Erkenntnisse zum Design von Abtastmatrizen für 'compressed sensing', Anwendungen von Dictionary Learning für die Bildrekonstruktion in der Magnetresonanzspektroskopie, und die wahrscheinlich erste und ganz sicher putzigste Schranke in der semidefiniten Ordnung für Matrizen von Auftrittswahrscheinlichkeiten in 'rejective sampling'.