Rozwiązanie formy zamkniętej dla problemu lasso, gdy macierz danych jest ukośna

13

nazwa operatora {diag}} Mamy problem:

minwRd(1ni=1n(w,xiyi)2+2λ||w||1),
przy założeniu, że:
i=1nxixiT=diag(σ12,...,σd2).

Czy w tym przypadku istnieje rozwiązanie w formie zamkniętej?

Mam to:

(XTX)1=diag(σ12,...,σd2),
więc myślę, że odpowiedź brzmi :
wj=yjmax{0,1λn|yj|},
dla yj=i=1nyixijσi2 , ale nie jestem pewien.
Arthur D.
źródło

Odpowiedzi:

9

Przejdę do pochodnej @ kardynała rozwiązania lasso zamkniętej postaci, gdy XTX=I , tutaj , z niewielkimi modyfikacjami.

Zakładam, że dla wszystkich . Jest to uzasadnione, ponieważ jeśli mamy to, że ta kolumna ma wartość 0 i myślę, że uzasadnione jest wykluczenie takiego przypadku. Powiem . Zauważ, że oznacza to również, że ma pełną pozycję, a rozwiązanie OLS jest jednoznacznie zdefiniowane.σi2>0iσi2=0iXXTX=DXβ^

Zamierzam również zmodyfikować twoją notację, aby lepiej pasowała do tej w odpowiedzi, do której się odwołuję. W tym celu będę rozwiązywał

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

Jest to identyczne z twoim problemem, ale mogę dodać więcej szczegółów tutaj, jeśli chcesz.

Po pochodnej @ kardynała mamy do rozwiązania

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

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

Biorąc pod uwagę, że rozwiązaniem OLS jest , mamy β^=(XTX)1XTY=D1XTY

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

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

Optymalizujemy każdy osobno, więc możemy rozwiązać każdy okres tej sumy osobno. Oznacza to, że musimy zminimalizować gdzie βjLj

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

Po całkowicie analitycznym argumencie do połączonej odpowiedzi stwierdzamy, że

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

Ponadto więc mamy β^=D1XTYβ^j=XjTYσj2

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

więc okazuje się, że predyktor jest dokładnie wtedy, gdy zrobiłby to, gdyby macierz projektowa była ortonormalna, a nie tylko ortogonalna. Widzimy więc, że w tym przypadku przy wybór zmiennych nie różni się od tego, jeśli , ale rzeczywiste współczynniki są skalowane zgodnie z wariancjami predyktora.XjXTX=DIXTX=Iβ^λ

Na koniec to rozwiązanie na podobne do twojego, co oznacza, że ​​musimy pomnożyć przez coś, aby uzyskać . Jeśli mamy to β^β^λ(β^λ)j0

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

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

od .a|a|=sgn(a)

Zwracając uwagę, że dokładnie wtedy, gdy (β^λ)j=0

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

widzimy, że możemy alternatywnie wyrazić jako β^λ

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

Jest to więc bardzo zbliżone do tego, co miałeś, ale nie dokładnie takie samo.

Zawsze lubię porównywać takie pochodne z dobrze znanymi bibliotekami, jeśli to możliwe, więc oto przykład w 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
źródło