Content deleted Content added
→Definitions: Replaced erroneous inequality with correct equality Tags: Mobile edit Mobile app edit Android app edit App section source |
|||
| (34 intermediate revisions by 8 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>\
A real-valued function <math>
<ol>
<li>''[[Positive homogeneity]]'''/'''[[Nonnegative homogeneity]]'':{{sfn|Schechter|1996|pp=313-315}} <math>
* This
<li>''[[Subadditivity]]'''/'''[[Triangle inequality]]'':{{sfn|Schechter|1996|pp=313-315}} <math>
* This subadditivity condition requires <math>
</ol>
A function <math>
It is a
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>
The set of all sublinear functions on <math>X,</math> denoted by <math>X^{\#},</math> can be [[Partial order|partially ordered]] by declaring <math>p \leq q</math> if and only if <math>p(x) \leq q(x)</math> for all <math>x \in X.</math>
Line 29 ⟶ 31:
Every [[Norm (mathematics)|norm]], [[seminorm]], and real linear functional is a sublinear function.
The [[identity function]] <math>\
More generally, for any real <math>a \
<math display=block>\begin{alignat}{4}
S_{a,b} :\;&& \
&& x &&\;\mapsto\;&
\begin{cases}
Line 39 ⟶ 41:
\end{cases} \\
\end{alignat}</math>
is a sublinear function on <math>X := \
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 \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 [[
<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 \Reals</math> is a
<math display=block>p(0) ~=~ 0 ~\leq~ p(x) + p(-x),</math>
for every <
<math display=block>0 ~\leq~ \max \{p(x), p(-x)\}.</math>
Subadditivity of <math>p : X \to \Reals</math> guarantees that for all vectors <math>x, y \in X,</math>{{sfn|Narici|Beckenstein|2011|pp=177-220}}<ref group=proof name=ReverseTriangle />
<math display=block>p(x) - p(y) ~\leq~ p(x - y),</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 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 sublinearity lemma}}{{sfn|Schechter|1996|pp=313-315}}
| math_statement = Suppose <math>p : X \to \Reals</math> is a sublinear functional on a vector space <math>X</math> and that <math>K \subseteq X</math> is a non-empty convex subset.
If <math>x \in X</math> is a vector and <math>a, c > 0</math> are positive real numbers such that
<math display=block>p(x) + a c ~<~ \inf_{k \in K} p(x + a k)</math>
then for every positive real <math>b > 0</math> there exists some <math>\mathbf{z} \in K</math> such that
<math display=block>p(x + a \mathbf{z}) + b c ~<~ \inf_{k \in K} p(x + a \mathbf{z} + b k).</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>
<li><math>p(0) = 0.</math>{{sfn|Narici|Beckenstein|2011|pp=120-121}}<ref group=proof>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> <math>\blacksquare</math></ref></li>▼
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>
▲<li><math>0 \leq \max \{p(x), p(- x)\}</math> for all <math>x \in X.</math>{{sfn|Narici|Beckenstein|2011|pp=120-121}}
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).
▲* When <math>X</math> is a real vector space then the map <math>q : X \to \R</math> defined by <math>q(x) := \max \{p(x), p(- x)\}</math> is a seminorm.{{sfn|Narici|Beckenstein|2011|pp=120-121}} </li>
===Associated seminorm===
If <math>p : X \to \
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)
More generally, if <math>p : X \to \
<math display=block>q(x) ~
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 71 ⟶ 101:
<ol>
<li><math>p</math> is a [[linear functional]].</li>
<li>for every <math>x \in X,</math> <math>p(x) + p(-
<li>for every <math>x \in X,</math> <math>p(x) + p(-
<li><math>p</math> is a minimal sublinear function.</li>
</ol>
Line 83 ⟶ 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 \
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 \
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 94 ⟶ 124:
{{Math theorem|name=Theorem{{sfn|Narici|Beckenstein|2011|pp=192-193}}|math_statement=
Suppose <math>f : X \to \
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 107 ⟶ 137:
<li><math>p</math> is uniformly continuous on <math>X</math>;</li>
</ol>
▲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 118 ⟶ 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
}}
Line 125 ⟶ 153:
{{Math theorem|name=Theorem{{sfn|Narici|Beckenstein|2011|pp=192-193}}|math_statement=
Suppose that <math>X</math> is a
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 132 ⟶ 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>
From
<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 144 ⟶ 175:
==Computer science definition==
In [[computer science]], a function <math>f : \Z^+ \to \
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 152 ⟶ 183:
* {{annotated link|Asymmetric norm}}
* {{annotated link|Auxiliary normed space}}
* {{annotated link|Hahn-Banach theorem}}
* {{annotated link|Linear functional}}
Line 162 ⟶ 194:
{{reflist|group=note}}
{{reflist|group=proof}}▼
'''Proofs'''
▲
▲
<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 170 ⟶ 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=}}-->
* {{Schaefer Wolff Topological Vector Spaces|edition=2}} <!--{{sfn|Schaefer|Wolff|1999|p=}}-->
* {{Schechter Handbook of Analysis and Its Foundations}} <!--{{sfn|Schechter|1996|p=}}-->
* {{Trèves François Topological vector spaces, distributions and kernels}} <!--{{sfn|Trèves|2006|p=}}-->
{{Functional
{{Topological vector spaces}}
[[Category:
[[Category:Functional analysis]]
[[Category:Linear algebra]]
[[Category:Types of functions]]
| |||