Consider we have a vector $\boldsymbol{x}_1^n$ which has a sparse structure in the sense that \begin{equation} \mathbb{P}(x_i=0)=\alpha>0. \end{equation} Further, assume that we have a sampled version $\boldsymbol{y}_1^m = A_{m\times n} \boldsymbol{x}_1^n$.
Can we lower bound the probability of the exact reconstruction of $\boldsymbol{x}_1^n$ using $\boldsymbol{y}_1^m$ and some conditions on $A$?
I guess there must be a weaker condition than on the SPARK (minimum linearly dependent columns) of $A$.