What is the convex conjugate or the fenchel conjugate of $f(x)=\lambda \|x\|_1$?
If $g(x)=\|x\|_1$, the convex conjugate is simply $g^*(x)=\mathbf{1}_{\|x\|_{\infty}\leq 1}(x)$.
However, I am not so sure when the constant $\lambda$ is multiplied to the norm.
$f^*(x)=\sup_y(x^Ty-\lambda\|y\|_1)$ and then I am stuck.
I am guessing the answer is $f^*(x)=\mathbf{1}_{\lambda\|x\|_{\infty}\leq 1}(x)$ but my intuition tells me that is not right.
My second attempt is $f^*(x)=\sup_y(x^Ty-\lambda\|y\|_1)=\lambda\sup_y(\frac{1}{\lambda}x^Ty-\|y\|_1)=\lambda\mathbf{1}_{\|\frac{x}{\lambda}\|_{\infty}\leq 1}(\frac{x}{\lambda})$
Like I said, you're almost there. Let's look at the general case. Given $$f^*(y) = \sup_x x^T y - f(x)$$ we can now do $g(x) = \lambda f(x)$ as follows: $$g^*(y) = \sup_x x^T y - g(x) = \sup_x x^T y - \lambda f(x) = \lambda \left( \sup_x \lambda^{-1} x^T y - f(x) \right) = \lambda f^*(\lambda^{-1} y)$$ So now that we have the general case, let's choose the specific case: $$f(x) = \|x\|_1, \quad g(x) = \lambda \|x\|_1 \quad\Longrightarrow\quad g^*(y) = \lambda f^*(\lambda^{-1} y) = \lambda \mathbf{1}_{\|\cdot\|_\infty\leq 1}(\lambda^{-1} y)$$ Now we can do a couple of simplifications. First, note that $\lambda \mathbf{1}(\cdot) = \mathbf{1}(\cdot)$ for any $\lambda >0$, so we can drop that outer $\lambda$. Secondly, note that (again, for $\lambda>0$) $$\|\lambda^{-1} y \|_\infty \leq 1 \quad\Longleftrightarrow\quad \|y\|_\infty \leq \lambda$$ So finally, we have in its simplest form: $$g(x) = \lambda \|x\|_1 \quad\Longrightarrow\quad g^*(y) = \mathbf{1}_{\|\cdot\|_\infty \leq \lambda}(y).$$