Put . The image penalty is discrete isotropic total variation ; the fidelity term is the L1 norm . Introduce scalars and minimize the linear objective
subject to the following affine residuals being cone-feasible:
where is the Lorentz cone. Every component displayed is affine in , so stacking them gives exactly the requested form, with
The first two inequalities imply , so separate nonnegativity constraints for are unnecessary. The cone constraints imply . Every lifted feasible objective bounds the original objective from above; choosing and 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 has full column rank: the box rows recover , the fidelity rows then recover , and the first coordinates of the Lorentz blocks recover . Strict feasibility is also explicit: choose , then take and .
For generic cone slack , a canonical barrier is
on and . 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 gives
Its 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 has
The affine composition is the barrier used in the primal variables; it need not itself be logarithmically homogeneous in because the image data and box offsets are affine constants.
Use the nonnegative-pairing dual cone . The Lagrangian is for . Its infimum over unrestricted is finite exactly when . Therefore the conic dual problem is
The final equality uses the self-dual cone assumption.
For the canonical self-concordant barrier, use its logarithmically homogeneous barrier normalization
At parameter , the primal barrier problem is
Write , the Legendre dual cone barrier. The matching dual barrier problem is
Defining the dual barrier this way is valid generally; self-duality of the cone alone does not assert that an arbitrarily selected barrier equals its Legendre dual.
The joint central path characterization is
The primal stationarity equation is , exactly the dual feasibility equation after defining . For the dual relation, logarithmic homogeneity gives , so . Thus dual stationarity is , giving the same primal equation. At these points,
Newton step. At a chosen target parameter , define
Linearizing the three equality conditions gives the central-path Newton system
Eliminating the slack and dual directions yields
The barrier Hessian is positive definite. Full column rank of therefore makes positive definite and the reduced solve unique. Use a damped step with and remaining interior; a full Newton step need not do so.
At an exact point with parameter , choosing gives and , the usual predictor towards the next path point. Infinitesimally,
The path definition presupposes interior feasibility and attainment of the barrier problems; strict primal-dual feasibility is a standard sufficient setting. The printed full-rank condition by itself is insufficient. For example , , and give the sole primal feasible point , with no interior slack at all, despite full column rank. Rank guarantees the Newton solve at an interior point, not existence of the central path.
Let
The proximal operator optimality condition says
By subgradient inversion under convex conjugacy, which uses Fenchel–Young inequality and from the Fenchel-Moreau theorem,
Consequently , meaning . Uniqueness of the backward subgradient step identifies the result:
This is the scaled Moreau decomposition. It requires one backward step on , with reciprocal parameter and scaled input , followed by a scalar multiplication and subtraction. No separate proximal computation of the convex conjugate is needed.
The forward subgradient step and backward subgradient step are the set-valued maps
Thus means . They are respectively the explicit and implicit time discretizations of subgradient flow . At a differentiable point the forward update is , while the backward update evaluates the gradient at the new point. For proper closed convex data the latter is the proximal operator
To prove at most one output, suppose . Then and . The two subgradient inequalities imply monotonicity of a convex subdifferential, giving
Since , . Convexity supplies this monotonicity; lower semicontinuity is not needed for this at-most-one argument.
Under the full printed assumptions the output actually exists at every . Properness ensures a finite point and excludes . Proper lower-semicontinuous convex has an affine minorant, so the quadratic proximal objective is coercive. Lower semicontinuity makes its minimum attained on a compact sublevel set. Convexity and the positive quadratic curvature make it strongly convex, hence its minimizer is unique. The subgradient optimality condition, with the differentiable quadratic term, is exactly . Thus
This also identifies precisely which assumptions provide existence, uniqueness and the update's optimality interpretation.
Use the standard form with unrestricted :
The nonnegative multiplier
satisfies and . This is a Farkas certificate for linear inequalities, so the system is infeasible by Farkas' lemma. In scalar form, adding twice the first inequality to the other two produces
which directly exhibits the contradiction.
One form of Farkas' lemma states that exactly one of the following holds:
Their mutual exclusion is immediate: if both held, .
For existence of the alternative certificate, let , the finitely generated cone of the columns of . It is convex. It is also closed, a fact that must be justified rather than assumed for arbitrary linear images of closed cones. In a representation with dependent active generators, choose a nonzero dependence with at least one . Subtract
from the nonnegative coefficient vector. The represented point is unchanged, all coefficients remain nonnegative, and at least one active coefficient disappears. Iteration produces a representation with independent active columns. For a convergent sequence in , pass to a subsequence using the same independent set, possible because there are finitely many sets. Its coefficients converge through a fixed left inverse, and their limits remain nonnegative. This proves closedness of finitely generated cones.
The indicator functional is therefore proper, lower semicontinuous and convex. Its Legendre-Fenchel transform is
Indeed a positive pairing with a cone generator can be scaled arbitrarily, while all nonpositive pairings give supremum zero. The Fenchel-Moreau theorem now gives
If , the left side is infinite, so some feasible has . Taking gives and . If , the first alternative holds. The biconjugation theorem applied to a closed finitely generated cone proves the alternative.
For inequalities with unrestricted , split and add nonnegative slack:
The equivalent Farkas certificate for linear inequalities is
Compute the convex conjugate of at a general pair . With , the independent variables become and , so
Therefore the Lagrange dual function is
Using strong duality from the preceding solution gives
Equivalently the conjugate of an infimal convolution is , and the continuous convex equals its biconjugate.
For practical subgradient computation, minimize the known convex dual objective
Every optimizer, and only an optimizer, belongs to by Fenchel–Young inequality. The full characterization is
This is infimal-convolution dual subgradients; the set is nonempty because is finite convex everywhere. If both conjugates are differentiable at the optimizer, solve . For nonsmooth conjugates, use the displayed aggregate subdifferential or a convex minimization algorithm. Replacing it by requires the usual subdifferential sum rule qualification; it is not automatically justified solely by knowing the two conjugates.
For each fixed , choose the convex perturbation function
It is jointly convex and has marginal
Because and are nonnegative and finite everywhere,
for every . The inf-convolution is convex: for approximate decompositions of , take their convex combination and use convexity of both costs; then let their approximation errors tend to zero. Thus is a finite convex function on all of , hence continuous everywhere. In particular is proper and finite near zero, so the qualification in the previous solution applies at every :
This is strong duality for a finite-valued infimal convolution.
No primal attainment was used. For example and meet all the stated assumptions, but is approached only as . This illustrates why a proof based on an assumed minimizing decomposition would be incomplete. The printed functions are real-valued everywhere, not merely extended-real; that distinction supplies continuity and the strong-duality qualification.
Use the maximizing-dual convention. For the perturbation function , define
The primal problem is ; the Lagrangian dual problem is . The sign convention makes the dual marginal concave for jointly convex data; some formulations negate to express a minimization problem.
The central convex perturbation duality calculation is
The last inequality is weak duality. A sufficient finite-dimensional condition for strong duality with dual attainment is: is jointly proper and convex, is proper with finite, and is finite on a neighborhood of zero. More generally suffices.
Indeed continuity of a convex function on the interior of its domain gives a supporting subgradient , so
Therefore and the dual maximum is attained. This qualification establishes equality and dual attainment; it does not by itself establish a primal minimizer.
Let . Maximizing a linear functional over this line segment occurs at an endpoint, so
This identifies as a support function. Its convex conjugate is the indicator functional : if , then for every , with equality at zero; if , strict separation and positive scaling of the separating vector make the supremum infinite.
For a convex function, equality in the Fenchel–Young inequality characterizes its subdifferential. Hence
This is support-function subgradients as exposed faces. In particular a maximizing really is a subgradient, since for every .
Writing , with , now gives
If , the last line is the singleton , so the formula includes that case.
The Legendre-Fenchel transform and biconjugate are
The Fenchel-Moreau theorem says that every proper convex function which is lower semicontinuous equals its biconjugate. More generally, if a proper extended-real has an affine minorant, then
where the right side is the greatest lower semicontinuous convex minorant. This is biconjugation as closed convexification. The affine-minorant hypothesis ensures that the closed convexification is proper; an unqualified statement including arbitrary improper functions would need separate conventions.
Here are the essential proof steps. The Fenchel–Young inequality gives . Every term in the supremum defining is an affine minorant of , and conversely any affine minorant has . Thus is exactly the supremum of all affine minorants, hence is convex and lower semicontinuous.
Put . Its epigraph is the closed convex hull of the epigraph of . Applying the half-space representation of a closed convex set in recovers that epigraph from its containing half-spaces. A containing half-space written
has , since epigraphs extend upwards. If , it is precisely the epigraph inequality of an affine minorant, .
Vertical half-spaces with must also be accounted for. Choose one affine minorant of , which exists because is proper and closed: strictly separate from its epigraph for a finite domain point ; the separating coefficient of cannot be zero, since that would not distinguish points with the same . If a vertical containing inequality is , then
is still an affine minorant on the domain of . At a point violating the vertical inequality, these minorants tend to infinity as . Thus vertical domain restrictions are also recovered by the supremum of affine minorants.
Consequently equals that supremum. Every affine minorant of is below , while the epigraph of any affine minorant of contains its closed convex epigraph hull. Therefore and have the same affine minorants, completing . The theorem in the previous solution supplies the geometric separation step behind biconjugation.
Let be the family of closed half-spaces containing . Certainly . To prove the reverse inclusion, exclude an arbitrary .
Suppose first that is nonempty. Its Euclidean projection onto a convex set exists: minimizing the continuous squared distance may be restricted to a sufficiently large closed ball, whose intersection with the closed set is compact. Put . For every , convexity puts in for . Minimality of gives
Thus the closed half-space
contains , while excludes . Since every point outside is excluded by some member of ,
This is the half-space representation of a closed convex set. If , every point can again be excluded by a containing half-space, so the intersection is empty. If , no proper half-space contains it and the empty intersection is, by convention, .
An explicit construction gives Bernstein's lethargy theorem in the requested inequality form. Set
Strict decrease makes every coefficient positive. Telescoping and the limit assumption give
Thus
defines a continuous function by the Weierstrass M-test and the uniform limit theorem. Apply the positive lacunary Chebyshev series calculation. At ,
For , choose so that . Its error is
Therefore the function satisfies
This explicit Chebyshev construction for Bernstein lethargy also has . It shows that continuity imposes no universal speed of convergence of best polynomial approximation, even though convergence itself follows from the Weierstrass approximation theorem.
The original PDF has indices ; the exponent is lost in the TeX transcription. This lacunary indexing is essential to the positive lacunary Chebyshev series argument below.
Let be the least nonnegative integer with , so for . Define
For the sum is empty and means the zero polynomial. Each included Chebyshev polynomial has degree at most . Also on the interval, so summability of the positive coefficients gives uniform convergence by the Weierstrass M-test, and
Choose and the points , . For every omitted index , the integer is odd. Consequently,
Every term of the tail has the same sign at a given point, and therefore
This shows both that the error norm is exactly and that it alternates at distinct points. The points are in decreasing order; reversing their order still gives alternation. The Chebyshev alternation theorem proves that this partial sum is the unique best uniform approximation. Hence
In particular, and . The equal signs of all tail terms at the same extrema are the reason positivity and the odd integer frequency ratios are useful.
We work in the usual real-valued setting of the Chebyshev alternation theorem. For and an algebraic polynomial of degree at most , the theorem says that is a best uniform approximation if and only if its error has ordered points with alternating maximal values:
If , the zero-error case is included directly.
Existence follows, for example, by taking a minimizing sequence: its supremum norms are bounded, all norms on the finite-dimensional polynomial space are equivalent, and a convergent coefficient subsequence attains the infimum. To prove uniqueness of best uniform polynomial approximation, let both attain the minimum error . Their average has error at most by the triangle inequality and therefore exactly by minimality.
If , both polynomials equal and are equal. Otherwise apply the Chebyshev alternation theorem to . At every alternating extremal point, is either or . But it is the average of and , each lying in . An average attains an endpoint of this interval only when both entries equal that endpoint. Hence at all points. The difference is a degree-at-most- polynomial with more than distinct zeros, so it is identically zero. The best approximating polynomial is unique.
For the uniform spline knots, translation reduces every degree-two basis function to a quadratic cardinal B-spline. From the Cox-de Boor recurrence, an order-three function takes the values
At the prescribed site , only and, when , have nonzero values. Hence the B-spline collocation matrix is
The shift satisfies . A finite geometric expansion gives the exact inverse
Its th absolute row sum is , so . Use the preceding bounds and the supplied stability constant :
Thus the linear growth of shifted quadratic spline interpolation is , which in particular is . The lower bound, rather than the upper bound alone, proves that these spline interpolation operators are not uniformly bounded.
Write , and let . We use the standard interpolation convention of distinct ordered sites . Together with , the Schoenberg–Whitney theorem makes the B-spline collocation matrix invertible. Equivalently, its invertibility is implicit in the existence of the interpolation operator for every data vector.
If distinctness is not understood, the printed positivity condition alone is insufficient. For the order-two basis on spline knots , take . Both diagonal B-spline values are , but the two rows of coincide. Arbitrary data cannot then be interpolated uniquely. The norm statement below concerns the intended well-defined interpolation operator.
Spline interpolation determines the coefficient vector by , and hence
Nonnegativity and the subpartition of unity for B-splines give
For completeness, extend the finite spline knot sequence beyond both ends. For the full sequence the order-one interval indicators sum to one. Summing the Cox-de Boor recurrence and shifting the index in its second term combines the two coefficients of each lower-order B-spline to one, so induction gives partition of unity at every order. Our finite collection is a subset of that nonnegative collection, and thus has sum at most one. Repeated spline knots are handled by the standard zero-term convention or a knot limit. This argument controls the entire interval, not only the basic knot interval.
Since , the operator norm upper bound is
Here the matrix operator norm is the maximum absolute row sum. For the lower bound, choose a row of with maximum absolute row sum and a data vector whose components are the signs of that row's entries. Then and
A continuous piecewise-linear function taking these values at the distinct ordered sites, and constant outside their range, has supremum norm one. Apply the given uniform-norm stability of a B-spline basis to its coefficient vector:
Therefore
The construction of the bounded continuous data extension is what permits the matrix norm to give a lower bound for a function-space operator norm.
For the indicated function the cosine substitution gives
The absolute-value function is Lipschitz continuous with constant one, and so is sine. Their composition therefore satisfies
Use the sharper intermediate estimate from the preceding part, rather than the ordinary interval modulus of continuity:
The usual inverse theorem for trigonometric approximation cannot hold verbatim with the ordinary interval modulus of continuity. It would imply
But comparison with the endpoint gives
which is of order and contradicts that bound as . This is an endpoint obstruction to an algebraic inverse approximation theorem. The algebraic approximation rate measures smoothness after cosine substitution; cosine compresses distances quadratically near the endpoints. A valid algebraic inverse theorem must account for that endpoint geometry rather than using the unchanged periodic formulation.
The first Jackson theorem for periodic approximation asserts that a universal constant satisfies
for every continuous -periodic function , where the infimum is over degree-at-most- trigonometric polynomials.
Apply it to the even function . If is a trigonometric polynomial approximating , its even part
has no larger error, because and the triangle inequality bounds each averaged error by . Every even trigonometric polynomial has the form
Here the Chebyshev polynomials have algebraic degree , so has degree at most . Surjectivity of cosine gives
Conversely, every algebraic polynomial of degree at most yields such an even trigonometric polynomial. Taking infima therefore proves the exact identity , not merely an inequality. Combine this with the periodic theorem and the preceding modulus of continuity estimate:
Symmetrization, the degree correspondence and the equality of norms justify every step in transferring the Jackson-type estimate.
For a periodic function use the modulus of continuity
On the interval, take the supremum over pairs of points whose distance is at most . The mean value theorem applied to cosine, whose derivative has absolute value at most one, gives
Both cosine values lie in , so for ,
Taking the supremum proves
The cosine substitution for polynomial approximation is also a linear isometry in the supremum norm, since cosine maps a full period onto ; its image consists of even continuous periodic functions.

