Improved RIC Bounds in Terms of $\delta _{\text{2}s}$ for Hard Thresholding-Based Algorithms
Lie-jun Xie
Abstract
Iterative hard thresholding (IHT) and hard thresholding pursuit (HTP) are two kinds of classical hard thresholding-based algorithms widely used in compressed sensing. Restricted isometry constant (RIC) of sensing matrix which ensures the convergence of iterative algorithms plays a key role in guaranteeing successful recovery. In the analysis of sufficient condition to ensure recovery performance, the RIC <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\delta _{\text{3}s}$</tex-math></inline-formula> is generally used in previous literature, while <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\delta _{\text{2}s}$</tex-math></inline-formula> is rarely addressed. In this letter, we first show that the theoretical optimal step-length is 1 while using sufficient condition in terms of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\delta _{\text{2}s}$</tex-math></inline-formula> . Furthermore, based on this optimal step-length, the RIC bound is greatly improved to <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\delta _{\text{2}s}< (\sqrt5-1)/(2\sqrt3)\approx 0.3568$</tex-math></inline-formula> compared to the existing one <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\delta _{\text{2}s}< 0.25$</tex-math></inline-formula> for IHT algorithm. Meanwhile, the RIC condition <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\delta _{\text{2}s}< \sqrt7/7\approx 0.3780$</tex-math></inline-formula> is developed for successful recovery via HTP algorithm. As far as we know, this is the first sufficient condition in terms of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\delta _{\text{2}s}$</tex-math></inline-formula> for HTP algorithm.