Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
What kind of object is $x$? A row vector? – littleO Jul 31 '14 at 8:35


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 described by Boyd

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.