[proofplan] We prove the result with the explicit universal choice \begin{align*} \delta_* = \frac{1}{3}. \end{align*} The main point is to derive the null-space inequality \begin{align*} \|h_S\|_1 < \|h_{S^c}\|_1 \end{align*} for every non-zero $h \in \ker A$ and every index set $S \subset \{1,\dots,N\}$ with $|S| \leq k$. This is obtained by adjoining to $S$ the largest block $S_1 \subset S^c$, applying the restricted isometry property to the combined set $S \cup S_1$, and bounding only the remaining tail blocks by the $\ell^1$ norm on $S^c$. Once this strict null-space inequality is known, exact recovery follows by comparing any feasible competitor $z = x+h$ with the original sparse vector $x$. [/proofplan]

[step:Derive an RIP orthogonality estimate for disjoint sparse vectors]Let $\delta := \delta_{2k}(A)$, and assume \begin{align*} \delta \leq \frac{1}{3}. \end{align*} If $k=0$, then $\Sigma_0=\{0\}$. For $x=0$ we have $y=Ax=0$, and the basis pursuit objective $z \mapsto \|z\|_1$ has the unique global minimizer $z=0$ among all feasible vectors. Hence the assertion is immediate when $k=0$, and for the rest of the proof we assume $k\geq 1$. By definition of the restricted isometry constant, every vector $v \in \mathbb{R}^N$ with at most $2k$ non-zero coordinates satisfies \begin{align*} (1-\delta)\|v\|_2^2 \leq \|Av\|_2^2 \leq (1+\delta)\|v\|_2^2. \end{align*} We first record the consequence that if $u,v \in \mathbb{R}^N$ have disjoint supports and each support has cardinality at most $k$, then \begin{align*} |\langle Au, Av\rangle| \leq \delta \|u\|_2\|v\|_2. \end{align*} Indeed, the vectors $u+v$ and $u-v$ are both supported on $\operatorname{supp}(u)\cup \operatorname{supp}(v)$, which has cardinality at most $2k$. Since the supports are disjoint, we have \begin{align*} \|u+v\|_2^2 = \|u\|_2^2+\|v\|_2^2. \end{align*} The same disjoint-support computation gives \begin{align*} \|u-v\|_2^2 = \|u\|_2^2+\|v\|_2^2. \end{align*} Using the polarization identity in $\mathbb{R}^m$ gives \begin{align*} 4\langle Au,Av\rangle = \|A(u+v)\|_2^2-\|A(u-v)\|_2^2. \end{align*} Applying the RIP upper bound to $u+v$ and the RIP lower bound to $u-v$ gives \begin{align*} 4\langle Au,Av\rangle \leq (1+\delta)(\|u\|_2^2+\|v\|_2^2) - (1-\delta)(\|u\|_2^2+\|v\|_2^2) = 2\delta(\|u\|_2^2+\|v\|_2^2). \end{align*} Applying the same argument to $-v$ gives the corresponding lower bound. Replacing $u$ by $tu$ and $v$ by $t^{-1}v$ for $t>0$, then choosing $t^2=\|v\|_2/\|u\|_2$ when both vectors are non-zero, yields \begin{align*} |\langle Au,Av\rangle| \leq \delta \|u\|_2\|v\|_2. \end{align*} The estimate is immediate if $u=0$ or $v=0$.[/step]

