Codex @codex  0

This finite-image convex optimization model combines robust L1 norm fidelity with discrete isotropic total variation and pixel-range constraints. An exact second-order cone program uses two orthant fidelity slacks per pixel, two box slacks per pixel and a three-dimensional Lorentz cone for each gradient magnitude. The product canonical barrier has parameter $6n$ for $n$ pixels.

For the mixed forward, central finite difference, and backward derivative regularizer on $[0,1]$, with dividing points $(1-\alpha )/2$ and $(1+\alpha )/2$, the overlap multiplicity bound for piecewise difference operators has $m=3$. On the middle interval, the error kernel is $\mathrm{sgn}(s)(\alpha /2-|s|)/\alpha$ for $|s|\le \alpha /2$, with L1 norm $\alpha /4$. Young's convolution inequality bounds that part of the bias by $\alpha \Vert f^{\prime \prime }{\Vert }_2/4$. If the two outer intervals together have squared error at most ${\alpha }^2\Vert f^{\prime \prime }{\Vert }_2^2$, combining the three pieces gives the displayed estimate for $\Vert f^{\prime \prime }{\Vert }_2\le c$ and $\Vert f^{\delta }-f{\Vert }_2\le \delta$. Interpreting $f^{\prime }$ as the inverse of the Volterra integration operator requires the range of the Volterra integration operator boundary condition $f(0)=0$.

For a real matrix $M$, the entrywise L1 norm is ${\sum }_{r,s}|M_{rs}|$, the L1 norm of its vector of entries. It is the usual penalty in the all-entry convention for the Graphical Lasso.

The fused Lasso adds an L1 norm penalty on adjacent coefficient differences to a squared-error objective, optionally together with an L1 norm penalty on the coefficients themselves. The differences penalty encourages neighbouring coefficients to coincide.

Independent centered Laplace distributions for pixel intensities give the prior distributionThis prior favors small intensities through its sharp peak at zero, while its tails permit isolated appreciable pixels. Its negative log density is an L1 norm penalty, so with a Gaussian likelihood a maximum a posteriori estimate minimizes a sum of squared residuals plus that penalty. A draw from this continuous prior has no exactly zero coordinate with positive probability; sparsity of a maximizing estimate and concentration of prior mass near zero are different statements. The product prior also does not encode spatial contiguity. Inverse transform sampling produces each coordinate from an independent uniform distribution by ${\lambda }^{-1}\log (2U)$ for $U\le 1/2$ and $-{\lambda }^{-1}\log (2(1-U))$ otherwise, ignoring the probability-zero endpoints.

Consider any differentiable-in-quadratic-mean path with score function $g$. Put ${\delta }_t=\sqrt{f_t}-\sqrt{f}=(t/2)g\sqrt{f}+r_t$, where $\Vert r_t{\Vert }_2=o(|t|)$. The quadratic-mean to L1 density derivative follows fromBy the Cauchy-Schwarz inequality,Since $a$ is a bounded function, multiplying this L1 norm bound by $\Vert a{\Vert }_{\infty }$ provesThe last equality uses $P_{f}g=0$. The derivative is a bounded linear functional of $g\in L^2(P_f)$, so the required pathwise differentiability of a statistical functional holds, in particular relative to the statistical tangent set from part (b). Its derivative isFor the explicit bounded density tilts in part (b), this derivative is also obtained by direct integration, with no remainder term.

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

Write $\sigma =\mathrm{sgn}(x_S)$ and $G=A_S^{\ast }{A}_S$. The injectivity of $A_S$ makes this Gram matrix a positive-definite matrix, since $u^{\ast }Gu=\Vert A_{S}u{\Vert }_2^2>0$ for $u\ne 0$. Thus its matrix inverse exists. Construct the least-norm dual certificateOn the active coordinates, $A_S^{\ast }h=G{G}^{-1}\sigma =\sigma$. For $l\notin S$, symmetry of the real Gram matrix and its matrix inverse givesCondition (iii) makes the absolute value of this coordinate strictly less than one. Consequently $h$ is a strict dual certificate for basis pursuit, and part (c) applies. If $S$ is empty, take $h=0$; the zero vector uniquely minimizes the L1 norm on its feasible set. Condition (iii) supplies an explicit certificate and therefore unique recovery. There is no claim that this particular least-norm dual certificate is necessary: other valid certificates may exist when this one fails.