A New and Improved Quantitative Recovery Analysis for Iterative Hard Thresholding Algorithms in Compressed Sensing
From MaRDI portal
Publication:2978705
DOI10.1109/TIT.2015.2399919zbMATH Open1359.94071arXiv1309.5406MaRDI QIDQ2978705FDOQ2978705
Authors: Coralia Cartis, Andrew Thompson 
Publication date: 28 April 2017
Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)
Abstract: We present a new recovery analysis for a standard compressed sensing algorithm, Iterative Hard Thresholding (IHT) (Blumensath and Davies, 2008), which considers the fixed points of the algorithm. In the context of arbitrary measurement matrices, we derive a sufficient condition for convergence of IHT to a fixed point and a necessary condition for the existence of fixed points. These conditions allow us to perform a sparse signal recovery analysis in the deterministic noiseless case by implying that the original sparse signal is the unique fixed point and limit point of IHT, and in the case of Gaussian measurement matrices and noise by generating a bound on the approximation error of the IHT limit as a multiple of the noise level. By generalizing the notion of fixed points, we extend our analysis to the variable stepsize Normalised IHT (N-IHT) (Blumensath and Davies, 2010). For both stepsize schemes, we obtain lower bounds on asymptotic phase transitions in a proportional-dimensional framework, quantifying the sparsity/undersampling trade-off for which recovery is guaranteed. Exploiting the reasonable average-case assumption that the underlying signal and measurement matrix are independent, comparison with previous results within this framework shows a substantial quantitative improvement.
Full work available at URL: https://arxiv.org/abs/1309.5406
Cited In (7)
- Approximately normalized iterative hard thresholding for nonlinear compressive sensing
- An efficient radiation analysis approach through compressive model for laser driven inertial confinement fusion
- Relationship between the optimal solutions of least squares regularized with \(\ell_{0}\)-norm and constrained by \(k\)-sparsity
- Constraint matrix factorization for space variant PSFs field restoration
- Performance comparisons of greedy algorithms in compressed sensing.
- On the minimization over sparse symmetric sets: projections, optimality conditions, and algorithms
- CGIHT: conjugate gradient iterative hard thresholding for compressed sensing and matrix completion
This page was built for publication: A New and Improved Quantitative Recovery Analysis for Iterative Hard Thresholding Algorithms in Compressed Sensing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2978705)
