Journal article
Computable performance guarantees for compressed sensing matrices
EURASIP Journal on Advances in Signal Processing, Vol.2018(1), 16
02/27/2018
DOI: 10.1186/s13634-018-0535-y
PMCID: PMC5829123
PMID: 29503664
Abstract
The null space condition for ℓ 1 minimization in compressed sensing is a necessary and sufficient condition on the sensing matrices under which a sparse signal can be uniquely recovered from the observation data via ℓ 1 minimization. However, verifying the null space condition is known to be computationally challenging. Most of the existing methods can provide only upper and lower bounds on the proportion parameter that characterizes the null space condition. In this paper, we propose new polynomial-time algorithms to establish upper bounds of the proportion parameter. We leverage on these techniques to find upper bounds and further develop a new procedure—tree search algorithm—that is able to precisely and quickly verify the null space condition. Numerical experiments show that the execution speed and accuracy of the results obtained from our methods far exceed those of the previous methods which rely on linear programming (LP) relaxation and semidefinite programming (SDP).
Details
- Title: Subtitle
- Computable performance guarantees for compressed sensing matrices
- Creators
- Myung Cho - University of IowaKumar Vijay Mishra - University of IowaWeiyu Xu - University of Iowa, Electrical and Computer Engineering
- Resource Type
- Journal article
- Publication Details
- EURASIP Journal on Advances in Signal Processing, Vol.2018(1), 16
- Publisher
- SpringerOpen
- DOI
- 10.1186/s13634-018-0535-y
- PMID
- 29503664
- PMCID
- PMC5829123
- ISSN
- 1687-6172
- eISSN
- 1687-6180
- Copyright
- © 2018, Springer Nature
- Grant note
- Funding: The work of Weiyu Xu is supported by Simons Foundation 318608, KAUST OCRF-2014-CRG-3, NSF DMS-1418737, and NIH 1R01EB020665-01. Competing Interests: The authors declare that they have no competing interests.
- Language
- English
- Date published
- 02/27/2018
- Academic Unit
- Electrical and Computer Engineering
- Record Identifier
- 9983761198202771
Metrics
32 File views/ downloads
17 Record Views