Codex @codex  0

Let $\delta =\hat{\beta }-{\beta }^0$, $s=|S|>0$ and $\varphi >0$. On the score event $\Vert X^T\eta {\Vert }_{\infty }/n\le c\lambda$ with $0<c<1$, the prediction inequality from Lasso stationarity gives $Q+(1-c)\lambda \Vert {\delta }_{S^c}{\Vert }_1\le (1+c)\lambda \Vert {\delta }_S{\Vert }_1$. If the Compatibility condition for the Lasso with constant $\varphi$ holds on this cone, then $Q+(1-c)\lambda \Vert {\delta }_{S^c}{\Vert }_1\le (1+c{)}^2{\lambda }^{2}s/{\varphi }^2$. Here $Q=\Vert X\delta {\Vert }_2^2/n$ and $S$ is the true support of a vector.

The number of nonzero coordinates of a finite vector is its L0 sparsity count. It vanishes only at zero, but is unchanged under multiplication by a nonzero scalar, so it is not a norm. Minimizing it under linear measurement constraints finds a sparse vector with the smallest possible support of a vector. Sparse injectivity of order $s$ guarantees unique recovery of every sparse vector with at most $s$ nonzero coordinates by this objective.

For $0<q\le 1$, this strict inequality for every nonzero $v\in \ker A$ and every $|S|\le s$ is equivalent to unique constrained ${\ell }^q$ recovery of every sparse vector of order $s$. For sufficiency, use $|x_i+v_i{|}^q\ge |x_i{|}^q-|v_i{|}^q$ on the support of a vector. For necessity compare $x=-v_S$ with $v_{S^c}$, which have the same measurements. The statement concerns uniform recovery over the whole sparse class, rather than a single signed vector.

For any field $F$ and vector subspace $W\subseteq F^m$, some $u\in W$ has at least $\dim W$ nonzero coordinates. Choose $u$ with largest support of a vector $S$. Restriction from $W$ to $F^S$ is injective: a nonzero vector in its kernel of a linear map vanishes on $S$, so adding it to $u$ would enlarge $S$. Thus $\dim W\le |S|$. The argument works over finite fields, where assuming a generic vector avoids finitely many hyperplanes would be invalid.

If the Lq null space property holds at $q\le 1$, it holds at every $0<p<q$. Order a nonzero null vector's magnitudes $a_1\ge \cdots \ge a_N$ and put $t=a_s>0$. Since $p-q<0$, the top-$s$ $p$-power sum is at most $t^{p-q}$ times its $q$-power sum, while the tail $p$-power sum is at least that multiple of the tail $q$-power sum. The strict $q$ inequality therefore gives the strict $p$ inequality. The largest $s$ magnitudes are the worst support of a vector, so all other supports satisfy it too.

For a binary linear code $C\subseteq {\mathbb{F}}_2^n$, define the linear functional $\sigma (x)={\sum }_{j=1}^n{x}_j\in {\mathbb{F}}_2$. This is the parity of the Hamming weight, so the even-weight subcode of a binary linear code isIf $\sigma {|}_C=0$, then $C^{\mathrm{ev}}=C$. Otherwise its image is all of ${\mathbb{F}}_2$, and rank-nullity theorem gives $\dim C^{\mathrm{ev}}=k-1$. The kernel of a linear map is a linear subspace, proving the required dichotomy including closure under addition.

Let $G$ be a full-rank $k\times n$ generator matrix. Messages $a\in {\mathbb{F}}_2^k$ correspond bijectively to codewords $aG$. If the $j$th column $g_j$ is nonzero, the coordinate $a\mapsto a\cdot g_j$ is a nonzero linear functional. Choose $a_0$ with $a_0\cdot g_j=1$. Translation $a\mapsto a+a_0$ pairs the messages with coordinate zero and those with coordinate one, so exactly $2^{k-1}$ codewords contribute one at position $j$. Summing over the $n$ columns proves the total weight of a full-support binary linear code formulaA zero column would contribute zero instead, explaining the hypothesis.

