Conference proceeding
New algorithms for verifying the null space conditions in compressed sensing
2013 Asilomar Conference on Signals, Systems and Computers, pp.1038-1042
11/2013
DOI: 10.1109/ACSSC.2013.6810449
Abstract
The null space condition is a condition under which k-sparse signal can be recovered uniquely in compressed sensing (CS) problems. In this paper, new efficient algorithms are introduced to verify the null space condition for l 1 minimization in compressed sensing. Suppose A is an (n - m) × n (m > 0) sensing matrix, we can verify whether the sensing matrix A satisfies the null space condition or not for k-sparse signals by computing α k = max {z: Az=0, z≠0} max {K:|K|≤k} ||z K ||1/||z||1, where K represents subsets of {1, 2,..., n}, and |K| is the cardinality of K. However, computing α k is known to be extremely challenging because of high computational complexity. In this paper, a series of new polynomial-time algorithms are proposed to compute upper bounds on α k . Based on these new polynomial-time algorithms, we further design new algorithm, which is called the sandwiching algorithm, to compute the exact α k with much lower complexity than exhaustive search.
Details
- Title: Subtitle
- New algorithms for verifying the null space conditions in compressed sensing
- Creators
- Myung Cho - University of IowaWeiyu Xu - University of Iowa
- Resource Type
- Conference proceeding
- Publication Details
- 2013 Asilomar Conference on Signals, Systems and Computers, pp.1038-1042
- Publisher
- IEEE
- DOI
- 10.1109/ACSSC.2013.6810449
- ISSN
- 1058-6393
- eISSN
- 2576-2303
- Language
- English
- Date published
- 11/2013
- Academic Unit
- Electrical and Computer Engineering
- Record Identifier
- 9984197105702771
Metrics
14 Record Views