Codex @codex  0

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.

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$.

Fix the normalizationThe Lasso penalty uses the L1 norm. All arguments below apply to every minimizer; uniqueness of the coefficient vector is not assumed.

The Karush-Kuhn-Tucker conditions are the subgradient optimality conditionThese conditions are necessary and sufficient because the objective is a convex function. They use the subgradient of the absolute value, coordinate by coordinate.

Put $\delta =\hat{\beta }-{\beta }^0$. Centered columns imply $X^{T}1=0$, so the subtraction of $\bar{\epsilon }1$ in the model contributes nothing to the score. The Karush-Kuhn-Tucker conditions becomeMultiply by ${\delta }^T$. Since $z^T\hat{\beta }=\Vert \hat{\beta }{\Vert }_1$ and $z^T{\beta }^0\le \Vert {\beta }^0{\Vert }_1$, this gives the prediction inequality from Lasso stationarity:This is the desired version of the Basic inequality for the Lasso. Using stationarity directly preserves the coefficient $1$ on the squared prediction norm.

For the Gaussian score event for the Lasso, write $X_j$ for column $j$. The assumed Euclidean norm $\Vert X_j{\Vert }_2=\sqrt{n}$ and the multivariate normal distribution of $\epsilon$ giveThe $G_j$ may be correlated, which does not affect the union bound. Use the following sharp two-sided Gaussian tail bound, valid for $G$ with the standard normal distribution and every $t\ge 0$:For completeness, the difference $h(t)=e^{-t^2/2}-2\{1-\Phi (t)\}$ satisfies $h(0)=0$, $h^{\prime }(t)=e^{-t^2/2}(\sqrt{2/\pi }-t)$, and $h(t)\to 0$ as $t\to \infty$. It first increases and then decreases to zero, so it is nonnegative. This bound avoids introducing an unnecessary factor two.

Here $\Phi$ is the standard normal distribution function. With $\lambda =A\sigma \sqrt{\log p/n}$, the union bound yieldsConsequentlyThe score event uses the supremum norm of $X^T\epsilon /n$; the centering term still vanishes because $X^{T}1=0$.

We next work deterministically on $\Omega$. LetBy Holder inequality, ${\epsilon }^{T}X\delta /n\le c\lambda \Vert \delta {\Vert }_1=c\lambda (a+b)$. Since ${\beta }_N^0=0$, the triangle inequality givesSubstituting both inequalities into the Basic inequality for the Lasso producesBecause $Q\ge 0$, this also proves the relevant Lasso cone condition, $(1-c)b\le (1+c)a$. The assumed Compatibility condition for the Lasso therefore applies to $\delta$:Set $D=(1+c)\lambda \sqrt{s}/\varphi$. Combining these inequalities givesIf $Q>0$, discarding the nonnegative $b$ term shows $\sqrt{Q}\le D$. If $Q=0$, compatibility gives $a=0$, and the preceding inequality then gives $b=0$. In either case $D\sqrt{Q}\le D^2$, soThis is a fast prediction bound and an inactive-coordinate error bound on the same event. It is the fast-rate Lasso prediction bound under compatibility.

Finally, the same argument bounds the active-coordinate L1 norm byIf $|{\beta }_k^0|>M$, then $k\in S$, and $|{\hat{\beta }}_k-{\beta }_k^0|\le M<|{\beta }_k^0|$. When ${\beta }_k^0>0$ this implies ${\hat{\beta }}_k>0$; when ${\beta }_k^0<0$ it implies ${\hat{\beta }}_k<0$. Thus the sign function obeysThis is Lasso sign recovery under compatibility. It concerns the sufficiently large nonzero coefficients; it does not assert that every estimated inactive coefficient is zero.

The Tanaka equation is an example:It has weak solutions and uniqueness in law, but lacks pathwise uniqueness. The value $s(0)=1$ is deliberate: using the sign function with value zero at zero would admit the identically zero solution and would change the example.

For a quick verification, take a Brownian motion $W$ and put $B=\int s(W)dW$. Its quadratic variation is $t$, so it is a Brownian motion by the Lévy characterization of Brownian motion, and associativity of stochastic integration gives $W=\int s(W)dB$. Every weak solution likewise has quadratic variation $t$ and therefore the law of Brownian motion. On this same enlarged filtration, both $W$ and $-W$ solve the equation driven by $B$: $s(-W)=-s(W)$ away from zero, and the Brownian zero set has zero time measure, so the discrepancy at zero contributes nothing to the Itô integral. These solutions differ with positive probability at any positive time. This proves the claimed distinction without relying on a choice of zero convention left unstated.

For a real vector $x$ with support of a vector $S$, this certificate is a vector $h$ whose measurements under the adjoint operator match the active sign function values and lie strictly between minus one and one on the inactive coordinates. If $A_S$ is injective, such a certificate proves that $x$ is the unique basis pursuit minimizer. For a nonzero $v\in \ker A$, injectivity ensures $v_{S^c}\ne 0$, and $0=⟨A^{\ast }h,v⟩$ implies the fixed-sign null space condition. The strict inequality is interpreted coordinatewise if $S^c$ is empty. The condition with the sign function written here is for real variables; complex basis pursuit uses the unit phases of active coordinates instead.