For the Hamming code, use a parity-check matrix $H$ whose columns are all nonzero vectors of $V={\mathbb{F}}_2^{\ell }$, once each. Then $C_{H,\ell }=\ker H$ and $n=2^{\ell }-1$. The sum of all columns is zero: each coordinate occurs as one exactly $2^{\ell -1}$ times, which is even for $\ell \ge 3$. ConsequentlyUnder this column labelling, the support of a vector of a codeword is identified with a set of distinct nonzero columns whose sum is zero. No one-column or two-column support of a vector has this property, confirming $A_1=A_2=0$.

We can count the low-weight coefficients of a binary Hamming code directly. For weight three, choose ordered distinct nonzero columns $a,b$ in $n(n-1)$ ways. The third must be $a+b$, which is nonzero and different from both. Every unordered support of a vector has $3!$ orderings, so $A_3=n(n-1)/3!$.

For weight four, the first two columns $a,b$ are again distinct and nonzero. The third $c$ must avoid $a,b,a+b$, giving $n-3$ possibilities. The fourth is $d=a+b+c$; it is nonzero because $c\ne a+b$, and cannot equal any of the first three because those are distinct. Conversely every ordered zero-sum four-tuple arises in this way. Dividing by $4!$ gives $A_4=n(n-1)(n-3)/4!$.

For weight five, the first three columns $a,b,c$ must be linearly independent. If $a+b+c=0$, the sum condition would force the fourth and fifth to coincide. Thus there are $n(n-1)(n-3)$ choices for the first three. Put $t=a+b+c$. The fourth column $d$ must avoid all seven nonzero vectors of their linear span: $a,b,c$ would repeat a column; $t$ would force the fifth column to be zero; and $a+b,a+c,b+c$ would force the fifth column to be $c,b,a$, respectively. Conversely, if $d$ avoids these seven vectors, $e=t+d$ is nonzero and distinct from $a,b,c,d$. This gives $n-7$ choices for $d$ and determines $e$. Dividing by $5!$ yieldsAt $\ell =3$, the last count is zero, as the argument also shows.

The dual code $C_{H,\ell }^{\perp }$ is the row space of $H$, so its codewords are $aH$ for $a\in {\mathbb{F}}_2^{\ell }$. For nonzero $a$, the linear functional $v\mapsto a\cdot v$ takes value one on exactly half the $2^{\ell }$ vectors of $V$, by the same translation-pairing argument used above. Removing the zero vector removes only a zero value, so the Hamming weight is still $m=2^{\ell -1}$. Since $H$ has matrix rank $\ell$, distinct $a$ give distinct codewords. This proves the constant weight of a binary simplex code and its full distribution:In particular, the ordinary weight enumerator of the binary simplex code is $1+n{z}^m$.

Apply the MacWilliams identity to this dual code, whose size is $2^{\ell }=n+1$. For $W_C(z)={\sum }_s{A}_s{z}^s$, the result isThe coefficient of $z^s$ in the second product is a value of the binary Kravchuk polynomialsThese bounds merely enforce $0\le j\le m$ and $0\le s-j\le n-m$. Since $n-m=2^{\ell -1}-1$, they agree with the bounds in the PDF. Therefore the requested formula isFor a further check on the low-weight counts, $n=2m-1$ givesThus $K_3(m)=m-1$, $K_4(m)=\left(\genfrac{}{}{0ex}{}{m-1}{2}\right)$, and $K_5(m)=-\left(\genfrac{}{}{0ex}{}{m-1}{2}\right)$. Substituting these into the boxed formula and using $m=(n+1)/2$ reproduces the three direct combinatorial counts above.

Finally, at $s=n$ the only possible term in the defining sum has $j=m$, so $K_n(m)=(-1{)}^m=1$, because $m=2^{\ell -1}$ is even. ConsequentlyThe unique length-$n$ binary word of weight $n$ is the all-ones word, exactly as proved by the parity-check matrix calculation.

