Proximal Operator - $ {L}_{1} $ Norm of a Linear Term - Generalization of Soft Threshold Operator For certain $\ell_1$-regularized optimization problems, a critical computational step is the soft threshold operator:
$\mathcal{S}_t(x) = \mathrm{sgn}(x)\circ \mathrm{max}(|x|-t)$
where $\circ$ is element-wise multiplication, or the Hadamard product.  This operator is the solution to the minimization problem
$\arg\min_z t||z||_1+\frac{1}{2}||z-x||^2_2$
which makes it a kind of proximity operator.  What I'd like to know is, is there a closed form solution for the proximity operator of $h(x) = ||xF||_1$ for arbitrary matrix $F$?  That is, is there a closed form solution to
$\arg\min_z t||zF||_1 + \frac{1}{2}||z-x||^2_2$
?  Thanks.
 A: $\newcommand{\prox}{\operatorname{prox}}$
No, there is no closed form solution unless F is semi-orthogonal or orthogonal.
The way to solve it is to notice that this problem is actually a generalized Lasso problem. Recall, that the general form of generalized Lasso is:
$\min$ $\lambda\|Fx\| + (1/2)\|Ax-b\|^2_2$
We can then introduce a new variable $z$ and solve it using ADMM as described in Stephen Boyd, Neal Parikh - Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers:
$\min$ $\lambda\|z\| + (1/2)\|x-b\|^2_2$
s.t. $Fx - z = 0$
ADMM is a standard algorithm used for convex optimization; in the general form, it can be written as:
$\min$ $f(x) + g(z)$
s.t. $Ax + Bz = c$
where $x \in R^n$, $z \in R^m$, $A \in R^{p\times n}$, $B \in R^{p \times m}$ and $c \in R^p$. We also make an assumption that $f(x)$ and $g(z)$ are convex. The idea of the procedure is rather standard: write augmented Lagrangian for the convex optimization problem above; minimize Lagrangian w.r.t. $x$ keeping $z$ and $y$ (Lagrangian multiplier) fixed; then minimize it w.r.t $z$ keeping $x$ and $y$ fixed; and finally perform dual update for $y$.
