Let $A: \mathbb{R}^{p} \rightarrow \mathbb{R}^{n}$ and $y \in \mathbb{R}^{p}$. Consider the following regularization problem:

\[\newcommand{\norm}[1]{\left\lVert#1\right\rVert} \begin{equation} \min_{x \in \mathbb{R}^{n}} \frac{1}{2} \norm{Ax - y}_{2}^{2} + \alpha \norm{x}_{1}. \label{eq:min-problem} \end{equation}\]This type of penalized regression is known as Lasso, see Tibshirani’s original paper (Tibshirani, 1996). It belongs to a more general type of regularization known as Tikhonov regularization (Tikhonov & Arsenin, 1977).

In this post, we first derive the dual problem, then show that the solution $x^{*}$ can be determined with the help of a projection operator. Under the assumption that $A^{-1}$ exists, the solution $x^{*}$ can be further expressed in terms of a mapping $\left(A^{T}\right)^{-1}$ from the dual space as a function of $y$. This is illustrated in Figure 1.

## Table of contents

- Formulation of the dual problem
- Solution of the dual problem
- Solution of the primal problem
- References

## Formulation of the dual problem

To derive the dual problem, introduce a dummy variable $z \in \mathbb{R}^{n}$

\[z = Ax\]and reformulate the minimization problem in \eqref{eq:min-problem} as a constrained problem P:

\[\begin{align*} \label{eq:primal-problem} \tag{P} &\underset{z \in \mathbb{R}^{n}, \, x \in \mathbb{R}^{p}}{\text{minimize}} \quad \frac{1}{2} \norm{y - z}_{2}^{2} + \alpha \norm{x}_{1} \\ &\text{subject to } \quad z = Ax \end{align*}\]Then, construct the Lagrangian by introducing the dual variable $p \in \mathbb{R}^{n}$, containing $n$ Lagrange multipliers:

\[L(x, z, p) = \frac{1}{2} \norm{y - z}_{2}^{2} + \alpha \norm{x}_{1} + p^{T} (z - Ax).\]The dual objective function is:

\[g(p) = \min_{z \in \mathbb{R}^{n}, \, x \in \mathbb{R}^{p}} \left\lbrace \frac{1}{2} \norm{y - z}_{2}^{2} + \alpha \norm{x}_{1} + p^{T} (z - Ax) \right\rbrace\]We will split the terms depending on $z$ and $x$ and minimize each part separately:

\[\begin{align*} g(p) &= \min_{z \in \mathbb{R}^{n}, \, x \in \mathbb{R}^{p}} \left\lbrace \frac{1}{2} \norm{y}_{2}^{2} - y^{T}z + \frac{1}{2} \norm{z}_{2}^{2} + p^{T}z + \alpha \norm{x}_{1} - p^{T}Ax \right\rbrace \\[.5em] &= \min_{z \in \mathbb{R}^{n}} \left\lbrace \frac{1}{2} \norm{y}_{2}^{2} - (y - p)^{T}z + \frac{1}{2} \norm{z}_{2}^{2} \right\rbrace + \max_{x \in \mathbb{R}^{p}} \left\lbrace \alpha \norm{x}_{1} - (A^{T}p)^{T}x \right\rbrace \end{align*}\]The stationarity condition says that at the optimal point, the subgradient of $L(x, z, p)$ with respect to $x$ and $z$ must contain 0. For the first part, since $L(x, z, p)$ is differentiable in $z$, the subgradient with respect to $z$ equals the gradient. By taking $\frac{\partial}{\partial z} L(x, z, p)$ and setting it to $0$, we get the stationarity condition:

\[z = y - p^{*}\]Plugging this into the first part, yields:

\[\frac{1}{2}\norm{y}_{2}^{2} - (y - p^{*})^{T}(y - p^{*}) + \frac{1}{2}\norm{y - p^{*}}_{2}^{2} = \frac{1}{2}\norm{y}_{2}^{2} - \frac{1}{2}\norm{y - p^{*}}_{2}^{2}.\]For the second part, because $\alpha \norm{x}_1$ is a non-differentiable function of $x$, we need to compute the subdifferential $\partial (\alpha \norm{x}_1)$.

From the rules for the subgradient, see (Boyd & Vandenberghe, 2008), we can derive that the $\partial \norm{x}_{1}$ can be expressed as follows:

\[\partial (\norm{x}_{1}) = \lbrace g : \norm{g}_{\infty} \leq 1, g^{T} x = \norm{x}_{1} \rbrace.\]Furthermore, by using the rule for scalar multiplication:

\[\partial (\alpha\norm{x}_{1}) = \lbrace g : \norm{g}_{\infty} \leq \alpha, g^{T} x = \alpha\norm{x}_{1} \rbrace\]we get the following stationarity condition:

\[g = A^{T}p \in \partial \alpha \norm{x}_{1}\]when

\[\begin{align*} \norm{A^{T}p}_{\infty} &\leq \alpha \\[.5em] \alpha \norm{x}_{1} &= (A^{T}p)^{T}x. \end{align*}\]Therefore, the dual problem D is:

\[\begin{align*} \label{eq:dual-problem} \tag{D} &\max_{p \in \mathbb{R}^{n} } \, \frac{1}{2}\norm{y}_{2}^{2} - \frac{1}{2}\norm{y - p}_{2}^{2} \\[.5em] &\text{subject to } \, \norm{A^{T}p}_{\infty} \leq \alpha \end{align*}\]## Solution of the dual problem

The solution $p^{*}$ of the dual problem will be determined with the help of a projection operator. Looking at the dual problem formulation \eqref{eq:dual-problem}, we see that $\frac{1}{2}\norm{y}_{2}^{2}$ can be omitted, since it doesn’t depend on $p$. Then, multiplying it by 2 and reversing the sign, we arive at equivalent dual problem:

\[\begin{align*} \label{eq:dual-problem-prime} \tag{D'} &\min_{p \in \mathbb{R}^{n} } \, \norm{y - p}_{2}^{2} \\[.5em] &\text{subject to } \, \norm{A^{T}p}_{\infty} \leq \alpha. \end{align*}\]Let $C \subset \mathbb{R}^{n}$ be closed and convex set. Define a projection operator $P_{C}$ as:

\[\DeclareMathOperator*{\argmin}{arg\,min} \begin{align*} P_{C} \text{: } & \mathbb{R}^{n} \rightarrow C \\[.5em] & y \mapsto P_{C}(y) := \argmin_{p \in C} \norm{y - p}_{2}. \end{align*}\]Looking at \eqref{eq:dual-problem-prime}, we see that $p^{*}$ is a projection

\[p^{*} = P_{C}(y)\]where $C$ is equal to:

\[C = \lbrace p \in \mathbb{R}^{n} : \norm{A^{T}p}_{\infty} \leq \alpha \rbrace.\]Notice that $C$ is indeed closed and convex. It can be expressed as:

\[\begin{equation}\nonumber C = (A^{T})^{-1}(D) \end{equation}\]where $D$ is equal to:

\[D = \lbrace d \in \mathbb{R}^{p} : \norm{d}_{\infty} \leq \alpha \rbrace.\]For example, let $n = 2, p = 2$ and

\[A^{T} = \begin{pmatrix} a_{11} & a_{21}\\ a_{12} & a_{22} \end{pmatrix}.\]Then,

\[\begin{equation}\nonumber C = \lbrace -\alpha \leq a_{11} p_{1} + a_{12} p_{2} \leq \alpha \rbrace \cap \lbrace -\alpha \leq a_{21} p_{1} + a_{22} p_{2} \leq \alpha \rbrace \end{equation}\]and

\[D = \lbrace -\alpha \leq d_{1} \leq \alpha \rbrace \cap \lbrace -\alpha \leq d_{2} \leq \alpha \rbrace.\]This is illustrated in Figure 2.

## Solution of the primal problem

From the optimality condition of the dual problem, we can infer the primal solution given the assumption of the existence of $A^{-1}$.

During the formulation of the dual problem, we introduced the dummy variable $z = Ax$ and derived the stationary condition $z = y - p^{*}$. This implies that every solution $x^{*}$ of \eqref{eq:primal-problem} should satisfy”

\[A x^{*} = y - p^{*}\]where $p^{*}$ is a solution of the dual problem \eqref{eq:dual-problem}. Therefore, if $A^{-1}$ exists, the solution is:

\[x^{*} = A^{-1} \left( y - P_{C}(y) \right).\]Since $P_{C}$ is a projection onto a convex set $C$, it follows that $x^{*}$ is also nonexpansive mapping as a function of $y$. This is not obvious and would probably be hard to show without the dual formulation.

The nonexpansive property:

\[\norm{P_{C}(y) - P_{C}(\tilde{y})} \leq \norm{y - \tilde{y}}.\]is demonstrated in Figure 3A. For constrast, the projection onto a non-convex set $N$ is depiced in Figure 3B.

## References

- Tibshirani, R. (1996). Regression Shrinkage and Selection Via the Lasso.
*Journal of the Royal Statistical Society: Series B (Methodological)*,*58*(1), 267–288. https://doi.org/https://doi.org/10.1111/j.2517-6161.1996.tb02080.x - Tikhonov, A. N., & Arsenin, V. Y. (1977).
*Solutions of ill-posed problems*(p. xiii+258). V. H. Winston \& Sons. https://catalogue.nla.gov.au/catalog/720231 - Boyd, S., & Vandenberghe, L. (2008).
*Subgradients Notes*. https://see.stanford.edu/materials/lsocoee364b/01-subgradients_notes.pdf