A new and improved quantitative recovery analysis for iterative hard thresholding algorithms in compressed sensing
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 the convergence o...
| Autors principals: | , |
|---|---|
| Format: | Journal article |
| Publicat: |
IEEE
2015
|
| _version_ | 1826261339447754752 |
|---|---|
| author | Cartis, C Thompson, A |
| author_facet | Cartis, C Thompson, A |
| author_sort | Cartis, C |
| collection | OXFORD |
| description | 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 the 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 (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 tradeoff 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. |
| first_indexed | 2024-03-06T19:19:50Z |
| format | Journal article |
| id | oxford-uuid:19b06a3e-a98e-495b-a4a3-f8a045eb68b3 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T19:19:50Z |
| publishDate | 2015 |
| publisher | IEEE |
| record_format | dspace |
| spelling | oxford-uuid:19b06a3e-a98e-495b-a4a3-f8a045eb68b32022-03-26T10:50:25ZA new and improved quantitative recovery analysis for iterative hard thresholding algorithms in compressed sensingJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:19b06a3e-a98e-495b-a4a3-f8a045eb68b3Symplectic Elements at OxfordIEEE2015Cartis, CThompson, AWe 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 the 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 (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 tradeoff 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. |
| spellingShingle | Cartis, C Thompson, A A new and improved quantitative recovery analysis for iterative hard thresholding algorithms in compressed sensing |
| title | A new and improved quantitative recovery analysis for iterative hard thresholding algorithms in compressed sensing |
| title_full | A new and improved quantitative recovery analysis for iterative hard thresholding algorithms in compressed sensing |
| title_fullStr | A new and improved quantitative recovery analysis for iterative hard thresholding algorithms in compressed sensing |
| title_full_unstemmed | A new and improved quantitative recovery analysis for iterative hard thresholding algorithms in compressed sensing |
| title_short | A new and improved quantitative recovery analysis for iterative hard thresholding algorithms in compressed sensing |
| title_sort | new and improved quantitative recovery analysis for iterative hard thresholding algorithms in compressed sensing |
| work_keys_str_mv | AT cartisc anewandimprovedquantitativerecoveryanalysisforiterativehardthresholdingalgorithmsincompressedsensing AT thompsona anewandimprovedquantitativerecoveryanalysisforiterativehardthresholdingalgorithmsincompressedsensing AT cartisc newandimprovedquantitativerecoveryanalysisforiterativehardthresholdingalgorithmsincompressedsensing AT thompsona newandimprovedquantitativerecoveryanalysisforiterativehardthresholdingalgorithmsincompressedsensing |