Heavy-ball-based hard thresholding algorithms for sparse signal recovery

Zhong Feng Sun, Jin Chuan Zhou, Yun Bin Zhao, Nan Meng

Research output: Journal PublicationArticlepeer-review

6 Citations (Scopus)

Abstract

The hard thresholding technique plays a vital role in the development of algorithms for sparse signal recovery. By merging this technique and heavy-ball acceleration method which is a multi-step extension of the traditional gradient descent method, we propose the so-called heavy-ball-based hard thresholding (HBHT) and heavy-ball-based hard thresholding pursuit (HBHTP) algorithms for signal recovery. It turns out that the HBHT and HBHTP can successfully recover a k-sparse signal if the restricted isometry constant of the measurement matrix satisfies δ3k<0.618 and δ3k<0.577, respectively. The guaranteed success of HBHT and HBHTP is also shown under the conditions δ2k<0.356 and δ2k<0.377, respectively. Moreover, the finite convergence of HBHTP and stability of the two algorithms are also established in this paper. Simulations on random problem instances are performed to compare the performance of the proposed algorithms and several existing ones. Empirical results indicate that the HBHTP performs very comparably to a few existing algorithms and it takes less average time to achieve the signal recovery than these existing methods.

Original languageEnglish
Article number115264
JournalJournal of Computational and Applied Mathematics
Volume430
DOIs
Publication statusPublished - 1 Oct 2023

Keywords

  • Compressed sensing
  • Hard thresholding algorithm
  • Heavy-ball method
  • Phase transition
  • Restricted isometry property
  • Sparse signal recovery

ASJC Scopus subject areas

  • Computational Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Heavy-ball-based hard thresholding algorithms for sparse signal recovery'. Together they form a unique fingerprint.

Cite this