  The null space condition for $\ell_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 $\ell_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).
