[proofplan]
We prove injectivity directly. If two $k$-sparse vectors have the same image under $A$, then their difference is $2k$-sparse and lies in the kernel of $A$. Although the full [restricted isometry constant](/page/Restricted%20Isometry%20Constant) condition includes both lower and upper bounds, this argument uses only the lower restricted isometry inequality with positive constant. That lower bound forces the Euclidean norm of the difference to vanish, because $1-\delta_{2k}(A)>0$.
[/proofplan]
[step:Subtract two sparse vectors with the same image]
Let $m,n \in \mathbb{N}$ be such that $A: \mathbb{R}^n \to \mathbb{R}^m$ is the [linear map](/page/Linear%20Map) in the statement, and let $k \in \mathbb{N}$ be the sparsity level from the statement. Let $|\cdot|$ denote the Euclidean norm on either $\mathbb{R}^n$ or $\mathbb{R}^m$, according to the vector being measured. Let $\Sigma_k$ denote the set of [sparse vectors](/page/Sparse%20Vector) in $\mathbb{R}^n$ with at most $k$ nonzero coordinates. For any vector $v \in \mathbb{R}^n$, define its coordinate support by
\begin{align*}
\operatorname{supp}(v) := \{i \in \{1,\dots,n\} : v_i \neq 0\}.
\end{align*}
Let $x,z \in \Sigma_k$ satisfy $Ax = Az$. Define the difference vector $h \in \mathbb{R}^n$ by $h := x-z$. Then $Ah = A(x-z) = Ax - Az = 0$.
Moreover,
\begin{align*}
\operatorname{supp}(h) \subseteq \operatorname{supp}(x) \cup \operatorname{supp}(z),
\end{align*}
because if $i \notin \operatorname{supp}(x) \cup \operatorname{supp}(z)$, then $x_i=z_i=0$, hence $h_i=0$. Therefore $|\operatorname{supp}(h)| \leq |\operatorname{supp}(x)| + |\operatorname{supp}(z)|$. Since $x,z \in \Sigma_k$, we have $|\operatorname{supp}(x)| \leq k$ and $|\operatorname{supp}(z)| \leq k$, so $|\operatorname{supp}(h)| \leq 2k$. Hence $h \in \Sigma_{2k}$.
[guided]
Let $m,n \in \mathbb{N}$ be such that $A: \mathbb{R}^n \to \mathbb{R}^m$ is the linear map in the statement, and let $k \in \mathbb{N}$ be the sparsity level from the statement. Let $|\cdot|$ denote the Euclidean norm on either $\mathbb{R}^n$ or $\mathbb{R}^m$, according to the vector being measured. Let $\Sigma_k$ denote the set of [sparse vectors](/page/Sparse%20Vector) in $\mathbb{R}^n$ with at most $k$ nonzero coordinates. For any vector $v \in \mathbb{R}^n$, define its coordinate support by
\begin{align*}
\operatorname{supp}(v) := \{i \in \{1,\dots,n\} : v_i \neq 0\}.
\end{align*}
Let $x,z \in \Sigma_k$ be two vectors with the same measurement, so $Ax = Az$. To prove injectivity, we must show that this forces $x = z$. The natural object to study is their difference. Define $h \in \mathbb{R}^n$ by
\begin{align*}
h := x-z.
\end{align*}
By linearity of matrix multiplication,
\begin{align*}
Ah = A(x-z).
\end{align*}
Since $A(x-z) = Ax - Az$ and $Ax = Az$, we obtain
\begin{align*}
Ah = 0.
\end{align*}
We also need to check that $h$ is sparse enough for the restricted isometry hypothesis to apply. Since $x$ and $z$ are each $k$-sparse, their nonzero coordinates lie in sets of size at most $k$. If a coordinate index $i$ belongs to neither support, then $x_i=0$ and $z_i=0$, so $h_i=x_i-z_i=0$. Hence
\begin{align*}
\operatorname{supp}(h) \subseteq \operatorname{supp}(x) \cup \operatorname{supp}(z).
\end{align*}
Taking cardinalities gives $|\operatorname{supp}(h)| \leq |\operatorname{supp}(x)| + |\operatorname{supp}(z)|$. Since $x,z \in \Sigma_k$, the two supports have cardinality at most $k$, and therefore $|\operatorname{supp}(h)| \leq 2k$. Thus $h \in \Sigma_{2k}$, which is exactly the sparsity level at which the RIP assumption is available.
[/guided]
[/step]
[step:Apply the lower restricted isometry bound to force the difference to vanish]
By the definition of the [restricted isometry constant](/page/Restricted%20Isometry%20Constant), since $h \in \Sigma_{2k}$, the lower restricted isometry inequality gives
\begin{align*}
(1-\delta_{2k}(A))|h|^2 \leq |Ah|^2.
\end{align*}
Using $Ah=0$, this becomes
\begin{align*}
(1-\delta_{2k}(A))|h|^2 \leq 0.
\end{align*}
Because $\delta_{2k}(A)<1$, we have $1-\delta_{2k}(A)>0$. Since $|h|^2 \geq 0$, the preceding inequality implies $|h|^2=0$, hence $h=0$.
[guided]
We now use the only analytic input in the proof: the lower half of the restricted isometry estimate. The definition of the [restricted isometry constant](/page/Restricted%20Isometry%20Constant) says that every vector $u \in \Sigma_{2k}$ satisfies
\begin{align*}
(1-\delta_{2k}(A))|u|^2 \leq |Au|^2.
\end{align*}
The previous step verified exactly the required hypothesis for this estimate, namely $h \in \Sigma_{2k}$. Applying the inequality with $u=h$ gives
\begin{align*}
(1-\delta_{2k}(A))|h|^2 \leq |Ah|^2.
\end{align*}
But the same previous step also proved $Ah=0$, so the right-hand side is zero:
\begin{align*}
(1-\delta_{2k}(A))|h|^2 \leq 0.
\end{align*}
The assumption $\delta_{2k}(A)<1$ gives $1-\delta_{2k}(A)>0$. Since $|h|^2$ is a squared Euclidean norm, $|h|^2 \geq 0$. A nonnegative number multiplied by a positive number cannot be less than or equal to zero unless that nonnegative number is zero. Therefore $|h|^2=0$, and the definiteness of the Euclidean norm gives $h=0$.
[/guided]
[/step]
[step:Conclude injectivity on $\Sigma_k$]
From $h=0$ and $h=x-z$, we obtain $x-z=0$, hence $x=z$. Therefore any two vectors $x,z \in \Sigma_k$ with $Ax=Az$ are equal. Define the restricted measurement map $T_A: \Sigma_k \to \mathbb{R}^m$ by $T_A(x) := Ax$ for $x \in \Sigma_k$. The preceding sentence proves that $T_A$ is injective.
[guided]
We have shown that whenever $x,z \in \Sigma_k$ satisfy $Ax=Az$, their difference $h:=x-z$ must be zero. Therefore
\begin{align*}
x-z=0,
\end{align*}
so $x=z$. Define the restricted measurement map $T_A: \Sigma_k \to \mathbb{R}^m$ by $T_A(x) := Ax$ for $x \in \Sigma_k$. The defining condition for injectivity of $T_A$ is precisely that $T_A(x)=T_A(z)$ implies $x=z$ for all $x,z \in \Sigma_k$. Since $T_A(x)=T_A(z)$ means $Ax=Az$, the argument above proves this condition. Hence $x\mapsto Ax$ is injective on $\Sigma_k$.
[/guided]
[/step]
