  Optimal $k$-thresholding algorithms are a class of $k$-sparse signal recovery
algorithms that overcome the shortcomings of traditional hard thresholding
algorithms caused by the oscillation of the residual function. In this paper, a
novel convergence analysis for optimal $k$-thresholding algorithms is
established, which reveals the data-time tradeoffs of these algorithms. Both
the analysis and numerical results demonstrate that when the number of
measurements is small, the algorithms cannot converge; when the number of
measurements is suitably large, the number of iterations required for
successful recovery has a negative correlation with the number of measurements,
and the algorithms can achieve linear convergence. Furthermore, the main
theorems indicate that the number of measurements required for successful
recovery is of the order of $k \log({n}/{k})$, where $n$ is the dimension of
the target signal.
