Analysis of Optimal Thresholding Algorithms for Compressed Sensing
Preprint
Abstract
The optimal thresholding is a new technique that has recently been developed for compressed sensing and signal approximation. The optimal $k$-thresholding (OT) and optimal $k$-thresholding pursuit (OTP) provide basic algorithmic frameworks that are fundamental to the development of practical and efficient optimal-thresholding-type algorithms for compressed sensing. In this paper, we first prove an improved bound for the guaranteed performance of these basic frameworks in terms of the $k$th order restricted isometry property of the sensing matrices. More importantly, we analyze the newly developed algorithms called relaxed optimal thresholding ($\textrm{ROT}\omega$) and relaxed optimal thresholding pursuit ($\textrm{ROTP}\omega$) which are derived from the tightest convex relaxation of the OT and OTP. Numerical results in \cite{Z19} have demonstrated that such approaches are truly efficient to recover a wide range of signals and can remarkably outperform the existing hard-thresholding-type methods as well as the classic $\ell_1$-minimization in numerous situations. However, the guaranteed performance/convergence of these algorithms with $ \omega \geq 2 $ has not yet established. The main purpose of this paper is to establish the first guaranteed performance results for the $\textrm{ROT}\omega$ and $\textrm{ROTP}\omega. $
Keywords
All Related Versions
This publication has 39 references indexed in Scilit:
- Iterative hard thresholding for low-rank recovery from rank-one projectionsLinear Algebra and its Applications, 2019
- A new iterative firm-thresholding algorithm for inverse problems with sparsity constraintsApplied and Computational Harmonic Analysis, 2013
- Sharp RIP bound for sparse signal and low-rank matrix recoveryApplied and Computational Harmonic Analysis, 2013
- Matrix Recipes for Hard Thresholding MethodsJournal of Mathematical Imaging and Vision, 2013
- A Mathematical Introduction to Compressive Sensing2013
- Iterative hard thresholding for compressed sensingApplied and Computational Harmonic Analysis, 2009
- CoSaMP: Iterative signal recovery from incomplete and inaccurate samplesApplied and Computational Harmonic Analysis, 2009
- Enhancing Sparsity by Reweighted ℓ 1 MinimizationJournal of Fourier Analysis and Applications, 2008
- Iterative Thresholding for Sparse ApproximationsJournal of Fourier Analysis and Applications, 2008
- An iterative thresholding algorithm for linear inverse problems with a sparsity constraintCommunications on Pure and Applied Mathematics, 2004