Sublinear function

From Quire, the open reference·Type of function in linear algebra·7 min read

In linear algebra, a sublinear function (or functional as is more often used in functional analysis), also called a quasi-seminorm, on a vector space is a real-valued function with 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 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 ${\displaystyle X}$ be a vector space over a field ${\displaystyle \mathbb {K} ,}$ where ${\displaystyle \mathbb {K} }$ is either the real numbers ${\displaystyle \mathbb {R} }$ or complex numbers ${\displaystyle \mathbb {C} .}$ A function ${\displaystyle p\colon X\to \mathbb {R} }$ is called 'sublinear' if it has these two properties:^[1]

Positive homogeneity,^[2] that is ${\displaystyle p(rx)=rp(x)}$ , for all ${\displaystyle r\geq 0}$ and ${\displaystyle x\in X}$ .
Subadditivity,^[2] that is ${\displaystyle p(x+y)\leq p(x)+p(y)}$ for ${\displaystyle x,y\in X.}$

A function ${\displaystyle p:X\to \mathbb {R} }$ is called positive^[3] or nonnegative if ${\displaystyle p(x)\geq 0}$ for all ${\displaystyle x\in X,}$ although some authors^[4] define positive to instead mean that ${\displaystyle p(x)\neq 0}$ whenever ${\displaystyle x\neq 0;}$ these definitions are not equivalent. It is a symmetric function if ${\displaystyle p(-x)=p(x)}$ for all ${\displaystyle x\in X.}$ Every subadditive symmetric function is necessarily nonnegative.^[5] 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 ${\displaystyle p(ux)\leq p(x)}$ for every unit length scalar ${\displaystyle u}$ and ${\displaystyle x\in X.}$

