Codex @codex  0

Put $d_i(u)=((G^{(1)}u{)}_i,(G^{(2)}u{)}_i)$. The image penalty is discrete isotropic total variation ${\sum }_i\Vert d_i(u){\Vert }_2$; the fidelity term is the L1 norm $\Vert u-f{\Vert }_1$. Introduce scalars $v_i,t_i$ and minimize the linear objectivesubject to the following affine residuals being cone-feasible:where ${\mathcal{L}}_3=\{(t,a,b):t\ge \sqrt{a^2+b^2}\}$ is the Lorentz cone. Every component displayed is affine in $(u,v,t)$, so stacking them gives exactly the requested $Ax-b\in K$ form, withThe first two inequalities imply $v_i\ge |u_i-f_i|$, so separate nonnegativity constraints for $v_i$ are unnecessary. The cone constraints imply $t_i\ge \Vert d_i(u){\Vert }_2$. Every lifted feasible objective bounds the original objective from above; choosing $v_i=|u_i-f_i|$ and $t_i=\Vert d_i(u){\Vert }_2$ gives equality. Since both objective weights are positive, an optimum uses these tight values. Thus the lift is an exact second-order cone program for box-constrained TV-L1 denoising.

The product cone is proper, closed, convex and self-dual. The stacked $A$ has full column rank: the box rows recover $u$, the fidelity rows then recover $v$, and the first coordinates of the Lorentz blocks recover $t$. Strict feasibility is also explicit: choose $u_i=1/2$, then take $v_i>|u_i-f_i|$ and $t_i>\Vert d_i(u){\Vert }_2$.

For generic cone slack $(r,q)$, a canonical barrier ison $r_j>0$ and $q_{i0}>\sqrt{q_{i1}^2+q_{i2}^2}$. The positive sheet condition matters: positivity of the quadratic expression alone would also include the wrong Lorentz nappe.

Composing the barrier with the affine residual map givesIts domain includes the strict inequalities above. Each orthant coordinate contributes one to the self-concordant barrier parameter and each Lorentz block contributes two. Therefore the product-cone logarithmically homogeneous barrier hasThe affine composition $\Phi$ is the barrier used in the primal variables; it need not itself be logarithmically homogeneous in $(u,v,t)$ because the image data and box offsets are affine constants.

The Szemerédi theorem says that for every integer $k\ge 2$ and every $\delta >0$, there is $N_0(k,\delta )$ such that, for $N\ge N_0$, every $A\subseteq \{1,\dots ,N\}$ with $|A|\ge \delta N$ contains a nonconstant arithmetic progressionEquivalently, every subset of the positive integers with positive upper asymptotic density contains arithmetic progressions of every finite length. Length one is immediate.

The Furstenberg multiple recurrence theorem states that for every probability measure-preserving system, every measurable $B$ with $\mu (B)>0$, and every integer $k\ge 2$, there is $n\ge 1$ withHere $T^{-jn}B$ means a preimage, so invertibility is unnecessary. The Furstenberg multiple recurrence theorem also does not assume an ergodic transformation.

We prove the implication to the finite Szemerédi theorem by constructing the Furstenberg correspondence principle explicitly. Suppose, to the contrary, that for fixed $k$ and $\delta >0$ there are $N_{\ell }\to \infty$ and $A_{\ell }\subseteq \{1,\dots ,N_{\ell }\}$ with $|A_{\ell }|\ge \delta N_{\ell }$, but with no length-$k$ arithmetic progression of positive common difference. In the binary full shift $\Omega =\{0,1{\}}^{\mathbb{Z}}$, encode $A_{\ell }$ as $x_j^{(\ell )}=1_{A_{\ell }}(j)$, taking all coordinates outside $A_{\ell }$ to be zero. Let $S$ be the left shift, $(S\omega {)}_j={\omega }_{j+1}$, and setThe cylinder set $C$ is a clopen set, and ${\nu }_{\ell }(C)=|A_{\ell }|/N_{\ell }\ge \delta$. The binary full shift is a compact metric space, so compactness of probability measures on a compact metric space gives a subsequence of these empirical measures with weak convergence of probability measures to a Borel probability measure $\nu$.

For every continuous $h$ on the full shift,Passing to the weak limit shows that $\nu$ is an invariant measure for the continuous left shift. Thus $(\Omega ,\mathcal{B},\nu ,S)$ is a probability measure-preserving system. Since the indicator function of $C$ is continuous, $\nu (C)\ge \delta$.

