Precisely Verifying the Null Space Conditions in Compressed Sensing: A Sandwiching Algorithm

Abstract

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 = _ : Az=0,z 0\_ : |K| k\ \|z_K \|_1\|z\|_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.

Tasks

Reproductions