  Let $X=(x_1,...,x_n)$ be a random vector that satisfies a weak small ball
property and whose coordinates $x_i$ satisfy that $\|x_i\|_{L_p} \lesssim
\sqrt{p} \|x_i\|_{L_2}$ for $p \sim \log n$. In \cite{LM_compressed}, it was
shown that $N$ independent copies of $X$ can be used as measurement vectors in
Compressed Sensing (using the basis pursuit algorithm) to reconstruct any
$d$-sparse vector with the optimal number of measurements $N\gtrsim d
\log\big(e n/d\big)$. In this note we show that the result is almost optimal.
We construct a random vector $X$ with iid, mean-zero, variance one coordinates
that satisfies the same weak small ball property and whose coordinates satisfy
that $\|x_i\|_{L_p} \lesssim \sqrt{p} \|x_i\|_{L_2}$ for $p \sim (\log n)/(\log
N)$, but the basis pursuit algorithm fails to recover even $1$-sparse vectors.
  The construction shows that `spiky' measurement vectors may lead to a poor
performance by the basis pursuit algorithm, but on the other hand may still
perform in an optimal way if one chooses a different reconstruction algorithm
(like $\ell_0$-minimization). This exhibits the fact that the convex relaxation
of $\ell_0$-minimization comes at a significant cost when using `spiky'
measurement vectors.