Apply the Furstenberg multiple recurrence theorem to $C$. For some $n\ge 1$, the clopen sethas $\nu (D)>0$. Its continuous indicator function gives ${\nu }_{\ell }(D)\to \nu (D)>0$. For large $\ell$, at least one $S^a{x}^{(\ell )}$ in the defining empirical measure therefore belongs to $D$. The choice of left shift impliesso $a,a+n,\dots ,a+(k-1)n$ lies in $A_{\ell }$. This contradicts the assumed absence of arithmetic progressions and proves the finite Szemerédi theorem. Applying the finite Szemerédi theorem on intervals where an infinite set has density bounded below proves the stated upper asymptotic density formulation.

For multiple recurrence for circle rotations, write $\mathbb{T}=\mathbb{R}/\mathbb{Z}$ and $R_{\alpha }x=x+\alpha$, with normalized Lebesgue measure $m$, which is the Haar measure of the circle group. Fix a measurable $B\subseteq \mathbb{T}$ with $m(B)>0$ and $k\ge 2$. If $\alpha$ is rational, there is $q\ge 1$ with $R_{\alpha }^q$ the identity, and $n=q$ gives an intersection of measure $m(B)$.

For irrational $\alpha$, the pigeonhole principle applied to $0,\alpha ,\dots ,Q\alpha$ in $Q$ equal arcs gives $1\le n\le Q$ with $\Vert n\alpha {\Vert }_{\mathbb{T}}\le 1/Q$. In particular there are arbitrarily small nonzero returns to zero for the irrational rotation of the circle.

We also need translation continuity in L1 on the circle. Given a measurable $B$, approximate its indicator function in the L1 norm by a continuous $g$ on the circle group. Such approximation follows from regularity of Lebesgue measure, or approximation by finite unions of intervals. Translation invariance and uniform continuity givewhere the approximation error is first made arbitrarily small. Equivalently, $m(B△(B-t))\to 0$.

Choose a return time $n\ge 1$ so small modulo one that for each $1\le j<k$,This is possible because multiplication by each fixed $j$ is continuous on the circle group and translation continuity in L1 on the circle applies to the finitely many translates. The union bound now givesThis proves the Furstenberg multiple recurrence theorem for every circle rotation with its normalized Lebesgue measure, including both rational and irrational angles.

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.

Write $\Omega ={\Sigma }^{-1}$ for a positive-definite matrix. Up to a constant independent of the parameters, the log-likelihood of the multivariate normal distribution isThe identityshows that, for each $\Omega \succ 0$, the unique optimizing mean is $\hat{\mu }=\bar{X}$. Using the matrix trace to rewrite the first quadratic sum, the profile likelihood isTherefore maximum likelihood estimation of the precision matrix, whenever the maximum exists, is exactlyThis is the profile likelihood for a Gaussian precision matrix. The sample covariance matrix here uses divisor $n$, as appropriate for maximum likelihood estimation.

There is an important rank qualification in the printed assumptions. If $S\succ 0$, differentiation gives $-{\Omega }^{-1}+S=0$, so the unique minimizer is $S^{-1}$. Uniqueness follows because the negative log-determinant is a strictly convex function on the positive-definite matrices. But full column rank of the uncentered $X$ alone does not imply $S\succ 0$: the rank of a centered sample covariance matrix depends on the centered design. For example, with $n=p=2$ and raw data matrix $X=I_2$,Although $X$ has full column rank, setting ${\Omega }_t=I_2+tv{v}^T$ gives objective $-\log (1+2t)+\mathrm{tr}(S)\to -\infty$. Thus an unpenalized maximizer need not exist under the literal raw-rank assumption. The likelihood reduction remains valid; existence requires full column rank of the centered data, equivalently $S\succ 0$. For the nonsingular Gaussian model this holds almost surely when $n>p$.

Use the entrywise-penalty convention for the Graphical Lasso:The sum is the entrywise matrix L1 norm. Its Graphical-Lasso Karush-Kuhn-Tucker conditions areHere $Z$ is symmetric; its nonzero-entry values are $\mathrm{sgn}({\hat{\Omega }}_{\lambda ,rs})$, and its zero-entry values are any numbers in $[-1,1]$. These are the subgradient optimality condition for this convex optimization problem. Since a positive-definite matrix has positive diagonal, $Z_{rr}=1$ and ${\hat{\Sigma }}_{rr}=S_{rr}+\lambda$. Counting both off-diagonal entries in the penalty and in the trace makes the same $\lambda$ appear in their stationarity equations. The common variant penalizing only off-diagonal entries instead sets $Z_{rr}=0$; the off-diagonal equations and the column argument below are unchanged.

