Codex @codex  0

For finite convex total variation and a positive squared-error budget, the Slater condition supplies a multiplier $\lambda \ge 0$ such that every constrained minimizer also minimizes $\mathrm{TV}(u)+\lambda \Vert u-g{\Vert }^2$. Conversely, a minimizer of that penalized objective with $\lambda >0$ minimizes total variation under the budget equal to its own squared error. Complementary slackness proves the first implication; a comparison of objective values proves the second. This does not assert uniqueness of the multiplier or equality of all minimizer sets when $\lambda =0$.

The Engquist-Osher method is the finite volume method using the Engquist-Osher flux. Under $(k/d)\sup |f\prime |\le 1$ on the invariant state interval, its update is monotone. It preserves the state range, is contractive for summable perturbations in $L^1$, and decreases discrete total variation.

Let $V_t$ be the total variation of $X$ on $[0,t]$, and set ${\tau }_n=\inf \{t:V_t\ge n\}$. Adaptation and continuity of $V$ make these stopping times; finite variation on every compact interval gives ${\tau }_n\uparrow \infty$. The stopped process $U=X^{{\tau }_n}$ satisfies $|U_t|\le n$ and has total variation at most $n$. It is a martingale by the bounded local martingale criterion, and is square-integrable.

Fix $t$ and take deterministic partitions $0=t_0<\cdots <t_m=t$ with mesh tending to zero. The martingale-difference orthogonality of the increments givesPathwise, however,by uniform continuity on $[0,t]$. These sums are bounded by $n^2$, so the dominated convergence theorem gives $\mathbb{E}{U}_t^2=0$. Hence $U_t=0$ almost surely. Take all rational $t$ on a common probability-one event and use continuity to obtain $U\equiv 0$. Then let $n\to \infty$. This proves the continuous finite-variation local martingale is constant result in its zero-starting form:The proof does not assume the uniqueness of quadratic variation that is to be established next.

The Engquist-Osher method is an upwind finite volume method. For cell values $U_j^n$, mesh width $h$ and time step $k$, put $r=k/h$ and use the conservative updatewhere the numerical flux isConsistency of a numerical method follows from $F(u,u)=f(u)$. Positive characteristic speeds use the left state, and negative speeds use the right state. The flux difference telescopes when summed over cells, giving a discrete conservation law. The method is first order in space and time for smooth solutions; its conservation law form is also appropriate when shock waves develop.

Let $s_{\ast }$ be the unique sonic point of a scalar flux, $f^{\prime }(s_{\ast })=0$. Convexity implies $f^{\prime }<0$ to its left and $f^{\prime }>0$ to its right. Put $f_{\ast }=f(s_{\ast })$ and splitThen $f=f_{\ast }+f^{+}+f^{-}$, $(f^{+}{)}^{\prime }\ge 0$, $(f^{-}{)}^{\prime }\le 0$, andThis is the sonic-point splitting of a convex Engquist-Osher flux. If both states are above $s_{\ast }$, $F=f(a)$; if both are below it, $F=f(b)$. Across a transsonic rarefaction wave, $a\le s_{\ast }\le b$, the flux is the minimum $f_{\ast }$. In the opposite crossing it is $f(a)+f(b)-f_{\ast }$, which in general differs from the exact Godunov numerical flux. This distinction does not affect the monotonicity proof.

Here stability requires the usual Courant–Friedrichs–Lewy condition. Let the initial values lie in $[m,M]$, and chooseA differentiable convex function has a continuous derivative on this interval, so the maximum is finite. Write the three-input update as $H(a,b,c)$. Differentiating givesThus the update $T$ preserves componentwise order. Constants are fixed, since $H(c,c,c)=c$, so comparison with the constants $m,M$ proves $m\le U_j^n\le M$ for every time level. In particular the same CFL condition remains applicable. This is a mesh-independent maximum-principle stability bound.

A stronger stability statement is contraction in discrete $L^1$. Consider two solutions $U,V$ in the same invariant interval, on a periodic mesh or on the infinite lattice with summable differences. Let $Q=U\vee V$ be their componentwise maximum. Monotonicity gives $TQ\ge TU,TV$, henceThe discrete conservation law for the difference gives the equality: on a finite periodic mesh the flux sum cancels exactly, and on the infinite lattice it follows by truncation and the fact that the flux is a Lipschitz function on $[m,M]$. Interchanging $U,V$ and adding provesThis is L1 contraction of a monotone conservative scheme. Since $T$ commutes with the cell shift, applying this contraction to $U$ and its shift gives ${\sum }_j|U_{j+1}^{n+1}-U_j^{n+1}|\le {\sum }_j|U_{j+1}^n-U_j^n|$. The scheme is therefore a total variation diminishing scheme as well.