Pinned article: Introduction to the OurBigBook Project

Welcome to the OurBigBook Project! Our goal is to create the perfect publishing platform for STEM subjects, and get university-level students to write the best free STEM tutorials ever.
Everyone is welcome to create an account and play with the site: ourbigbook.com/go/register. We belive that students themselves can write amazing tutorials, but teachers are welcome too. You can write about anything you want, it doesn't have to be STEM or even educational. Silly test content is very welcome and you won't be penalized in any way. Just keep it legal!
We have two killer features:
  1. topics: topics group articles by different users with the same title, e.g. here is the topic for the "Fundamental Theorem of Calculus" ourbigbook.com/go/topic/fundamental-theorem-of-calculus
    Articles of different users are sorted by upvote within each article page. This feature is a bit like:
    • a Wikipedia where each user can have their own version of each article
    • a Q&A website like Stack Overflow, where multiple people can give their views on a given topic, and the best ones are sorted by upvote. Except you don't need to wait for someone to ask first, and any topic goes, no matter how narrow or broad
    This feature makes it possible for readers to find better explanations of any topic created by other writers. And it allows writers to create an explanation in a place that readers might actually find it.
    Figure 1.
    Screenshot of the "Derivative" topic page
    . View it live at: ourbigbook.com/go/topic/derivative
  2. local editing: you can store all your personal knowledge base content locally in a plaintext markup format that can be edited locally and published either:
    This way you can be sure that even if OurBigBook.com were to go down one day (which we have no plans to do as it is quite cheap to host!), your content will still be perfectly readable as a static site.
    Figure 5. . You can also edit articles on the Web editor without installing anything locally.
    Video 3.
    Edit locally and publish demo
    . Source. This shows editing OurBigBook Markup and publishing it using the Visual Studio Code extension.
  3. https://raw.githubusercontent.com/ourbigbook/ourbigbook-media/master/feature/x/hilbert-space-arrow.png
  4. Infinitely deep tables of contents:
    Figure 6.
    Dynamic article tree with infinitely deep table of contents
    .
    Descendant pages can also show up as toplevel e.g.: ourbigbook.com/cirosantilli/chordate-subclade
All our software is open source and hosted at: github.com/ourbigbook/ourbigbook
Further documentation can be found at: docs.ourbigbook.com
Feel free to reach our to us for any help or suggestions: docs.ourbigbook.com/#contact