Решение замкнутой формы задачи Лассо, когда матрица данных диагональна

13

У нас проблема: при условии, что: \ sum_ {я = 1} ^ nx_ix_i ^ T = \ диаг (\ sigma_1 ^ 2, ..., \ sigma_d ^ 2).

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

Есть ли в этом случае решение в замкнутой форме?

У меня есть это:

(XTX)1=diag(σ12,...,σd2),
и поэтому я думаю, что ответ :
весJзнак равноYJМаксимум{0,1-λN|YJ|},
для YJзнак равноΣязнак равно1NYяИксяJσя2 , но я не уверен.
Артур Д.
источник

Ответы:

9

Я собираюсь пройти через вывод @ cardinal решения Лассо в замкнутой форме, когда , найденный здесь , с небольшими изменениями.XTX=I

Я буду предполагать, что для всех . Это оправдано, потому что если у нас есть то это говорит о том, что й столбец равен 0, и я думаю, что разумно исключить такой случай. Я позволю . Обратите внимание, что это также означает, что имеет полный ранг, а решение OLS определено однозначно.я сг 2 я = 0 я Х Х Т Х = Д Х βσi2>0iσi2=0iXXTX=DXβ^

Я также собираюсь изменить вашу запись, чтобы она лучше соответствовала ответу, на который я ссылаюсь. С этой целью я буду решать

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

Это идентично вашей проблеме, но я могу добавить больше подробностей здесь, если хотите.

После деривации @ cardinal у нас есть, что нам нужно решить

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

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

Отмечая, что решение OLS - это , у нас есть β^=(XTX)1XTY=D1XTY

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

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

Мы оптимизируем по каждому отдельно, поэтому мы можем решить каждый член этой суммы отдельно. Это означает, что нам нужно минимизировать где βjLj

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

Следуя совершенно анало гичному аргументу к связанному ответу, мы находим, что

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

Кроме того, поэтому у нас есть β^=D1XTYβ^j=XjTYσj2

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

так получается, что предиктор обнуляется именно тогда, когда он был бы, если матрица дизайна была ортонормированной, а не просто ортогональной. Таким образом, мы можем видеть, что в этом случае при выбор переменной не отличается от того, если , но фактические коэффициенты масштабируются в соответствии с дисперсиями предикторов.XjXTX=DIXTX=Iβ^λ

В завершение я превращу это решение в решение, похожее на ваше, что означает, что нам нужно умножить на что-то, чтобы получить . Если то у нас есть это β^β^λ(β^λ)j0

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

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

так как .a|a|=sgn(a)

Отмечая, что точно, когда (β^λ)j=0

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

мы видим, что мы можем альтернативно выразить как β^λ

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

Так что это очень близко к тому, что вы имели, но не совсем то же самое.

Мне всегда нравится проверять подобные деривации в известных библиотеках, если это возможно, поэтому вот пример в 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
источник