# Derivation of closed form lasso solution

For the lasso problem $\min_\beta (Y-X\beta)^T(Y-X\beta)$ such that $\|\beta\|_1 \leq t$. I often see the soft-thresholding result $$\beta_j^{\text{lasso}}= \mathrm{sgn}(\beta^{\text{LS}}_j)(|\beta_j^{\text{LS}}|-\gamma)^+$$ for the orthonormal $X$ case. It is claimed that the solution can be "easily shown" to be such, but I've never seen a worked solution. Has anyone seen one or perhaps has done the derivation?

• This seems slightly confused. At the beginning you assume a constraint $t$ and in the solution you introduce a parameter $\gamma$. I'm guessing you intend these two to be related via the dual problem, but maybe you can make clear what you are looking for. Nov 1, 2011 at 0:41
• Partially responding to @cardinal, finding the $\beta$ that minimizes $(Y-X\beta )'(Y-X\beta )$ subject to $\|\beta\|_1 \leq t$ is equivalent to finding the $\beta$ that minimizes $(Y-X\beta )'(Y-X\beta )+\gamma\sum_j |\beta_j |$. There is a 1-1 relationship between $t$ and $\gamma$. To 'easily' see why the soft-thresholding result is so, I'd recommend solving the second expression (in my comment).
– user5594
Nov 1, 2011 at 1:12
• Another note, when finding the $\beta$ that minimizes $(Y-X\beta )'(Y-X\beta )+\gamma\sum_j |\beta_j |$, break the problem up into the cases $\beta_j >0$, $\beta_j<0$, and $\beta=0$.
– user5594
Nov 1, 2011 at 1:19
• @cardinal Ah yes, 1-1 is incorrect. Correction: for every $t\geq0$, you can find a $\gamma\geq 0$.
– user5594
Nov 1, 2011 at 1:31
• Thanks for a great discussion! I came across this video on coursera - Deriving the lasso coordinate descent update, that is very relevant to this discussion, and walks through the solution very elegantly. Might be helpful for future visitors :-) May 14, 2016 at 13:26

This can be attacked in a number of ways, including fairly economical approaches via the Karush–Kuhn–Tucker conditions.

Below is a quite elementary alternative argument.

The least squares solution for an orthogonal design


Some equivalent problems

Via the Lagrangian form, it is straightforward to see that an equivalent problem to that considered in the question is $$\min_\beta \frac{1}{2} \|y - X \beta\|_2^2 + \gamma \|\beta\|_1 \>.$$

Expanding out the first term we get $\frac{1}{2} y^T y - y^T X \beta + \frac{1}{2}\beta^T \beta$ and since $y^T y$ does not contain any of the variables of interest, we can discard it and consider yet another equivalent problem, $$\min_\beta (- y^T X \beta + \frac{1}{2} \|\beta\|^2) + \gamma \|\beta\|_1 \>.$$

Noting that $\bls = X^T y$, the previous problem can be rewritten as $$\min_\beta \sum_{i=1}^p - \bls_i \beta_i + \frac{1}{2} \beta_i^2 + \gamma |\beta_i| \> .$$

Our objective function is now a sum of objectives, each corresponding to a separate variable $\beta_i$, so they may each be solved individually.

The whole is equal to the sum of its parts

Fix a certain $i$. Then, we want to minimize $$\mathcal L_i = -\bls_i \beta_i + \frac{1}{2}\beta_i^2 + \gamma |\beta_i| \> .$$

If $\bls_i > 0$, then we must have $\beta_i \geq 0$ since otherwise we could flip its sign and get a lower value for the objective function. Likewise if $\bls_i < 0$, then we must choose $\beta_i \leq 0$.

Case 1: $\bls_i > 0$. Since $\beta_i \geq 0$, $$\mathcal L_i = -\bls_i \beta_i + \frac{1}{2}\beta_i^2 + \gamma \beta_i \> ,$$ and differentiating this with respect to $\beta_i$ and setting equal to zero, we get $\beta_i = \bls_i - \gamma$ and this is only feasible if the right-hand side is nonnegative, so in this case the actual solution is $$\blasso_i = (\bls_i - \gamma)^+ = \mathrm{sgn}(\bls_i)(|\bls_i| - \gamma)^+ \>.$$

Case 2: $\bls_i \leq 0$. This implies we must have $\beta_i \leq 0$ and so $$\mathcal L_i = -\bls_i \beta_i + \frac{1}{2}\beta_i^2 - \gamma \beta_i \> .$$ Differentiating with respect to $\beta_i$ and setting equal to zero, we get $\beta_i = \bls_i + \gamma = \mathrm{sgn}(\bls_i)(|\bls_i| - \gamma)$. But, again, to ensure this is feasible, we need $\beta_i \leq 0$, which is achieved by taking $$\blasso_i = \mathrm{sgn}(\bls_i)(|\bls_i| - \gamma)^+ \>.$$

