Compressed Sensing-Beziehung zur L1-Regularisierung

8

Ich verstehe , dass die Drucksensor sparsamsten Lösung findet wobei x R D , A R k × D und y R k , k < < D .

y=Ax
xRDARk×DyRkk<<D

Auf diese Weise können wir x (das Original) mit y (der Komprimierung) relativ schnell rekonstruieren . Wir sagen, dass x die spärlichste Lösung ist. Sparsity kann als l0 -Norm für Vektoren verstanden werden.

Wir wissen auch, dass die l1 -Norm (lösbar mit linearer Programmierung) eine gute Annäherung an die l0 -Norm ist (die für große Vektoren NP-hart ist). Daher ist x auch die kleinste l1 -Lösung für Ax=y

Ich habe gelesen, dass die komprimierte Wahrnehmung der Regression mit einer Lasso-Strafe ähnelt ( l1 ). Ich habe auch geometrische Interpretationen davon gesehen, aber ich habe die Verbindung nicht mathematisch hergestellt.

Welche Beziehung besteht (komprimiert) zwischen Komprimierung und Lasso, abgesehen von der Minimierung der l1 -Norm?

ilanman
quelle
Verwandte: quora.com/…
Charlie Parker
Nach meinem Verständnis ist Compressed Sensing das Gebiet, in dem die Wiederherstellung spärlicher Signale untersucht wird, und die L1-Regularisierung ist nur eine spezifische Formulierung, um sie näherungsweise zu lösen.
Charlie Parker

Antworten:

6

Es gibt im Wesentlichen keinen Unterschied. Es ist nur die Terminologie eines Statistikers im Vergleich zur Terminologie eines Elektrotechnikers.

Compressed Sensing (genauer gesagt, Basisverfolgung Entrauschen [1]) ist dieses Problem:

arg minx12Axb+λx1

während das Lasso [2] dieses Problem ist

arg minβ12yXβ+λβ1

Da es einen Unterschied gibt, können Sie (der Ingenieur) in Compressed Sensing-Anwendungen auswählen , um sich "gut zu benehmen", während Sie (der Statistiker) für das Lasso nicht wählen müssen und müssen beschäftigen sich mit was auch immer die Daten sind (und sie sind selten "nett" ...). Folglich konzentrierte sich Großteil der nachfolgenden Compressed-Sensing-Literatur darauf, so "effizient" wie möglich zu wählen , während sich ein Großteil der nachfolgenden statistischen Literatur auf Verbesserungen des Lassos konzentrierte, die immer noch mit funktionieren und das Lasso "brechen".AXAX

[1] SS Chen, DL Donoho, MA Saunders. "Atomzerlegung durch Basisverfolgung." SIAM Journal on Scientific Computing 20 (1), S. 33-61, 1998. https://doi.org/10.1137/S1064827596304010

[2] R. Tibshirani "Schrumpfung und Selektion der Regression über das Lasso." Zeitschrift der Royal Statistical Society: Reihe B 58 (1), S. 267–88, 1996. JSTOR 2346178.

mweylandt
quelle
Normalerweise wird die komprimierte Erfassung jedoch als formuliert so dass . Entspricht das wirklich min von wenn ja warum und wie fällt Lambda in das Originalbild? minx1Ax=bAxb+λx1
Charlie Parker
Die Formulierung, die Sie (mit der Gleichheitsbeschränkung) geben, ist die "Grenze" in gewissem Sinne als . Es entsteht, wenn Sie davon ausgehen, dass das System kein Rauschen enthält (daher wird es häufig als "Basisverfolgung" im Gegensatz zu "Basisverfolgungsentrauschung" bezeichnet). λ0
Mweylandt
etwas, das mich verwirrt, ist, dass ich Verfolgungsmethoden anpasse, bei denen gierige Algorithmen (ungefähr) lösen . Aber ich dachte , weiche Schwellwerte Algorithmen , wo genau Solver zur konvexen Entspannung Formulierung . Wenn dies wahr ist, würden sie dann zu derselben Lösung führen? dh es scheint, dass Lasso und OM das gleiche Problem lösen, jedoch mit einer sehr unterschiedlichen Formulierung. Jeder Algorithmus für LASSO liefert die gleiche Lösung, da sein konvexer Put, wenn OM ein gieriger Algorithmus für L0 ist, ich würde annehmen, dass sie sehr unterschiedlich sind. Ist das richtig? Xwy2+λw0Xwy2+λw1
Charlie Parker
Ich denke, das ist es wert, in einer separaten Frage gestellt zu werden. Im Allgemeinen sind die Lösungen L1 (Lasso) und L0 (beste Teilmengen) unterschiedlich. Es gibt jedoch spezielle, gut untersuchte Umstände, unter denen die L0- und L1-Versionen des Basisverfolgungsproblems (nicht Basisverfolgungsgeräusche) dieselbe Lösung bieten.
Mweylandt
1
Hier ist die andere Frage: stats.stackexchange.com/questions/337113/…
Charlie Parker