Sublinear function

Summary

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.

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 edit

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 edit

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 edit

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 edit

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 edit

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 edit

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 edit

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 edit

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 edit

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 edit

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 edit

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 edit

Notes edit

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.  

References edit

  1. ^ a b c d e f g h i Narici & Beckenstein 2011, pp. 177–220.
  2. ^ a b c Schechter 1996, pp. 313–315.
  3. ^ a b c d e Narici & Beckenstein 2011, pp. 120–121.
  4. ^ Kubrusly 2011, p. 200.
  5. ^ a b Narici & Beckenstein 2011, pp. 177–221.
  6. ^ Rudin 1991, pp. 56–62.
  7. ^ a b c d e 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 edit

  • Kubrusly, Carlos S. (2011). The Elements of Operator Theory (Second ed.). Boston: Birkhäuser. ISBN 978-0-8176-4998-2. OCLC 710154895.
  • Rudin, Walter (1991). Functional Analysis. International Series in Pure and Applied Mathematics. Vol. 8 (Second ed.). New York, NY: McGraw-Hill Science/Engineering/Math. ISBN 978-0-07-054236-5. OCLC 21163277.
  • Narici, Lawrence; Beckenstein, Edward (2011). Topological Vector Spaces. Pure and applied mathematics (Second ed.). Boca Raton, FL: CRC Press. ISBN 978-1584888666. OCLC 144216834.
  • Schaefer, Helmut H.; Wolff, Manfred P. (1999). Topological Vector Spaces. GTM. Vol. 8 (Second ed.). New York, NY: Springer New York Imprint Springer. ISBN 978-1-4612-7155-0. OCLC 840278135.
  • Schechter, Eric (1996). Handbook of Analysis and Its Foundations. San Diego, CA: Academic Press. ISBN 978-0-12-622760-4. OCLC 175294365.
  • Trèves, François (2006) [1967]. Topological Vector Spaces, Distributions and Kernels. Mineola, N.Y.: Dover Publications. ISBN 978-0-486-45352-1. OCLC 853623322.