Sublinear function

Last updated

In linear algebra, a sublinear function (or functional as is more often used in functional analysis), also called a quasi-seminorm or a Banach functional, on a vector space is a real-valued function with only some of the properties of a seminorm. Unlike seminorms, a sublinear function does not have to be nonnegative-valued and also does not have to be absolutely homogeneous. Seminorms are themselves abstractions of the more well known notion of norms, where a seminorm has all the defining properties of a norm except that it is not required to map non-zero vectors to non-zero values.

Contents

In functional analysis the name Banach functional is sometimes used, reflecting that they are most commonly used when applying a general formulation of the Hahn–Banach theorem. The notion of a sublinear function was introduced by Stefan Banach when he proved his version of the Hahn-Banach theorem. [1]

There is also a different notion in computer science, described below, that also goes by the name "sublinear function."

Definitions

Let be a vector space over a field where is either the real numbers or complex numbers A real-valued function on is called a sublinear function (or a sublinear functional if ), and also sometimes called a quasi-seminorm or a Banach functional, if it has these two properties: [1]

  1. Positive homogeneity / Nonnegative homogeneity : [2] for all real and all
    • This condition holds if and only if for all positive real and all
  2. Subadditivity / Triangle inequality : [2] for all
    • This subadditivity condition requires to be real-valued.

A function is called positive [3] or nonnegative if for all although some authors [4] define positive to instead mean that whenever these definitions are not equivalent. It is a symmetric function if for all Every subadditive symmetric function is necessarily nonnegative. [proof 1] A sublinear function on a real vector space is symmetric if and only if it is a seminorm. A sublinear function on a real or complex vector space is a seminorm if and only if it is a balanced function or equivalently, if and only if for every unit length scalar (satisfying ) and every

The set of all sublinear functions on denoted by can be partially ordered by declaring if and only if for all A sublinear function is called minimal if it is a minimal element of under this order. A sublinear function is minimal if and only if it is a real linear functional. [1]

Examples and sufficient conditions

Every norm, seminorm, and real linear functional is a sublinear function. The identity function on is an example of a sublinear function (in fact, it is even a linear functional) that is neither positive nor a seminorm; the same is true of this map's negation [5] More generally, for any real the map is a sublinear function on and moreover, every sublinear function is of this form; specifically, if and then and

If and are sublinear functions on a real vector space then so is the map More generally, if is any non-empty collection of sublinear functionals on a real vector space and if for all then is a sublinear functional on [5]


A function which is subadditive, convex, and satisfies is also positively homogeneous (the latter condition is necessary as the example of on shows). If is positively homogeneous, it is convex if and only if it is subadditive. Therefore, assuming , any two properties among subadditivity, convexity, and positive homogeneity implies the third.

Properties

Every sublinear function is a convex function: For

If is a sublinear function on a vector space then [proof 2] [3] for every which implies that at least one of and must be nonnegative; that is, for every [3] Moreover, when is a sublinear function on a real vector space then the map defined by is a seminorm. [3]

Subadditivity of guarantees that for all vectors [1] [proof 3] so if is also symmetric then the reverse triangle inequality will hold for all vectors

Defining then subadditivity also guarantees that for all the value of on the set is constant and equal to [proof 4] In particular, if is a vector subspace of then and the assignment which will be denoted by is a well-defined real-valued sublinear function on the quotient space that satisfies If is a seminorm then is just the usual canonical norm on the quotient space

Pryce's sublinearity lemma [2]   Suppose is a sublinear functional on a vector space and that is a non-empty convex subset. If is a vector and are positive real numbers such that then for every positive real there exists some such that

Adding to both sides of the hypothesis (where ) and combining that with the conclusion gives which yields many more inequalities, including, for instance, in which an expression on one side of a strict inequality can be obtained from the other by replacing the symbol with (or vice versa) and moving the closing parenthesis to the right (or left) of an adjacent summand (all other symbols remain fixed and unchanged).

Associated seminorm

If is a real-valued sublinear function on a real vector space (or if is complex, then when it is considered as a real vector space) then the map defines a seminorm on the real vector space called the seminorm associated with [3] A sublinear function on a real or complex vector space is a symmetric function if and only if where as before.

More generally, if is a real-valued sublinear function on a (real or complex) vector space then will define a seminorm on if this supremum is always a real number (that is, never equal to ).

Relation to linear functionals

If is a sublinear function on a real vector space then the following are equivalent: [1]

  1. is a linear functional.
  2. for every
  3. for every
  4. is a minimal sublinear function.

If is a sublinear function on a real vector space then there exists a linear functional on such that [1]

If is a real vector space, is a linear functional on and is a positive sublinear function on then on if and only if [1]

Dominating a linear functional