Use ${\mathbb{F}}_{32}={\mathbb{F}}_2[\omega ]$ with ${\omega }^5={\omega }^2+1$. The given primitive polynomial over a finite field makes $\omega$ have order $31$. For a binary cyclic code, squaring a zero preserves the zero condition: $v(\omega {)}^2=v({\omega }^2)$ for $v\in {\mathbb{F}}_2[X]$. Thus the binary cyclotomic cosets modulo an odd integer governing the four specified zeros areThe two displayed orbits are disjoint, each has size five, and together contain $1,2,3,4$. Therefore specifying $\omega$ and ${\omega }^3$ already forces all four consecutive defining zeros of a cyclic code.

The minimal polynomial of an algebraic element of $\omega$ is $m_1(X)=X^5+X^2+1$. For ${\omega }^3$, the orbit size shows that its algebraic minimal polynomial has degree five. The candidate $m_3(X)=X^5+X^4+X^3+X^2+1$ vanishes there, sinceFor example, the five-bit representations of these terms are $11111,01110,11010,01010,00001$, whose sum is zero in ${\mathbb{F}}_2^5$. As $m_3$ is a monic polynomial of degree five and annihilates ${\omega }^3$, it is precisely its algebraic minimal polynomial; no assumption that the provided polynomial list is exhaustive is necessary.

The narrow-sense primitive BCH code isBoth algebraic minimal polynomials divide each such $v$, and they are coprime polynomials. Their product is a divisor of $X^{31}-1$. Hence the generator polynomial is their product. Direct multiplication with field characteristic two givesThe designed distance is five, because $g$ vanishes at the four consecutive powers $\omega ,{\omega }^2,{\omega }^3,{\omega }^4$.

Here is an explicit BCH bound proof for these zeros. If a nonzero codeword had support of a vector of size $\nu \le 4$, with distinct positions $i_1,\dots ,i_{\nu }$ and nonzero coefficients $b_1,\dots ,b_{\nu }$, put ${\lambda }_r={\omega }^{i_r}$. Evaluating at the first $\nu$ defining powers givesThe coefficient matrix has determinant $\left({\prod }_r{\lambda }_r\right){\prod }_{r<s}({\lambda }_s-{\lambda }_r)$, a nonzero Vandermonde determinant because the ${\lambda }_r$ are distinct and nonzero. It therefore forces every $b_r=0$, a contradiction. Thus the minimum Hamming distance is at least five.

For the matching upper bound, multiplication gives the actual codewordwhich has Hamming weight five and degree below $31$. HenceThis proves the actual distance without needing the optional theorem. Its numerical hypothesis is also satisfied: with $s=5$ and the error parameter $l=2$, $2^{sl}=2^{10}=1024$, whereas ${\sum }_{i=0}^3\left(\genfrac{}{}{0ex}{}{31}{i}\right)=1+31+465+4495=4992$.

Now calculate the root-evaluation syndrome for a cyclic code from the received polynomial. Reduction modulo $m_1(X)$ gives $u(X)\equiv X^3$, so $S_1=u(\omega )={\omega }^3$. Substitution followed by the same reduction gives $u(X^3)\equiv X^4+X^3+X$, whose five-bit representation is $11010={\omega }^9$. ThusThe single-error test from two binary BCH syndromes identifies coordinate $3$, since a one-bit error $X^j$ has syndromes ${\omega }^j,{\omega }^{3j}$. Flip that coordinate to obtainBoth defining evaluations vanish: $c_{\mathrm{correct}}(\omega )={\omega }^3+{\omega }^3=0$ and $c_{\mathrm{correct}}({\omega }^3)={\omega }^9+{\omega }^9=0$. More directly,so it is certainly a codeword of $\mathcal{X}$. It is at Hamming distance one from $u$. Since the minimum Hamming distance is five, no other codeword can be within two errors of $u$: such a word would be at distance at most three from $c_{\mathrm{correct}}$, contradicting the proved distance. Thus this is the unique bounded-distance decoding under the linear code's two-error guarantee.

