Solução de formulário fechado para o problema do laço quando a matriz de dados é diagonal

13

Temos o problema: supondo que: \ 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).

Existe uma solução fechada neste caso?

Eu tenho isso:

(XTX)1=diag(σ12,...,σd2),
e , portanto, acho que a resposta é :
wj=yjmax{0,1λn|yj|},
para yj=i=1nyixijσi2 , mas não tenho certeza.
Arthur D.
fonte

Respostas:

9

Vou passar pela derivação do @ cardinal da solução de laço de forma fechada quando , encontrado aqui , com pequenas modificações.XTX=I

que para todos . Isso é justificado porque, se tivermos um , isso nos diz que a ésima coluna de é toda 0, e acho razoável excluir um caso desse tipo. Vou deixá- . Observe que isso também significa quei σ 2 i = 0 i X X T X = D X βσi2>0iσi2=0iXXTX=DX é a classificação completa e a solução OLS é definida exclusivamente.β^

Também vou modificar sua notação para corresponder melhor à resposta que estou referenciando. Para esse fim, eu vou resolver

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

Isso é idêntico ao seu problema, mas posso adicionar mais detalhes aqui, se desejar.

Após a derivação do @ cardinal, temos que resolver

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

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

Observando que a solução OLS é , temos esse β X=argmin  - β TDβ+1β^=(XTX)1XTY=D1XTY

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

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

Estamos otimizando cada separadamente, para que possamos resolver cada termo dessa soma separadamente. Isso significa que precisamos minimizar onde βjLj

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

Após um argumento completamente análogo à resposta vinculada, descobrimos que

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

Além disso, portanto temos isso β^=D1XTYβ^j=XjTYσj2

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

portanto, um preditor é zerado exatamente quando ocorreria se a matriz de design fosse ortonormal, não apenas ortogonal. Portanto, podemos ver que, neste caso com , a seleção de variáveis ​​não é diferente de se , mas os coeficientes reais são dimensionados de acordo com as variações do preditor.XjXTX=DIXTX=Iβ^λ

Como observação final, vou transformar essa solução em uma que se assemelhe à sua, o que significa que precisamos multiplicar por algo para obter . Se , temos esse β^β^λ(β^λ)j0

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

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

desdea|a|=sgn(a) .

Observando que exatamente quando (β^λ)j=0

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

vemos que podemos alternativamente expressar como β^λ

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

Portanto, isso é muito próximo do que você tinha, mas não exatamente o mesmo.

Eu sempre gosto de verificar derivações como essa em bibliotecas conhecidas, se possível, então aqui está um exemplo em 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
fonte