Write a finite binary word as and denote its prefix cylinder set by
More generally, a cylinder set fixes finitely many coordinates, or prescribes a subset of their finite coordinate product, leaving all other coordinates free. Each coordinate factor is discrete, so finite-coordinate inverse images are both open and closed. Thus cylinders are clopen. The basic open sets of the product topology restrict only finitely many coordinates, so cylinders form a base. Any finite-coordinate cylinder is a finite union of prefix cylinders of one sufficiently long common length; the prefix cylinders therefore also form a base.
The Bernoulli space here is Cantor space, with compatible metric
It is a compact metric space: from any sequence, choose successively subsequences constant in the first, second and subsequent coordinates, and take the diagonal subsequence. Agreement on the first coordinates bounds the distance by , proving convergence. Compactness also follows from Tychonoff theorem.
Every cylinder indicator function is continuous because the cylinder is clopen. Hence is a vector subspace of the space of continuous functions on a compact space. To prove density, fix and . By uniform continuity, choose so that implies . Choose a point in each length- prefix cylinder and put
Then and . This proves cylinder-function density in Cantor space:
Positivity of implies monotonicity. The pointwise bounds therefore give
Evaluation on attains equality, so is continuous and has norm one. This is the norm of a positive functional on C(K).
The object extended to open sets is the set function , rather than the functional itself. Positivity gives , and linearity gives finite additivity on disjoint cylinders. To construct its extension directly, use the disjoint cylinder decomposition of open subsets of Cantor space. For an open , take the shortest prefixes for which . They are prefix-free, their cylinders are disjoint, and their union is . Define
For , use the empty prefix; for , use the empty sum.
This value is independent of the chosen disjoint prefix-cylinder decomposition. Indeed, compare two such decompositions and . For each fixed , its intersections with the give a disjoint open cover of the compact cylinder . Compactness reduces this to finitely many nonempty intersections. Each intersection is a prefix cylinder or is empty, so finite additivity gives . Sum over and rearrange the nonnegative double sum. Doing the same with each proves equality of the two totals.
For disjoint open sets , combine their disjoint cylinder decompositions to obtain one for . Rearrangement of nonnegative sums proves countable additivity on this family of open sets. The extension is unique because any countably additive extension must have the prescribed sum on every disjoint cylinder decomposition. Open sets are not themselves a sigma-algebra; countable additivity here concerns disjoint open families and their open union.
For the Borel probability measure, let be the algebra of finite unions of prefix cylinders. It is also the algebra of clopen sets, because every clopen set is compact and has a finite cylinder cover. Define on . If with all sets in , compactness of gives a finite subcover by the . Disjointness makes all remaining members empty. Thus finite additivity already establishes the premeasure condition.
The Caratheodory extension theorem gives a unique measure on . This is the Borel sigma-algebra, since the cylinders are a countable base; . Its values on open sets agree with the extension above. For cylinder simple functions,
Both sides are continuous in the supremum norm, so cylinder-function density in Cantor space gives
Any other Borel probability measure with this property agrees on every cylinder indicator function, hence on , and uniqueness in the Caratheodory extension theorem makes it equal to . This proves the Cantor-space representation of positive functionals without assuming the general representation theorem.
Now let be the supplied continuous surjection. The pullback
is a unital isometric embedding: surjectivity gives . On the vector subspace , define . This is well-defined, has norm one and satisfies .
The real Hahn-Banach theorem extends to on all of with the same norm. Norm preservation alone does not automatically mean positivity, so verify it. If , then and
Scaling proves positivity for every nonnegative . This is the unital contraction positivity criterion, giving a positive extension from a unital subspace of C(K).
Represent by the already constructed Borel probability measure on and take the pushforward measure . Continuity of makes its Borel inverse images measurable, and . The pushforward integral identity gives
This is compact-metric representation by Cantor-space pullback. The hypothesis already excludes an empty . The measure is on the Borel sets; no uniqueness claim on an unspecified larger collection of subsets is needed.
Write , and use the second modulus of smoothness . The Jackson kernel is even, nonnegative and has unit integral. Pairing the two halves of its convolution therefore gives
We need a weighted moment estimate rather than just concentration of the Jackson kernel. For , the bounds and imply
Consequently, splitting the integral at gives
The second modulus of smoothness satisfies for . To see this, choose when , put , and factor the function translation difference . Squaring gives at most translated second differences of step . Each function translation is an isometry in the supremum norm, and centered and forward second differences have the same supremum norm. This proves the stated scaling bound.
Taking , using , and integrating against the Jackson kernel now proves
Thus the Jackson operator estimate is uniform in both and .
For the requested degree- best uniform approximation, note that the Jackson kernel, and hence , has trigonometric polynomial degree at most . Indeed the fourth power in the Jackson kernel is the squared modulus of a squared sum of consecutive complex exponentials. Choose , so and . The second-difference integral formula gives
Applying the Jackson operator estimate with this yields the concise answer
The change of index is essential: itself generally has degree , exceeding the permitted degree.
First prove necessity. If polynomials with integer coefficients converge to in the supremum norm, their values at and are convergent sequences of integers. Each such sequence is eventually constant, since a convergent sequence is Cauchy and two distinct integers are at distance at least one. Its limit is an integer. Thus .
For sufficiency we also need uniform convergence of the Bernstein polynomial to . Here is a direct argument. For , write . The binomial distribution has and . For every , uniform continuity of and the Chebyshev inequality give
First make small and then large; the bound is uniform in . Hence .
If the endpoints are integers, part (b) gives . Each coefficient multiplying in is an integer. Expanding by the binomial theorem therefore gives integer coefficients in the ordinary monomial basis. The triangle inequality proves . Thus the integer endpoint condition is necessary and sufficient for integer-coefficient polynomial approximation.
Both maxima exist by continuity on the compact set . Their sum is nonnegative and vanishes only for . The identities and the triangle inequality follow by applying the corresponding supremum norm facts to and . This proves that is a norm.
For , . Hence the first unit ball has image contained in : derivative evaluation is a bounded linear functional for this norm.
For the supremum norm alone, take . These smooth functions satisfy , but . Thus the second image is unbounded. The distinction is the unboundedness of derivative evaluation in the supremum norm, not a failure of differentiability of the individual functions.
Take . In the normalization used here, the Dirichlet kernel has the finite expansion
Averaging a finite number of the integral formulas for the Fourier partial sums is legitimate by linearity of the integral. Hence the Fejér sum is convolution with
To obtain the nonnegative form of the Fejér kernel, expand a squared geometric sum:
The coefficient counts pairs of indices whose difference is . Dividing by and summing the geometric progression gives
At the ratio has its continuous limiting value . Thus this is a continuous, nonnegative trigonometric polynomial, not a kernel with genuine singularities.
Integration over a full period kills every nonconstant cosine term, so
Translation invariance of integration over the circle consequently gives, for every ,
The first step is the integral triangle inequality, the second uses nonnegativity, and the last uses the mass just computed. Taking the supremum norm proves
In particular, Fejér summation is a uniform-norm contraction. The factor , rather than , is essential for the half-normalized Dirichlet kernel and Fejér kernel in this problem.
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.
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.
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.
Put and . On a small closed time interval and a closed ball around the initial point, let bound and let be its spatial Lipschitz constant. The map
sends the corresponding closed ball of continuous paths into itself when the time length times is at most the ball radius. If the time length times is less than one, it is a contraction in the supremum norm. The Banach fixed-point theorem gives a local solution and uniqueness; differentiating its integral equation gives the ordinary differential equation. Overlapping local solutions agree by this uniqueness.
For continuation, the growth assumption gives, on any bounded time interval,
for forward time, with the analogous reversed-time bound. The Gronwall inequality bounds the trajectory on that interval. A finite terminal time is impossible: within the resulting compact ball the field is bounded, so the path has a limit at the endpoint, and the local construction restarts there. This proves the global characteristic flow under linear growth. No differentiability of the flow with respect to its initial point is needed for this existence and uniqueness proof.
Fix an arbitrary finite and use the Banach space of bounded continuous functions with the supremum norm. Set . For in this space, the velocity integral
is bounded by . If , the integrands converge pointwise and are bounded by the integrable function . The dominated convergence theorem proves continuity. Thus the rank-one gain on bounded continuous functions, , is continuous and bounded. The same theorem applied to the time integral shows that maps this space into itself, including at .
Time ordering gives the factorial bound for a Volterra iterate:
Consequently the Volterra series for the linear Boltzmann equation
converges uniformly on the whole finite time slab, so its sum is continuous and bounded and satisfies the fixed point equation. Tracking the damping factors gives the sharper pointwise bound . This proves existence for every finite , without requiring or uniform continuity of . Boundedness on finite slabs does not assert a uniform bound over infinite time.
In the Gaussian white noise model, observe the entire path
where is standard Brownian motion and the deterministic drift belongs to L2 space on . Equivalently, . For every deterministic , the observed stochastic integral satisfies
The noise is an isonormal Gaussian process. In particular its variance is . Gaussian white noise is interpreted through these integrals, rather than as an ordinary random function with a pointwise value at every time. No smoothness of is needed.
Here is the Gaussian maximum bound without independence. Put . It is integrable since it is bounded by . For every ,
The second inequality uses only the moment-generating function of the standard normal distribution, so independence is unnecessary. Jensen inequality gives , hence
Minimizing at proves
For the dyadic partition, let , , putting the endpoint into the final interval. The Haar scaling functions
form an orthonormal basis of the space of functions constant on each interval. The Haar wavelets can be written as
For , the constant function together with , , is another orthonormal basis of . Indeed, each successive level splits a cell's two constants into their sum and difference; the number of basis elements is . Thus the Haar projection is the orthogonal projection
On cell its value is . The first formula also applies to .
Estimate each coefficient by its observed stochastic integral:
This is the Haar projection estimator in Gaussian white noise. The noise integrals over disjoint intervals form a Gaussian vector with zero off-diagonal covariance. The principle that uncorrelated jointly Gaussian variables are independent then makes these coefficients independent. Therefore
Taking expectations shows that is an unbiased estimator of , both coefficientwise and pointwise for the stated step-function representatives.
Only one scaling function is nonzero in each cell, so the supremum norm of the error has the exact form
The endpoint convention ensures the same identity at . Apply the Gaussian maximum bound without independence with to obtain the supremum norm risk of a Haar projection estimator:
The factor comes from cellwise scaling, while the extra square root of comes from taking the maximum over Gaussian errors.
All vector spaces in this solution are complex, while convex combinations use real coefficients. An extreme point of a convex set is one for which , and , forces . Equivalently, is not the midpoint of two distinct points of .
The Krein-Milman theorem says that every nonempty compact convex set in a Hausdorff locally convex space is the closed convex hull of its extreme points. Here is a proof. A face of a convex set is a convex set such that whenever an interior point of a segment in belongs to , both endpoints belong to . Consider nonempty compact faces, ordered by reverse inclusion. A chain has nonempty intersection by compactness and the finite intersection property; that intersection is again a compact face. The Zorn lemma therefore gives a minimal nonempty compact face .
If contains distinct , a continuous real linear functional on the underlying real locally convex space distinguishes them. Such a linear functional exists because the space is Hausdorff and locally convex, by the Hahn-Banach theorem. The maximizers of on form a nonempty proper compact face of . A face of a face is a face of , contradicting minimality. Therefore is a singleton, yielding an extreme point. The same argument inside any nonempty compact face of supplies an extreme point of lying in that face.
Let be the closed convex hull of the extreme points of . It is a nonempty closed subset of compact , hence compact. If , the Hahn-Banach separation theorem provides a continuous real linear functional with . Its maximizer set on is a nonempty compact face, which contains an extreme point of . But and , a contradiction. Thus , proving Krein-Milman theorem.
For a nonempty compact Hausdorff space , the extreme points of the dual unit ball of C(K) are
This is the permitted description without proof, with denoting the complex space of continuous functions on a compact space equipped with the supremum norm. If is empty, and the closed unit ball of its continuous dual space has the single extreme point instead.
The complex Banach–Stone theorem states that a surjective complex-linear isometric isomorphism of normed spaces has the form
where and is a homeomorphism. Conversely, every such map is a surjective complex-linear isometric isomorphism of normed spaces for the supremum norm.
To prove this, suppose first that are nonempty. The Banach-space adjoint is a bijective isometric isomorphism of normed spaces on the continuous dual spaces, so it bijects their closed unit balls and preserves extreme points. The displayed extreme point description gives uniquely
Uniqueness follows by evaluating at the constant function , and then using that continuous functions separate points of a compact Hausdorff space. Evaluation gives the required formula for , and is continuous. Surjectivity of on extreme points proves surjectivity of : the preimage of any is for some . If , every function in the range of has equal values at these two points after division by ; surjectivity of and separation of points force . Thus is bijective.
For every , is continuous. The evaluation map , , is a continuous injection of a compact Hausdorff space into a Hausdorff product topology, hence a homeomorphism onto its image. Continuity of every coordinate proves continuity of . A continuous bijection between compact Hausdorff spaces is a homeomorphism. Conversely the weighted-composition formula plainly preserves the supremum norm, and its inverse is
If one compact space is empty, a surjective isometric isomorphism of normed spaces forces the other to be empty, and the empty homeomorphism gives the corresponding trivial case. This completes Banach–Stone theorem.
Neither the space of sequences converging to zero nor can be isometrically a continuous dual space of a Banach space. Indeed, every nonzero continuous dual space has a nonempty weak-star compact closed unit ball by Banach-Alaoglu theorem, and Krein-Milman theorem then guarantees an extreme point. A bijective linear isometry preserves extreme points of closed unit balls.
The closed unit ball of has no extreme points. Given with , choose with and . The two distinct elements remain in that closed unit ball and have midpoint .
The closed unit ball of the complex Lp space also has no extreme points. An element of norm less than one can be perturbed by a sufficiently small nonzero Lp space element in both directions. If , the non-atomic measure admits a measurable set of mass ; for example the continuous function attains . Put . For , the distinct functions both have Lp norm
with the two coefficients interchanged for the minus sign. Their midpoint is . Thus neither proposed space is isometrically a Banach dual.
Finally, is a connected space, whereas is disconnected. They cannot be homeomorphic. By Banach–Stone theorem, and are not isometrically isomorphic as complex Banach spaces.
Work over and take a nonzero commutative unital Banach algebra , with . A character of an algebra is a nonzero multiplicative complex linear functional . It satisfies . Moreover : otherwise would be invertible, although its image under is zero. The bound on the spectrum of an element therefore gives , proving automatic continuity of characters and .
Every proper maximal ideal of is closed. Indeed its closure is an ideal; if this closure were all of , would contain an element within distance less than one of . Such an element is invertible by the Neumann series, forcing . Thus the closure is proper and maximality makes it equal to . The quotient Banach space , with its quotient Banach algebra structure, is a complex normed division algebra. By the Gelfand-Mazur theorem, it is , so the quotient map gives a character of an algebra with kernel . Conversely, the kernel of every character of an algebra is a maximal ideal, since the character is onto . The Zorn lemma supplies a maximal ideal containing every proper ideal, so the character space of an algebra is nonempty.
These facts give the exact relation between the character space and the spectrum of an element:
One inclusion was proved above. For the other, if is noninvertible, the principal ideal it generates is proper because is commutative. Contain it in a maximal ideal and use its corresponding character of an algebra to obtain .
Give the Gelfand topology, namely its subspace topology from the weak-star topology on . In the closed unit ball of , it is the intersection of the closed conditions
Consequently Banach-Alaoglu theorem makes a compact Hausdorff space. For every , define the Gelfand transform . This is a continuous function on by definition of the Gelfand topology. The Gelfand representation theorem gives a contractive unital algebra homomorphism over a field
Multiplicativity and linearity follow by evaluating at each character of an algebra; the supremum norm equality follows from the preceding spectrum of an element identity. Its kernel is
the Jacobson radical. Equivalently, its elements have spectrum of an element . Thus is injective precisely when is a semisimple commutative Banach algebra, and it gives a faithful continuous representation of as a function algebra. Its range contains the constants and separates points of , because distinct characters of an algebra differ on some . An arbitrary Banach algebra need not have an isometric or surjective Gelfand transform, nor a uniformly dense range: those conclusions require further hypotheses.
For the Banach algebra on a nonempty compact Hausdorff space , all characters of an algebra are evaluation characters. To see this, let be a maximal ideal. If its elements had no common zero, compactness would supply with no common zero. The continuous function belongs to , is strictly positive on , and has a continuous reciprocal. It is therefore invertible, a contradiction. Hence all elements of vanish at some , so and maximality gives equality. The associated character of an algebra must be : since , its value on is .
The map is a continuous bijection , using separation of points by continuous functions. Compactness and the Hausdorff property make it a homeomorphism. Under this identification the Gelfand transform is , so it is the identity representation of , in particular an isometric onto map. The empty gives the zero algebra, whose empty character space represents the zero function space; it was excluded by the nonzero unital convention above.
Now let be a commutative unital C-star algebra. The stronger conclusion is the Commutative Gelfand--Naimark theorem: the Gelfand transform is an isometric onto C-star homomorphism . We prove the additional assertions without assuming this conclusion.
First every character of an algebra respects the C-star algebra involution. If , the elements , , are unitary elements of a C-star algebra, and their norm is one by the C-star identity. Continuity and multiplicativity give . Thus for every real , forcing to be real. Writing with and self-adjoint gives . Therefore the range of is closed under complex conjugation.
Every element of commutative is a Normal element of a C-star algebra. For a normal , use the C-star identity, and then the same identity for the self-adjoint element , to obtain
Its powers are also normal, so . The spectral radius formula gives , hence . The Gelfand transform is therefore an isometry, and its range is complete and closed in the supremum norm. It contains constants, separates points and is closed under complex conjugation. The complex Stone-Weierstrass theorem makes that range dense, hence all of .
The approximation step in Stone-Weierstrass theorem can also be seen directly here. For a unital conjugation-closed point-separating subalgebra , the real-valued part of its uniform closure is closed under absolute values, by polynomial approximation to on bounded intervals, hence under pointwise maxima and minima. Its real-valued functions separate points. Given real and , for each an affine rescaling of a separating function produces agreeing with at ; take a constant when . For fixed , finitely many neighbourhoods of where cover . Their maximum exceeds everywhere and agrees with at , hence is less than near . Finitely many of these latter neighbourhoods cover ; the minimum of their lies between and everywhere. Approximate real and imaginary parts separately. This proves the density used above and completes the C-star algebra conclusion.
Every finitely supported sequence lies in : if for , set for and afterwards. Then is a bounded sequence and . Consequently . The finitely supported sequences are dense in the space of sequences converging to zero for the supremum norm, by truncation, so continuity of the bounded linear functional gives . For in the real convergent sequence space, with ordinary limit , we have . Therefore .
We prove compactness of zero-boundary Poisson solutions. Here the printed must mean ; otherwise the boundary condition refers to an unspecified set. Use this intended boundary condition throughout. Let . A maximum-principle barrier gives a uniform bound on : with , we have and on . Since ,
The weak maximum principle gives , so .
Standard elliptic regularity on the smooth ball first gives . The global Schauder estimate then gives
Thus the functions and all their derivatives through order two are uniformly bounded and equicontinuous on the closed ball. The Arzelà-Ascoli theorem gives a subsequence converging uniformly along with all these derivatives. Integration along line segments identifies the limiting derivatives, so the convergence is in .
It remains to keep the limit in the set, rather than merely proving relative compactness. If in , then the zero boundary values pass to the limit and uniformly. For each pair of distinct points,
Taking suprema gives , while . Hence . The limit belongs to the set, proving sequential compactness in . The fixed positive Hölder exponent supplies the compactness; a bound on the supremum norm of alone would not supply this argument.
The Baire category theorem in the needed version states that a nonempty complete metric space cannot be a countable union of closed sets with empty interior. To prove it, suppose are such sets and start with a nonempty open set . Inductively choose closed balls of positive radius at most , with and . This is possible because each complement is open and dense. The centres form a Cauchy sequence; completeness supplies a limit in every closed ball. It lies in and outside every , proving the theorem.
Here the sequence spaces are over the real scalars, as required by the Euclidean-plane assertion. Suppose an isometry existed. On the compact complete space , the sets
are closed. They cover that space: for a nonzero sequence in , the supremum norm is attained at a coordinate; for every coordinate works. By the Baire category theorem, one contains a product of open arcs. Shrink the arcs to be disjoint. The real coordinate difference is then continuous and nonzero, so its sign is constant on the product. Thus the chord distance has the separated form
In particular its alternating sum on every four-point rectangle is zero. Parametrize the arcs by angles with . Their chord distance is , whose mixed derivative is
The zero rectangle identity would force this mixed derivative to vanish, a contradiction. Therefore no such isometry exists.
For a real vector , list its signed sums over all choices , followed by infinitely many zero coordinates:
This is linear, has finite support and lies in . Choosing the signs of the components gives . Thus , the required linear isometry.
Use integer graph vertices in the boxes: , and set . Thus , , and for .
If , erase loops from an open graph path to obtain a self-avoiding walk. Let be its first graph vertex on . Split at . The prefix certifies , while a segment of the suffix certifies : the final graph vertex is at supremum norm distance at least from , so the suffix first hits that translated boundary. The two certificates use disjoint edges. Therefore the BK boundary-splitting estimate, the union bound, the Van den Berg-Kesten inequality, and translation invariance give
The cases or follow directly from , so this proves the bound including the endpoints.
Here is an explicit way to remove the polynomial boundary factor. For put , . By symmetry in , assume . Then
Consequently is a subadditive sequence. The Fekete lemma states that any real subadditive sequence satisfies , possibly . In this case the direct horizontal open graph path gives , so this limit of a sequence is bounded below by . Since , its upper bound is zero. Finally,
has the same limit of a sequence. Thus the percolation one-arm decay rate exists and
For , every with is zero and . No exponential-decay theorem or assumption that is below the percolation critical probability is needed.
Fix the normalization
The 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 condition
These conditions are necessary and sufficient because the objective is a convex function. They use the subgradient of the absolute value, coordinate by coordinate.
Put . Centered columns imply , so the subtraction of in the model contributes nothing to the score. The Karush-Kuhn-Tucker conditions become
Multiply by . Since and , 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 on the squared prediction norm.
For the Gaussian score event for the Lasso, write for column . The assumed Euclidean norm and the multivariate normal distribution of give
The may be correlated, which does not affect the union bound. Use the following sharp two-sided Gaussian tail bound, valid for with the standard normal distribution and every :
For completeness, the difference satisfies , , and as . It first increases and then decreases to zero, so it is nonnegative. This bound avoids introducing an unnecessary factor two.
Here is the standard normal distribution function. With , the union bound yields
Consequently
The score event uses the supremum norm of ; the centering term still vanishes because .
We next work deterministically on . Let
By Holder inequality, . Since , the triangle inequality gives
Substituting both inequalities into the Basic inequality for the Lasso produces
Because , this also proves the relevant Lasso cone condition, . The assumed Compatibility condition for the Lasso therefore applies to :
Set . Combining these inequalities gives
If , discarding the nonnegative term shows . If , compatibility gives , and the preceding inequality then gives . In either case , so
This 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 by
If , then , and . When this implies ; when it implies . Thus the sign function obeys
This is Lasso sign recovery under compatibility. It concerns the sufficiently large nonzero coefficients; it does not assert that every estimated inactive coefficient is zero.
For the constant monomial , the binomial theorem gives . For , the binomial coefficient identity gives
Thus , including by evaluation of the polynomials.
For and , substitute the preceding coefficient identity into the Bernstein polynomial sum and write . This yields the Bernstein monomial recurrence
The coefficients are nonnegative and sum to ; and the others tend to zero. The weights in any Bernstein polynomial sum are nonnegative and sum to , so . Induction on therefore gives : the term has that limit and the other finitely many terms vanish. In fact, the same estimate in the supremum norm proves uniform convergence on .
As an independent quantitative bound, take a binomial distribution variable with parameters . Then . On , factoring the difference of powers gives ; the Cauchy-Schwarz inequality and the variance of give
For the error is exactly zero. Finally the requested sum equals , so
The unheaded preliminary requests are addressed before the first example. A norm is a function satisfying exactly for , , and . Its induced metric is . Translation preserves this distance, and scalar multiplication satisfies , so both are continuous; multiplication by zero is constant.
The open unit ball determines the norm uniquely through its Minkowski functional:
because is equivalent to . This also works for .
Under the given radial and convexity hypotheses, set and for . The finite symmetric segment along each line gives positivity, absolute homogeneity and . If and , then , and the stated convexity condition yields . Hence ; taking and proves the triangle inequality. Thus this is a norm determined by a convex radial unit ball. The case is immediate.
For the coordinate box, the Minkowski functional is the supremum norm:
Indeed exactly when .