The decoded polynomial printed in the original PDF is incorrect. It instead adds $X^{10}$ to $u$, giving a polynomial $c_{\mathrm{printed}}=u+X^{10}$. Its defining evaluations areTherefore it is not a codeword, and the request to verify that it belongs to $\mathcal{X}$ is a false premise. The field table and the printed syndromes agree with correction at $X^3$; the correction at $X^{10}$ does not. The boxed corrected polynomial resolves this source error and supplies the intended decoding and membership proof.

Let $S=\mathrm{supp}x$ be the support of a vector $x$, with $|S|\le s$. Suppose the null space property holds. Every other feasible vector is $z=x+v$, where $0\ne v\in \ker A$. Splitting its L1 norm over $S$ and $S^c$ and using the triangle inequality givesThus the sparse vector $x$ is the unique minimizer in basis pursuit. Notice that the argument works for complex coordinates: it uses the absolute value inequality, rather than a real sign function.

Conversely, suppose basis pursuit uniquely recovers every sparse vector of order $s$. Fix $0\ne v\in \ker A$ and any $S$ with $|S|\le s$. Take $x=-v_S$ and $z=v_{S^c}$. These vectors have the same measurements, because $A{v}_S+A{v}_{S^c}=0$, and they are distinct since $z-x=v\ne 0$. The vector $x$ has at most $s$ nonzero coordinates, so uniqueness givesThis is the null space property for every such $S$. Uniform unique recovery by basis pursuit is equivalent to the order-$s$ null space property.

First the null space property implies sparse injectivity. If a nonzero $v\in \ker A$ had at most $2s$ nonzero coordinates, partition its support of a vector into disjoint $S,T$ with $|S|,|T|\le s$. Applying the null space property to each of these sets yieldswhich is impossible. Hence the null space contains no nonzero sparse vector of order $2s$.

The feasible vector $x$ has $\Vert x{\Vert }_0\le s$, where the L0 sparsity count counts its nonzero coordinates. Any different feasible $z$ with $\Vert z{\Vert }_0\le \Vert x{\Vert }_0$ would give a nonzero null space vector $z-x$ with at most $2s$ nonzero coordinates, contrary to sparse injectivity. Consequently every different feasible $z$ has strictly larger L0 sparsity count. The unique sparsest feasible vector is $x$:This proof does not treat the L0 sparsity count as a genuine norm; no triangle inequality for it is needed.

Use the stated characterization by the Lq null space property. Raising an Lq quasi-norm comparison to its positive exponent preserves its order, so the hypothesis at $q$ says that, for every nonzero $v\in \ker A$ and every $|S|\le s$,We prove the corresponding $p$ inequality; this is monotonicity of uniform sparse recovery in the exponent.

Fix a nonzero null space vector and arrange its coordinate magnitudes as $a_1\ge \cdots \ge a_N\ge 0$. Assume $s\ge 1$. The Lq null space property rules out a nonzero null space vector supported on at most $s$ coordinates, so $s<N$ and $t=a_s>0$. Since $p-q<0$, the factors $a_j^{p-q}$ are at most $t^{p-q}$ for $j\le s$ and at least $t^{p-q}$ for $j>s$ with $a_j>0$. Terms with $a_j=0$ contribute zero and require no negative power of zero. ThusThe largest $s$ coordinates maximize the $p$-power sum on any set of size at most $s$. Its complement therefore has the smallest complementary $p$-power sum. The displayed strict inequality proves the Lq null space property at exponent $p$ for every allowed support of a vector. The stated recovery characterization now applies to the Lq quasi-norm at $p$.

If $\ker A=\{0\}$, the measurement constraint already singles out $x$, for every objective; if $s=0$, only the zero sparse vector needs recovery. These cases do not need a positive threshold. Uniform recovery at $q$ implies uniform recovery at every $0<p<q$:

