  We study a weaker formulation of the nullspace property which guarantees
recovery of sparse signals from linear measurements by l_1 minimization. We
require this condition to hold only with high probability, given a distribution
on the nullspace of the coding matrix A. Under some assumptions on the
distribution of the reconstruction error, we show that testing these weak
conditions means bounding the optimal value of two classical graph partitioning
problems: the k-Dense-Subgraph and MaxCut problems. Both problems admit
efficient, relatively tight relaxations and we use a randomization argument to
produce new approximation bounds for k-Dense-Subgraph. We test the performance
of our results on several families of coding matrices.
