Compressed Sensing-Beziehung zur L1-Regularisierung

Ich verstehe , dass die Drucksensor sparsamsten Lösung findet wobei , und , .

y = A x

$y = Ax$

x \in R^{D}

$x \in \mathbb{R}^D$

A \in R^{k \times D}

$A \in \mathbb{R}^{k \times D}$

y \in R^{k}

$y \in \mathbb{R}^{k}$

k << D

$k << 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 $l_0$ -Norm für Vektoren verstanden werden.

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

Ich habe gelesen, dass die komprimierte Wahrnehmung der Regression mit einer Lasso-Strafe ähnelt ( $l_1$ ). 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 $l_1$ -Norm?

lasso sparse 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

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:

$\text{arg min}_x \frac{1}{2}\|Ax - b\| + \lambda \|x\|_1$

während das Lasso [2] dieses Problem ist

$\text{arg min}_{\beta} \frac{1}{2}\|y - X\beta\| + \lambda \|\beta\|_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". $A$ $X$ $A$ $X$

[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?

m i n ‖ x ‖_{1}

$min \| x \|_1$

A x = b

$Ax=b$

‖ A x - b ‖ + λ ‖ x ‖_{1}

$\|Ax - b \| + \lambda \| x \|_1$

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).

λ \to 0

$\lambda \to 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?

‖ X w - y ‖^{2} + λ ‖ w ‖_{0}

$\| Xw - y \|^2 + \lambda \| w \|_0$

‖ X w - y ‖^{2} + λ ‖ w ‖_{1}

$\| Xw - y \|^2 + \lambda \| w \|_1$

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

Hier ist die andere Frage: stats.stackexchange.com/questions/337113/…

Charlie Parker

Compressed Sensing-Beziehung zur L1-Regularisierung

Antworten: