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.

Motivation

Bearbeiten

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.

Lösungen

Bearbeiten

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.

Literatur

Bearbeiten
  • 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
Bearbeiten
  • 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)