Analysis of Optimal Thresholding Algorithms for Compressed Sensing
Preprint
Abstract
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.
Keywords
All Related Versions
This publication has 40 references indexed in Scilit:
- Interpolation via weighted ℓ1 minimizationApplied and Computational Harmonic Analysis, 2016
- 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