Basis Pursuit

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Basis Pursuit (BP) ist ein in der Signalverarbeitung wichtiges mathematisches Optimierungsproblem der Form

,

wobei der Lösungsvektor, der Beobachtungsvektor der Messung und eine Transformationsmatrix (oft auch Messmatrix genannt) ist. Hierbei gilt , wodurch das lineare Gleichungssystem unterbestimmt ist.

Unter den Lösungen der Gleichung wird also diejenige mit minimalem Wert der -Norm (Summe der Koordinatenbeträge, siehe Manhattan-Metrik) gesucht.

Ein klassisches Problem der Signalverarbeitung besteht darin, eine sparsame (d. h. aus wenigen Elementen gebildete) Zerlegung eines gegebenen Signals in einer umfangreichen Menge von Funktionen zu finden, die zum Beispiel trigonometrische Reihen und Wavelets enthält. Der Vektor ist das zu zerlegende Signal, die Spalten der Matrix sind aus der gegebenen Funktionenmenge und die Komponenten von sind die gesuchten Koeffizienten, durch die das Signal dargestellt werden soll. Es soll also

gelten, wobei die -te Spalte von bezeichnet. Die Bedingung ergibt sich daraus, dass eine sehr umfangreiche Menge von Funktionen verwendet werden soll. Aus ihr folgt, dass die Zerlegung von nicht eindeutig ist. Weil man eine sparsame Zerlegung sucht, sollen möglichst wenige der Koeffizienten von Null verschieden sein. Man sucht also die Lösung des Problems

mit . Diese sparsame Zerlegung ermöglicht eine kompakte Komprimierung des Signals.

Dieses Problem ist jedoch NP-schwer. Als handhabbare Annäherung betrachtet man deswegen das Problem

,

dessen Lösung häufig nur wenige von Null verschiedene Komponenten hat, und das man mit Methoden der linearen Optimierung in polynomieller Zeit lösen kann.

Die Lösungsmenge ist konvex, was die Anwendung klassischer Optimierungsverfahren ermöglicht. Die Lösungsmenge ist nichtleer, wenn im Bild von liegt.

Für einen Vektor bezeichnen wir und mit die aus den entsprechenden Spalten von gebildete Matrix. Entsprechend bezeichnen wir mit den aus den -Komponenten gebildeten Vektor und mit , dessen -Komponente je nach Vorzeichen von ist.

Existenz von Lösungen: ist genau dann eine Lösung, wenn es ein gibt, so dass und .

Eindeutigkeit von Lösungen: ist genau dann die einzige Lösung, wenn zusätzlich injektiv ist und sogar gilt.

  • Stephen Boyd, Lieven Vandenbergh: Convex Optimization, Cambridge University Press, 2004, ISBN 9780521833783, S. 337–337
  • Simon Foucart, Holger Rauhut: A Mathematical Introduction to Compressive Sensing. Springer, 2013, ISBN 9780817649487, S. 77–110
  • Shaobing Chen, David Donoho: Basis Pursuit
  • Terence Tao: Compressed Sensing. Mahler Lecture Series (Folien)
  • J. Ch. Gilbert: On the solution uniqueness characterization in the l1 norm and polyhedral gauge recovery, Journal of Optimization Theory and Applications, 2016 (online)