Sublinear function

Sublinear function

A sublinear function, in linear algebra and related areas of mathematics, is a function f: V ightarrow mathbf{F} on a vector space "V" over F, an ordered field (e.g. the real numbers mathbb{R}), which satisfies, for all scalars γ and vectors "x" and "y":f(gamma x) = vert gamma vert f(x) ("positive homogenity"):f(x + y) le f(x) + f(y) ("subadditivity")

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

In computer science, a function f: mathbb{Z^+} ightarrow mathbb{R} is called sublinear if f(n) in o(n) in asymptotic notation (Notice the small ,o). Formally, f(n) in o(n) if and only if, for any given ,c > 0, you can choose an ,n_0 such that [cite book | author = Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein | title = Introduction to Algorithms | origyear = 1990 | edition = 2nd edition | year = 2001 | publisher = MIT Press and McGraw-Hill | pages = 47-48 | chapter = 3.1 | id = ISBN 0-262-03293-7]

: n geq n_0 Rightarrow 0 leq f(n) < c cdot n

This means that for any linear function f',, for sufficiently large input f, grows slower than f',.

Examples

* Every (semi-)norm is a sublinear function. Opposite is not true, because (semi-)norms can have their domain vector space over any field (not necessarily ordered) and must have mathbb{R} as their codomain.

Properties

* Every sublinear function is a convex functional.

Operators

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.

References


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Hardy-Littlewood maximal function — In mathematics, the Hardy Littlewood maximal operator M is a significant non linear operator used in real analysis and harmonic analysis. It takes a function f (a complex valued and locally integrable function) : f:mathbb{R}^{d} ightarrow… …   Wikipedia

  • Hahn–Banach theorem — In mathematics, the Hahn–Banach theorem is a central tool in functional analysis. It allows the extension of bounded linear operators defined on a subspace of some vector space to the whole space, and it also shows that there are enough… …   Wikipedia

  • List of mathematics articles (S) — NOTOC S S duality S matrix S plane S transform S unit S.O.S. Mathematics SA subgroup Saccheri quadrilateral Sacks spiral Sacred geometry Saddle node bifurcation Saddle point Saddle surface Sadleirian Professor of Pure Mathematics Safe prime Safe… …   Wikipedia

  • Norm (mathematics) — This article is about linear algebra and analysis. For field theory, see Field norm. For ideals, see Norm of an ideal. For group theory, see Norm (group). For norms in descriptive set theory, see prewellordering. In linear algebra, functional… …   Wikipedia

  • Clique problem — The brute force algorithm finds a 4 clique in this 7 vertex graph (the complement of the 7 vertex path graph) by systematically checking all C(7,4)=35 4 vertex subgraphs for completeness. In computer science, the clique problem refers to any of… …   Wikipedia

  • Modulus of continuity — In mathematical analysis, a modulus of continuity is a function used to measure quantitatively the uniform continuity of functions. So, a function admits ω as a modulus of continuity if and only if for all x and y in the domain of f. Since moduli …   Wikipedia

  • Time complexity — In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the size of the input to the problem. The time complexity of an algorithm is commonly expressed using big O… …   Wikipedia

  • Selection algorithm — In computer science, a selection algorithm is an algorithm for finding the kth smallest number in a list (such a number is called the kth order statistic). This includes the cases of finding the minimum, maximum, and median elements. There are… …   Wikipedia

  • Coherent risk measure — In the field of financial economics there are a number of ways that risk can be defined; to clarify the concept theoreticians have described a number of properties that a risk measure might or might not have. A coherent risk measure is a function …   Wikipedia

  • MASORAH — This article is arranged according to the following outline: 1. THE TRANSMISSION OF THE BIBLE 1.1. THE SOFERIM 1.2. WRITTEN TRANSMISSION 1.2.1. Methods of Writing 1.2.1.1. THE ORDER OF THE BOOKS 1.2.1.2. SEDARIM AND PARASHIYYOT …   Encyclopedia of Judaism

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”