Precisely Verifying the Null Space Conditions in Compressed Sensing: A Sandwiching Algorithm
share
In this paper, we propose new efficient algorithms to verify the null space condition in compressed sensing (CS). Given an (n-m) × n (m>0) CS matrix A and a positive k, we are interested in computing α_k = _{z: Az=0,z≠ 0}_{K: |K|≤ k} z_K _1z_1, where K represents subsets of {1,2,...,n}, and |K| is the cardinality of K. In particular, we are interested in finding the maximum k such that α_k < 12. However, computing α_k is known to be extremely challenging. In this paper, we first propose a series of new polynomial-time algorithms to compute upper bounds on α_k. Based on these new polynomial-time algorithms, we further design a new sandwiching algorithm, to compute the exact α_k with greatly reduced complexity. When needed, this new sandwiching algorithm also achieves a smooth tradeoff between computational complexity and result accuracy. Empirical results show the performance improvements of our algorithm over existing known methods; and our algorithm outputs precise values of α_k, with much lower complexity than exhaustive search.
READ FULL TEXT