Spärliche Näherung - Sparse approximation

Die Theorie der spärlichen Approximation (auch als spärliche Darstellung bekannt ) befasst sich mit spärlichen Lösungen für lineare Gleichungssysteme . Techniken zum Auffinden dieser Lösungen und deren Nutzung in Anwendungen finden breite Anwendung in der Bildverarbeitung , Signalverarbeitung , maschinellem Lernen , medizinischen Bildgebung und mehr.

Spärliche Zersetzung

Geräuschlose Beobachtungen

Betrachten Sie ein lineares Gleichungssystem mit einer unterbestimmten Matrix und . Die Matrix (typischerweise als vollwertig angenommen) wird als Wörterbuch bezeichnet und ist ein Signal von Interesse. Das Core-Sparse-Repräsentationsproblem ist definiert als die Suche nach der dünnstmöglichen Repräsentation, die zufriedenstellend ist . Aufgrund der Unterbestimmtheit von , lässt dieses lineare System im Allgemeinen unendlich viele mögliche Lösungen zu, und unter diesen suchen wir die mit den wenigsten Nicht-Nullen. Formal gesagt lösen wir ${\displaystyle x=D\alpha}$${\displaystyle D}$ ${\displaystyle m\times p}$ ${\displaystyle (m<p)}$${\displaystyle x\in\mathbb{R}^{m},\alpha\in\mathbb{R}^{p}}$${\displaystyle D}$${\displaystyle x}$${\displaystyle\alpha}$${\displaystyle x=D\alpha}$${\displaystyle D}$

${\displaystyle \min_{\alpha\in\mathbb{R}^{p}}\|\alpha\|_{0}{\text{ unterliegt }}x=D\alpha ,}$