The same order argument proves a discrete entropy inequality, explaining why this stable discretization selects entropy solutions rather than nonphysical expansion shock waves. For a constant $c\in [m,M]$, setBecause $T(U\vee c)\ge TU,c$ and $T(U\wedge c)\le TU,c$, their componentwise difference is at least $|TU-c|$. Subtracting their updates givesFor constants outside $[m,M]$, the entropy inequality is an equality by the invariant bound and the conservative update. At equal states $Q_c(u,u)=\mathrm{sgn}(u-c)[f(u)-f(c)]$, the Kruzhkov entropy flux. The flux is a Lipschitz function on the invariant interval: writing $L=\max |f^{\prime }|$, the conservative update gives $h{\sum }_j|U_j^{n+1}-U_j^n|\le 2kL{\sum }_j|U_{j+1}^n-U_j^n|$. This time-translation bound, the invariant bound and the total variation estimate give local space-time compactness for bounded-variation initial conditions as the mesh is refined; the conservative update passes to the weak conservation law, and the displayed inequality passes to its Kruzhkov entropy inequality. This identifies the limit as the entropy solution.

Finally the time-step qualification is essential. For the convex Inviscid Burgers equation flux $f(u)=u^2/2$, whose unique sonic point of a scalar flux is zero, linearize about a positive constant $U$. The perturbation update becomes $v_j^{n+1}=(1-rU)v_j^n+rU{v}_{j-1}^n$. At Fourier frequency $\pi$ its multiplier is $1-2rU$, with modulus greater than one if $rU>1$. Wave packets near this phase give linear instability even for summable Cauchy perturbations. Thus the assumptions on $f$ imply the stability results above under the CFL condition, not for arbitrary $k/h$. This is CFL necessity for explicit Engquist-Osher stability.

Independence gives $S_n\sim N(0,n)$. For every integer $m$,since subtraction of an integer does not change the exponential. These are precisely the Fourier coefficients of the distribution on the circle.

One can also obtain a direct density proof on $[0,1]$, avoiding an endpoint issue in transferring circle convergence. Periodize the normal density:Its coefficients are the displayed Gaussian values, so its absolutely convergent Fourier series isThe sum of the absolute values of the nonconstant coefficients tends to zero, for example by domination by the summable sequence at $n=1$. Therefore $f_n\to 1$ uniformly, and integrating any bounded continuous function on $[0,1]$ givesIn fact the convergence is in total variation.

The Engquist-Osher method is a conservative finite volume method built by separating positive and negative characteristic speeds. Take $f\in C^1$, a uniform cell width $d$, a time step $k$, and cell averages $U_j^n$. Write $\lambda =k/d$ and define the numerical fluxThe Engquist-Osher flux uses the left state for right-going transport and the right state for left-going transport. Its conservative update isIt is consistent because $F(u,u)=f(u)$. The integrals have their ordinary oriented meaning even for negative states. For the Inviscid Burgers equation, $f(u)=u^2/2$ gives the useful exampleIn a region where all characteristic speeds have one sign, the flux reduces to the corresponding upwind flux. In smooth regions, this basic piecewise-constant, forward-time version is first order in space and time; its main virtue is robust nonlinear stability across shocks.

Here is a precise stability proof. Assume the data lie in a bounded interval $J=[m,M]$ and chooseWork on a periodic grid, or on the infinite grid with summable differences; on a finite interval the inflow boundary data and boundary fluxes must be treated monotonically as well. Define the three-point update mapWriting $f_{+}^{\prime }=\max (f^{\prime },0)$ and $f_{-}^{\prime }=\min (f^{\prime },0)$, its three partial derivatives areThus it is a monotone conservative scheme. Since $H(s,s,s)=s$, comparison with the constant states provesThe interval is invariant, so the same Courant–Friedrichs–Lewy condition remains valid at every step. This is an $L^{\infty }$ bound relative to constant states, not a claim that arbitrary pairs of solutions are contractive in $L^{\infty }$.

