Heavy-ball-based optimal thresholding algorithms for sparse linear inverse problems

DOI10.1007/S10915-023-02315-1zbMATH Open1519.94010arXiv2305.03247OpenAlexW4385768695MaRDI QIDQ6134435FDOQ6134435

Jinchuan Zhou, Zhongfeng Sun, Yun-Bin Zhao

Publication date: 22 August 2023

Published in: Journal of Scientific Computing (Search for Journal in Brave)

Abstract: Linear inverse problems arise in diverse engineering fields especially in signal and image reconstruction. The development of computational methods for linear inverse problems with sparsity tool is one of the recent trends in this area. The so-called optimal $k$-thresholding is a newly introduced method for sparse optimization and linear inverse problems. Compared to other sparsity-aware algorithms, the advantage of optimal $k$-thresholding method lies in that it performs thresholding and error metric reduction simultaneously and thus works stably and robustly for solving medium-sized linear inverse problems. However, the runtime of this method remains high when the problem size is relatively large. The purpose of this paper is to propose an acceleration strategy for this method. Specifically, we propose a heavy-ball-based optimal $k$-thresholding (HBOT) algorithm and its relaxed variants for sparse linear inverse problems. The convergence of these algorithms is shown under the restricted isometry property. In addition, the numerical performance of the heavy-ball-based relaxed optimal $k$-thresholding pursuit (HBROTP) has been studied, and simulations indicate that HBROTP admits robust capability for signal and image reconstruction even in noisy environments.

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

zbMATH Keywords

phase transitionimage processingrestricted isometry propertyheavy-ball methodoptimal \(k\)-thresholdingsparse linear inverse problems

Mathematics Subject Classification ID

Quadratic programming (90C20) Convex programming (90C25) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Image processing (compression, reconstruction, etc.) in information and communication theory (94A08) Inverse problems in linear algebra (15A29) Numerical methods of relaxation type (49M20)

Cites Work

• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• Ideal spatial adaptation by wavelet shrinkage
• Atomic Decomposition by Basis Pursuit
• Enhancing sparsity by reweighted \(\ell _{1}\) minimization
• Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints
• Title not available (Why is that?)
• Title not available (Why is that?)
• Decoding by Linear Programming
• Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit
• Sparse and Redundant Representations
• De-noising by soft-thresholding
• 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
• Bregman Iterative Algorithms for $\ell_1$-Minimization with Applications to Compressed Sensing
• Iterative thresholding for sparse approximations
• Regularization preconditioners for frame-based image deblurring with reduced boundary artifacts
• 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
• Sparse Bayesian Learning for Basis Selection
• Analysis and Generalizations of the Linearized Bregman Method
• 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
• CGIHT: conjugate gradient iterative hard thresholding for compressed sensing and matrix completion
• Performance comparisons of greedy algorithms in compressed sensing
• Quadratic Combinatorial Optimization Using Separable Underestimators
• Sharp Time–Data Tradeoffs for Linear Inverse Problems
• AMP-Inspired Deep Networks for Sparse Linear Inverse Problems
• Krylov subspace split Bregman methods
• Linearized Krylov subspace Bregman iteration with nonnegativity constraint
• Constructing New Weighted ℓ₁-Algorithms for the Sparsest Points of Polyhedral Sets
• Newton-Step-Based Hard Thresholding Algorithms for Sparse Signal Recovery
• Partial gradient optimal thresholding algorithms for a class of sparse optimization problems
• Newton-type optimal thresholding algorithms for sparse optimization problems
• Robustness of Accelerated First-Order Algorithms for Strongly Convex Optimization Problems
• Distributed Heavy-Ball: A Generalization and Acceleration of First-Order Methods With Gradient Tracking
• Heavy-ball-based hard thresholding algorithms for sparse signal recovery
• Convergence rates of the heavy-ball method under the Łojasiewicz property
• Improved RIP-based bounds for guaranteed performance of two compressed sensing algorithms
• Differentially Private Accelerated Optimization Algorithms
• Back-Projection Based Fidelity Term for Ill-Posed Linear Inverse Problems

Cited In (4)

• An iterative thresholding-like algorithm for inverse problems with sparsity constraints in Banach space
• Heavy-ball-based hard thresholding algorithms for sparse signal recovery
• A new iterative firm-thresholding algorithm for inverse problems with sparsity constraints
• Dynamic thresholding algorithm with memory for linear inverse problems

   Recommendations

• Optimal $k$-Thresholding Algorithms for Sparse Optimization Problems 👍 👎
• Newton-type optimal thresholding algorithms for sparse optimization problems 👍 👎
• Partial gradient optimal thresholding algorithms for a class of sparse optimization problems 👍 👎
• Heavy-ball-based hard thresholding algorithms for sparse signal recovery 👍 👎
• A new iterative firm-thresholding algorithm for inverse problems with sparsity constraints 👍 👎

This page was built for publication: Heavy-ball-based optimal thresholding algorithms for sparse linear inverse problems

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