3
$\begingroup$

The accepted answer in this thread does a great job of showing that there is a one-to-one correspondence between $c$ and $\lambda$ in the two formulations of the ridge regression: $$ \underset{\beta}{min}(y-X\beta)^T(y-X\beta) + \lambda\beta^T\beta $$ and $$ \underset{\beta}{min}(y-X\beta)^T(y-X\beta) \text{ s.t. }\beta^T\beta\leq{c} $$

The linked answer shows this in the orthogonal case.

In a general (non-orthogonal case), how can I compute $\lambda$ from $c$?

Update Here is an answer for going from $\lambda$ to $c$:

Assuming that the coefs are constrained by the penalty, $$ \beta^T\beta = c $$ and $$ \beta = (X^TX + \lambda I)^{-1}X^Ty\\ \beta^T\beta = c = \beta^T(X^TX + \lambda I)^{-1}X^Ty $$

Still working on going the other way

$\endgroup$
  • $\begingroup$ On your last two lines, it should be a $\lambda I$, the scalar $\lambda$ times the identity matrix $I$. Going from $\lambda$ to $c$ is easy. Going the other direction, I don't think there's a simple, closed form solution. $\endgroup$ – Matthew Gunn Jan 18 '17 at 21:55
  • $\begingroup$ Isn't it? Fooling around it looks possible but messy. Don't have time to check my work just now though... $\endgroup$ – generic_user Jan 18 '17 at 22:15
3
$\begingroup$

Form the Lagrangian

$$ (\mathbf{y} - X \mathbf{B})'(\mathbf{y} - X \mathbf{B}) + \lambda (\mathbf{b}'\mathbf{b} - c)$$

Your $\lambda$ for the first problem is essentially the same $\lambda$ that's a Lagrange multiplier in the second problem.

If you solve the second problem, using some convex optimization software, you should be able to get the Lagrange multiplier (aka dual variable) associated with the constraint $\mathbf{b}'\mathbf{b} \leq c$.

Eg. for the CVX software package, search down this page until you get to the section on dual variables.

Towards a closed form solution...

Combining the first order conditions (see comments), you get:

\begin{align*} c &= \mathbf{y}'X\left(X'X + \lambda I \right)^{-2}X'\mathbf{y} \\ &= \mathbf{y}'X\left(Q \Lambda Q^{-1} + \lambda QQ^{-1} \right)^{-2}X'\mathbf{y} \quad \quad \text{by applying eigenvalue decomposition} \\ &= \mathbf{y}'X\left[Q \left( \Lambda + \lambda I \right) Q^{-1} \right]^{-2}X'\mathbf{y}\\ &= \mathbf{y}'X Q \left( \Lambda + \lambda I \right)^{-2} Q^{-1}X'\mathbf{y} \end{align*}

Let $\mathbf{w} = Q^{-1} X'\mathbf{y}$. Then $$ c = \mathbf{w'} \left( \Lambda + \lambda I \right) ^{-2} \mathbf{w} $$

Where $Q\Lambda Q^{-1} = X'X$ is the eigenvalue decomposition of $X'X$ and $\Lambda_i$ is the $i$th element of diagonal matrix $\Lambda$. (I think this is right, but I haven't checked my work.)

$$ c = \sum_i \frac{w_i^2}{\left( \Lambda_i + \lambda \right) ^2} $$

Then solving for $\lambda$ from $c$ looks like a polynomial mess?

$\endgroup$
  • $\begingroup$ Neat. Do you think that there isn't a closed-form solution? $\endgroup$ – generic_user Jan 18 '17 at 0:05
  • 3
    $\begingroup$ The first order conditions $X'\mathbf{y} = (X'X + \lambda I) \mathbf{b}$ and $\mathbf{b}'\mathbf{b} = c$. Solve that system and you have the answer. $\endgroup$ – Matthew Gunn Jan 18 '17 at 1:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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