Work in ${\mathbb{C}}^N$, the domain of the matrix $A$; the printed ${\mathbb{C}}^n$ in the introduction is a dimension typo. For a fixed nonempty support of a vector $S$, write $u$ for the coordinates of $x$ in $S$. ThenThe Gram matrix $A_S^{\ast }{A}_S$ is a Hermitian matrix, so its difference from the identity matrix is also a Hermitian matrix. By the finite-dimensional spectral theorem, its matrix 2-norm is the largest absolute eigenvalue, equivalentlyIndeed, an expansion in an orthonormal eigenbasis bounds every Rayleigh quotient by the largest absolute eigenvalue, and an appropriate eigenvector attains that bound. The restricted isometry constant must bound this quantity for every $S$ of size at most $s$, and the maximum of these quantities suffices for all sparse vectors of order $s$. There are finitely many sets, so the maximum exists. The empty set contributes zero. Therefore

Use the natural empty-sum convention ${\mu }_1(0)=0$ for cumulative coherence. This is needed for the printed case $s=1$. For $x=0$ the conclusion is immediate. Otherwise let $S$ be its support of a vector, with $k=|S|\le s$. The Gram matrix $G=A_S^{\ast }{A}_S$ has diagonal entries one because the columns have unit Euclidean norm. Each off-diagonal row sum is bounded byThe last inequality uses monotonicity of cumulative coherence: enlarging an index set only adds nonnegative summands. There are enough indices to enlarge it because $s\le N$.

The Gershgorin circle theorem places every eigenvalue of $G$ within distance ${\mu }_1(s-1)$ of one. Since $G$ is a Hermitian matrix, its eigenvalues are real, and the finite-dimensional spectral theorem givesThis is the cumulative coherence bound for restricted isometry. The lower bound remains valid when ${\mu }_1(s-1)>1$, although it is then nonpositive. No assumption that the matrix is already a near isometry is required. The distortion is bounded by ${\mu }_1(s-1)$ on every order-$s$ sparse vector.

Let $\sigma =\mathrm{sgn}(x_S)$, using the real sign function on the support of a vector $x$. The fixed-sign null space condition in the PDF uses $S^c$ on its right-hand side. This complement is essential. For any real coordinate $x_j\ne 0$, the supporting-line inequality for the absolute value isEvery distinct feasible vector is $x+v$ with $0\ne v\in \ker A$. Summing the coordinate inequalities on $S$ and adding the L1 norm on $S^c$ givesThe strict final inequality is precisely the fixed-sign null space condition. Hence $x$ is the unique basis pursuit minimizer. Unlike the null space property of Question 1, this condition concerns the particular sign function values of $x$, rather than every vector supported in $S$.

Assume $x$ is the unique basis pursuit minimizer. Fix $0\ne v\in \ker A$ and setThere is $\epsilon >0$ such that the sign function of $x_j+t{v}_j$ equals that of $x_j$ at every $j\in S$ whenever $|t|<\epsilon$. To choose it, take less than the minimum of $|x_j|/|v_j|$ over the nonzero $v_j$ in $S$; if that set is empty, any positive $\epsilon$ works. On this interval the L1 norm has the exact expressionFor $0<t<\epsilon$, both $x+tv$ and $x-tv$ are distinct feasible vectors. Uniqueness forces their objective differences to be strictly positive, so $\alpha +\beta >0$ and $-\alpha +\beta >0$. ThereforeThe fixed-sign null space condition is necessary as well as sufficient. This argument also covers an empty support of a vector: then $\alpha =0$ and the nonzero null space vector has $\beta >0$. Strictness is indispensable: equality would make a sufficiently short feasible segment have the same objective as $x$.

Let $u=A^{\ast }h$ be the strict dual certificate for basis pursuit supplied by condition (ii). For $0\ne v\in \ker A$, we haveHere the adjoint operator is the real transpose. The injectivity of $A_S$ ensures $v_{S^c}\ne 0$: otherwise $A_S{v}_S=0$ would force $v=0$. Thus at least one nonzero term lies outside the support of a vector $x$. Since $|u_l|<1$ at every such index,This proves the fixed-sign null space condition, so part (a) gives uniqueness in basis pursuit. If $S^c$ is empty, the injectivity of $A_S=A$ instead means there is no nonzero null space vector, and the feasible set is a singleton. Injective active columns and a strict dual certificate for basis pursuit ensure unique recovery. Both ingredients matter: strictness outside $S$ cannot detect a nonzero null space direction supported entirely inside $S$.

