Lösung des Lasso-Problems in geschlossener Form, wenn die Datenmatrix diagonal ist

13

Wir haben das Problem: mit der Annahme, dass: \ sum_ {i = 1} ^ nx_ix_i ^ T = \ diag (\ sigma_1 ^ 2, ..., \ sigma_d ^ 2).

minwRd(1ni=1n(w,xiyi)2+2λ||w||1),
i=1nxixiT=diag(σ12,...,σd2).

Gibt es in diesem Fall eine geschlossene Lösung?

Ich habe folgendes:

(XTX)1=diag(σ12,...,σd2),
und daher denke ich, dass die Antwort lautet :
wj=yjmax{0,1λn|yj|},
für yj=i=1nyixijσi2 , aber ich bin nicht sicher.
Arthur D.
quelle

Antworten:

9

Ich werde @ cardinals Herleitung der Lasso-Lösung in geschlossener Form durchgehen, wenn , hier gefunden , mit geringfügigen Änderungen.XTX=I

Ich gehe davon aus, dass für alle . Dies ist gerechtfertigt, weil, wenn wir ein dies uns sagt, dass dasi & sgr; 2 i = 0 i X X T X = D X βσi2>0iσi2=0i te Spalte von alle 0 ist, und ich denke, es ist vernünftig, einen solchen Fall auszuschließen. Ich lasse . Beachten Sie, dass dies auch bedeutet, dass vollen Rang hat und die OLS-Lösung eindeutig definiert ist.XXTX=DXβ^

Ich werde auch Ihre Notation so ändern, dass sie der Antwort, auf die ich verweise, besser entspricht. Zu diesem Zweck werde ich

β^λ=argminβRp12||YXβ||22+λ||β||1.

Dies ist identisch mit Ihrem Problem, aber ich kann hier weitere Details hinzufügen, wenn Sie möchten.

Nach der Herleitung von @ cardinal müssen wir lösen.

β^λ=argmin 12(YTY2YTXβ+βTXTXβ)+λ||β||1

=argmin YTXβ+12βTDβ+λ||β||1.

Festzustellen, dass die OLS-Lösung ist β & lgr;=argmin  - β TDβ+1β^=(XTX)1XTY=D1XTY , haben wir

β^λ=argmin β^TDβ+12βTDβ+λ||β||1

=argmin j=1pβ^jβjσj2+σj22βj2+λ|βj|.

Wir optimieren jedes separat, damit wir jeden Term dieser Summe separat lösen können. Das heißt, wir müssen minimierenL j L j = - β j β j σ 2 j + σ 2 jβjLj mit

Lj=β^jβjσj2+σj22βj2+λ|βj|.

Nach einem völlig analogen Argument zur verknüpften Antwort finden wir das

(β^λ)j=sgn(β^j)(|β^j|λσj2)+.

Außerdemβ^=D1XTYβ^j=XjTYσj2 sodass wir das

(|β^j|λσj2)+=1σj2(|XjTY|λ)+

es stellt sich also heraus, dass ein Prädiktor genau dann auf Null gesetzt wird, wenn die Entwurfsmatrix orthonormal und nicht nur orthogonal wäre. Wir können also sehen, dass in diesem Fall mit die Variablenauswahl nicht anders ist als mitXjXTX=DIXTX=I , aber die tatsächlichen Koeffizienten werden gemäß den Prädiktorvarianzen skaliert.β^λ

Abschließend möchte ich diese Lösung in eine Lösung umwandeln, die Ihrer ähnelt. Dies bedeutet, dass wir mit etwas multiplizieren müssen, um . Ifβ^β^λ(β^λ)j0 dann haben wir das

(β^λ)j=sgn(β^j)(|β^j|λσj2)=β^jsgn(β^j)λσj2

=β^j(1λσj2|β^j|)

schon seit a|a|=sgn(a) .

Beachten Sie, dass genau wann (β^λ)j=0

|β^j|λσj20|β^j|λσj21λσj2|β^j|1λσj2|β^j|0,

wir sehen, dass wir alternativ als β^λ

(β^λ)j=β^j(1λσj2|β^j|)+.

Das kommt dem sehr nahe, was du hattest, ist aber nicht genau dasselbe.

Ich mag es immer, solche Ableitungen mit bekannten Bibliotheken abzugleichen, also hier ein Beispiel in R:

## generating `x`
set.seed(1)
n = 1000
p = 5
sigma2s = 1:p
x = svd(matrix(rnorm(n * p), n, p))$u %*% diag(sqrt(sigma2s))

## check this
# t(x) %*% x

## generating `y`
betas = 1:p
y = x %*% betas + rnorm(nrow(x), 0, .5)

lambda = 2

## using a well-known library to fit lasso
library(penalized)
penalized(y, x, lambda1 = lambda)@penalized


## using closed form solution
betahat = lm(y ~ x - 1)$coef
ifelse(betahat > 0, 1, -1) * sapply(abs(betahat) - lambda / sigma2s, function(v) max(c(0, v)))
jld
quelle