The problem is given by:
\begin{equation}
\widetilde{f} = \arg \min_{f} \frac{1}{2} {\left\| f – x \right\|}_{2}^{2} + \lambda {\left\| f \right\|}_{0}.
\end{equation}
How do I find the closed form solution for hard thresholding operator?
I have intuition that $f_i=0$ or $f_i=x_i$ for minimum but can anyone explain the cases and conditions in detail?
Best Answer
The problem can be written as:
$$ \arg \min_{f} \frac{1}{2} {\left\| f - x \right\|}_{2}^{2} + \lambda {\left\| f \right\|}_{0} = \arg \min_{f} \frac{1}{2} \sum_{i = 1}^{n} \left( {f}_{i} - {x}_{i} \right)^{2} + \lambda \mathbb{1}_{ \left\{ {f}_{i} \neq 0 \right\} } $$
Due to its component wise property one could basically solve the Scalar Problem:
$$ \arg \min_{ {f}_{i} } \frac{1}{2} \left( {f}_{i} - {x}_{i} \right)^{2} + \lambda \mathbb{1}_{ \left\{ {f}_{i} \neq 0 \right\} } $$
Now, in case $ {f}_{i} = 0 $ the cost is $ \frac{1}{2} {x}_{i}^{2} $. Hence as long $ \frac{1}{2} {x}_{i}^{2} \leq \lambda $ it is worth to set $ {f}_{i} = 0 $.
In the other case ($ {f}_{i} \neq 0 $) the minimum value of the cost function is $ \lambda $ where $ {f}_{i} = {x}_{i} $.
Hence:
$$ \tilde{f}_{i} = \begin{cases} 0 & \text{ if } \frac{1}{2} {x}_{i}^{2} \leq \lambda \\ {x}_{i} & \text{ if } \frac{1}{2} {x}_{i}^{2} > \lambda \end{cases} $$
Which is the Hard Threshold operator.