Conjugate of Sum of $L1$ and $L2$ Norms

Question

We want to find the conjugate of $g(x) = \frac{\lambda}{2}||x||_2^2 + \sigma||x||_1$.

Here, the conjugate $g^*(y) = \arg\min_z \Big[z^Ty - g(z)\Big]$

I know that for $f(x)=\frac{1}{p}||x||_p^p$, we have $f^*(y)=\frac{1}{q}||x||_q^q$ where $\frac{1}{p} + \frac{1}{q} = 1$, but how do I find the sum? I tried getting $\nabla g(x)$, which is $y_j = \lambda x_j + \sigma \text{ sign}(x_j)$. Is this correct? How do I proceed?

Answer 1

Using the identity $(f+g)^*(y) = \min_z \{ f^*(z) + g^*(y-z) \}$, you get

$$g^*(y) = \begin{cases}0 & \text{ if } \exists z : ||z||_2 \leq \frac{\lambda}{2}, ||y-z||_{\infty} \leq \sigma \\ \infty & \text{otherwise.}\end{cases}$$