The Proximal (Prox) Operator of the $ {L}_{0} $ Pseudo Norm Function

Question

What is the Proximal Operator ($ \operatorname{Prox} $) of the Pseudo $ {L}_{0} $ Norm?

Namely:

$$ \operatorname{Prox}_{\lambda {\left\| \cdot \right\|}_{0} } \left( \boldsymbol{y} \right) = \arg \min_{\boldsymbol{x}} \frac{1}{2} {\left\| \boldsymbol{x} - \boldsymbol{y} \right\|}_{2}^{2} + \lambda {\left\| \boldsymbol{x} \right\|}_{0} $$

Where $ {\left\| \boldsymbol{x} \right\|}_{0} = \mathrm{nnz}(x) $, namely teh number of non zeros elements in the vector $ \boldsymbol{x} $.

Answer 1

Since both the $ \frac{1}{2} {\left\| \boldsymbol{x} - \boldsymbol{y} \right\|}_{2}^{2} $ and the $ \lambda {\left\| \boldsymbol{x} \right\|}_{0} $ are element wise the problem could be solved per element.

There are 2 possible solutions for the value of $ {x}_{i} $:

1. The value of $ {y}_{i} $.
2. The value $ 0 $.

For each there is a different loss hence the choice is by the higher loss:

1. Value of $ {y}_{i} $ -> The loss is $ \lambda $.
2. Value of $ 0 $ -> The loss is $ \frac{1}{2} {y}_{i}^{2} $.

Then the solution is given by:

$$ {x}_{i} = \begin{cases} {y}_{i} & \text{ if } \frac{1}{2} {y}_{i}^{2} > \lambda \\ 0 & \text{ if } \frac{1}{2} {y}_{i}^{2} \leq \lambda \end{cases} $$

Mathematically, for the case $ \frac{1}{2} {y}_{i}^{2} = \lambda $ one could chose either solution.
The above operation is called Hard Threshold.