Sublinear function: Difference between revisions

Revision as of 19:42, 3 September 2022

Latest revision as of 17:21, 18 April 2025

(20 intermediate revisions by 6 users not shown)

Line 1:

{{Short description|Type of function in linear algebra}}

In [[linear algebra]], a '''sublinear''' function (or [[Functional (mathematics)|functional]] as is more often used in [[functional analysis]]), also called a '''quasi-seminorm''' or a '''Banach functional''', on a [[vector space]] <math>X</math> is a [[Real number|real]]-valued [[Function (mathematics)|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 [[Norm (mathematics)|norms]], where a seminorm has all the defining properties of a norm {{em|except}} that it is not required to map non-zero vectors to non-zero values.

Line 8 ⟶ 9:

==Definitions==

Let <math>X</math> be a [[vector space]] over a field <math>\mathbb{K},</math> where <math>\mathbb{K}</math> is either the [[real number]]s <math>\RReals</math> or [[complex number]]s <math>\C.</math>

A real-valued function <math>p : X \to \mathbb{R}</math> on <math>X</math> is called a ''{{em|{{visible anchor|sublinear function}}}}'' (or a ''{{em|{{visible anchor|sublinear functional|text=sublinear [[functional (mathematics)|functional]]}}}}'' if <math>\mathbb{K} = \RReals</math>), and also sometimes called a ''{{em|{{visible anchor|quasi-seminorm}}}}'' or a ''{{em|{{visible anchor|Banach functional}}}}'', if it has these two properties:{{sfn|Narici|Beckenstein|2011|pp=177-220}}

<ol>

<li>''[[Positive homogeneity]]'''/'''[[Nonnegative homogeneity]]'':{{sfn|Schechter|1996|pp=313-315}} <math>p(r x) = r p(x)</math> for all real <math>r \geq 0</math> and all <math>x \in X.</math>

* This condition holds if and only if <math>p(r x) \leq= r p(x)</math> for all positive real <math>r > 0</math> and all <math>x \in X.</math></li>

<li>''[[Subadditivity]]'''/'''[[Triangle inequality]]'':{{sfn|Schechter|1996|pp=313-315}} <math>p(x + y) \leq p(x) + p(y)</math> for all <math>x, y \in X.</math>

* This subadditivity condition requires <math>p</math> to be real-valued.</li>

</ol>

A function <math>p : X \to \RReals</math> is called ''{{em|{{visible anchor|positive}}}}''{{sfn|Narici|Beckenstein|2011|pp=120-121}} or ''{{em|{{visible anchor|nonnegative}}}}'' if <math>p(x) \geq 0</math> for all <math>x \in X.,</math> although some authors{{sfn|Kubrusly|2011|p=200}} define {{em|{{visible anchor|positive}}}} to instead mean that <math>p(x) \neq 0</math> whenever <math>x \neq 0;</math> these definitions are not equivalent.

It is a ''{{em|{{visible anchor|symmetric function}}}}'' if <math>p(-x) = p(x)</math> for all <math>x \in X.</math>

Every subadditive symmetric function is necessarily nonnegative.<ref group=proof name=SubadditiveSymmetricIsNonnegative />

Every subadditive symmetric function is necessarily nonnegative.<ref group=proof>Let <math>x \in X.</math> The triangle inequality and symmetry imply <math>p(0) = p(x + (- x)) \leq p(x) + p(-x) = p(x) + p(x) = 2 p(x).</math> Substituting <math>0</math> for <math>x</math> and then subtracting <math>p(0)</math> from both sides proves that <math>0 \leq p(0).</math> Thus <math>0 \leq p(0) \leq 2 p(x)</math> which implies <math>0 \leq p(x).</math> <math>\blacksquare</math></ref>

A sublinear function on a real vector space is [[#symmetric function|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 <math>p(u x) \leq p(x)</math> for every [[unit length]] scalar <math>u</math> (satisfying <math>|u| = 1</math>) and every <math>x \in X.</math>

Line 30 ⟶ 31:

Every [[Norm (mathematics)|norm]], [[seminorm]], and real linear functional is a sublinear function.

The [[identity function]] <math>\RReals \to \RReals</math> on <math>X := \RReals</math> 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 <math>x \mapsto -x.</math>{{sfn|Narici|Beckenstein|2011|pp=177-221}}

More generally, for any real <math>a \leq b,</math> the map

<math display=block>\begin{alignat}{4}

S_{a,b} :\;&& \RReals &&\;\to \;& \RReals \\[0.3ex]

&& x &&\;\mapsto\;&

\begin{cases}

Line 40 ⟶ 41:

\end{cases} \\

\end{alignat}</math>

is a sublinear function on <math>X := \RReals</math> and moreover, every sublinear function <math>p : \RReals \to \RReals</math> is of this form; specifically, if <math>a := - p(-1)</math> and <math>b := p(1)</math> then <math>a \leq b</math> and <math>p = S_{a, b}.</math>

If <math>p</math> and <math>q</math> are sublinear functions on a real vector space <math>X</math> then so is the map <math>x \mapsto \max \{p(x), q(x)\}.</math> More generally, if <math>\mathcal{P}</math> is any non-empty collection of sublinear functionals on a real vector space <math>X</math> and if for all <math>x \in X,</math> <math>q(x) := \sup \{p(x) : p \in \mathcal{P}\},</math> then <math>q</math> is a sublinear functional on <math>X.</math>{{sfn|Narici|Beckenstein|2011|pp=177-221}}

A function <math>p : X \to \R</math> is sublinear if and only if it is [[Subadditivity|subadditive]], [[Convex function|convex]], and satisfies <math>p(0) \leq 0.</math>

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

==Properties==

Every sublinear function is a [[convex function]].: For <math>0 \leq t \leq 1,</math>

<math display=block>\begin{alignat}{3}

p(t x + (1 - t) y)

&\leq p(t x) + p((1 - t) y) && \quad\text{ subadditivity} \\

&= t p(x) + (1 - t) p(y) && \quad\text{ nonnegative homogeneity} \\

\end{alignat}</math>

If <math>p : X \to \RReals</math> is a sublinear function on a vector space <math>X</math> then<ref group=proof>If <math>x \in X</math> and <math>r :name=NullAtZeroAndSumUpperBound 0</math> then nonnegative homogeneity implies that <math>p(0) = p(r x) = r p(x) = 0 p(x) = 0.</math> Consequently, <math>0 = p(0) = p(x + (-x)) \leq p(x) + p(-x),</math> which is only possible if <math>0 \leq \max \{p(x), p(- x)\}.</math> <math>\blacksquare</math></ref>{{sfn|Narici|Beckenstein|2011|pp=120-121}}

<math display=block>p(0) ~=~ 0 ~\leq~ p(x) + p(- x) \qquad \text{ for every } x \in X,</math>

for every <math>x \in X,</math> which implies that at least one of <math>p(x)</math> and <math>p(- x)</math> must be nonnegative; that is, for every <math>x \in X,</math>{{sfn|Narici|Beckenstein|2011|pp=120-121}}

<math display=block>0 ~\leq~ \max \{p(x), p(- x)\} \qquad \text{ for every } x \in X.</math>

Moreover, when <math>p : X \to \RReals</math> is a sublinear function on a real vector space then the map <math>q : X \to \RReals</math> defined by <math>q(x) :~\stackrel{\scriptscriptstyle\text{def}}{=}~ \max \{p(x), p(- x)\}</math> is a seminorm.{{sfn|Narici|Beckenstein|2011|pp=120-121}}

Subadditivity of <math>p : X \to \RReals</math> guarantees that for all vectors <math>x, y \in X,</math>{{sfn|Narici|Beckenstein|2011|pp=177-220}}<ref group=proof><math>p(x) name=ReverseTriangle p(y + (x - y)) \leq p(y) + p(x - y),</math> which happens if and only if <math>p(x) - p(y) \leq p(x - y).</math> <math>\blacksquare</math></ref>

<math display=block>p(x) - p(y) ~\leq~ p(x - y) \qquad \text{ for all } x, y \in X</math>

<math display=block>- p(x) ~\leq~ p(-x),</math>

so if <math>p</math> is also [[#symmetric function|symmetric]] then the [[reverse triangle inequality]] will hold:

so if <math display=block>|p(x)</math> -is p(y)also [[#symmetric function|symmetric]] ~\leq~then p(xthe -[[reverse y)triangle \qquadinequality]] \text{will hold for all }vectors <math> x, y \in X.,</math>

<math display=block>|p(x) - p(y)| ~\leq~ p(x - y).</math>

Defining <math>\ker p ~\stackrel{\scriptscriptstyle\text{def}}{=}~ p^{-1}(0),</math> then subadditivity also guarantees that for all <math>x \in X,</math> the value of <math>p</math> on the set <math>x + (\ker p \cap -\ker p) = \{x + k : p(k) = 0 = p(-k)\}</math> is constant and equal to <math>p(x).</math><ref group=proof name=ConstantOnEquivClasses />

In particular, if <math>\ker p = p^{-1}(0)</math> is a vector subspace of <math>X</math> then <math>- \ker p = \ker p</math> and the assignment <math>x + \ker p \mapsto p(x),</math> which will be denoted by <math>\hat{p},</math> is a well-defined real-valued sublinear function on the [[Quotient space (linear algebra)|quotient space]] <math>X \,/\, \ker p</math> that satisfies <math>\hat{p} ^{-1}(0) = \ker p.</math> If <math>p</math> is a seminorm then <math>\hat{p}</math> is just the usual canonical norm on the quotient space <math>X \,/\, \ker p.</math>

{{Math theorem

| name = {{visible anchor|Pryce's Sublinearitysublinearity Lemmalemma}}{{sfn|Schechter|1996|pp=313-315}}

| math_statement = Suppose <math>p : X \to \RReals</math> is a sublinear functional on a vector space <math>X</math> and that <math>CK \subseteq X</math> is a non-empty convex subset.

If <math>x \in X</math> is a vector and <math>r_0a, Rc > 0</math> are positive real numbers such that

<math display=block>p(x) + r_0a Rc ~<~ \inf_{ck \in CK} p\left(x + r_0a c\rightk)</math>

then for every positive real <math>tb > 0</math> there exists some <math>c_0\mathbf{z} \in CK</math> such that

<math display=block>p\left(x + r_0a c_0\rightmathbf{z}) + tb Rc ~<~ \inf_{ck \in CK} p\left(x + r_0a c_0\mathbf{z} + tb c\rightk).</math>

}}

Adding <math>b c</math> to both sides of the hypothesis <math display=inline>p(x) + a c \,<\, \inf_{} p(x + a K)</math> (where <math>p(x + a K) ~\stackrel{\scriptscriptstyle\text{def}}{=}~ \{p(x + a k) : k \in K\}</math>) and combining that with the conclusion gives

<math display=block>p(x) + a c + b c ~<~ \inf_{} p(x + a K) + b c ~\leq~ p(x + a \mathbf{z}) + b c ~<~ \inf_{} p(x + a \mathbf{z} + b K)</math>

which yields many more inequalities, including, for instance,

<math display=block>p(x) + a c + b c ~<~ p(x + a \mathbf{z}) + b c ~<~ p(x + a \mathbf{z} + b \mathbf{z})</math>

in which an expression on one side of a strict inequality <math>\,<\,</math> can be obtained from the other by replacing the symbol <math>c</math> with <math>\mathbf{z}</math> (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 <math>p : X \to \RReals</math> is a real-valued sublinear function on a real vector space <math>X</math> (or if <math>X</math> is complex, then when it is considered as a real vector space) then the map <math>q(x) :~\stackrel{\scriptscriptstyle\text{def}}{=}~ \max \{p(x), p(- x)\}</math> defines a [[seminorm]] on the real vector space <math>X</math> called the '''seminorm associated with <math>p.</math>'''{{sfn|Narici|Beckenstein|2011|pp=120-121}}

A sublinear function <math>p</math> on a real or complex vector space is a [[#symmetric function|symmetric function]] if and only if <math>p = q</math> where <math>q(x) :~\stackrel{\scriptscriptstyle\text{def}}{=}~ \max \{p(x), p(- x)\}</math> as before.

More generally, if <math>p : X \to \RReals</math> is a real-valued sublinear function on a (real or complex) vector space <math>X</math> then

<math display=block>q(x) ~:\stackrel{\scriptscriptstyle\text{def}}{=}~ \sup_{|u|=1} p(u x) ~=~ \sup \{p(u x) : u \text{ is a unit scalar }\}</math>

will define a [[seminorm]] on <math>X</math> if this supremum is always a real number (that is, never equal to <math>\infty</math>).

Line 84 ⟶ 101:

<ol>

<li><math>p</math> is a [[linear functional]].</li>

<li>for every <math>x \in X,</math> <math>p(x) + p(- x) \leq 0.</math></li>

<li>for every <math>x \in X,</math> <math>p(x) + p(- x) = 0.</math></li>

<li><math>p</math> is a minimal sublinear function.</li>

</ol>

Line 96 ⟶ 113:

A real-valued function <math>f</math> defined on a subset of a real or complex vector space <math>X</math> is said to be {{em|dominated by}} a sublinear function <math>p</math> if <math>f(x) \leq p(x)</math> for every <math>x</math> that belongs to the ___domain of <math>f.</math>

If <math>f : X \to \RReals</math> is a real [[linear functional]] on <math>X</math> then{{sfn|Rudin|1991|pp=56-62}}{{sfn|Narici|Beckenstein|2011|pp=177-220}} <math>f</math> is dominated by <math>p</math> (that is, <math>f \leq p</math>) if and only if <math display=block>-p(-x) \leq f(x) \leq p(x) \quad \text{ for every } x \in X.</math>

Moreover, if <math>p</math> is a seminorm or some other {{em|symmetric map}} (which by definition means that <math>p(-x) = p(x)</math> holds for all <math>x</math>) then <math>f \leq p</math> if and only if <math>|f| \leq p.</math>

{{Math theorem|name=Theorem{{sfn|Narici|Beckenstein|2011|pp=177-220}}|math_statement=

If <math>p : X \to \RReals</math> be a sublinear function on a real vector space <math>X</math> and if <math>z \in X</math> then there exists a linear functional <math>f</math> on <math>X</math> that is dominated by <math>p</math> (that is, <math>f \leq p</math>) and satisfies <math>f(z) = p(z).</math>

Moreover, if <math>X</math> is a [[topological vector space]] and <math>p</math> is continuous at the origin then <math>f</math> is continuous.

}}

Line 107 ⟶ 124:

{{Math theorem|name=Theorem{{sfn|Narici|Beckenstein|2011|pp=192-193}}|math_statement=

Suppose <math>f : X \to \RReals</math> is a subadditive function (that is, <math>f(x + y) \leq f(x) + f(y)</math> for all <math>x, y \in X</math>).

Then <math>f</math> is continuous at the origin if and only if <math>f</math> is uniformly continuous on <math>X.</math>

If <math>f</math> satisfies <math>f(0) = 0</math> then <math>f</math> is continuous if and only if its absolute value <math>|f| : X \to [0, \infty)</math> is continuous.

Line 120 ⟶ 137:

<li><math>p</math> is uniformly continuous on <math>X</math>;</li>

</ol>

and if <math>p</math> is positive then wethis list may addbe extended to this listinclude:

and if <math>p</math> is positive then we may add to this list:

<ol start=4>

<li><math>\{x \in X : p(x) < 1\}</math> is open in <math>X.</math></li>

Line 131 ⟶ 147:

{{Math theorem|name=Theorem{{sfn|Narici|Beckenstein|2011|pp=192-193}}|math_statement=

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

if in addition <math>U</math> is [[Balanced set|balanced]] then <math>p_U</math> is a [[seminorm]] on <math>X.</math>

}}

Line 138 ⟶ 153:

{{Math theorem|name=Theorem{{sfn|Narici|Beckenstein|2011|pp=192-193}}|math_statement=

Suppose that <math>X</math> is a TVS[[topological vector space]] (not necessarily [[Locally convex topological vector space|locally convex]] or [[Hausdorff space|Hausdorff]]) over the real or complex numbers.

Then the open convex subsets of <math>X</math> are exactly those that are of the form <math display=block>z + \{x \in X : p(x) < 1\} = \{x \in X : p(x - z) < 1\}</math> for some <math>z \in X</math> and some positive continuous sublinear function <math>p</math> on <math>X.</math>

}}

Line 145 ⟶ 160:

Let <math>V</math> be an open convex subset of <math>X.</math>

If <math>0 \in V</math> then let <math>z := 0</math> and otherwise let <math>z \in V</math> be arbitrary.

Let <math>p : X \to [0, \infty)</math> be the [[Minkowski functional]] of <math>V - z,</math> where <math>p</math>which is a continuous sublinear function on <math>X</math> since <math>V - z</math> is convex, [[Absorbing set|absorbing]], and open (<math>p</math> however is not necessarily a seminorm since <math>V</math> was not assumed to be [[Balanced set|balanced]]).

From the properties of Minkowski functionals, it is known that <math>V - zX = \{x \in X : p(x)- < 1\}z,</math> fromit whichfollows that

<math>V = z + \{x \in X : p(x) < 1\}</math> follows. Since <math mathdisplay=block>z + \{x \in X : p(x) < 1\} = \{x \in X : p(x - z) < 1\},.</math> this completes the proof. [[Q.E.D.|<math>\blacksquare</math>]]

It will be shown that <math>V = z + \{x \in X : p(x) < 1\},</math> which will complete the proof.

One of the known [[Minkowski functional#Properties|properties of Minkowski functionals]] guarantees <math display=inline>\{x \in X : p(x) < 1\} = (0, 1)(V - z),</math> where <math>(0, 1)(V - z) \;\stackrel{\scriptscriptstyle\text{def}}{=}\; \{t x : 0 < t < 1, x \in V - z\} = V - z</math> since <math>V - z</math> is convex and contains the origin.

Thus <math>V - z = \{x \in X : p(x) < 1\},</math> as desired. [[Q.E.D.|<math>\blacksquare</math>]]

}}

Line 157 ⟶ 175:

==Computer science definition==

In [[computer science]], a function <math>f : \Z^+ \to \RReals</math> is called '''sublinear''' if <math>\lim_{n \to \infty} \frac{f(n)}{n} = 0,</math> or <math>f(n) \in o(n)</math> in [[Big O notation#Little-o notation|asymptotic notation]] (notice the small <math>o</math>).

Formally, <math>f(n) \in o(n)</math> if and only if, for any given <math>c > 0,</math> there exists an <math>N</math> such that <math>f(n) < c n</math> for <math>n \geq N.</math><ref>{{cite book|author=[[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]|title=[[Introduction to Algorithms]]|orig-year=1990|edition=2nd|year=2001|publisher=MIT Press and McGraw-Hill|pages=47–48|chapter=3.1|isbn=0-262-03293-7}}</ref>

That is, <math>f</math> grows slower than any linear function.

Line 176 ⟶ 194:

{{reflist|group=note}}

{{reflist|group=proof}}

'''Proofs'''

{{reflist|group=proof}}|refs=

Every subadditive symmetric function is necessarily nonnegative.<ref group=proof name=SubadditiveSymmetricIsNonnegative>Let <math>x \in X.</math> The triangle inequality and symmetry imply <math>p(0) = p(x + (- x)) \leq p(x) + p(-x) = p(x) + p(x) = 2 p(x).</math> Substituting <math>0</math> for <math>x</math> and then subtracting <math>p(0)</math> from both sides proves that <math>0 \leq p(0).</math> Thus <math>0 \leq p(0) \leq 2 p(x)</math> which implies <math>0 \leq p(x).</math> <math>\blacksquare</math></ref>

<ref group=proof name=NullAtZeroAndSumUpperBound>If <math>x \in X</math> and <math>r := 0</math> then nonnegative homogeneity implies that <math>p(0) = p(r x) = r p(x) = 0 p(x) = 0.</math> Consequently, <math>0 = p(0) = p(x + (-x)) \leq p(x) + p(-x),</math> which is only possible if <math>0 \leq \max \{p(x), p(-x)\}.</math> <math>\blacksquare</math></ref>

<ref group=proof name=ReverseTriangle><math>p(x) = p(y + (x - y)) \leq p(y) + p(x - y),</math> which happens if and only if <math>p(x) - p(y) \leq p(x - y).</math> <math>\blacksquare</math> Substituting <math>y := -x</math> and gives <math>p(x) - p(-x) \leq p(x - (-x)) = p(x + x) \leq p(x) + p(x),</math> which implies <math>- p(-x) \leq p(x)</math> (positive homogeneity is not needed; the triangle inequality suffices). <math>\blacksquare</math></ref>

<ref group=proof name=ConstantOnEquivClasses>Let <math>x \in X</math> and <math>k \in p^{-1}(0) \cap (-p^{-1}(0)).</math> It remains to show that <math>p(x + k) = p(x).</math> The triangle inequality implies <math>p(x + k) \leq p(x) + p(k) = p(x) + 0 = p(x).</math> Since <math>p(-k) = 0,</math> <math>p(x) = p(x) - p(-k) \leq p(x - (-k)) = p(x + k),</math> as desired. <math>\blacksquare</math></ref>

}}

==References==

Line 184 ⟶ 213:

==Bibliography==

* {{Kubrusly The Elements of Operator Theory 2nd Edition 2011}} <!--{{sfn|Kubrusly|2011|p=}}-->

* {{Rudin Walter Functional Analysis|edition=2}} <!--{{sfn|Rudin|1991|p=}}-->

* {{Narici Beckenstein Topological Vector Spaces|edition=2}} <!--{{sfn|Narici|Beckenstein|2011|p=}}-->