Suppose we have a $k$-sparse vector $x_0 \in \mathbb{R}^N$, and a Gaussian measurement matrix $A \in \mathbb{R}^{m\times n}$. Set $y=Ax_0$ and solve the problem $\min \|x\|_0$ subject to $Ax=y$. How many measurements do we need for $\ell_0$ minimization to recovery the exact solution with probability 1?

It is easy to see that $2k+1$ measurements suffice, as done in Lemma 2.1 of http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.91.9526&rep=rep1&type=pdf. But I think the result can be improved to $k+1$.

Suppose $m=k+1$. All vectors $x'$ such that $\|x'\|_0 \leq \|x_0\|_0$ lie on a union of $\binom{n}{k}$ $k$-dimensional subspaces spanned by $k$ coordinate vectors. The null space of $A$ is $n-k-1$ dimensional, so the affine set $S$ of all solutions of $Ax=y$ is $n-k-1$ dimensional. If $S$ intersects any of the $\binom{n}{k}$ subspaces at a point not equal to $x_0$, then we don't have a unique solution and the algorithm fails. But I think the probability of this event should be $0$, hence we obtain recovery with probability 1. Is this true? If so, how can I show this formally?

Edit: I guess the question can be formed in a simpler form. I have a point $x_0$ that lies on a $k$-dimensional subspace spanned by $k$ coordinate vectors, and a random affine set of dimension $n-k-1$ that passes through $x_0$. What is the probability that this random affine set intersects any other $k$-dimensional subspace spanned by coordinate vectors? For the case $n=2$ and $k=1$, the probability is clearly $0$ since the affine set contains one point $x_0$. I wonder if this generalizes to higher dimensions.