Computable performance guarantees for compressed sensing matrices
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 b...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
SpringerOpen
2018-02-01
|
| Series: | EURASIP Journal on Advances in Signal Processing |
| Subjects: | |
| Online Access: | http://link.springer.com/article/10.1186/s13634-018-0535-y |
| _version_ | 1818886566892797952 |
|---|---|
| author | Myung Cho Kumar Vijay Mishra Weiyu Xu |
| author_facet | Myung Cho Kumar Vijay Mishra Weiyu Xu |
| author_sort | Myung Cho |
| collection | DOAJ |
| description | 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). |
| first_indexed | 2024-12-19T16:23:23Z |
| format | Article |
| id | doaj.art-e6b8dd1087514edbb4ec022a44fc61df |
| institution | Directory Open Access Journal |
| issn | 1687-6180 |
| language | English |
| last_indexed | 2024-12-19T16:23:23Z |
| publishDate | 2018-02-01 |
| publisher | SpringerOpen |
| record_format | Article |
| series | EURASIP Journal on Advances in Signal Processing |
| spelling | doaj.art-e6b8dd1087514edbb4ec022a44fc61df2022-12-21T20:14:25ZengSpringerOpenEURASIP Journal on Advances in Signal Processing1687-61802018-02-012018111810.1186/s13634-018-0535-yComputable performance guarantees for compressed sensing matricesMyung Cho0Kumar Vijay Mishra1Weiyu Xu2Department of ECE, University of IowaDepartment of ECE, University of IowaDepartment of ECE, University of IowaAbstract 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).http://link.springer.com/article/10.1186/s13634-018-0535-yCompressed sensingNull space conditionℓ 1 minimizationPerformance guaranteeSensing matrix |
| spellingShingle | Myung Cho Kumar Vijay Mishra Weiyu Xu Computable performance guarantees for compressed sensing matrices EURASIP Journal on Advances in Signal Processing Compressed sensing Null space condition ℓ 1 minimization Performance guarantee Sensing matrix |
| title | Computable performance guarantees for compressed sensing matrices |
| title_full | Computable performance guarantees for compressed sensing matrices |
| title_fullStr | Computable performance guarantees for compressed sensing matrices |
| title_full_unstemmed | Computable performance guarantees for compressed sensing matrices |
| title_short | Computable performance guarantees for compressed sensing matrices |
| title_sort | computable performance guarantees for compressed sensing matrices |
| topic | Compressed sensing Null space condition ℓ 1 minimization Performance guarantee Sensing matrix |
| url | http://link.springer.com/article/10.1186/s13634-018-0535-y |
| work_keys_str_mv | AT myungcho computableperformanceguaranteesforcompressedsensingmatrices AT kumarvijaymishra computableperformanceguaranteesforcompressedsensingmatrices AT weiyuxu computableperformanceguaranteesforcompressedsensingmatrices |