wo ist die Pseudonorm, die die Anzahl der Nicht-Null-Komponenten von zählt . Dieses Problem ist bekanntlich NP-schwer mit einer Reduktion auf NP-vollständige Teilmengenauswahlprobleme bei der kombinatorischen Optimierung . ${\displaystyle \|\alpha\|_{0}=\#\{i:\alpha_{i}\neq 0,\,i=1,\ldots ,p\}}$${\displaystyle \ell_{0}}$${\displaystyle\alpha}$

Sparsity of impliziert, dass nur wenige ( ) Komponenten darin ungleich Null sind. Die zugrunde liegende Motivation für eine solche spärliche Zerlegung ist der Wunsch, eine möglichst einfache Erklärung als Linearkombination von möglichst wenigen Säulen aus , auch Atome genannt, zu geben. Als solches kann das Signal als ein Molekül angesehen werden, das aus einigen wenigen grundlegenden Elementen besteht, die aus entnommen wurden . ${\displaystyle\alpha}$${\displaystyle k\llm<p}$${\displaystyle x}$${\displaystyle D}$${\displaystyle x}$${\displaystyle D}$

Obwohl das oben gestellte Problem tatsächlich NP-schwer ist, kann seine Lösung oft mithilfe von Approximationsalgorithmen gefunden werden. Eine solche Option ist eine konvexe Lockerung des Problems, die durch die Verwendung der -norm anstelle von erhalten wird , wobei einfach die absoluten Werte der Einträge in summiert werden . Dies ist als Basisverfolgungsalgorithmus (BP) bekannt, der mit jedem linearen Programmierlöser verarbeitet werden kann . Eine alternative Näherungsmethode ist eine gierige Technik, wie z. B. die Matching-Verfolgung (MP), die den Ort der Nicht-Nullen nacheinander findet. ${\displaystyle \ell_{1}}$${\displaystyle \ell_{0}}$${\displaystyle \|\alpha \|_{1}}$${\displaystyle\alpha}$

Überraschenderweise kann unter milden Bedingungen auf (unter Verwendung des Funkens (Mathematik) , der gegenseitigen Kohärenz oder der eingeschränkten Isometrieeigenschaft ) und dem Grad der Sparsity in der Lösung, gezeigt werden , dass das Problem der spärlichen Darstellung eine eindeutige Lösung hat, und BP und MP finden sie garantiert perfekt. ${\displaystyle D}$${\displaystyle k}$

Laute Beobachtungen

Das beobachtete Signal ist oft verrauscht. Durch Lockern der Gleichheitsbeschränkung und Auferlegen einer -Norm für den Datenanpassungsterm wird das Problem der spärlichen Zerlegung zu ${\displaystyle x}$${\displaystyle \ell_{2}}$

${\displaystyle \min_{\alpha\in\mathbb{R}^{p}}\|\alpha\|_{0}{\text{ unterliegt }}\|xD\alpha \|_{2} ^{2}\leq\epsilon^{2},}$

oder in eine Lagrangesche Form gebracht,

${\displaystyle \min_{\alpha\in\mathbb{R}^{p}}\lambda\|\alpha\|_{0}+{\frac{1}{2}}\|xD\alpha\ |_{2}^{2},}$

wo ersetzt die . ${\displaystyle \lambda}$${\displaystyle \epsilon}$

Genau wie im rauschfreien Fall sind diese beiden Probleme im Allgemeinen NP-schwer, können aber mit Verfolgungsalgorithmen angenähert werden. Genauer gesagt, wenn wir die in eine -Norm ändern , erhalten wir ${\displaystyle \ell_{0}}$${\displaystyle \ell_{1}}$

${\displaystyle \min_{\alpha\in\mathbb{R}^{p}}\lambda\|\alpha\|_{1}+{\frac{1}{2}}\|xD\alpha\ |_{2}^{2},}$

die als Basis Verfolgung Entrauschung bekannt ist . In ähnlicher Weise kann eine Anpassungsverfolgung verwendet werden, um die Lösung der obigen Probleme anzunähern, indem die Orte der Nicht-Nullen einzeln gefunden werden, bis der Fehlerschwellenwert erreicht ist. Auch hier legen theoretische Garantien nahe, dass BP und MP in Abhängigkeit von den Eigenschaften von und der Mächtigkeit der Lösung zu nahezu optimalen Lösungen führen . Ein weiteres interessantes theoretisches Ergebnis bezieht sich auf den Fall, in dem unitär ist. Unter dieser Annahme lassen die oben gestellten Probleme (mit entweder oder ) geschlossene Lösungen in Form von nichtlinearer Schrumpfung zu. ${\displaystyle D}$${\displaystyle k}$${\displaystyle D}$${\displaystyle \ell_{0}}$${\displaystyle \ell_{1}}$

Variationen

Es gibt mehrere Variationen des grundlegenden dünnbesetzten Approximationsproblems.

Strukturierte Sparsity : In der ursprünglichen Version des Problems kann jedes der Atome im Wörterbuch ausgewählt werden. Im strukturierten (Block-)Spasity-Modell sollen Atome nicht einzeln, sondern in Gruppen ausgewählt werden. Diese Gruppen können sich überlappen und unterschiedlich groß sein. Das Ziel besteht darin, so darzustellen , dass es spärlich ist, während diese Blockstruktur erzwungen wird. ${\displaystyle x}$

Kollaboratives (gemeinsames) Sparse Coding : Die ursprüngliche Version des Problems wird für ein einzelnes Signal definiert . Im kollaborativen (gemeinsamen) Sparse-Codierungsmodell steht eine Reihe von Signalen zur Verfügung, von denen angenommen wird, dass sie jeweils aus (fast) der gleichen Menge von Atomen aus stammen . In diesem Fall zielt die Verfolgungsaufgabe darauf ab, eine Reihe von spärlichen Darstellungen wiederherzustellen, die die Daten am besten beschreiben, während sie gleichzeitig gezwungen werden, dieselbe (oder nahegelegene) Unterstützung zu teilen. ${\displaystyle x}$${\displaystyle D}$

Andere Strukturen : Im weiteren Sinne kann das Problem der spärlichen Approximation gegossen werden, während eine spezifische gewünschte Struktur auf das Muster von Nicht-Null-Orten in gezwungen wird . Zwei Fälle von Interesse, die ausführlich untersucht wurden, sind die baumbasierte Struktur und allgemeiner eine verteilte Boltzmann-Unterstützung. ${\displaystyle\alpha}$

Algorithmen

Wie bereits oben erwähnt, gibt es verschiedene Approximationsalgorithmen (auch als Verfolgung bezeichnet ), die für das Problem der dünnbesetzten Darstellung entwickelt wurden:

${\displaystyle \min_{\alpha\in\mathbb{R}^{p}}\|\alpha\|_{0}{\text{ unterliegt }}\|xD\alpha \|_{2} ^{2}\leq\epsilon^{2}.}$

Im Folgenden erwähnen wir einige dieser Hauptmethoden.

• Matching Pursuit ist ein gieriger iterativer Algorithmus, um das obige Problem näherungsweise zu lösen. Es funktioniert, indem es nach und nach die Positionen der Nicht-Nullen nacheinander findet. Die Kernidee besteht darin, in jedem Schritt die Spalte (Atom) zu finden , die am besten mit dem aktuellen Residuum (initialisiert auf ) korreliert , und dann dieses Residuum zu aktualisieren, um das neue Atom und seinen Koeffizienten zu berücksichtigen. Die passende Verfolgung kann das gleiche Atom mehrmals auswählen.${\displaystyle\alpha}$${\displaystyle D}$${\displaystyle x}$
• Orthogonales Matching-Verfolgung ist dem Matching-Verfolgung sehr ähnlich, mit einem Hauptunterschied: In jedem Schritt des Algorithmus werden alle von Null verschiedenen Koeffizienten durch kleinste Quadrate aktualisiert . Infolgedessen ist der Rest orthogonal zu den bereits ausgewählten Atomen, und daher kann ein Atom nicht mehr als einmal ausgewählt werden.
• Stufenweise gierige Methoden: Verbesserte Variationen gegenüber den oben genannten sind Algorithmen, die gierig arbeiten, während sie zwei kritische Merkmale hinzufügen: (i) die Fähigkeit, Gruppen von Nicht-Nullen gleichzeitig hinzuzufügen (anstelle einer Nicht-Null pro Runde); und (ii) Einschließen eines Beschneidungsschritts in jeder Runde, bei dem mehrere der Atome vom Träger verworfen werden. Vertreter dieses Ansatzes sind der Subspace-Pursuit-Algorithmus und der CoSaMP.

• Die Basisverfolgung löst eine konvexe entspannte Version des Problems, indem sie die durch eine -Norm ersetzt. Beachten Sie, dass dies nur ein neues Ziel definiert, während die Frage nach dem zu verwendenden Algorithmus zum Erhalten der gewünschten Lösung offen bleibt. Allgemein als solche Algorithmen angesehen werden IRLS , LARS und iterative Soft-Shrinkage-Methoden.${\displaystyle \ell_{0}}$${\displaystyle \ell_{1}}$

• Es gibt mehrere andere Methoden zur Lösung von Sparse-Zerlegungsproblemen: Homotopie-Methode, Koordinatenabstieg , iteratives Hard-Thresholding, proximale Methoden erster Ordnung , die mit den oben erwähnten iterativen Soft-Shrinkage-Algorithmen verwandt sind, und Dantzig-Selektor.

Anwendungen

Sparse-Approximationsideen und -algorithmen wurden in großem Umfang in der Signalverarbeitung , Bildverarbeitung , maschinellem Lernen , medizinischen Bildgebung , Array-Verarbeitung , Data Mining und mehr verwendet. In den meisten dieser Anwendungen wird das interessierende unbekannte Signal als eine spärliche Kombination einiger Atome aus einem gegebenen Wörterbuch modelliert, und dies wird als Regularisierung des Problems verwendet. Diese Probleme werden typischerweise von einem Wörterbuch-Lernmechanismus begleitet , der darauf abzielt, das Modell am besten an die gegebenen Daten anzupassen. Die Verwendung von Sparsity-inspirierten Modellen hat zu hochmodernen Ergebnissen in einer Vielzahl von Anwendungen geführt. Neuere Arbeiten legen nahe, dass es eine enge Verbindung zwischen Sparse Representation Modeling und Deep Learning gibt. ${\displaystyle D}$

Siehe auch

• Compressed Sensing
• Spärliches Wörterbuch lernen
• K-SVD
• Lasso (Statistik)
• Regularisierung (Mathematik) und inverse Probleme

Verweise