CGIHT: Conjugate Gradient Iterative Hard Thresholding for Compressed Sensing and Matrix Completion
We introduce the Conjugate Gradient Iterative Hard Thresholding (CGIHT) family of algorithms for the efficient solution of constrained underdetermined linear systems of equations arising in compressed sensing, row sparse approximation, and matrix completion. CGIHT is designed to balance the low per...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Published: |
2015
|
| _version_ | 1797068756878360576 |
|---|---|
| author | Tanner, J Blanchard, J Wei, K |
| author_facet | Tanner, J Blanchard, J Wei, K |
| author_sort | Tanner, J |
| collection | OXFORD |
| description | We introduce the Conjugate Gradient Iterative Hard Thresholding (CGIHT) family of algorithms for the efficient solution of constrained underdetermined linear systems of equations arising in compressed sensing, row sparse approximation, and matrix completion. CGIHT is designed to balance the low per iteration complexity of simple hard thresholding algorithms with the fast asymptotic convergence rate of employing the conjugate gradient method. We establish provable recovery guarantees and stability to noise for variants of CGIHT with sufficient conditions in terms of the restricted isometry constants of the sensing operators. Extensive empirical performance comparisons establish significant computational advantages for CGIHT both in terms of the size of problems which can be accurately approximated and in terms of overall computation time. |
| first_indexed | 2024-03-06T22:14:41Z |
| format | Journal article |
| id | oxford-uuid:52fe28b5-c53b-4611-a605-de48fd9495d6 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T22:14:41Z |
| publishDate | 2015 |
| record_format | dspace |
| spelling | oxford-uuid:52fe28b5-c53b-4611-a605-de48fd9495d62022-03-26T16:28:58ZCGIHT: Conjugate Gradient Iterative Hard Thresholding for Compressed Sensing and Matrix CompletionJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:52fe28b5-c53b-4611-a605-de48fd9495d6Symplectic Elements at Oxford2015Tanner, JBlanchard, JWei, KWe introduce the Conjugate Gradient Iterative Hard Thresholding (CGIHT) family of algorithms for the efficient solution of constrained underdetermined linear systems of equations arising in compressed sensing, row sparse approximation, and matrix completion. CGIHT is designed to balance the low per iteration complexity of simple hard thresholding algorithms with the fast asymptotic convergence rate of employing the conjugate gradient method. We establish provable recovery guarantees and stability to noise for variants of CGIHT with sufficient conditions in terms of the restricted isometry constants of the sensing operators. Extensive empirical performance comparisons establish significant computational advantages for CGIHT both in terms of the size of problems which can be accurately approximated and in terms of overall computation time. |
| spellingShingle | Tanner, J Blanchard, J Wei, K CGIHT: Conjugate Gradient Iterative Hard Thresholding for Compressed Sensing and Matrix Completion |
| title | CGIHT: Conjugate Gradient Iterative Hard Thresholding for Compressed Sensing and Matrix Completion |
| title_full | CGIHT: Conjugate Gradient Iterative Hard Thresholding for Compressed Sensing and Matrix Completion |
| title_fullStr | CGIHT: Conjugate Gradient Iterative Hard Thresholding for Compressed Sensing and Matrix Completion |
| title_full_unstemmed | CGIHT: Conjugate Gradient Iterative Hard Thresholding for Compressed Sensing and Matrix Completion |
| title_short | CGIHT: Conjugate Gradient Iterative Hard Thresholding for Compressed Sensing and Matrix Completion |
| title_sort | cgiht conjugate gradient iterative hard thresholding for compressed sensing and matrix completion |
| work_keys_str_mv | AT tannerj cgihtconjugategradientiterativehardthresholdingforcompressedsensingandmatrixcompletion AT blanchardj cgihtconjugategradientiterativehardthresholdingforcompressedsensingandmatrixcompletion AT weik cgihtconjugategradientiterativehardthresholdingforcompressedsensingandmatrixcompletion |