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$
2
  • $\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$ Jan 18, 2017 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$ Jan 18, 2017 at 22:15

1 Answer 1

4
$\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$
2
  • $\begingroup$ Neat. Do you think that there isn't a closed-form solution? $\endgroup$ Jan 18, 2017 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$ Jan 18, 2017 at 1:05

Your Answer

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

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