5
$\begingroup$

Suppose I want to perform ridge-regularized linear regression, except that we shrink the coefficients to a nonzero matrix: $$ W^* = \arg\min_W \|Y - X W \|^2_2 + \lambda\|W-W_0\|^2_2. $$ However, I want to use a solver that expects to solve the standard ridge regression problem $$ \min \|Y - X W \|^2_2 + \lambda\|W\|^2_2. $$ Is there a way to reduce my problem to the standard form?

One option would obviously be to solve the original problem directly. Another option would be to perform the change of variables $W_\Delta = W - W_0$, which leads to $$ W^* = W_0 + \arg\min_{W_\Delta} \|(Y-XW_0) - X W_\Delta\|^2_2 + \lambda \|W_\Delta\|^2_2. $$ But suppose I'm (for no good reason, honestly) stubborn and don't want to have to add back in $W_0$ to the argmin of the ridge regression objective. Is there a way to do this?

$\endgroup$

2 Answers 2

4
$\begingroup$

Consider rewriting the objective as:

\begin{align} &\quad \|y - X w \|^2_2 + \lambda\|w-\mu\|^2_2 \\ &= y^Ty + w^T X^TXw -2 y^T Xw + \lambda(\mu^T\mu + w^T w - 2\mu^T w) \\ &= w^T (X^TX + \lambda I)w - 2(y^TX + \lambda\mu^T)w + c \end{align}

Now we can concatenate $\sqrt{\lambda} I$ onto $X$ to form $X'$ such that $X'^T X' = X^TX + \lambda I$. (If $X$ is an $n \times d$ matrix, then $X'$ will be an $n\!+\!d \times d$ matrix.) Likewise, concatenate $\sqrt{\lambda} \mu$ onto $y$ to form $y'$ such that $y'^T X' = y^TX + \lambda \mu^T$. So now we've reduced the problem to ordinary least squares:

$$\|y' - X' w \|^2_2$$

$\endgroup$
1
$\begingroup$

In addition to @shimao's answer, here's another approach (also assuming univariate $y \in R^{n}, X \in R^{n \times d}$ for simplicity). Using the identity derived by @shimao, \begin{align} \quad \|y - X w \|^2_2 + \lambda\|w-\mu\|^2_2 = w^T (X^TX + \lambda I)w - 2(y^TX + \lambda\mu^T)w + c, \end{align} we can also construct $\tilde{X}$ via Cholesky factorization, rather than concatenation. You find lower Cholesky factor $L$ of the following $$ L L^T = X^T X + \lambda I_d. $$ Then $\tilde{X} = L^T$, a $d \times d$ upper triangular matrix. We want $\tilde{X}^T \tilde{y} = X^T y + \lambda \mu$, so we solve

$$ \tilde{y} = L^{-1} \Big(X^T y + \lambda \mu\Big) $$ Since $L$ is lower-triangular, this can be obtained via forward substitution.

@shimao's solution is better for general usage, since it requires no Cholesky factorization or forward substitution.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.