Ein gieriger iterativer Algorithmus zur sparsamen Approximation, der eine k-sparsame Darstellung eines Signals aufbaut, indem er wiederholt das Dictionary-Atom auswählt, das am stärksten mit dem aktuellen Residuum korreliert, das Signal orthogonal auf den Spann der ausgewählten Atome projiziert, um Koeffizienten zu aktualisieren, und das Residuum aktualisiert, bis ein Abbruchkriterium erfüllt ist.

Prinzip

Wähle in jeder Iteration das Dictionary-Element mit maximalem absolutem Skalarprodukt zum Residuum (gierige Auswahl), löse dann ein kleinstquadratisches Problem auf den ausgewählten Atomen (orthogonale Projektion) zur Koeffizientenbestimmung, um inkonsistente Neugewichtung bereits gewählter Atome zu vermeiden und die Residuumnorm monoton zu reduzieren.

Demonstration

Signalapproximation y mit einer redundanten Basis (Dictionary): Residuum r=y initialisieren, Atom mit größter Korrelation auswählen, zur aktiven Menge hinzufügen, das Kleinstquadrate-Problem lösen, r=y - D_active c_active aktualisieren und wiederholen, bis Residuumnorm oder gewünschte Sparsität erreicht ist; Ergebnis ist ein interpretierbarer sparsamer Code.

Fehlanwendung

OMP zu früh stoppen, während wichtige Atome ungewählt bleiben, was zu verzerrten Approximationen führt, oder OMP bei sehr kohärenten Dictionary-Spalten ohne Modifikation (z. B. Regularisierung) anwenden, was falsche Atomselektionen und schlechte Rekonstruktion zur Folge haben kann.

Konsequenz

Unter Bedingungen wie sparsamer Signalstruktur und Näherung an Inkoherenz/Restricted-Isometry-Eigenschaften rekonstruiert OMP schnell sinnvolle sparse Darstellungen mit interpretierbarem Support und geringeren Rechenkosten als exhaustive Suche; es liefert einen klaren Kompromiss zwischen Sparsität und Approximationserror.

Umkehrung

Dichte Kleinste-Quadrate-Anpassung auf dem vollständigen Dictionary: globale L2-Minimierung unter Verwendung aller Atome lösen, was bei gegebener Norm ein niedrigeres Residuum liefert, aber dichte Koeffizienten ohne erzwungene Sparsität oder Interpretierbarkeit der gewählten Atome erzeugt.

Abgrenzung

Geltungsbereich: lineare sparse Approximation mit einer expliziten Dictionary-Matrix und moderater Kohärenz, bei der gierige Auswahl sinnvoll ist; ausgeschlossen sind Probleme, die exakte l0-Minimierung in stark kohärenten Dictionaries erfordern, oder Signale, die besser durch strukturierte (gruppierte oder hierarchische) Sparsität modelliert sind, ohne Anpassung des Algorithmus.

Semantische Spannung

Spannung zwischen Gierigkeit und globaler Optimalität: OMPs lokale, gierige Entscheidungen sind schnell und interpretierbar, können aber global optimale sparsity-Supports verfehlen; das steht im Gegensatz zu konvexen Relaxationsansätzen (L1-Minimierung), die andere Kompromisse zwischen Robustheit und Rechenaufwand bieten.

Synthese

Orthogonale Matching Pursuit ist ein gieriger Sparse-Coding-Algorithmus, der iterativ das am stärksten mit dem Residuum korrelierende Atom auswählt und Koeffizienten durch orthogonale Projektion neu berechnet, um eine sparsame Darstellung mit monoton fallender Residuumnorm und interpretierbarem Support aufzubauen.