A real-valued function defined on a subset of a real or complex vector space is said to be dominated by a sublinear function if for every that belongs to the domain of If is a real linear functional on then [6] [1] is dominated by (that is, ) if and only if Moreover, if is a seminorm or some other symmetric map (which by definition means that holds for all ) then if and only if

Theorem [1]   If be a sublinear function on a real vector space and if then there exists a linear functional on that is dominated by (that is, ) and satisfies Moreover, if is a topological vector space and is continuous at the origin then is continuous.

Continuity

Theorem [7]   Suppose is a subadditive function (that is, for all ). Then is continuous at the origin if and only if is uniformly continuous on If satisfies then is continuous if and only if its absolute value is continuous. If is non-negative then is continuous if and only if is open in

Suppose is a topological vector space (TVS) over the real or complex numbers and is a sublinear function on Then the following are equivalent: [7]

  1. is continuous;
  2. is continuous at 0;
  3. is uniformly continuous on ;

and if is positive then this list may be extended to include:

  1. is open in

If is a real TVS, is a linear functional on and is a continuous sublinear function on then on implies that is continuous. [7]

Relation to Minkowski functions and open convex sets

Theorem [7]   If is a convex open neighborhood of the origin in a topological vector space then the Minkowski functional of is a continuous non-negative sublinear function on such that if in addition is a balanced set then is a seminorm on

Relation to open convex sets

Theorem [7]   Suppose that is a topological vector space (not necessarily locally convex or Hausdorff) over the real or complex numbers. Then the open convex subsets of are exactly those that are of the form for some and some positive continuous sublinear function on

Proof

Let be an open convex subset of If then let and otherwise let be arbitrary. Let be the Minkowski functional of which is a continuous sublinear function on since is convex, absorbing, and open ( however is not necessarily a seminorm since was not assumed to be balanced). From it follows that It will be shown that which will complete the proof. One of the known properties of Minkowski functionals guarantees where since is convex and contains the origin. Thus as desired.

Operators

The concept can be extended to operators that are homogeneous and subadditive. This requires only that the codomain be, say, an ordered vector space to make sense of the conditions.

Computer science definition

In computer science, a function is called sublinear if or in asymptotic notation (notice the small ). Formally, if and only if, for any given there exists an such that for [8] That is, grows slower than any linear function. The two meanings should not be confused: while a Banach functional is convex, almost the opposite is true for functions of sublinear growth: every function can be upper-bounded by a concave function of sublinear growth. [9]

See also