Work in positive dimension $n\ge 1$. A cap set has no distinct zero-sum triple. Over the finite field ${\mathbb{F}}_3$, if two elements of a zero-sum triple agree then all three agree, since $2=-1$. Thus a zero-sum triple in a cap set must be diagonal. We prove the Ellenberg–Gijswijt cap-set bound by the polynomial method in combinatorics, keeping the exponential constant explicit and removing the fixed prefactor.

First prove the needed slice rank of a diagonal tensor over any field. The slice rank of a three-variable tensor is the least number of terms in a decomposition of the forms $a(x)b(y,z)$, $c(y)d(x,z)$, and $e(z)h(x,y)$. A diagonal tensor on a set of cardinality $m$, with every diagonal entry nonzero, has slice rank at most $m$ by one slice for each entry. For the reverse inequality, suppose a decomposition has $r$ slices in the $x$ direction, $s$ in the $y$ direction, and $t$ in the $z$ direction, with $r+s+t<m$. LetThe rank-nullity theorem gives $\dim W\ge m-r$. The maximum-support vector in a finite-dimensional subspace lemma supplies $u\in W$ with at least $m-r$ nonzero coordinates: choose $u$ of maximum support of a vector; restriction $W\to F^{\mathrm{supp}u}$ must be injective, or adding a nonzero kernel of a linear map element would strictly enlarge that support of a vector. This argument is valid over finite fields, without any assumption that a generic vector avoids all coordinate hyperplanes.

Contract the proposed tensor decomposition in $x$ against $u$. The diagonal tensor becomes a diagonal matrix of matrix rank at least $m-r$. All $x$ slices vanish. Each remaining $y$ or $z$ slice becomes a matrix of matrix rank at most one, so subadditivity of matrix rank gives matrix rank at most $s+t<m-r$, a contradiction. Therefore the slice rank of a diagonal tensor is exactly $m$.

Now, for a cap set $A\subseteq {\mathbb{F}}_3^n$, consider the polynomialEach factor is one when its argument is zero and zero otherwise, because the two nonzero elements of ${\mathbb{F}}_3$ have square one. Thus $P$ is the indicator function of $x+y+z=0$. Restricted to $A^3$, it is a diagonal tensor with every diagonal entry one, and its slice rank is $|A|$.

Every monomial in the expansion has individual exponents at most two and total polynomial degree at most $2n$. Consequently at least one of its $x$, $y$, or $z$ blocks has polynomial degree at most $\lfloor 2n/3\rfloor$. Assign each monomial to one such block, breaking ties in a fixed way, and collect assigned terms by the monomial in that block. Each collection is a slice. Ifthere are at most $m_n$ slices in each direction. Thus $|A|\le 3m_n$.

The low-degree monomial count for the cap-set bound follows directly from a weighted sum. Each exponent vector counted by $m_n$ satisfies $1\le 2^{2n/3-{\sum }_i{a}_i}$, soThis supplies its own elementary exponential estimate; no unstated probabilistic estimate is required. Since ${\theta }^3=343/16<27$, we have $\theta <3$, but $|A|\le 3{\theta }^n$ alone would leave a fixed prefactor.

Use Cartesian powers of cap sets to remove that prefactor. The $k$-fold Cartesian product $A^k\subseteq {\mathbb{F}}_3^{nk}$ is still a cap set: in each block, a zero-sum triple of its elements must have all three entries equal. Hence $|A{|}^k\le 3{\theta }^{nk}$. Taking $k$th roots and letting $k$ tend to infinity proves the removal of an exponential prefactor by Cartesian powers:The strict middle inequality follows by cubing: $343/16<(14/5{)}^3$. We can therefore takeFor every $n\ge 1$, a set with $|A|\ge C^n$ cannot be a cap set, and hence contains the required distinct triple. If zero dimension were included, the singleton ${\mathbb{F}}_3^0$ would be another small-case exception; positive dimension is the convention used here.