In both cases, we get the desired form, and so we are done.

Final remarks

Note that as $\gamma$ increases, then each of the $|\blasso_i|$ necessarily decreases, hence so does $\|\blasso\|_1$. When $\gamma = 0$, we recover the OLS solutions, and, for $\gamma > \max_i |\bls_i|$, we obtain $\blasso_i = 0$ for all $i$.

• +1 The entire second half can be replaced by the simple observation that the objective function $\beta\to\frac{1}{2}\beta^2+(\pm\gamma-\hat{\beta})\beta$ is a union of parts of two convex parabolas with vertices at $\pm\gamma-\hat{\beta}$, where the negative sign is taken for $\beta\lt 0$ and the positive otherwise. The formula is just a fancy way of choosing the lower vertex.
– whuber
Nov 1, 2011 at 3:12
• If possible, I would like to see the derivations using the KKT-optimality conditions. What other ways are there to derive this result? Nov 10, 2012 at 20:23
• @Cardinal: thanks for a nice derivation. One observation. If I recall, matrix with orthogonal columns is not the same as an orthogonal (aka orthonormal) matrix. Then $X'X=D$ for some diagonal matrix $D$ (not necessarily identity matrix). With orthogonal matrix assumption (as is in the original question), we do have $X'X=I$ and all looks great :) Nov 2, 2013 at 21:25
• @cardinal I don't get why you say "since otherwise we could flip its sign and get a lower value for the objective function". We are taking the derivative of the objective function. So what if the objective function is higher or lower, who cares. All we care about is the derivative is set to zero, we care about the extrema. Whether it's higher or lower by a constant does not affect the argmin. Jan 16, 2018 at 3:20
• @whuber that's not what I meant. I cant see why this soft thresholding gives us the vertex of the lower parabola. Can you explain it please? Jun 7, 2021 at 4:34

Assume that the covariates $x_j$, the columns of $X \in \mathbb{R}^{n \times p}$, are also standardized so that $X^T X = I$. This is just for convenience later: without it, the notation just gets heavier since $X^T X$ is only diagonal. Further assume that $n \geq p$. This is a necessary assumption for the result to hold. Define the least squares estimator $\hat\beta_{OLS} = \arg\min_\beta \|y - X \beta\|_2^2$. Then, the (Lagrangian form of the) lasso estimator \begin{align*} \hat\beta_\lambda & = \arg\min_{\beta} \frac{1}{2n} \|y - X \beta\|_2^2 + \lambda \|\beta\|_1 \tag{defn.} \\ & = \arg\min_\beta \frac{1}{2n} \|X \hat\beta_{OLS} - X \beta\|_2^2 + \lambda \|\beta\|_1 \tag{OLS is projection} \\ & = \arg\min_\beta \frac{1}{2n} \|\hat\beta_{OLS} - \beta\|_2^2 + \lambda \|\beta\|_1 \tag{$X^TX=I$} \\ & = \arg\min_\beta \frac{1}{2} \|\hat\beta_{OLS} - \beta\|_2^2 + n \lambda \|\beta\|_1 \tag{algebra} \\ & = \mathrm{prox}_{n \lambda \|\cdot\|_1} \left( \hat\beta_{OLS} \right) \tag{defn.} \\ & = S_{n \lambda} \left( \hat\beta_{OLS} \right) \tag{takes some work}, \end{align*} where $\mathrm{prox}_f$ is the proximal operator of a function $f$ and $S_{\alpha}$ soft thresholds by the amount $\alpha$.

This is a derivation that skips the detailed derivation of the proximal operator that Cardinal works out, but, I hope, clarifies the main steps that make possible a closed form.

• what happens if we don't have $X$ being orthonormal? Oct 8, 2021 at 14:18
• @CharlieParker In practice, I usually the QR transform. So $X = QR$ then $X \beta$ becomes $Q \hat{\beta}$ with $\hat{\beta} = R \beta$. Then, at the end, transform back and check that the original $\beta$ has the sparsity you want. If not, increase $\lambda$ and repeat. Usually, I just find a $\lambda$ that tends to work for my dataset, set it, and deploy. I like the coordinate descent implementation because it can be done in a distributed manner, and oftentimes can be interrupted while still giving me a workable answer. Feb 23 at 16:38