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

DOI10.1016/J.CAM.2023.115264zbMATH Open1520.94023arXiv2204.09300OpenAlexW4366166383MaRDI QIDQ6137779FDOQ6137779

Nan Meng, Zhongfeng Sun, Jinchuan Zhou, Yun-Bin Zhao

Publication date: 4 September 2023

Published in: Journal of Computational and Applied Mathematics (Search for Journal in Brave)

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 $delt{a}_{3k}<0.618$ and $delt{a}_{3k}<0.577,$ respectively. The guaranteed success of HBHT and HBHTP is also shown under the conditions $delt{a}_{2k}<0.356$ and $delt{a}_{2k}<0.377,$ respectively. Moreover, the finite convergence 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.

Full work available at URL: https://arxiv.org/abs/2204.09300

zbMATH Keywords

phase transitioncompressed sensingrestricted isometry propertysparse signal recoveryheavy-ball methodhard thresholding algorithm

Mathematics Subject Classification ID

Convex programming (90C25) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Iterative numerical methods for linear systems (65F10)

Cites Work

• iPiano: inertial proximal algorithm for nonconvex optimization
• Ideal spatial adaptation by wavelet shrinkage
• Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints
• Decoding by Linear Programming
• Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit
• Sparse and Redundant Representations
• De-noising by soft-thresholding
• Iterative hard thresholding for compressed sensing
• CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
• A mathematical introduction to compressive sensing
• An iterative thresholding algorithm for linear inverse problems with a sparsity constraint
• Iterative thresholding for sparse approximations
• Matrix recipes for hard thresholding methods
• Subspace Pursuit for Compressive Sensing Signal Reconstruction
• Some methods of speeding up the convergence of iteration methods
• Hard Thresholding Pursuit: An Algorithm for Compressive Sensing
• Optimal $k$-Thresholding Algorithms for Sparse Optimization Problems
• Why Simple Shrinkage Is Still Relevant for Redundant Representations?
• On the Convergence Rate of Incremental Aggregated Gradient Algorithms
• Sparse Optimization Theory and Methods
• A Tight Bound of Hard Thresholding
• CGIHT: conjugate gradient iterative hard thresholding for compressed sensing and matrix completion
• Performance comparisons of greedy algorithms in compressed sensing
• Scaled Heavy-Ball Acceleration of the Richardson-Lucy Algorithm for 3D Microscopy Image Restoration
• Partial gradient optimal thresholding algorithms for a class of sparse optimization problems
• Distributed Heavy-Ball: A Generalization and Acceleration of First-Order Methods With Gradient Tracking

Cited In (6)

• Heavy-ball-based optimal thresholding algorithms for sparse linear inverse problems
• Sparse Signal Reconstruction from Quantized Noisy Measurements via GEM Hard Thresholding
• Non-negative sparse recovery via momentum-boosted adaptive thresholding algorithm
• Fast thresholding algorithms with feedbacks for sparse signal recovery
• Dynamic thresholding algorithm with memory for linear inverse problems
• Convergence on thresholding-based algorithms for dictionary-sparse recovery

   Recommendations

• A Generalized Class of Hard Thresholding Algorithms for Sparse Signal Recovery 👍 👎
• A new conjugate gradient hard thresholding pursuit algorithm for sparse signal recovery 👍 👎
• Hard thresholding pursuit algorithms: number of iterations 👍 👎
• Hard Thresholding Pursuit: An Algorithm for Compressive Sensing 👍 👎
• Heavy-ball-based optimal thresholding algorithms for sparse linear inverse problems 👍 👎

This page was built for publication: Heavy-ball-based hard thresholding algorithms for sparse signal recovery

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6137779)