Basis Pursuit

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

$\min _{x}\|x\|_{1}\quad {\mbox{mit}}\quad y=Ax$,

wobei $x\in \mathbb {C} ^{n}$ der Lösungsvektor, $y\in \mathbb {C} ^{m}$ der Beobachtungsvektor der Messung und $A\in \mathbb {C} ^{m\times n}$ eine Transformationsmatrix (oft auch Messmatrix genannt) ist. Hierbei gilt $m<n$, wodurch das lineare Gleichungssystem $y=Ax$ unterbestimmt ist.

Unter den Lösungen $x$ der Gleichung $y=Ax$ wird also diejenige mit minimalem Wert der $L_{1}$-Norm (Summe der Koordinatenbeträge, siehe Manhattan-Metrik) gesucht.

Motivation

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 $b\in \mathbb {R} ^{m}$ ist das zu zerlegende Signal, die Spalten der Matrix $A$ sind aus der gegebenen Funktionenmenge und die Komponenten von $x\in \mathbb {R} ^{n}$ sind die gesuchten Koeffizienten, durch die das Signal dargestellt werden soll. Es soll also

$b=\sum _{j=1}^{n}x_{j}A^{j}$

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

$\min _{x}\|x\|_{0}\quad {\mbox{mit}}\quad y=Ax$

mit $\|x\|_{0}=\sharp \left\{j\colon x_{j}\not =0\right\}$. 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

$\min _{x}\|x\|_{1}\quad {\mbox{mit}}\quad y=Ax$,

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

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

Für einen Vektor $x\in \mathbb {R} ^{n}$ bezeichnen wir $I=\left\{i\colon x_{i}\not =0\right\},I^{c}=\left\{i\colon x_{i}=0\right\}$ und mit $A_{I},A_{I^{c}}$ die aus den entsprechenden Spalten von $A$ gebildete Matrix. Entsprechend bezeichnen wir mit $x_{I}$ den aus den $I$-Komponenten gebildeten Vektor und mit $sign(x_{I})$, dessen $i$-Komponente $\pm 1$ je nach Vorzeichen von $x_{i}$ ist.

Existenz von Lösungen: $x\in \mathbb {R} ^{n}$ ist genau dann eine Lösung, wenn es ein $y\in \mathbb {R} ^{m}$ gibt, so dass $A_{I}^{T}y=sign(x_{I})$ und $\Vert A_{I^{c}}^{T}y\Vert _{\infty }\leq 1$.

Eindeutigkeit von Lösungen: $x\in \mathbb {R} ^{n}$ ist genau dann die einzige Lösung, wenn zusätzlich $A_{I}$ injektiv ist und sogar $\Vert A_{I^{c}}^{T}y\Vert _{\infty }<1$ gilt.

Literatur

• 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

Weblinks

• Shaobing Chen, David Donoho: Basis Pursuit
• Terence Tao: Compressed Sensing. Mahler Lecture Series (Folien)
• J. Ch. Gilbert: On the solution uniqueness characterization in the l₁ norm and polyhedral gauge recovery, Journal of Optimization Theory and Applications, 2016 (online)