[Math] Proximal Operator – $ {L}_{1} $ Norm of a Linear Term – Generalization of Soft Threshold Operator

convex optimizationconvex-analysisoptimizationproximal-operators

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.

Best Answer

$\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$.

Related Question