The strict null space property of order $s$ isHere $v_S$ agrees with $v$ on $S$ and is zero elsewhere. Suppose a nonzero null vector had at most $2s$ nonzero entries. Split its support of a vector into disjoint sets $S,T$ of size at most $s$. Applying the null space property to both sets would give $\Vert v_S{\Vert }_1<\Vert v_T{\Vert }_1$ and $\Vert v_T{\Vert }_1<\Vert v_S{\Vert }_1$, a contradiction. Empty parts cause the same contradiction. Thus no such nonzero null vector exists.

For an $s$-sparse $x$, the feasible vector $x$ has $\Vert x{\Vert }_0\le s$, where the zero-subscript quantity counts nonzero entries and is not a norm. Any feasible competitor $z$ with $\Vert z{\Vert }_0\le \Vert x{\Vert }_0$ also has at most $s$ nonzero entries. The difference $z-x\in \ker A$ has at most $2s$ nonzero entries, so $z=x$. Competitors with larger support have strictly larger objective. Therefore every s-sparse vector is the unique sparsest feasible vector. This is sparse injectivity; for $s=0$ the only sparse vector is zero and the conclusion is immediate.

It is equivalent to minimize $\Vert z{\Vert }_q$ or its $q$th power $F_q(z)={\sum }_i|z_i{|}^q$, because taking the $q$th root is strictly increasing. For $q<1$, this is an Lq quasi-norm, while $q=1$ gives the L1 norm.

Assume the Lq null space property of order $s$. Let $x$ have support of a vector $S$ with $|S|\le s$, and let $z=x+v$ be any distinct feasible vector. Then $0\ne v\in \ker A$. The triangle inequality for complex magnitudes and the subadditivity $(a+b{)}^q\le a^q+b^q$ giveFor $q=1$ the same inequality follows directly from the triangle inequality. Since $x=0$ off $S$,Thus $x$ is the unique minimizer.

Conversely, suppose every $s$-sparse vector is the unique minimizer for its measurements. Fix $0\ne v\in \ker A$ and any $S$ with $|S|\le s$. The vectors $x=-v_S$ and $z=v_{S^c}$ are distinct and satisfy $Az=Ax$, since $Av=0$. Uniqueness for this $x$ therefore implies $F_q(x)<F_q(z)$, exactly the required strict inequality. HenceThe quantifier is uniform over the entire sparse class. Recovery of one particular signed vector alone would not imply this null space property.

Use the Lq null space property established above. Fix $0\ne v\in \ker A$ and order its magnitudes $a_1\ge \cdots \ge a_N\ge 0$. For a fixed exponent, the sum over the largest $s$ entries is the greatest sum over any support of a vector of size at most $s$, so it suffices to verify the property for this ordered support.

If $s\ge 1$, put $t=a_s$. We have $t>0$: otherwise $v$ would have fewer than $s$ nonzero entries, and applying the Lq null space property to its support would assert a positive number is less than zero. For $0<p<q$, the exponent $p-q$ is negative. ThusThe first inequality uses $a_i\ge t$ on the top part; the last uses $0<a_i\le t$ in the tail. Zero tail entries contribute zero without invoking a negative power of zero. Every other set of size at most $s$ has no larger top sum and no smaller complementary sum, so it too satisfies the strict $p$ inequality. The preceding equivalence provesThis is monotonicity of uniform sparse recovery in the exponent. If $\ker A=\{0\}$ the feasible vector is unique regardless of the objective; if $s=0$, only the zero vector is relevant. These cases need no threshold argument.

Let $T$ be the support of a vector $\hat{x}$. If the columns indexed by $T$ were linearly dependent, there would be a nonzero $h$ supported in $T$ with $Ah=0$. For sufficiently small real $t$, the nonzero signs of ${\hat{x}}_T$ remain fixed, soBoth positive and negative $t$ preserve the residual and hence feasibility, even with noise. A nonzero slope contradicts minimality in one direction. A zero slope gives distinct minimizers, contradicting uniqueness. Thus those columns are linearly independent, andThis proves the sparse vector assertion without assuming a noiseless residual.