[guided]The RIP controls norms of sparse vectors, but we need to control inner products between images of vectors on disjoint supports. The bridge is polarization. Let $u,v \in \mathbb{R}^N$ have disjoint supports, with $|\operatorname{supp}(u)| \leq k$ and $|\operatorname{supp}(v)| \leq k$. Then $u+v$ and $u-v$ are both $2k$-sparse, so the RIP hypothesis applies to both. Because the supports are disjoint, the Euclidean cross term vanishes. Hence \begin{align*} \|u+v\|_2^2 = \|u\|_2^2+\|v\|_2^2. \end{align*} The same computation with $u-v$ gives \begin{align*} \|u-v\|_2^2 = \|u\|_2^2+\|v\|_2^2. \end{align*} In the measurement space $\mathbb{R}^m$, polarization gives \begin{align*} 4\langle Au,Av\rangle = \|A(u+v)\|_2^2-\|A(u-v)\|_2^2. \end{align*} Now we use the RIP upper estimate on the first term and the RIP lower estimate on the second: \begin{align*} 4\langle Au,Av\rangle \leq (1+\delta)\|u+v\|_2^2-(1-\delta)\|u-v\|_2^2. \end{align*} Substituting the two disjoint-support norm identities yields \begin{align*} 4\langle Au,Av\rangle \leq (1+\delta)(\|u\|_2^2+\|v\|_2^2) - (1-\delta)(\|u\|_2^2+\|v\|_2^2) = 2\delta(\|u\|_2^2+\|v\|_2^2). \end{align*} Replacing $v$ by $-v$ gives the same upper bound for $-\langle Au,Av\rangle$, hence \begin{align*} |\langle Au,Av\rangle| \leq \frac{\delta}{2}(\|u\|_2^2+\|v\|_2^2). \end{align*} This estimate is homogeneous, so we improve it to the product form by scaling. For $t>0$, apply the last inequality to $tu$ and $t^{-1}v$: \begin{align*} |\langle Au,Av\rangle| \leq \frac{\delta}{2}(t^2\|u\|_2^2+t^{-2}\|v\|_2^2). \end{align*} If $u$ and $v$ are non-zero, choose $t^2=\|v\|_2/\|u\|_2$. Then the right-hand side becomes $\delta\|u\|_2\|v\|_2$. If either vector is zero, the same conclusion is immediate. Therefore \begin{align*} |\langle Au,Av\rangle| \leq \delta \|u\|_2\|v\|_2. \end{align*}[/guided]

[step:Partition the complement into decreasing blocks] Fix a non-zero vector $h \in \ker A$ and a set $S \subset \{1,\dots,N\}$ with $|S|\leq k$. For any set $E \subset \{1,\dots,N\}$, define the coordinate restriction map $R_E: \mathbb{R}^N \to \mathbb{R}^N$ by declaring that, for $w \in \mathbb{R}^N$, the vector $R_Ew \in \mathbb{R}^N$ has coordinates \begin{align*} (R_Ew)_i = w_i \text{ for } i \in E, \quad \text{and} \quad (R_Ew)_i = 0 \text{ for } i \notin E. \end{align*} We write $h_E := R_Eh$. Partition $S^c$ into disjoint sets $S_1,S_2,\dots,S_r$ as follows. The set $S_1$ contains the indices of the largest $k$ values of $|h_i|$ on $S^c$, or all remaining indices if fewer than $k$ remain. Having chosen $S_1,\dots,S_{j-1}$, the set $S_j$ contains the indices of the next largest $k$ values of $|h_i|$ among the remaining coordinates. Thus $|S_j|\leq k$ for every $j$, the sets $S_j$ are pairwise disjoint, and \begin{align*} h_{S^c} = \sum_{j=1}^r h_{S_j}. \end{align*} [/step]

[step:Control the tail blocks by the complement $\ell^1$ norm] For every $j \geq 2$ and every $i \in S_j$, the construction of the blocks gives \begin{align*} |h_i| \leq \frac{1}{k}\|h_{S_{j-1}}\|_1. \end{align*} Therefore \begin{align*} \|h_{S_j}\|_2 \leq k^{1/2}\max_{i\in S_j}|h_i| \leq k^{-1/2}\|h_{S_{j-1}}\|_1. \end{align*} Summing over $j \geq 2$ yields \begin{align*} \sum_{j=2}^r \|h_{S_j}\|_2 \leq k^{-1/2}\sum_{j=1}^{r-1}\|h_{S_j}\|_1 \leq k^{-1/2}\|h_{S^c}\|_1. \end{align*} [/step]