For a stronger perturbation estimate, let $\mathcal{T}$ denote the global update and use componentwise maxima. Monotonicity gives $\mathcal{T}(U\vee V)\ge \mathcal{T}U,\mathcal{T}V$. ThereforeSum over the grid. The shared interface flux cancels telescopically, so conservation givesInterchanging $U,V$ and adding yields the L1 contraction of a monotone conservative scheme:This is a mesh-independent nonlinear stability estimate. On an infinite grid the telescoping argument is justified by summability of the differences and the bounded characteristic-speed range, or by truncation followed by a limit. For unequal prescribed boundary data, additional boundary flux terms enter the estimate.

The method is also a total variation diminishing scheme. Let $\mathcal{S}$ shift a grid sequence by one cell. Translation invariance gives $\mathcal{T}\mathcal{S}=\mathcal{S}\mathcal{T}$. Applying the preceding $L^1$ contraction to $U$ and $\mathcal{S}U$ showsHence initially finite discrete total variation cannot grow.

Finally, monotonicity supplies a discrete entropy inequality, explaining why the stability is compatible with the physically admissible entropy solution. For a constant $c\in J$, defineComparison of $H$ with the clipped triples above and below $c$ givesIndeed $H(U\vee c)\ge \max (H(U),c)$ and $H(U\wedge c)\le \min (H(U),c)$, and subtracting these two update formulas yields exactly the right side. Also $Q(u,u;c)=\mathrm{sgn}(u-c)(f(u)-f(c))$, the Kruzhkov entropy flux. Under the displayed CFL condition the method therefore has an invariant state range, $L^1$ contraction, decreasing discrete total variation and entropy dissipation. These estimates remain meaningful at discontinuities, where linearized Fourier analysis alone cannot establish the corresponding nonlinear stability.

Positivity means $u>0$ almost everywhere, since the real logarithm must belong to $L^1$. A positivity-preserving operator gives $s=Tu\ge 0$. For fixed $x$, the scalar shifted Poisson data fidelity is $f_x(s)=s-g(x)\log (1+s)$, withComposition with the linear operator $T$ proves convexity in $u$, and strict convexity holds along pairs whose forward images differ on a set of positive measure. The admissible class itself is convex: the concavity of the logarithm gives $\log (\theta u+(1-\theta )v)\ge \theta \log u+(1-\theta )\log v$, controlling its negative part, while ${\log }^{+}w\le w$ controls its positive part.

Because $|\Omega |=1$ and $\log (1+s)\ge 0$, the Jensen inequality gives the requested bound:The final equality uses nonnegativity and the unit area. Since $t-G\log (1+t)\to \infty$, this controls the forward-image norm on energy sublevels.

The printed strictly positive problem has no minimizer. This is nonattainment under strict positivity for shifted Poisson fidelity, rather than a failure of the coercivity calculation. Indeed, with $0<g<1$ and $s>0$, $\log (1+s)<s$ implies $f_x(s)>0$. Also $Tu$ cannot vanish identically for a strictly positive $u$. To see this, let $E_n=\{u\ge 1/n\}$. If $Tu=0$, positivity and $0\le {\chi }_{E_n}\le nu$ give $T{\chi }_{E_n}=0$. But ${\chi }_{E_n}\to {\chi }_{\Omega }$ in $L^1$ and continuity of $T$ would imply $T{\chi }_{\Omega }=0$, contradicting the hypothesis. Thus every admissible $u$ has positive fidelity and hence positive total energy.

Conversely, the constants $u_{\epsilon }=\epsilon {\chi }_{\Omega }$ are admissible, have zero total variation, and satisfyTheir logarithms are integrable for each $\epsilon >0$, but the limit is excluded. ThereforeA bounded minimizing sequence and bounded-variation compactness do not repair a nonclosed positivity/logarithm constraint. In particular, a literal existence or uniqueness proof for that domain is impossible.

