Data-time tradeoffs for optimal k-thresholding algorithms in quantized compressed sensing

Relaxed optimal k-thresholding (ROT) algorithms are designed as a new thresholding technique in compressed sensing to efficiently recover a k-sparse signal from a small number of noisy linear measurements, which overcome the shortcomings of traditional hard thresholding algorithms caused by the oscillation of the residual function. In this paper, we carry out a novel data-time tradeoff analysis to characterize the tradeoff between the number of measurements and the number of iterations under any fixed recovery accuracy for the relaxed optimal k-thresholding algorithms in quantized compressed sensing. Both the analysis and numerical results from synthetic signal recovery demonstrate the data-time tradeoffs of ROT algorithms in sparse reconstruction problems. Furthermore, the theory presents the order of the number of measurements required for successful recovery in compressed sensing, quantized compressed sensing, and corrupted sensing.