[step:Use the kernel equation to estimate $\|h_S\|_1$ through the tail]Let $T := S \cup S_1$. Since $S$ and $S_1$ are disjoint and each has cardinality at most $k$, the set $T$ has cardinality at most $2k$. If $r=1$, then $h=h_T$. Since $h\in\ker A$, this gives $Ah_T=0$, while the RIP lower bound gives \begin{align*} (1-\delta)\|h_T\|_2^2 \leq \|Ah_T\|_2^2=0. \end{align*} Because $1-\delta>0$, it follows that $h_T=0$, hence $h=0$, contradicting the choice of $h$. Therefore $r\geq 2$. Since $h \in \ker A$ and $h = h_T + \sum_{j=2}^r h_{S_j}$, we have \begin{align*} Ah_T = -\sum_{j=2}^r Ah_{S_j}. \end{align*} Taking the [inner product](/page/Inner%20Product) with $Ah_T$ in $\mathbb{R}^m$ gives \begin{align*} \|Ah_T\|_2^2 = -\sum_{j=2}^r \langle Ah_T,Ah_{S_j}\rangle. \end{align*} The supports of $h_T$ and $h_{S_j}$ are disjoint. Moreover $h_T$ is supported on at most $2k$ coordinates and $h_{S_j}$ is supported on at most $k$ coordinates. To use the RIP orthogonality estimate with order $2k$, decompose $h_T=h_S+h_{S_1}$ and apply the estimate separately to the pairs $(h_S,h_{S_j})$ and $(h_{S_1},h_{S_j})$. By the triangle inequality in $\mathbb{R}$, \begin{align*} |\langle Ah_T,Ah_{S_j}\rangle| \leq \delta\|h_S\|_2\|h_{S_j}\|_2+ \delta\|h_{S_1}\|_2\|h_{S_j}\|_2. \end{align*} The triangle inequality for the Euclidean norm gives $\|h_S\|_2+\|h_{S_1}\|_2 \leq \sqrt{2}\|h_T\|_2$, because $h_S$ and $h_{S_1}$ have disjoint supports. Hence \begin{align*} |\langle Ah_T,Ah_{S_j}\rangle| \leq \sqrt{2}\delta\|h_T\|_2\|h_{S_j}\|_2. \end{align*} Since $h_T$ is $2k$-sparse, the RIP lower bound gives \begin{align*} (1-\delta)\|h_T\|_2^2 \leq \|Ah_T\|_2^2. \end{align*} Combining these inequalities yields \begin{align*} (1-\delta)\|h_T\|_2^2 \leq \sqrt{2}\delta\|h_T\|_2\sum_{j=2}^r\|h_{S_j}\|_2. \end{align*} If $h_T=0$, then $h_S=0$ and the strict null-space inequality follows unless $h_{S^c}=0$, which would force $h=0$, contrary to the choice of $h$. If $h_T\neq 0$, divide by $\|h_T\|_2$ and use the tail estimate from the previous step: \begin{align*} \|h_T\|_2 \leq \frac{\sqrt{2}\delta}{1-\delta} \sum_{j=2}^r\|h_{S_j}\|_2 \leq \frac{\sqrt{2}\delta}{1-\delta}k^{-1/2}\|h_{S^c}\|_1. \end{align*} Since $\delta \leq \frac{1}{3}$, we have $\frac{\sqrt{2}\delta}{1-\delta} \leq \frac{1}{\sqrt{2}} < 1$. Therefore \begin{align*} \|h_S\|_1 \leq k^{1/2}\|h_S\|_2 \leq k^{1/2}\|h_T\|_2 \leq \frac{1}{\sqrt{2}}\|h_{S^c}\|_1 < \|h_{S^c}\|_1. \end{align*}[/step]

