  We consider the Linear Programming (LP) solution of the Compressed Sensing
(CS) problem over reals, also known as the Basis Pursuit (BasP) algorithm. The
BasP allows interpretation as a channel-coding problem, and it guarantees
error-free reconstruction with a properly chosen measurement matrix and
sufficiently sparse error vectors. In this manuscript, we examine how the BasP
performs on a given measurement matrix and develop an algorithm to discover the
sparsest vectors for which the BasP fails. The resulting algorithm is a
generalization of our previous results on finding the most probable
error-patterns degrading performance of a finite size Low-Density Parity-Check
(LDPC) code in the error-floor regime. The BasP fails when its output is
different from the actual error-pattern. We design a CS-Instanton Search
Algorithm (ISA) generating a sparse vector, called a CS-instanton, such that
the BasP fails on the CS-instanton, while the BasP recovery is successful for
any modification of the CS-instanton replacing a nonzero element by zero. We
also prove that, given a sufficiently dense random input for the error-vector,
the CS-ISA converges to an instanton in a small finite number of steps. The
performance of the CS-ISA is illustrated on a randomly generated $120\times
512$ matrix. For this example, the CS-ISA outputs the shortest instanton (error
vector) pattern of length 11.
