Improved RIP-based bounds for guaranteed performance of two compressed sensing algorithms

DOI10.1007/S11425-021-1987-2MaRDI QIDQ6041666zbMATH OpenOpenAlexFDO

Authors Yun-Bin Zhao, Zhi-Quan Luo

Publication date 12 May 2023

Published in Science China. Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

compressed sensingcompressive sampling matching pursuitguaranteed performanceiterative hard thresholdingrestricted isometry property

Mathematics Subject Classification ID

Inverse problems in linear algebra (15A29) Iterative numerical methods for linear systems (65F10) Nonlinear programming (90C30) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: Iterative hard thresholding (IHT) and compressive sampling matching pursuit (CoSaMP) are two types of mainstream compressed sensing algorithms using hard thresholding operators for signal recovery and approximation. The guaranteed performance for signal recovery via these algorithms has mainly been analyzed under the condition that the restricted isometry constant of a sensing matrix, denoted by $delt{a}_K$ (where $K$ is an integer number), is smaller than a certain threshold value in the interval $(0,1).$ The condition $delt{a}_K<delt{a}^{\ast }$ for some constant $delt{a}^{\ast }leq1$ ensuring the success of signal recovery with a specific algorithm is called the restricted-isometry-property-based (RIP-based) bound for guaranteed performance of the algorithm. At the moment, the best known RIP-based bound for the guaranteed recovery of $k$-sparse signals via IHT is $delt{a}_{3k}<1/sqrt3approx0.5774,$ and the bound for guaranteed recovery via CoSaMP is $delt{a}_{4k}<\mathrm{0.4782.}$ A fundamental question in this area is whether such theoretical results can be further improved. The purpose of this paper is to affirmatively answer this question and rigorously show that the RIP-based bounds for guaranteed performance of IHT can be significantly improved to $delt{a}_{3k}<(sqrt5-1)/2approx0.618,$ and the bound for CoSaMP can be improved and pushed to $delt{a}_{4k}<\mathrm{0.5102.}$ These improvements are achieved through a deep property of the hard thresholding operator.

Recommendations

• Optimal D-RIP bounds in compressed sensing
• New bounds for RIC in compressed sensing
• A Probabilistic and RIPless Theory of Compressed Sensing
• Improved RIP conditions for compressed sensing with coherent tight frames
• An Improved RIP-Based Performance Guarantee for Sparse Signal Recovery via Orthogonal Matching Pursuit
• Theory of compressive sensing via _1-minimization: a non-RIP analysis and extensions
• \(\mathrm{L_1RIP}\)-based robust compressed sensing
• RIP-Based Near-Oracle Performance Guarantees for SP, CoSaMP, and IHT
• Quantized compressive sensing with RIP matrices: the benefit of dithering
• On Compressive Sensing in Coding Problems: A Rigorous Approach

Cites work

• A generalized class of hard thresholding algorithms for sparse signal recovery
• A mathematical introduction to compressive sensing
• A simple proof of the restricted isometry property for random matrices
• A tight bound of hard thresholding
• Best subset selection via a modern optimization lens
• Between hard and soft thresholding: optimal iterative thresholding algorithms
• Compressed sensing
• Compressed sensing and its applications. Selected papers of the third international MATHEON conference, TU Berlin, Berlin, Germany, December 4--8, 2017
• Compressive sampling
• CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
• Decoding by Linear Programming
• Global and quadratic convergence of Newton hard-thresholding pursuit
• Hard thresholding pursuit algorithms: number of iterations
• Hard thresholding pursuit: an algorithm for compressive sensing
• scientific article; zbMATH DE number 1906319 (Why is no real title available?)
• Ideal spatial adaptation by wavelet shrinkage
• Iterative hard thresholding for compressed sensing
• Iterative hard thresholding for low-rank recovery from rank-one projections
• Iterative thresholding algorithms
• Iterative thresholding for sparse approximations
• Linear Convergence of Stochastic Iterative Greedy Algorithms With Sparse Constraints
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• Newton-Step-Based Hard Thresholding Algorithms for Sparse Signal Recovery
• Oblique Pursuits for Compressed Sensing
• Optimal $k$-Thresholding Algorithms for Sparse Optimization Problems
• Optimal Variable Selection and Adaptive Noisy Compressed Sensing
• RIP-Based Near-Oracle Performance Guarantees for SP, CoSaMP, and IHT
• RSP-Based Analysis for Sparsest and Least \ell₁-Norm Solutions to Underdetermined Linear Systems
• Sparse and redundant representations. From theory to applications in signal and image processing.
• Sparse optimization theory and methods
• Sparse Representation of a Polytope and Recovery of Sparse Signals and Low-Rank Matrices
• Sparsity constrained nonlinear optimization: optimality conditions and algorithms
• Subspace Pursuit for Compressive Sensing Signal Reconstruction
• Tight Oracle Inequalities for Low-Rank Matrix Recovery From a Minimal Number of Noisy Random Measurements
• Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit
• Uniform uncertainty principle for Bernoulli and subgaussian ensembles
• Weak stability of \(\ell_1\)-minimization methods in sparse data reconstruction
• Why Simple Shrinkage Is Still Relevant for Redundant Representations?

Cited in

(11)

• On the number of iterations for convergence of CoSaMP and subspace pursuit algorithms
• Adaptive iterative hard thresholding for low-rank matrix recovery and rank-one measurements
• Heavy-ball-based optimal thresholding algorithms for sparse linear inverse problems
• Non-negative sparse recovery via momentum-boosted adaptive thresholding algorithm
• From theoretical guarantee to practical performance: selectable and optimal step-lengths for IHT and HTP algorithms in compressed sensing
• Splitting alternating algorithms for sparse solutions of linear systems with concatenated orthogonal matrices
• Sufficient condition based on nearly optimal order RIC for IHT algorithm
• Heavy-ball enhanced pseudo-inverse-based hard thresholding algorithms for sparse linear inverse problems
• Recovery performance of PhaseLift for phase retrieval from coded diffraction patterns
• General decomposition pursuit algorithm for linear inverse problems
• Iterative hard thresholding for compressed sensing

This page was built for publication: Improved RIP-based bounds for guaranteed performance of two compressed sensing algorithms

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