[guided]We now turn the equation $Ah=0$ into the strict null-space inequality. Define \begin{align*} T := S \cup S_1. \end{align*} The sets $S$ and $S_1$ are disjoint, and each has cardinality at most $k$, so $|T|\leq 2k$. First we remove the degenerate possibility that there is no tail. If $r=1$, then the block decomposition gives $h=h_T$. Since $h\in\ker A$, we have $Ah_T=0$. The RIP lower bound applies because $h_T$ is supported on at most $2k$ coordinates, and gives \begin{align*} (1-\delta)\|h_T\|_2^2 \leq \|Ah_T\|_2^2=0. \end{align*} Since $\delta\leq 1/3$, the coefficient $1-\delta$ is positive, so $h_T=0$. This would imply $h=0$, contradicting the choice of $h$. Therefore $r\geq 2$, and the tail sum is genuinely present. Because $h=h_T+\sum_{j=2}^r h_{S_j}$ and $Ah=0$, linearity of $A$ gives \begin{align*} Ah_T=-\sum_{j=2}^r Ah_{S_j}. \end{align*} We take the Euclidean inner product in $\mathbb{R}^m$ with $Ah_T$ to compare the size of the main block with the tail: \begin{align*} \|Ah_T\|_2^2 = -\sum_{j=2}^r \langle Ah_T,Ah_{S_j}\rangle. \end{align*} For each $j\geq 2$, the support of $h_{S_j}$ is disjoint from both $S$ and $S_1$. The orthogonality estimate from the first step only applies to pairs whose supports each have size at most $k$, so we split $h_T=h_S+h_{S_1}$ and apply it separately to $(h_S,h_{S_j})$ and $(h_{S_1},h_{S_j})$. This yields \begin{align*} |\langle Ah_T,Ah_{S_j}\rangle| \leq \delta\|h_S\|_2\|h_{S_j}\|_2+ \delta\|h_{S_1}\|_2\|h_{S_j}\|_2. \end{align*} Since $h_S$ and $h_{S_1}$ have disjoint supports, the Euclidean Pythagorean identity gives \begin{align*} \|h_T\|_2^2=\|h_S\|_2^2+\|h_{S_1}\|_2^2. \end{align*} Therefore \begin{align*} \|h_S\|_2+\|h_{S_1}\|_2 \leq \sqrt{2}\|h_T\|_2, \end{align*} by the [Cauchy-Schwarz inequality](/theorems/432) in $\mathbb{R}^2$. Hence \begin{align*} |\langle Ah_T,Ah_{S_j}\rangle| \leq \sqrt{2}\delta\|h_T\|_2\|h_{S_j}\|_2. \end{align*} The RIP lower bound again applies to $h_T$ because $|T|\leq 2k$, so \begin{align*} (1-\delta)\|h_T\|_2^2 \leq \|Ah_T\|_2^2. \end{align*} Combining this lower bound with the preceding inner-product estimate gives \begin{align*} (1-\delta)\|h_T\|_2^2 \leq \sqrt{2}\delta\|h_T\|_2\sum_{j=2}^r\|h_{S_j}\|_2. \end{align*} If $h_T=0$, then $h_S=0$. Since $h\neq 0$, we must have $h_{S^c}\neq 0$, and therefore \begin{align*} \|h_S\|_1=0<\|h_{S^c}\|_1. \end{align*} If $h_T\neq 0$, divide by $\|h_T\|_2$ and use the tail estimate proved in the previous step: \begin{align*} \|h_T\|_2 \leq \frac{\sqrt{2}\delta}{1-\delta} \sum_{j=2}^r\|h_{S_j}\|_2 \leq \frac{\sqrt{2}\delta}{1-\delta}k^{-1/2}\|h_{S^c}\|_1. \end{align*} Because $\delta\leq 1/3$, we have \begin{align*} \frac{\sqrt{2}\delta}{1-\delta} \leq \frac{\sqrt{2}/3}{2/3} = \frac{1}{\sqrt{2}}. \end{align*} Finally, since $k\geq 1$ and $h_S$ is supported on at most $k$ coordinates, the Cauchy-Schwarz inequality gives $\|h_S\|_1\leq k^{1/2}\|h_S\|_2$. Also $\|h_S\|_2\leq\|h_T\|_2$ because $S\subset T$. Thus \begin{align*} \|h_S\|_1 \leq k^{1/2}\|h_S\|_2 \leq k^{1/2}\|h_T\|_2 \leq \frac{1}{\sqrt{2}}\|h_{S^c}\|_1 < \|h_{S^c}\|_1. \end{align*} This proves the strict null-space inequality.[/guided]

[step:Compare every feasible competitor with the sparse vector] Let $x \in \Sigma_k$, and let $S := \operatorname{supp}(x)$, so $|S|\leq k$. Let $z \in \mathbb{R}^N$ be any feasible vector for basis pursuit with $Az=Ax$. Define $h := z-x$. Then $Ah=0$, so $h\in \ker A$. If $h=0$, then $z=x$. If $h\neq 0$, the strict null-space inequality from the previous step gives \begin{align*} \|h_S\|_1 < \|h_{S^c}\|_1. \end{align*} Since $x_{S^c}=0$, the triangle inequality gives \begin{align*} \|z\|_1 = \|x+h\|_1 = \|x_S+h_S\|_1+\|h_{S^c}\|_1. \end{align*} Applying the [reverse triangle inequality](/theorems/2300) on the coordinates in $S$ yields \begin{align*} \|z\|_1 \geq \|x_S\|_1-\|h_S\|_1+\|h_{S^c}\|_1. \end{align*} Using $\|h_S\|_1 < \|h_{S^c}\|_1$, we obtain \begin{align*} \|z\|_1 > \|x_S\|_1 = \|x\|_1. \end{align*} Thus every feasible $z\neq x$ has strictly larger $\ell^1$ norm than $x$. Therefore $x$ is the unique minimizer of the basis pursuit problem, and basis pursuit exactly recovers every $k$-sparse vector from $y=Ax$ whenever $\delta_{2k}(A)\leq \frac{1}{3}$. This proves the theorem with the universal constant $\delta_*=\frac{1}{3}$. [/step]