Verwirrung über das Problem der komprimierten Abtastung

Ich habe einige Referenzen gelesen, einschließlich dieser .

Ich bin irgendwie verwirrt, welches Optimierungsproblem die komprimierte Abtastung aufbaut und zu lösen versucht. Ist es

oder und

oder / und noch was?

Brian ist genau richtig. Ich halte es jedoch für hilfreich, einen komprimierten Erfassungskontext hinzuzufügen.

Beachten Sie zunächst, dass die sogenannte 0-Norm - die Kardinalitätsfunktion oder die Anzahl der Nicht-Null-Werte in x - keine Norm ist . Es ist wahrscheinlich am besten, es als etwas wie card ( x ) in etwas anderem als den beiläufigsten Zusammenhängen zu schreiben . Versteh mich nicht falsch, du bist in guter Gesellschaft, wenn du die Abkürzung ‖ x ‖ 0 verwendest , aber ich denke, das kann Verwirrung stiften.$\|x\|_0$$x$$\mathop{\textbf{card}}(x)$$\|x\|_0$

Die Leute wissen seit langem, dass die Minimierung der Norm ‖ x ‖ 1 dazu neigt, spärliche Lösungen zu produzieren. Dafür gibt es einige theoretische Gründe, die mit linearer Komplementarität zu tun haben. Am interessantesten war jedoch nicht, dass die Lösungen spärlich waren, sondern dass sie oft so spärlich wie möglich waren . Das heißt, wenn Sie ‖ x ‖ 1 minimieren , erhalten Sie in bestimmten nützlichen Fällen tatsächlich die Lösung mit der minimalen Kardinalität. (Wie haben sie das herausgefunden, wenn das Problem der minimalen Kardinalität NP-hart ist? Indem sie künstliche Probleme mit bekannten spärlichen Lösungen konstruierten.) Dies konnte die lineare Komplementaritätstheorie nicht vorhersagen.$\ell_1$$\|x\|_1$$\|x\|_1$

Das Gebiet der komprimierten Abtastung wurde geboren, als die Forscher begannen, Bedingungen auf der Matrix zu identifizieren , die es ihnen ermöglichen würden, im Voraus zu garantieren, dass die ℓ 1- Lösung auch die dünnste war. Siehe zum Beispiel die frühesten Arbeiten von Candés, Romberg und Tao und andere Diskussionen über die Eigenschaft Restricted Isometry ( RIP) . Eine andere nützliche Website, wenn Sie wirklich in eine Theorie eintauchen möchten, ist die komprimierte Erfassungsseite von Terence Tao .$A$$\ell_1$

Wir würden gerne lösen können

$\min \| x \|_{0}$

st

$Ax=b$

Dieses Problem ist jedoch ein kombinatorisches NP-Hard-Optimierungsproblem, das in der Praxis nicht zu lösen ist, wenn , x und b die für die kompressive Abtastung typischen Größen haben. Es ist möglich, effizient zu lösen$A$$x$$b$

$\min \| x \|_{1}$

st

$Ax=b$

$\| x \|_{1}$$\| x \|_{0}$$x$$Ax=b$$\| x \|_{1}$

$Ax=b$$\| Ax - b \|_{2} \leq \delta$

$\min \| Ax - b\|_{2}^{2} + \lambda \| x \|_{1}$

$\ell^1$$\ell^0$

Mit wenigen Messungen können spärliche Signale identifiziert werden.

Bei Compressed Sensing geht es wirklich darum, so wenig Messungen wie möglich durchzuführen , um ein Signal in einer bestimmten Klasse von Signalen zu identifizieren.

Eine einprägsame Phrase ist:

Warum sollte Ihre 5-Megapixel-Kamera wirklich 15 Millionen Werte (drei für jedes Pixel) messen, die Sie 15 Megabyte Daten kosten, wenn sie nur etwa 2 Megabyte (nach der Komprimierung) speichert?
Könnte es möglich sein, die 2 Megabyte sofort zu messen?

Es sind ganz unterschiedliche Frameworks möglich:

• lineare Messungen
• nichtlineare (zB "phasenlose")
• Vektordaten, Matrix- / Tensordaten
• Sparsamkeit als nur die Anzahl der Nicht-Nullen
• sparsity als "low-rank" oder gar "low complex").

Es gibt auch mehr Methoden zur Berechnung von spärlichen Lösungen wie Matching-Verfolgungen (Varianten wie Orthogonal Matching-Verfolgung (OMP), Regularized Orthogonal Matching-Verfolgung (ROMP), CoSaMP) oder neuere Methoden, die auf Message-Passing- Algorithmen basieren .

$\ell^1$$\ell^0$

Wenn man jedoch nur an spärlichen Lösungen für lineare Systeme interessiert ist, tut man etwas, was ich als spärliche Rekonstruktion bezeichnen würde .