Notes

    Proofs

    1. Let The triangle inequality and symmetry imply Substituting for and then subtracting from both sides proves that Thus which implies
    2. If and then nonnegative homogeneity implies that Consequently, which is only possible if
    3. which happens if and only if Substituting and gives which implies (positive homogeneity is not needed; the triangle inequality suffices).
    4. Let and It remains to show that The triangle inequality implies Since as desired.

    Related Research Articles

    In mathematics, more specifically in functional analysis, a Banach space is a complete normed vector space. Thus, a Banach space is a vector space with a metric that allows the computation of vector length and distance between vectors and is complete in the sense that a Cauchy sequence of vectors always converges to a well-defined limit that is within the space.

    The Hahn–Banach theorem is a central tool in functional analysis. It allows the extension of bounded linear functionals defined on a vector subspace of some vector space to the whole space, and it also shows that there are "enough" continuous linear functionals defined on every normed vector space to make the study of the dual space "interesting". Another version of the Hahn–Banach theorem is known as the Hahn–Banach separation theorem or the hyperplane separation theorem, and has numerous uses in convex geometry.

    <span class="mw-page-title-main">Normed vector space</span> Vector space on which a distance is defined

    In mathematics, a normed vector space or normed space is a vector space over the real or complex numbers on which a norm is defined. A norm is a generalization of the intuitive notion of "length" in the physical world. If is a vector space over , where is a field equal to or to , then a norm on is a map , typically denoted by , satisfying the following four axioms:

    1. Non-negativity: for every ,.
    2. Positive definiteness: for every , if and only if is the zero vector.
    3. Absolute homogeneity: for every and ,
    4. Triangle inequality: for every and ,

    The Riesz representation theorem, sometimes called the Riesz–Fréchet representation theorem after Frigyes Riesz and Maurice René Fréchet, establishes an important connection between a Hilbert space and its continuous dual space. If the underlying field is the real numbers, the two are isometrically isomorphic; if the underlying field is the complex numbers, the two are isometrically anti-isomorphic. The (anti-) isomorphism is a particular natural isomorphism.

    In mathematics, the Lp spaces are function spaces defined using a natural generalization of the p-norm for finite-dimensional vector spaces. They are sometimes called Lebesgue spaces, named after Henri Lebesgue, although according to the Bourbaki group they were first introduced by Frigyes Riesz.

    In mathematics, a topological vector space is one of the basic structures investigated in functional analysis. A topological vector space is a vector space that is also a topological space with the property that the vector space operations are also continuous functions. Such a topology is called a vector topology and every topological vector space has a uniform topological structure, allowing a notion of uniform convergence and completeness. Some authors also require that the space is a Hausdorff space. One of the most widely studied categories of TVSs are locally convex topological vector spaces. This article focuses on TVSs that are not necessarily locally convex. Other well-known examples of TVSs include Banach spaces, Hilbert spaces and Sobolev spaces.

    In mathematics, a linear form is a linear map from a vector space to its field of scalars.

    In functional analysis and related areas of mathematics, Fréchet spaces, named after Maurice Fréchet, are special topological vector spaces. They are generalizations of Banach spaces. All Banach and Hilbert spaces are Fréchet spaces. Spaces of infinitely differentiable functions are typical examples of Fréchet spaces, many of which are typically not Banach spaces.

    In mathematics, particularly in functional analysis, a seminorm is a norm that need not be positive definite. Seminorms are intimately connected with convex sets: every seminorm is the Minkowski functional of some absorbing disk and, conversely, the Minkowski functional of any such set is a seminorm.

    In functional analysis and related areas of mathematics, locally convex topological vector spaces (LCTVS) or locally convex spaces are examples of topological vector spaces (TVS) that generalize normed spaces. They can be defined as topological vector spaces whose topology is generated by translations of balanced, absorbent, convex sets. Alternatively they can be defined as a vector space with a family of seminorms, and a topology can be defined in terms of that family. Although in general such spaces are not necessarily normable, the existence of a convex local base for the zero vector is strong enough for the Hahn–Banach theorem to hold, yielding a sufficiently rich theory of continuous linear functionals.

    In functional analysis and related branches of mathematics, the Banach–Alaoglu theorem states that the closed unit ball of the dual space of a normed vector space is compact in the weak* topology. A common proof identifies the unit ball with the weak-* topology as a closed subset of a product of compact sets with the product topology. As a consequence of Tychonoff's theorem, this product, and hence the unit ball within, is compact.

    In mathematics, a norm is a function from a real or complex vector space to the non-negative real numbers that behaves in certain ways like the distance from the origin: it commutes with scaling, obeys a form of the triangle inequality, and is zero only at the origin. In particular, the Euclidean distance in a Euclidean space is defined by a norm on the associated Euclidean vector space, called the Euclidean norm, the 2-norm, or, sometimes, the magnitude or length of the vector. This norm can be defined as the square root of the inner product of a vector with itself.

    <span class="mw-page-title-main">Minkowski functional</span> Function made from a set

    In mathematics, in the field of functional analysis, a Minkowski functional or gauge function is a function that recovers a notion of distance on a linear space.

    <span class="mw-page-title-main">Ordered vector space</span> Vector space with a partial order

    In mathematics, an ordered vector space or partially ordered vector space is a vector space equipped with a partial order that is compatible with the vector space operations.

    In mathematics, an asymmetric norm on a vector space is a generalization of the concept of a norm.

    In functional analysis, the dual norm is a measure of size for a continuous linear function defined on a normed vector space.

    In mathematics, especially measure theory, a set function is a function whose domain is a family of subsets of some given set and that (usually) takes its values in the extended real number line which consists of the real numbers and

    The theorem on the surjection of Fréchet spaces is an important theorem, due to Stefan Banach, that characterizes when a continuous linear operator between Fréchet spaces is surjective.

    This is a glossary for the terminology in a mathematical field of functional analysis.

    In functional analysis and related areas of mathematics, a metrizable topological vector space (TVS) is a TVS whose topology is induced by a metric. An LM-space is an inductive limit of a sequence of locally convex metrizable TVS.

    References

    1. 1 2 3 4 5 6 7 8 9 Narici & Beckenstein 2011, pp. 177–220.
    2. 1 2 3 Schechter 1996, pp. 313–315.
    3. 1 2 3 4 5 Narici & Beckenstein 2011, pp. 120–121.
    4. Kubrusly 2011, p. 200.
    5. 1 2 Narici & Beckenstein 2011, pp. 177–221.
    6. Rudin 1991, pp. 56–62.
    7. 1 2 3 4 5 Narici & Beckenstein 2011, pp. 192–193.
    8. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (2001) [1990]. "3.1". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 47–48. ISBN   0-262-03293-7.{{cite book}}: CS1 maint: multiple names: authors list (link)
    9. Ceccherini-Silberstein, Tullio; Salvatori, Maura; Sava-Huss, Ecaterina (2017-06-29). Groups, graphs, and random walks. Cambridge. Lemma 5.17. ISBN   9781316604403. OCLC   948670194.{{cite book}}: CS1 maint: location missing publisher (link)

    Bibliography