For the given column problem, abbreviateIts smooth part expands to $\frac{1}{2}{b}^{T}Ab-s_j^{T}b$ plus a constant, because $W$ is symmetric and $W{W}^{-1}=I$. The matrix $A$ is a positive-definite matrix, so this quadratic is a strictly convex function. Adding the convex L1 norm penalty preserves strict convexity, and the objective tends to infinity as $\Vert b{\Vert }_2\to \infty$. The minimizer $b^{\ast }$ exists and is unique. Its Karush-Kuhn-Tucker conditions are

We identify that minimizer directly from the precision matrix. Write $\hat{\Omega }={\hat{\Omega }}_{\lambda }$ and defineThe denominator is positive. The off-diagonal part of column $j$ of $\hat{\Sigma }\hat{\Omega }=I$ givesOn the other hand, the off-diagonal Graphical-Lasso Karush-Kuhn-Tucker conditions readBecause ${\hat{\Omega }}_{jj}>0$, the coordinates of $\tilde{b}$ have the opposite signs from those of ${\hat{\Omega }}_{-j,j}$ and vanish at exactly the same positions. The subgradient of the absolute value therefore satisfiesIt follows thatThese are exactly the Lasso column problem's Karush-Kuhn-Tucker conditions. Its unique minimizer must be $b^{\ast }=\tilde{b}$, yieldingThis is the Graphical Lasso column regression identity. The minus sign is essential: it converts the precision-entry subgradient into the regression-coefficient subgradient. The argument uses the inverse identity directly, so it does not require proving the supplied block inverse formula.

The interior of the diamond is $B=\{(x_1,x_2):|x_1|+|x_2|<1\}$. Its Minkowski functional, or the uniqueness argument already proved, gives the L1 norm:The final unheaded set $C$ cannot be an open unit ball of a norm, because every norm ball is convex by homogeneity and the triangle inequality. Both $p=(9/10,0)$ and $q=(0,9/10)$ lie in $C$: their squared-distance expression is $101/100>1$. Their midpoint has that expressionso $(p+q)/2\notin C$. Thus $\boxed{\text{no norm has }C\text{ as its open unit ball}}$. The strict inequalities in the definition are respected by this explicit counterexample.

The Martingale convergence theorem in its $L^1$-bounded form says that a martingale with ${\sup }_n\mathbb{E}|M_n|<\infty$ has an integrable limit $M_{\infty }$ andThe norm bound on the limit follows from Fatou lemma. Boundedness in $L^1$ by itself does not imply convergence in L1. The uniformly integrable martingale convergence theorem gives the stronger conclusion: if $(M_n)$ is uniformly integrable, then $M_n\to M_{\infty }$ both almost surely and in L1 norm, and $M_n=\mathbb{E}[M_{\infty }\mid {\mathcal{F}}_n]$. Conversely, convergence in L1 implies uniform integrability.

For the distinction, the fair-coin doubling martingale $M_n=2^n{1}_{\{\text{first }n\text{ tosses are heads}\}}$ has expectation one for every $n$ but converges almost surely to zero. Its L1 norm remains one, so its convergence is not in L1 norm. These two formulations specify exactly which hypothesis is needed in part (d).

Work on $([0,1],\mathcal{B},dt)$ as a probability space, with Lebesgue measure of total mass one. Let ${\mathcal{F}}_n$ be the filtration generated by the level-$n$ half-open dyadic cells together with the separate null cell $\{1\}$. Define the dyadic slope martingale byThe endpoint $t=1$ may be assigned any value, since it is a null set for Lebesgue measure. The two child slopes average to their parent slope, by telescoping the two increments. Therefore $\mathbb{E}[G_{n+1}\mid {\mathcal{F}}_n]=G_n$ almost everywhere, so this is a martingale. The Lipschitz condition gives $|G_n|\le K$ everywhere except possibly at the freely chosen endpoint, where we take zero.

Apply the Lp martingale convergence theorem with $p=2$. Its limit $g$ has $|g|\le K$ almost everywhere and $G_n\to g$ in L1 norm as well, by Cauchy-Schwarz inequality. Choose a measurable representative of $g$ and set it to zero on any exceptional null set; it is then a bounded measurable function on the entire interval.

