TY - JOUR
T1 - Computable performance guarantees for compressed sensing matrices
AU - Cho, Myung
AU - Vijay Mishra, Kumar
AU - Xu, Weiyu
N1 - KAUST Repository Item: Exported on 2020-10-01
Acknowledged KAUST grant number(s): OCRF-2014-CRG-3
Acknowledgements: The work of Weiyu Xu is supported by Simons Foundation 318608, KAUST OCRF-2014-CRG-3, NSF DMS-1418737, and NIH 1R01EB020665-01.
This publication acknowledges KAUST support, but has no KAUST affiliated authors.
PY - 2018/2/27
Y1 - 2018/2/27
N2 - 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).
AB - 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).
UR - http://hdl.handle.net/10754/629746
UR - https://asp-eurasipjournals.springeropen.com/articles/10.1186/s13634-018-0535-y
UR - http://www.scopus.com/inward/record.url?scp=85042718747&partnerID=8YFLogxK
U2 - 10.1186/s13634-018-0535-y
DO - 10.1186/s13634-018-0535-y
M3 - Article
SN - 1687-6180
VL - 2018
JO - EURASIP Journal on Advances in Signal Processing
JF - EURASIP Journal on Advances in Signal Processing
IS - 1
ER -