Thresholding
For a real or complex scalar \(x\), the hard thresholding operator can be defined as:
(1)\[\begin{split}\mathbf{HT}_{\gamma}(x) = \begin{cases}
x & \text{for} & |x| \gt \gamma\\
0 & \text{for} & |x| \le \gamma
\end{cases}\end{split}\]
For a multi-dimensional array, we apply the same operator on each entry in the array.
The soft thresholding operator for real and complex scalars can be defined as:
(2)\[\begin{split}\mathbf{ST}_{\gamma}(x) = \begin{cases}
x\left ( 1 - \frac{\gamma}{|x|} \right ) & \text{for} & |x| \gt \gamma\\
0 & \text{for} & |x| \le \gamma
\end{cases}\end{split}\]
For real numbers, this reduces to:
(3)\[\begin{split}\mathbf{ST}_{\gamma}(x) = \begin{cases}
x - \gamma & \text{for} & x \gt \gamma \\
x + \gamma & \text{for} & x \lt -\gamma \\
0 & \text{for} & |x| \le \gamma
\end{cases}\end{split}\]
[CCSW14] consider the general minimization problem:
(4)\[\widehat{x} = \text{arg} \min_{x} \| b - A x \|_2^2 + \mathbf{R}(x)\]
where \(x\) is a vector in the model space, \(b\) is a vector in the data space,
\(A\) is a linear operator from model space to data space, and
\(\mathbf{R}(x)\) is the regularization term on the model vector.
They specifically consider the regularizations
(5)\[\mathbf{R}(x) = \tau \|x\|_p^p\]
for \(p\)-norms where \(0 \leq p \leq 1\).
This can be solved by the IST (Iterative Shrinkage and Thresholding)
algorithm where the thresholding operator depends on the selection of \(p\)-norm and the
regularization parameter \(\tau\).
They describe the IST iterations in terms of a more general thresholding operator \(\mathbf{T}_{\gamma(\tau, p)}(x)\):
(6)\[x_{n+1} = \mathbf{T}_{\gamma(\tau, p)}\left [x_n + A^H (b - A x_n) \right ]\]
They provide the definition of the thresholding operator for:
\(p=0\) hard thresholding
\(p=1\) soft thresholding
\(p=1/2\) half thresholding
Hard thresholding
Whe \(p=0\), we have:
(7)\[\mathbf{R}(x) = \| x \|_0\]
(8)\[\gamma(\tau, 0) = \sqrt{2 \tau}\]
The hard thresholding operator reduces to:
(9)\[\begin{split}\mathbf{T}_{\gamma(\tau, 0)}(x) = \begin{cases}
x & \text{for} & |x| \gt \gamma (\tau, 0)\\
0 & \text{for} & |x| \le \gamma (\tau, 0)
\end{cases}\end{split}\]
Soft thresholding
Whe \(p=1\), we have:
(10)\[\mathbf{R}(x) = \| x \|_1\]
(11)\[\gamma(\tau, 1) = \tau\]
The soft thresholding operator reduces to:
(12)\[\begin{split}\mathbf{T}_{\gamma(\tau, 1)}(x) = \begin{cases}
x\left ( 1 - \frac{\gamma}{|x|} \right ) & \text{for} & |x| \gt \gamma (\tau, 1)\\
0 & \text{for} & |x| \le \gamma (\tau, 1)
\end{cases}\end{split}\]
Half thresholding
Whe \(p=\frac{1}{2}\), we have:
(13)\[\mathbf{R}(x) = \| x \|_{\frac{1}{2}}^{\frac{1}{2}}\]
(14)\[\gamma(\tau, \frac{1}{2}) = \frac{3}{2} \tau^{\frac{2}{3}}\]
The half thresholding operator is more complicated:
(15)\[\begin{split}\mathbf{T}_{\gamma(\tau, 1)}(x) = \begin{cases}
\frac{2}{3} x\left ( 1 + \cos \left ( \frac{2}{3} \pi - \frac{2}{3} \arccos \left ( \frac{\tau}{8} \left (\frac{|x|}{3} \right)^{\frac{3}{2}}
\right ) \right ) \right )
& \text{for} & |x| \gt \gamma (\tau, \frac{1}{2})\\
0 & \text{for} & |x| \le \gamma (\tau, \frac{1}{2})
\end{cases}\end{split}\]
