Given $f(x) = ||x||_1$ with $\ \ f: \mathbb{R^n} \rightarrow \mathbb{R}$
I would like to find the proximal operator of $f(x)$, defining the proximal operator as:
$$\text{prox}_{\lambda f}(a) := \underset{x \in \mathbb R^n}{\text{argmin }} \frac{1}{2}\|x-a\|_2^2 + \lambda f(x),$$
Using the Moreau identity, the proximal operator can be solved using the Fenchel Conjugate,
$$ \text{prox}_{\lambda f}(a) = a – \text{prox}_{\frac{1}{\lambda} f^*}\left(\frac{a}{\lambda}\right)$$
The conjugate of $f(x)$ defined as:
$$f^*(z) = \underset{x \in \mathbb R^n}{\text{sup }}z^Tx – f(x)$$
Using Holders Equality, $$||x||_1 = \underset{y\ |\ \ ||y||_{\infty}\le 1 }{\text{sup }} x^Ty$$
Then solving the conjugate optimization problem,
$$f^*(z) = \underset{x \in \mathbb R^n}{\text{sup }}z^Tx – \underset{ \{y\ |\ \ ||y||_{\infty}\le 1 \} }{\text{sup }} x^Ty$$
$$=\underset{x \in \mathbb R^n}{\text{sup }}z^Tx + \underset{ \{y\ |\ \ ||y||_{\infty}\le 1 \} }{\text{inf }} -x^Ty$$
$$=\underset{x \in \mathbb R^n}{\text{sup }}\ \ \underset{ \{y\ |\ \ ||y||_{\infty}\le 1 \} }{\text{inf }} x^T(z-y)$$
Applying Sion's minimax theorem since the function is continuous and quasiconvex,
$$f^*(z)=\underset{ \{y\ |\ \ ||y||_{\infty}\le 1 \} }{\text{inf }}\underset{x \in \mathbb R^n}{\text{sup }}\ \ x^T(z-y)$$
$$= \underset{y | \ \ \|y\|_{\infty} \le 1}{\inf }\begin{cases}0,&\mbox y = z\\+\infty, &\mbox{ otherwise}\end{cases}
$$
Implies,
$$f^*(z) = \begin{cases}0,&\mbox ||z||_{\infty} \le 1\\+\infty, &\mbox{ otherwise}\end{cases}$$
Then we need to solve $\text{prox}_{\frac{1}{\lambda} f^*}\left(\frac{a}{\lambda}\right)$
$$\text{prox}_{\frac{1}{\lambda} f^*}\left(\frac{a}{\lambda}\right)=\underset{x \in \mathbb R^n}{\text{argmin }} \frac{1}{2}\|x-\frac{a}{\lambda}\|_2^2 + \frac{1}{\lambda} f^*(x)$$
$$=\underset{x \in \mathbb R^n}{\text{argmin }} \frac{1}{2}\|x-\frac{a}{\lambda}\|_2^2 + \frac{1}{\lambda} \begin{cases}0,&\mbox ||x||_{\infty} \le 1\\+\infty, &\mbox{ otherwise}\end{cases}$$
Which simplifies to a euclidean projection,
$$\text{prox}_{\frac{1}{\lambda} f^*}\left(\frac{a}{\lambda}\right)=\underset{||x||_{\infty} \le 1}{\text{argmin }} \frac{1}{2}\|x-\frac{a}{\lambda}\|_2^2$$
Supposedly, this equals $(\lambda \text{sgn}(a_1), … ,\lambda \text{sgn}(a_n))$ but I am not sure how to get to there.
What I think it should equal is the following:
$$\text{min}(\frac{a_i}{\lambda}, \text{sgn}(a_i))$$
This leads me to two thoughts:
First, that the definition of Moreau identity used could be incorrect. I think there should be an extra factor of $\lambda$ multiplying the proximal operator of the conjugate function.
Second, I am not sure why the $\frac{a_i}{\lambda}$ is ignored.
The final solution in this case should be:
$$ \text{prox}_{\lambda f}(a) = \text{max}(0, a_i-\text{sgn}(a_i)\lambda)$$
I am following closely answers to these questions:
$ {L}_{1} $ Regularized Unconstrained Optimization Problem
Thanks for reading!
Best Answer
I believe a solved the issue.
The Moreau identity is as follows:
$$\text{prox}_{\lambda f}(x) = x- \lambda \text{prox}_{\lambda^{-1}f^*}(\lambda^{-1}x)$$
I was missing a factor of $\lambda$ in the identity for the problem statement causing the original confusing.