The set of all sublinear functions on ${\displaystyle X,}$ denoted by ${\displaystyle X^{\#},}$ can be partially ordered by declaring ${\displaystyle p\leq q}$ if and only if ${\displaystyle p(x)\leq q(x)}$ for all ${\displaystyle x\in X.}$ A sublinear function is called 'minimal' if it is a minimal element of ${\displaystyle X^{\#$ 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 ${\displaystyle \mathbb {R} }$ 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 ${\displaystyle x\mapsto -x.}$ ^[6] More generally, for any real ${\displaystyle a\leq b,}$ the map

${\displaystyle S_{a,b}\colon \mathbb {R} \to \mathbb {R} ,\quad x\mapsto {\begin{cases}ax,&{\text{if x\leq 0,\\bx,&{\text{if x\geq 0\end{cases$

is a sublinear function on ${\displaystyle \mathbb {R} }$ and moreover, every sublinear function ${\displaystyle p\colon \mathbb {R} \to \mathbb {R} }$ is of this form; specifically, if ${\displaystyle a=-p(-1)}$ and ${\displaystyle b=p(1)}$ then ${\displaystyle a\leq b}$ and ${\displaystyle p=S_{a,b}.}$

If ${\displaystyle p}$ and ${\displaystyle q}$ are sublinear functions on a real vector space ${\displaystyle X}$ then so is the map ${\displaystyle x\mapsto \max\{p(x),q(x)\}.}$ More generally, if ${\displaystyle {\mathcal {P$ is any non-empty collection of sublinear functionals on a real vector space ${\displaystyle X}$ and if for all ${\displaystyle x\in X,}$ ${\displaystyle q(x)=\sup\{p(x)\,;\,p\in {\mathcal {P\},}$ then ${\displaystyle q}$ is a sublinear functional on ${\displaystyle X.}$ ^[6]

A function ${\displaystyle p\colon X\to \mathbb {R} }$ which is subadditive, convex, and satisfies ${\displaystyle p(0)\leq 0}$ is also positively homogeneous (the latter condition ${\displaystyle p(0)\leq 0}$ is necessary as the example of ${\displaystyle p(x)={\sqrt {x^{2}+1$ on ${\displaystyle X=\mathbb {R} }$ shows). If ${\displaystyle p}$ is positively homogeneous, it is convex if and only if it is subadditive. Therefore, assuming ${\displaystyle p(0)\leq 0}$ , any two properties among subadditivity, convexity, and positive homogeneity implies the third.

Properties#edit

Every sublinear function is a convex function: For ${\displaystyle 0\leq t\leq 1,}$ ${\displaystyle {\begin{alignedat}{3}p(tx+(1-t)y)&\leq p(tx)+p((1-t)y)&&\quad {\text{ subadditivity\\&=tp(x)+(1-t)p(y)&&\quad {\text{ nonnegative homogeneity\\\end{alignedat$

If ${\displaystyle p:X\to \mathbb {R} }$ is a sublinear function on a vector space ${\displaystyle X}$ then^[7]^[3] ${\displaystyle p(0)~=~0~\leq ~p(x)+p(-x),}$ for every ${\displaystyle x\in X,}$ which implies that at least one of ${\displaystyle p(x)}$ and ${\displaystyle p(-x)}$ must be nonnegative; that is, for every ${\displaystyle x\in X,}$ ^[3] ${\displaystyle 0~\leq ~\max\{p(x),p(-x)\}.}$ Moreover, when ${\displaystyle p:X\to \mathbb {R} }$ is a sublinear function on a real vector space then the map ${\displaystyle q:X\to \mathbb {R} }$ defined by ${\displaystyle q(x)~{\stackrel {\scriptscriptstyle {\text{def{=~\max\{p(x),p(-x)\$ is a seminorm.^[3]

Subadditivity of ${\displaystyle p:X\to \mathbb {R} }$ guarantees that for all vectors ${\displaystyle x,y\in X,}$ ^[1]^[8] ${\displaystyle p(x)-p(y)~\leq ~p(x-y),}$ ${\displaystyle -p(x)~\leq ~p(-x),}$ so if ${\displaystyle p}$ is also symmetric then the reverse triangle inequality will hold for all vectors ${\displaystyle x,y\in X,}$ ${\displaystyle |p(x)-p(y)|~\leq ~p(x-y).}$

Defining ${\displaystyle \ker p~{\stackrel {\scriptscriptstyle {\text{def{=~p^{-1}(0),}$ then subadditivity also guarantees that for all ${\displaystyle x\in X,}$ the value of ${\displaystyle p}$ on the set ${\displaystyle x+(\ker p\cap -\ker p)=\{x+k:p(k)=0=p(-k)\$ is constant and equal to ${\displaystyle p(x).}$ ^[9] In particular, if ${\displaystyle \ker p=p^{-1}(0)}$ is a vector subspace of ${\displaystyle X}$ then ${\displaystyle -\ker p=\ker p}$ and the assignment ${\displaystyle x+\ker p\mapsto p(x),}$ which will be denoted by ${\displaystyle {\hat {p,}$ is a well-defined real-valued sublinear function on the quotient space ${\displaystyle X\,/\,\ker p}$ that satisfies ${\displaystyle {\hat {p^{-1}(0)=\ker p.}$ If ${\displaystyle p}$ is a seminorm then ${\displaystyle {\hat {p$ is just the usual canonical norm on the quotient space ${\displaystyle X\,/\,\ker p.}$

Pryce's sublinearity lemma^[2]—Suppose ${\displaystyle p:X\to \mathbb {R} }$ is a sublinear functional on a vector space ${\displaystyle X}$ and that ${\displaystyle K\subseteq X}$ is a non-empty convex subset. If ${\displaystyle x\in X}$ is a vector and ${\displaystyle a,c>0}$ are positive real numbers such that ${\displaystyle p(x)+ac~<~\inf _{k\in K}p(x+ak)}$ then for every positive real ${\displaystyle b>0}$ there exists some ${\displaystyle \mathbf {z} \in K}$ such that ${\displaystyle p(x+a\mathbf {z} )+bc~<~\inf _{k\in K}p(x+a\mathbf {z} +bk).}$

Adding ${\displaystyle bc}$ to both sides of the hypothesis ${\textstyle p(x)+ac\,<\,\inf _{}p(x+aK)}$ (where ${\displaystyle p(x+aK)~{\stackrel {\scriptscriptstyle {\text{def{=~\{p(x+ak):k\in K\$ ) and combining that with the conclusion gives ${\displaystyle p(x)+ac+bc~<~\inf _{}p(x+aK)+bc~\leq ~p(x+a\mathbf {z} )+bc~<~\inf _{}p(x+a\mathbf {z} +bK)}$ which yields many more inequalities, including, for instance, ${\displaystyle p(x)+ac+bc~<~p(x+a\mathbf {z} )+bc~<~p(x+a\mathbf {z} +b\mathbf {z} )}$ in which an expression on one side of a strict inequality ${\displaystyle \,<\,}$ can be obtained from the other by replacing the symbol ${\displaystyle c}$ with ${\displaystyle \mathbf {z} }$ (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 ${\displaystyle p:X\to \mathbb {R} }$ is a real-valued sublinear function on a real vector space ${\displaystyle X}$ (or if ${\displaystyle X}$ is complex, then when it is considered as a real vector space) then the map ${\displaystyle q(x)~{\stackrel {\scriptscriptstyle {\text{def{=~\max\{p(x),p(-x)\$ defines a seminorm on the real vector space ${\displaystyle X}$ called the seminorm associated with ${\displaystyle p.}$ ^[3] A sublinear function ${\displaystyle p}$ on a real or complex vector space is a symmetric function if and only if ${\displaystyle p=q}$ where ${\displaystyle q(x)~{\stackrel {\scriptscriptstyle {\text{def{=~\max\{p(x),p(-x)\$ as before.

More generally, if ${\displaystyle p:X\to \mathbb {R} }$ is a real-valued sublinear function on a (real or complex) vector space ${\displaystyle X}$ then ${\displaystyle q(x)~{\stackrel {\scriptscriptstyle {\text{def{=~\sup _{|u|=1}p(ux)~=~\sup\{p(ux):u{\text{ is a unit scalar \$ will define a seminorm on ${\displaystyle X}$ if this supremum is always a real number (that is, never equal to ${\displaystyle \infty }$ ).

Relation to linear functionals#edit

If ${\displaystyle p}$ is a sublinear function on a real vector space ${\displaystyle X}$ then the following are equivalent:^[1]

${\displaystyle p}$ is a linear functional.
for every ${\displaystyle x\in X,}$ ${\displaystyle p(x)+p(-x)\leq 0.}$
for every ${\displaystyle x\in X,}$ ${\displaystyle p(x)+p(-x)=0.}$
${\displaystyle p}$ is a minimal sublinear function.

If ${\displaystyle p}$ is a sublinear function on a real vector space ${\displaystyle X}$ then there exists a linear functional ${\displaystyle f}$ on ${\displaystyle X}$ such that ${\displaystyle f\leq p.}$ ^[1]

If ${\displaystyle X}$ is a real vector space, ${\displaystyle f}$ is a linear functional on ${\displaystyle X,}$ and ${\displaystyle p}$ is a positive sublinear function on ${\displaystyle X,}$ then ${\displaystyle f\leq p}$ on ${\displaystyle X}$ if and only if ${\displaystyle f^{-1}(1)\cap \{x\in X:p(x)<1\}=\varnothing .}$ ^[1]

Dominating a linear functional#edit

A real-valued function ${\displaystyle f}$ defined on a subset of a real or complex vector space ${\displaystyle X}$ is said to be dominated by a sublinear function ${\displaystyle p}$ if ${\displaystyle f(x)\leq p(x)}$ for every ${\displaystyle x}$ that belongs to the domain of ${\displaystyle f.}$ If ${\displaystyle f:X\to \mathbb {R} }$ is a real linear functional on ${\displaystyle X}$ then^[10]^[1] ${\displaystyle f}$ is dominated by ${\displaystyle p}$ (that is, ${\displaystyle f\leq p}$ ) if and only if ${\displaystyle -p(-x)\leq f(x)\leq p(x)\quad {\text{ for every x\in X.}$ Moreover, if ${\displaystyle p}$ is a seminorm or some other symmetric map (which by definition means that ${\displaystyle p(-x)=p(x)}$ holds for all ${\displaystyle x}$ ) then ${\displaystyle f\leq p}$ if and only if ${\displaystyle |f|\leq p.}$

Theorem^[1]—If ${\displaystyle p:X\to \mathbb {R} }$ be a sublinear function on a real vector space ${\displaystyle X}$ and if ${\displaystyle z\in X}$ then there exists a linear functional ${\displaystyle f}$ on ${\displaystyle X}$ that is dominated by ${\displaystyle p}$ (that is, ${\displaystyle f\leq p}$ ) and satisfies ${\displaystyle f(z)=p(z).}$ Moreover, if ${\displaystyle X}$ is a topological vector space and ${\displaystyle p}$ is continuous at the origin then ${\displaystyle f}$ is continuous.

Continuity#edit

Theorem^[11]—Suppose ${\displaystyle f:X\to \mathbb {R} }$ is a subadditive function (that is, ${\displaystyle f(x+y)\leq f(x)+f(y)}$ for all ${\displaystyle x,y\in X}$ ). Then ${\displaystyle f}$ is continuous at the origin if and only if ${\displaystyle f}$ is uniformly continuous on ${\displaystyle X.}$ If ${\displaystyle f}$ satisfies ${\displaystyle f(0)=0}$ then ${\displaystyle f}$ is continuous if and only if its absolute value ${\displaystyle |f|:X\to [0,\infty )}$ is continuous. If ${\displaystyle f}$ is non-negative then ${\displaystyle f}$ is continuous if and only if ${\displaystyle \{x\in X:f(x)<1\$ is open in ${\displaystyle X.}$

Suppose ${\displaystyle X}$ is a topological vector space (TVS) over the real or complex numbers and ${\displaystyle p}$ is a sublinear function on ${\displaystyle X.}$ Then the following are equivalent:^[11]

${\displaystyle p}$ is continuous;
${\displaystyle p}$ is continuous at 0;
${\displaystyle p}$ is uniformly continuous on ${\displaystyle X}$ ;

and if ${\displaystyle p}$ is positive then this list may be extended to include:

${\displaystyle \{x\in X:p(x)<1\$ is open in ${\displaystyle X.}$

If ${\displaystyle X}$ is a real TVS, ${\displaystyle f}$ is a linear functional on ${\displaystyle X,}$ and ${\displaystyle p}$ is a continuous sublinear function on ${\displaystyle X,}$ then ${\displaystyle f\leq p}$ on ${\displaystyle X}$ implies that ${\displaystyle f}$ is continuous.^[11]

Relation to Minkowski functions and open convex sets#edit

Theorem^[11]—If ${\displaystyle U}$ is a convex open neighborhood of the origin in a topological vector space ${\displaystyle X}$ then the Minkowski functional of ${\displaystyle U,}$ ${\displaystyle p_{U}:X\to [0,\infty ),}$ is a continuous non-negative sublinear function on ${\displaystyle X}$ such that ${\displaystyle U=\left\{x\in X:p_{U}(x)<1\right\};}$ if in addition ${\displaystyle U}$ is a balanced set then ${\displaystyle p_{U$ is a seminorm on ${\displaystyle X.}$

Relation to open convex sets#edit

Theorem^[11]—Suppose that ${\displaystyle X}$ is a topological vector space (not necessarily locally convex or Hausdorff) over the real or complex numbers. Then the open convex subsets of ${\displaystyle X}$ are exactly those that are of the form ${\displaystyle z+\{x\in X:p(x)<1\}=\{x\in X:p(x-z)<1\$ for some ${\displaystyle z\in X}$ and some positive continuous sublinear function ${\displaystyle p}$ on ${\displaystyle X.}$

Proof

Let ${\displaystyle V}$ be an open convex subset of ${\displaystyle X.}$ If ${\displaystyle 0\in V}$ then let ${\displaystyle z:=0}$ and otherwise let ${\displaystyle z\in V}$ be arbitrary. Let ${\displaystyle p:X\to [0,\infty )}$ be the Minkowski functional of ${\displaystyle V-z,}$ which is a continuous sublinear function on ${\displaystyle X}$ since ${\displaystyle V-z}$ is convex, absorbing, and open ( ${\displaystyle p}$ however is not necessarily a seminorm since ${\displaystyle V}$ was not assumed to be balanced). From ${\displaystyle X=X-z,}$ it follows that ${\displaystyle z+\{x\in X:p(x)<1\}=\{x\in X:p(x-z)<1\}.}$ It will be shown that ${\displaystyle V=z+\{x\in X:p(x)<1\},}$ which will complete the proof. One of the known properties of Minkowski functionals guarantees ${\textstyle \{x\in X:p(x)<1\}=(0,1)(V-z),}$ where ${\displaystyle (0,1)(V-z)\;{\stackrel {\scriptscriptstyle {\text{def{=\;\{tx:0<t<1,x\in V-z\}=V-z}$ since ${\displaystyle V-z}$ is convex and contains the origin. Thus ${\displaystyle V-z=\{x\in X:p(x)<1\},}$ as desired. ${\displaystyle \blacksquare }$

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 ${\displaystyle f:\mathbb {Z} ^{+}\to \mathbb {R} }$ is called sublinear if ${\displaystyle \lim _{n\to \infty }{\frac {f(n)}{n=0,}$ or ${\displaystyle f(n)\in o(n)}$ in asymptotic notation (notice the small ${\displaystyle o}$ ). Formally, ${\displaystyle f(n)\in o(n)}$ if and only if, for any given ${\displaystyle c>0,}$ there exists an ${\displaystyle N}$ such that ${\displaystyle f(n)<cn}$ for ${\displaystyle n\geq N.}$ ^[12] That is, ${\displaystyle 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 ${\displaystyle f(n)\in o(n)}$ can be upper-bounded by a concave function of sublinear growth.^[13]

Notes#edit

Proofs

^ a b c d e f g h i Narici & Beckenstein 2011, pp. 177–220.
^ a b c Schechter 1996, pp. 313–315.
^ a b c d e Narici & Beckenstein 2011, pp. 120–121.
^ Kubrusly 2011, p. 200.
^ Let ${\displaystyle x\in X.}$ The triangle inequality and symmetry imply ${\displaystyle p(0)=p(x+(-x))\leq p(x)+p(-x)=p(x)+p(x)=2p(x).}$ Substituting ${\displaystyle 0}$ for ${\displaystyle x}$ and then subtracting ${\displaystyle p(0)}$ from both sides proves that ${\displaystyle 0\leq p(0).}$ Thus ${\displaystyle 0\leq p(0)\leq 2p(x)}$ which implies ${\displaystyle 0\leq p(x).}$ ${\displaystyle \blacksquare }$
^ a b Narici & Beckenstein 2011, pp. 177–221.
^ If ${\displaystyle x\in X}$ and ${\displaystyle r:=0}$ then nonnegative homogeneity implies that ${\displaystyle p(0)=p(rx)=rp(x)=0p(x)=0.}$ Consequently, ${\displaystyle 0=p(0)=p(x+(-x))\leq p(x)+p(-x),}$ which is only possible if ${\displaystyle 0\leq \max\{p(x),p(-x)\}.}$ ${\displaystyle \blacksquare }$
^ ${\displaystyle p(x)=p(y+(x-y))\leq p(y)+p(x-y),}$ which happens if and only if ${\displaystyle p(x)-p(y)\leq p(x-y).}$ ${\displaystyle \blacksquare }$ Substituting ${\displaystyle y:=-x}$ and gives ${\displaystyle p(x)-p(-x)\leq p(x-(-x))=p(x+x)\leq p(x)+p(x),}$ which implies ${\displaystyle -p(-x)\leq p(x)}$ (positive homogeneity is not needed; the triangle inequality suffices). ${\displaystyle \blacksquare }$
^ Let ${\displaystyle x\in X}$ and ${\displaystyle k\in p^{-1}(0)\cap (-p^{-1}(0)).}$ It remains to show that ${\displaystyle p(x+k)=p(x).}$ The triangle inequality implies ${\displaystyle p(x+k)\leq p(x)+p(k)=p(x)+0=p(x).}$ Since ${\displaystyle p(-k)=0,}$ ${\displaystyle p(x)=p(x)-p(-k)\leq p(x-(-k))=p(x+k),}$ as desired. ${\displaystyle \blacksquare }$
^ Rudin 1991, pp. 56–62.
^ a b c d e Narici & Beckenstein 2011, pp. 192–193.
^ 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.
^ Ceccherini-Silberstein, Tullio; Salvatori, Maura; Sava-Huss, Ecaterina (2017-06-29). Groups, graphs, and random walks. Cambridge. Lemma 5.17. ISBN 9781316604403. OCLC 948670194.

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.

This article is mirrored from “Sublinear function” on English Wikipedia, revision 1374573005, written by Wikipedia's contributors and licensed CC BY-SA 4.0. Editing it here creates a Quire copy with its own history.

Synced with Wikipedia revision 1374573005 · just now