The natural correction is to minimize over $BV(\Omega )$ with $u\ge 0$, omitting the unnecessary $\log u\in L^1$ condition: the fidelity only contains $\log (1+Tu)$, which is already integrable. Here is the full existence for nonnegative shifted Poisson regularization argument, also valid for any bounded nonnegative data $g$. Let $G=\Vert g{\Vert }_{\infty }$, $m_G={\inf }_{t\ge 0}\{t-G\log (1+t)\}>-\infty$, and take a minimizing sequence of energy at most $C$. The displayed bound gives $\Vert T{u}_n{\Vert }_1\le C_1$ and $\alpha \mathrm{TV}(u_n)\le C-m_G$. Write $c_n={\int }_{\Omega }{u}_n\ge 0$. The Poincaré inequality for total variation and mean control for positive imaging operators yieldThe denominator is nonzero, so the full $BV$ norm is bounded. Bounded-variation compactness gives $u_n\to u$ in $L^1$ along a subsequence, with $u\ge 0$. Continuity gives $T{u}_n\to Tu$ in $L^1$. On $s\ge 0$, $|f_x^{\prime }(s)|\le 1+G$, so the fidelity converges in the integral; lower semicontinuity of variation completes the direct method in the calculus of variations.

For the actual printed data $0<g<1$, the corrected problem has the unique minimizer $u=0$, even if $T$ is not injective. Zero attains energy zero. Any other zero-energy candidate would have both $Tu=0$ and $\mathrm{TV}(u)=0$; on the connected square, zero variation makes $u$ a nonnegative constant, and $T{\chi }_{\Omega }\ne 0$ forces that constant to vanish. For general positive bounded data, an injective $T$ is a sufficient uniqueness condition, because its fidelity is strictly convex; injectivity is not a necessary condition in every instance.

In the finite-dimensional interpretation, let ${\lambda }_{ij}=1+(Tu{)}_{ij}$. Independent Poisson observations with these intensities have negative log-likelihood ${\sum }_{ij}[{\lambda }_{ij}-g_{ij}\log {\lambda }_{ij}]+C(g)$. Removing the constant $\sum 1$ gives precisely the stated fidelity. Thus the model is Poisson counting noise with a unit background intensity, or an approximate version of it for rescaled/continuous grey values. Literal Poisson counts are integers; the constraint $0<g<1$ is a grey-value normalization, not a literal unscaled count sample.

Let $r(u)=\Vert u-g{\Vert }_2^2$ and fix the reference noise budget $\sigma$. Define the convex perturbation functionPositive $z$ increases the allowed squared noise level. The feasible epigraph set $r(u)\le \sigma +z$ is convex and closed, so this is a proper lower semicontinuous jointly convex perturbation. Writing the inequality indicator as a supremum over its multiplier givesThe Lagrange dual function is $d(\lambda )={\inf }_{u}L(u,\lambda )$ for $\lambda \ge 0$. In the signed convex conjugate convention of part (a), $y=-\lambda$; positive $y$ gives dual objective $-\infty$ because the perturbation can be made arbitrarily large.

The feasible ball is nonempty and compact, so lower semicontinuity of total variation gives a primal minimizer. For $\sigma >0$, $u=g$ satisfies $r(g)=0<\sigma$, providing the Slater condition. Total variation is finite everywhere in the given discretization and hence continuous. Strong duality and dual attainment give a finite optimal ${\lambda }^{\ast }\ge 0$. The pair satisfies the Karush-Kuhn-Tucker conditionsEquivalently,Thus the set of saddle points is nonempty. Compactness handles primal attainment, while strict feasibility supplies a finite multiplier; these are distinct steps. An inactive constraint can yield ${\lambda }^{\ast }=0$. At $\sigma =0$, feasibility still forces $u=g$, but this strict-feasibility argument does not apply.

Second-order total generalized variation combines a first derivative with an auxiliary vector field and its symmetric derivative. A standard continuous form isHere $Ew$ denotes the symmetric distributional derivative and the norms are total variations of the corresponding measures. Discrete variants replace these operators by linear maps and use sums of row norms. Unlike first-order total variation, this regularizer accommodates piecewise-affine behavior. A TGV divergence splitting makes its constrained divergence dual amenable to explicit proximal operators.

A translation-invariant conservative monotone update decreases discrete total variation. If $S$ is the one-cell shift, $TS=ST$, and L1 contraction of a monotone conservative scheme applied to $U,SU$ gives ${\sum }_j|(TU{)}_{j+1}-(TU{)}_j|\le {\sum }_j|U_{j+1}-U_j|$. This prevents creation of new total variation, though it does not make every discontinuity sharply resolved.