[proofplan]
We prove the equivalence directly. Exact recovery implies the null space property by testing basis pursuit on the specially chosen sparse vector $x = -h_S$ and comparing it with the feasible competitor $h_{S^c}$. Conversely, the null space property makes every nonzero feasible perturbation $h \in \ker A$ increase the $\ell^1$ norm of a $k$-sparse vector, so the original sparse vector is the unique minimizer.
[/proofplan]
[step:Derive the null space inequality from exact recovery]
Assume that basis pursuit recovers every vector in $\Sigma_k$ uniquely. Let $h \in \ker A \setminus \{0\}$, and let $S \subset \{1,\dots,d\}$ satisfy $|S| \leq k$. Define
\begin{align*}
x := -h_S \in \mathbb{R}^d.
\end{align*}
Since $\operatorname{supp}(x) \subset S$, we have $x \in \Sigma_k$.
Because $h = h_S + h_{S^c}$ and $Ah = 0$, we have
\begin{align*}
A(-h_S) = A(h_{S^c}).
\end{align*}
Thus $h_{S^c}$ is feasible for the basis pursuit problem with data $Ax$. The vector $h_{S^c}$ is not equal to $x$: if $h_{S^c} = -h_S$, then $h = h_S + h_{S^c} = 0$, contradicting $h \neq 0$. Since $x$ is the unique minimizer for its measurement $Ax$, every other feasible vector has strictly larger $\ell^1$ norm. Therefore
\begin{align*}
\|h_S\|_{\ell^1}
=
\|-h_S\|_{\ell^1}
=
\|x\|_{\ell^1}
<
\|h_{S^c}\|_{\ell^1}.
\end{align*}
This is exactly the null space property of order $k$.
[guided]
Assume that basis pursuit uniquely recovers every $k$-sparse vector. To prove the null space property, we must begin with an arbitrary nonzero null vector and an arbitrary small index set. Thus let $h \in \ker A \setminus \{0\}$, and let $S \subset \{1,\dots,d\}$ satisfy $|S| \leq k$.
The key idea is to build a sparse vector from the part of $h$ supported on $S$. Define
\begin{align*}
x := -h_S \in \mathbb{R}^d.
\end{align*}
Since $h_S$ vanishes outside $S$, the vector $x$ also vanishes outside $S$. Hence
\begin{align*}
|\operatorname{supp}(x)| \leq |S| \leq k,
\end{align*}
so $x \in \Sigma_k$.
Now we compare $x$ with the complementary part $h_{S^c}$. Since $h = h_S + h_{S^c}$ and $h \in \ker A$, we have
\begin{align*}
0 = Ah = A h_S + A h_{S^c}.
\end{align*}
Rearranging gives
\begin{align*}
A(-h_S) = A(h_{S^c}).
\end{align*}
Therefore $h_{S^c}$ satisfies the same measurement constraint as $x = -h_S$.
We also need to check that $h_{S^c}$ is genuinely a different feasible vector. If $h_{S^c} = x = -h_S$, then
\begin{align*}
h = h_S + h_{S^c} = h_S - h_S = 0,
\end{align*}
contradicting the assumption $h \neq 0$. Hence $h_{S^c} \neq x$.
By the assumed unique recovery property, $x$ is the unique minimizer of the basis pursuit problem with data $Ax$. Since $h_{S^c}$ is another feasible vector and is not equal to $x$, it must have strictly larger $\ell^1$ norm:
\begin{align*}
\|x\|_{\ell^1} < \|h_{S^c}\|_{\ell^1}.
\end{align*}
Finally, $x = -h_S$, and the $\ell^1$ norm is unchanged by multiplication by $-1$, so
\begin{align*}
\|h_S\|_{\ell^1}
=
\|-h_S\|_{\ell^1}
=
\|x\|_{\ell^1}
<
\|h_{S^c}\|_{\ell^1}.
\end{align*}
This proves the null space property of order $k$.
[/guided]
[/step]
[step:Use the null space property to make every feasible perturbation increase the norm]
Assume that $A$ satisfies the null space property of order $k$. Let $x \in \Sigma_k$, and define $S := \operatorname{supp}(x)$. Then $|S| \leq k$ and $x = x_S$.
Let $z \in \mathbb{R}^d$ be feasible for the basis pursuit problem with data $Ax$, so $Az = Ax$. If $z \neq x$, define
\begin{align*}
h := z - x \in \mathbb{R}^d.
\end{align*}
Then $h \neq 0$ and
\begin{align*}
Ah = A(z - x) = Az - Ax = 0,
\end{align*}
so $h \in \ker A \setminus \{0\}$. Since $x_{S^c} = 0$, we have $z_S = x_S + h_S$ and $z_{S^c} = h_{S^c}$.
Using additivity of the $\ell^1$ norm over disjoint supports, we obtain
\begin{align*}
\|z\|_{\ell^1}
=
\|z_S\|_{\ell^1} + \|z_{S^c}\|_{\ell^1}.
\end{align*}
Substituting $z_S = x_S + h_S$ and $z_{S^c} = h_{S^c}$ gives
\begin{align*}
\|z\|_{\ell^1}
=
\|x_S + h_S\|_{\ell^1} + \|h_{S^c}\|_{\ell^1}.
\end{align*}
Applying the triangle inequality in the form $\|a+b\|_{\ell^1} \geq \|a\|_{\ell^1} - \|b\|_{\ell^1}$ with $a = x_S$ and $b = h_S$, we get
\begin{align*}
\|z\|_{\ell^1}
\geq
\|x_S\|_{\ell^1} - \|h_S\|_{\ell^1} + \|h_{S^c}\|_{\ell^1}.
\end{align*}
By the null space property applied to $h$ and $S$,
\begin{align*}
\|h_S\|_{\ell^1} < \|h_{S^c}\|_{\ell^1}.
\end{align*}
Therefore
\begin{align*}
\|z\|_{\ell^1}
>
\|x_S\|_{\ell^1}
=
\|x\|_{\ell^1}.
\end{align*}
Thus every feasible $z \neq x$ has strictly larger $\ell^1$ norm than $x$.
[/step]
[step:Conclude uniqueness of basis pursuit recovery]
For each $x \in \Sigma_k$, the vector $x$ is feasible for the constraint $Az = Ax$. The previous step shows that every other feasible vector $z \neq x$ has $\|z\|_{\ell^1} > \|x\|_{\ell^1}$. Hence $x$ is the unique solution of
\begin{align*}
\min_{z \in \mathbb{R}^d} \|z\|_{\ell^1}
\quad \text{subject to} \quad
Az = Ax.
\end{align*}
Since $x \in \Sigma_k$ was arbitrary, basis pursuit recovers every $k$-sparse vector. This completes the proof of the equivalence.
[/step]
