Sublinear function

In linear algebra, a sublinear function (or functional, as is more often used in functional analysis) is a function f : X → 𝔽 on a vector space X over an ordered field 𝔽 (usually the real numbers ℝ or complex numbers ℂ), that satisfies the following properties:

  1. Positive homogeneity: f(rx) = r f(x) for any positive r ∈ 𝔽 and any xX; and
  2. Subadditivity: f(x+y) ≤ f(x) + f(y) for all x, yX.

In functional analysis the name Banach functional is used for sublinear functions, especially when formulating Hahn–Banach theorem.

In contrast, in computer science, a function is called sublinear if , or f(n) ∈ o(n) in asymptotic notation (notice the small ). Formally, f(n) ∈ o(n) if and only if, for any given c > 0, there exists an N such that f(n) < cn for nN.[1] That is, f 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 f(n) ∈ o(n) can be upper-bounded by a concave function of sublinear growth.[2]

DefinitionsEdit

A sublinear functional f is called positive if f(x) ≥ 0 for all xX.[3]

We partially order the set of all sublinear functionals on X, denoted by X#, by declaring pq if and only if p(x) ≤ q(x) for all xX. A sublinear functional is called minimal if it is a minimal element of X# under this order. It can be shown a sublinear functional is minimal if and only if it is a linear functional.[4]

Examples and sufficient conditionsEdit

  • Every seminorm and norm is a sublinear function.
    • The converse is not true, because (semi-)norms can have their domain vector space over any field (not necessarily ordered) and must have as their codomain.
  • Every linear functional a sublinear function. The converse is not true in general.
  • If p and q are sublinear functions on a real vector space X then so is the map x ↦ max { p(x), q(x) }.
    • More generally, if 𝒫 is any non-empty collection of sublinear functionals on a real vector space X and if for all xX, q(x) := sup { p(x) : p ∈ 𝒫 } < ∞, then q is a sublinear functional on X.[5]
  • The linear functional x ↦ -x on X = ℝ is a sublinear functional that is not positive and is not a seminorm.[5]

PropertiesEdit

If p is a real-valued sublinear functional on X then:

  • Every sublinear function is a convex functional.
  • p(0) = 0.[3]
  • 0 ≤ max {p(x), p(-x) } for all xX.[3] This implies that at least one of p(x) and p(-x) is non-negative.
  • p(x) - p(y) ≤ p(x - y) for all x, yX.[4]

Associated seminormEdit

If p is a real-valued sublinear functional on X then the map q(x) := max { p(x), p(-x)} defines a seminorm on X called the seminorm associated with p.[3]

Relation to linear functionalsEdit

If p is a sublinear functional on a real vector space X then the following are equivalent:[4]

  1. p is a linear functional;
  2. for every xX, p(x) + p(-x) ≤ 0;
  3. for every xX, p(x) + p(-x) = 0;
  4. p is a minimal sublinear functional.

If p is a sublinear functional on a real vector space X then there exists a linear functional f on X such that fp.[4]

If X is a real vector space, f is a linear functional on X, and p is a sublinear functional on X, then fp on X if and only if f-1(1) ∩ { xX : p(x) < 1 } = ∅.[4]

ContinuityEdit

Suppose X is a TVS over the real or complex numbers and p is a sublinear functional on X. Then the following are equivalent:

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

and if p is positive then we may add to this list:

  1. { xX : p(x) < 1 } is open in X.

If X is a real TVS, f is a linear functional on X, and p is a continuous sublinear functional on X, then fp on X implies that f is continuous.[4]

Relation to open convex setsEdit

Suppose that X is a TVS (not necessarily locally convex or Hausdorff) over the real or complex numbers. Then the open convex subsets of X are exactly those that are of the form z + { xX : p(x) < 1 } = { xX : p(x - z) < 1} for some zX and some positive continuous sublinear functional p on X.[4]

OperatorsEdit

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.

See alsoEdit

ReferencesEdit

  1. ^ 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.CS1 maint: multiple names: authors list (link)
  2. ^ Ceccherini-Silberstein, Tullio; Salvatori, Maura; Sava-Huss, Ecaterina (2017-06-29). Groups, graphs, and random walks. Cambridge. Lemma 5.17. ISBN 9781316604403. OCLC 948670194.
  3. ^ a b c d Narici 2011, pp. 120-121.
  4. ^ a b c d e f g Narici 2011, pp. 177-220.
  5. ^ a b Narici 2011, pp. 177-221.