  The optimal $k$-thresholding (OT) and optimal $k$-thresholding pursuit (OTP)
are newly introduced frameworks of thresholding techniques for compressed
sensing and signal approximation. Such frameworks motivate the practical and
efficient algorithms called relaxed optimal $k$-thresholding
($\textrm{ROT}\omega$) and relaxed optimal $k$-thresholding pursuit
($\textrm{ROTP}\omega$) which are developed through the tightest convex
relaxations of OT and OTP, where $\omega$ is a prescribed integer number. The
preliminary numerical results demonstrated in \cite{Z19} indicate that these
approaches can stably reconstruct signals with a wide range of sparsity levels.
However, the guaranteed performance of these algorithms with parameter $ \omega
\geq 2 $ has not yet established in \cite{Z19}. The purpose of this paper is to
show the guaranteed performance of OT and OTP in terms of the restricted
isometry property (RIP) of nearly optimal order for the sensing matrix
governing the $k$-sparse signal recovery, and to establish the first guaranteed
performance result for $\textrm{ROT}\omega$ and $\textrm{ROTP}\omega$ with $
\omega\geq 2.$ In the meantime, we provide a numerical comparison between
ROTP$\omega$ and several existing thresholding methods.