Set $f_n(x)=f(0)+{\int }_0^x{G}_n(t)dt$. Telescoping at the grid points shows that $f_n$ is the linear interpolation of $f$ on the dyadic grid. The Lipschitz condition gives $\Vert f_n-f{\Vert }_{\infty }\le K{2}^{-n}\to 0$. AlsoThe two uniform limits coincide, giving the absolutely continuous function representationThe chosen bound holds for every $t$ after the null-set modification; the integral identity holds for every $x$ simultaneously.

Use the same dyadic slope martingale $G_n$ and dyadic filtration as in (c). Each $G_n$ is integrable, since it takes finitely many finite values. On each dyadic cell, the absolute slope is $2^n$ times the absolute endpoint increment. Consequently the hypothesis in the PDF is exactlyThus $(G_n)$ is uniformly integrable. It is also bounded in L1 norm: choose a finite ${\lambda }_0>0$ at which the supremum of the tails is finite, and use $\Vert G_n{\Vert }_1\le {\lambda }_0+{\sup }_j{V}_j(f,{\lambda }_0)$. The uniformly integrable martingale convergence theorem supplies $g\in L^1([0,1])$ with $G_n\to g$ in L1 norm.

The functions $f_n(x)=f(0)+{\int }_0^x{G}_n(t)dt$ are again the dyadic linear interpolations of $f$. Since $f$ is continuous on a compact interval, it is uniformly continuous, and $\Vert f_n-f{\Vert }_{\infty }\le {\omega }_f(2^{-n})\to 0$, where ${\omega }_f$ is its modulus of continuity. On the other hand, the integral of $G_n-g$ is uniformly bounded in absolute value by $\Vert G_n-g{\Vert }_1\to 0$. Hence the dyadic slope-tail criterion for absolute continuity givesNo boundedness of $g$ is asserted here; the tail condition permits integrable densities that are unbounded.

Put $L={\sup }_x\Vert \nabla f(x){\Vert }_{\infty }$, the uniform bound on the supremum norm of the gradient. The fundamental theorem of calculus on a line segment, together with the inner product inequality $|⟨a,b⟩|\le \Vert a{\Vert }_{\infty }\Vert b{\Vert }_1$, givesThus $f$ is Lipschitz continuous with respect to the L1 norm. The Gaussian random variables comprising $X$ and $Y$ have finite exponential moments of their absolute values. More explicitly, for $c\ge 0$, Hölder's inequality gives $\mathbb{E}{e}^{c\Vert X{\Vert }_1}\le {\prod }_{j=1}^n(\mathbb{E}{e}^{nc|X_j|}{)}^{1/n}<\infty$. Consequently $\mathbb{E}f(X)$ and every exponential expression below are finite, including when the covariance matrix is singular.

Use the convex function $\Psi (v)=e^{\lambda |v|}$. Since $Y$ is an independent copy of $X$, Jensen inequality for the conditional expectation givesFor $0\le \theta \le \pi /2$, define the Gaussian rotation of independent copiesWriting $\Sigma =\mathrm{Cov}(X)$, both rotated covariance matrices are $\Sigma$ and their cross-covariance is zero. The pair has a centered multivariate normal distribution, so its components are independent and $(U_{\theta },V_{\theta })$ has the same probability law as $(X,Y)$. This calculation uses no inverse of $\Sigma$ and therefore also proves the assertion for degenerate multivariate normal distributions.

The path $\theta \mapsto U_{\theta }$ runs from $Y$ to $X$. The chain rule and the fundamental theorem of calculus give the pathwise identityApply Jensen inequality to the uniform probability measure on $[0,\pi /2]$. Then use Tonelli theorem and the Gaussian rotation of independent copies to obtainThis proves the Gaussian rotation interpolation inequality in the required form:The stated almost-sure domination now gives an exponential moment of an absolute standard normal variable bound. If $a=\lambda \pi /2$, completing the square in the standard normal density yieldswhere $\Phi$ is the standard normal distribution function. Hence Markov inequality gives, for every $\lambda >0$,The exponent is minimized at $\lambda =4u/{\pi }^2>0$. Therefore the resulting Gaussian tail bound isNo independence of $Z$ from $X$ or $Y$ is needed: only the given almost-sure domination is used.

