cdsommegolfzp

2022-07-04

What is the Proximal Operator ($\mathrm{Prox}$) of the Pseudo ${L}_{0}$ Norm?
Namely:
${\mathrm{Prox}}_{\lambda {‖\cdot ‖}_{0}}\left(\mathbit{y}\right)=\mathrm{arg}\underset{\mathbit{x}}{min}\frac{1}{2}{‖\mathbit{x}-\mathbit{y}‖}_{2}^{2}+\lambda {‖\mathbit{x}‖}_{0}$
Where ${‖\mathbit{x}‖}_{0}=\mathrm{n}\mathrm{n}\mathrm{z}\left(x\right)$, namely teh number of non zeros elements in the vector $\mathbit{x}$.

billyfcash5n

Since both the $\frac{1}{2}{‖\mathbit{x}-\mathbit{y}‖}_{2}^{2}$ and the $\lambda {‖\mathbit{x}‖}_{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:

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

Do you have a similar question?