Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
    
What kind of object is $x$? A row vector? –  littleO Jul 31 at 8:35

1 Answer 1

$\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 described by Boyd http://web.stanford.edu/~boyd/papers/pdf/admm_distr_stats.pdf:

$\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|improve this answer

Your Answer

 
discard

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.