For multi-indices $\alpha ,\beta$, defineThese seminorms define the Fréchet space topology of the Schwartz space: ${\phi }_j\to \phi$ exactly when every $p_{\alpha ,\beta }({\phi }_j-\phi )$ tends to zero. An equivalent increasing family isA tempered distribution is a continuous linear functional on this space. Equivalently, $|⟨T,\phi ⟩|\le C{q}_m(\phi )$ for some $C,m$. The usual weak convergence of tempered distributions means $⟨T_j,\phi ⟩\to ⟨T,\phi ⟩$ for every fixed Schwartz function. The strong dual topology instead requires uniform convergence on every subset of the Schwartz space that is a bounded set in a topological vector space; the Fourier maps below are continuous in both topologies.

Using $\hat{\phi }(\xi )=\int e^{-ix\cdot \xi }\phi (x)dx$, differentiation under the integral and integration by parts giveThe omitted coefficient has modulus one. By the Leibniz rule, every integrand is a finite sum of a polynomial times a derivative of $\phi$. Inserting the integrable weight $(1+|x|{)}^{-n-1}$ bounds its L1 norm by finitely many Schwartz space seminorms. In particular $q_m(\hat{\phi })\le C_m{q}_{m+n+1}(\phi )$. Thus the Fourier transform maps $\mathcal{S}$ continuously into itself.

For completeness, the Fourier inversion theorem follows here by Gaussian regularization. The inverse transform of $e^{-t|\xi {|}^2}$ is $g_t(x)=(4\pi t{)}^{-n/2}{e}^{-|x{|}^2/(4t)}$. The Fourier transform of a Gaussian and Fubini's theorem showAs $t\downarrow 0$, the right side tends to $\phi (x)$ by the approximate identity property, while the left side tends to the undamped inverse integral by dominated convergence theorem, since $\hat{\phi }\in L^1$. HenceThe inverse is $(2\pi {)}^{-n}$ times reflection composed with the continuous Fourier transform, and is therefore continuous on the Schwartz space. This proves a continuous linear isomorphism with continuous inverse.

Define the Fourier transform of a tempered distribution byThe continuous map on Schwartz space makes this a tempered distribution; the transpose of ${\mathcal{F}}^{-1}$ supplies its inverse. Pointwise convergence of pairings proves weak continuity. For the strong dual topology, the transform of a bounded set of Schwartz functions is bounded, so uniform convergence of pairings on bounded sets proves continuity of both Fourier maps there too.

Now let $R\in SO(n)$ be a rotation matrix in the special orthogonal group and write ${\rho }_{R}T=T\circ R$. A change of variables with unit Jacobian givesThe rotation equivariance of the Fourier transform on tempered distributions follows by duality:Therefore $\widehat{{\rho }_{R}T}={\rho }_R\hat{T}$. Applying this identity and the inverse Fourier transform gives the two directions:This is precisely preservation of radial tempered distributions. For $n>1$, $SO(n)$ acts transitively on spheres, so an invariant smooth function is an ordinary radial function.

Use localization and cancellation of the assumed interval-adapted wavelet basis: at scale $j$, every detail wavelet has support diameter at most $B{2}^{-j}$, L1 norm at most $B^{\prime }{2}^{-j/2}$, and annihilates polynomials of degree less than $q$. These bounds also apply to the modified boundary wavelets; a restriction of an arbitrary whole-line wavelet without the cancellation-preserving boundary construction would not suffice. The finitely many coarse scaling functions can be treated separately.

Write $\alpha =r+\beta$ with $0<\beta \le 1$ as above. Because $\alpha <q$, we have $r<q$. Choose $x_0$ in the support of a function of ${\psi }_{j,n}$, and let $T_{x_0}$ be the degree-$r$ Taylor polynomial of $f$. The Hölder-Taylor remainder bound givesFor $r=0$ this is the Hölder seminorm bound. For $r\ge 1$, the integral Taylor remainder is bounded using $f^{(r)}(t)-f^{(r)}(x_0)$, whose magnitude is at most $[f^{(r)}{]}_{C^{0,\beta }}|t-x_0{|}^{\beta }$.

The vanishing moments remove $T_{x_0}$ from the inner product. Applying the remainder estimate and the L1 norm bound on the localized support yields the wavelet coefficient decay for Hölder functionsThusHere $C$ depends on the fixed wavelet family, the exponent and boundary construction, but not on $f,j,n$. The proof uses the assumed regularity and moments; it does not identify the minimal Daubechies wavelet order with its differentiability order, which need not coincide.

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.