www.wikidata.de-de.nina.az

Basis Pursuit BP ist ein in der Signalverarbeitung wichtiges mathematisches Optimierungsproblem der Form min x x 1 mit y

Basis Pursuit

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

Weblinks 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)
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Basis Pursuit BP ist ein in der Signalverarbeitung wichtiges mathematisches Optimierungsproblem der Form min x x 1 mit y A x displaystyle min x x 1 quad mbox mit quad y Ax wobei x C n displaystyle x in mathbb C n der Losungsvektor y C m displaystyle y in mathbb C m der Beobachtungsvektor der Messung und A C m n displaystyle A in mathbb C m times n eine Transformationsmatrix oft auch Messmatrix genannt ist Hierbei gilt m lt n displaystyle m lt n wodurch das lineare Gleichungssystem y A x displaystyle y Ax unterbestimmt ist Unter den Losungen x displaystyle x der Gleichung y A x displaystyle y Ax wird also diejenige mit minimalem Wert der L 1 displaystyle L 1 Norm Summe der Koordinatenbetrage siehe Manhattan Metrik gesucht Inhaltsverzeichnis 1 Motivation 2 Losungen 3 Literatur 4 WeblinksMotivation BearbeitenEin 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 enthalt Der Vektor b R m displaystyle b in mathbb R m nbsp ist das zu zerlegende Signal die Spalten der Matrix A displaystyle A nbsp sind aus der gegebenen Funktionenmenge und die Komponenten von x R n displaystyle x in mathbb R n nbsp sind die gesuchten Koeffizienten durch die das Signal dargestellt werden soll Es soll also b j 1 n x j A j displaystyle b sum j 1 n x j A j nbsp gelten wobei A j displaystyle A j nbsp die j displaystyle j nbsp te Spalte von A displaystyle A nbsp bezeichnet Die Bedingung m lt n displaystyle m lt n nbsp ergibt sich daraus dass eine sehr umfangreiche Menge von Funktionen verwendet werden soll Aus ihr folgt dass die Zerlegung von x displaystyle x nbsp nicht eindeutig ist Weil man eine sparsame Zerlegung sucht sollen moglichst wenige der Koeffizienten x j displaystyle x j nbsp von Null verschieden sein Man sucht also die Losung des Problems min x x 0 mit y A x displaystyle min x x 0 quad mbox mit quad y Ax nbsp mit x 0 j x j 0 displaystyle x 0 sharp left j colon x j not 0 right nbsp Diese sparsame Zerlegung ermoglicht eine kompakte Komprimierung des Signals Dieses Problem ist jedoch NP schwer Als handhabbare Annaherung betrachtet man deswegen das Problem min x x 1 mit y A x displaystyle min x x 1 quad mbox mit quad y Ax nbsp dessen Losung haufig nur wenige von Null verschiedene Komponenten hat und das man mit Methoden der linearen Optimierung in polynomieller Zeit losen kann Losungen BearbeitenDie Losungsmenge ist konvex was die Anwendung klassischer Optimierungsverfahren ermoglicht Die Losungsmenge ist nichtleer wenn b displaystyle b nbsp im Bild von A displaystyle A nbsp liegt Fur einen Vektor x R n displaystyle x in mathbb R n nbsp bezeichnen wir I i x i 0 I c i x i 0 displaystyle I left i colon x i not 0 right I c left i colon x i 0 right nbsp und mit A I A I c displaystyle A I A I c nbsp die aus den entsprechenden Spalten von A displaystyle A nbsp gebildete Matrix Entsprechend bezeichnen wir mit x I displaystyle x I nbsp den aus den I displaystyle I nbsp Komponenten gebildeten Vektor und mit s i g n x I displaystyle sign x I nbsp dessen i displaystyle i nbsp Komponente 1 displaystyle pm 1 nbsp je nach Vorzeichen von x i displaystyle x i nbsp ist Existenz von Losungen x R n displaystyle x in mathbb R n nbsp ist genau dann eine Losung wenn es ein y R m displaystyle y in mathbb R m nbsp gibt so dass A I T y s i g n x I displaystyle A I T y sign x I nbsp und A I c T y 1 displaystyle Vert A I c T y Vert infty leq 1 nbsp Eindeutigkeit von Losungen x R n displaystyle x in mathbb R n nbsp ist genau dann die einzige Losung wenn zusatzlich A I displaystyle A I nbsp injektiv ist und sogar A I c T y lt 1 displaystyle Vert A I c T y Vert infty lt 1 nbsp gilt Literatur BearbeitenStephen 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 110Weblinks BearbeitenShaobing 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 Abgerufen von https de wikipedia org w index php title Basis Pursuit amp oldid 236869225