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

DOI10.1016/J.CAM.2023.115264MaRDI QIDQ6137779zbMATH OpenOpenAlexFDO

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

Publication date 4 September 2023

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

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

zbMATH Keywords

compressed sensinghard thresholding algorithmheavy-ball methodphase transitionrestricted isometry propertysparse signal recovery

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(14)

• Fast thresholding algorithms with feedbacks for sparse signal recovery
• A generalized class of hard thresholding algorithms for sparse signal recovery
• A robust reconstruction algorithm for sparse signals
• Sparse Signal Reconstruction from Quantized Noisy Measurements via GEM Hard Thresholding
• \({A^\dag}\) graded hard thresholding pursuit algorithm
• Heavy-ball-based optimal thresholding algorithms for sparse linear inverse problems
• Non-negative sparse recovery via momentum-boosted adaptive thresholding algorithm
• Dynamic thresholding algorithm with memory for linear inverse problems
• Convergence on thresholding-based algorithms for dictionary-sparse recovery
• Heavy-ball enhanced pseudo-inverse-based hard thresholding algorithms for sparse linear inverse problems
• Heavy-ball-based relaxed optimal \(\mathrm{s}\)-thresholding algorithms for solving compressed sensing problem
• A new framework for compressed sensing by p-concave functions
• Accelerated iterative simultaneous hard thresholding algorithm for joint sparse optimization
• Accelerated nonnegative proximal gradient algorithm for sparse linear complementarity problem

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)