Sublinear function

In linear algebra, a sublinear function (or functional as is more often used in functional analysis), also called a quasi-seminorm or a Banach functional, on a vector space is a real-valued 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 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 his version of 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

Let be a vector space over a field where is either the real numbers or complex numbers A real-valued function on is called a sublinear function (or a sublinear functional if ), and also sometimes called a quasi-seminorm or a Banach functional, if it has these two properties:[1]

  1. Positive homogeneity/Nonnegative homogeneity:[2] for all real and all
    • This condition holds if and only if for all positive real and all
  2. Subadditivity/Triangle inequality:[2] for all
    • This subadditivity condition requires to be real-valued.

A function is called positive[3] or nonnegative if for all although some authors[4] define positive to instead mean that whenever these definitions are not equivalent. It is a symmetric function if for all Every subadditive symmetric function is necessarily nonnegative.[proof 1] 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 for every unit length scalar (satisfying ) and every

The set of all sublinear functions on denoted by can be partially ordered by declaring if and only if for all A sublinear function is called minimal if it is a minimal element of under this order. A sublinear function is minimal if and only if it is a real linear functional.[1]

Examples and sufficient conditions

Every norm, seminorm, and real linear functional is a sublinear function. The identity function on 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 [5] More generally, for any real the map is a sublinear function on and moreover, every sublinear function is of this form; specifically, if and then and

If and are sublinear functions on a real vector space then so is the map More generally, if is any non-empty collection of sublinear functionals on a real vector space and if for all then is a sublinear functional on [5]


A function which is subadditive, convex, and satisfies is also positively homogeneous (the latter condition is necessary as the example of on shows). If is positively homogeneous, it is convex if and only if it is subadditive. Therefore, assuming , any two properties among subadditivity, convexity, and positive homogeneity implies the third.

Properties

Every sublinear function is a convex function: For

If is a sublinear function on a vector space then[proof 2][3] for every which implies that at least one of and must be nonnegative; that is, for every [3] Moreover, when is a sublinear function on a real vector space then the map defined by is a seminorm.[3]

Subadditivity of guarantees that for all vectors [1][proof 3] so if is also symmetric then the reverse triangle inequality will hold for all vectors

Defining then subadditivity also guarantees that for all the value of on the set is constant and equal to [proof 4] In particular, if is a vector subspace of then and the assignment which will be denoted by is a well-defined real-valued sublinear function on the quotient space that satisfies If is a seminorm then is just the usual canonical norm on the quotient space

Pryce's sublinearity lemma[2] — Suppose is a sublinear functional on a vector space and that is a non-empty convex subset. If is a vector and are positive real numbers such that then for every positive real there exists some such that

Adding to both sides of the hypothesis (where ) and combining that with the conclusion gives which yields many more inequalities, including, for instance, in which an expression on one side of a strict inequality can be obtained from the other by replacing the symbol with (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 is a real-valued sublinear function on a real vector space (or if is complex, then when it is considered as a real vector space) then the map defines a seminorm on the real vector space called the seminorm associated with [3] A sublinear function on a real or complex vector space is a symmetric function if and only if where as before.

More generally, if is a real-valued sublinear function on a (real or complex) vector space then will define a seminorm on if this supremum is always a real number (that is, never equal to ).

Relation to linear functionals

If is a sublinear function on a real vector space then the following are equivalent:[1]

  1. is a linear functional.
  2. for every
  3. for every
  4. is a minimal sublinear function.

If is a sublinear function on a real vector space then there exists a linear functional on such that [1]

If is a real vector space, is a linear functional on and is a positive sublinear function on then on if and only if [1]

Dominating a linear functional

A real-valued function defined on a subset of a real or complex vector space is said to be dominated by a sublinear function if for every that belongs to the domain of If is a real linear functional on then[6][1] is dominated by (that is, ) if and only if Moreover, if is a seminorm or some other symmetric map (which by definition means that holds for all ) then if and only if

Theorem[1] — If be a sublinear function on a real vector space and if then there exists a linear functional on that is dominated by (that is, ) and satisfies Moreover, if is a topological vector space and is continuous at the origin then is continuous.

Continuity

Theorem[7] — Suppose is a subadditive function (that is, for all ). Then is continuous at the origin if and only if is uniformly continuous on If satisfies then is continuous if and only if its absolute value is continuous. If is non-negative then is continuous if and only if is open in

Suppose is a topological vector space (TVS) over the real or complex numbers and is a sublinear function on Then the following are equivalent:[7]

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

and if is positive then this list may be extended to include:

  1. is open in

If is a real TVS, is a linear functional on and is a continuous sublinear function on then on implies that is continuous.[7]

Relation to Minkowski functions and open convex sets

Theorem[7] — If is a convex open neighborhood of the origin in a topological vector space then the Minkowski functional of is a continuous non-negative sublinear function on such that if in addition is a balanced set then is a seminorm on

Relation to open convex sets

Theorem[7] — Suppose that is a topological vector space (not necessarily locally convex or Hausdorff) over the real or complex numbers. Then the open convex subsets of are exactly those that are of the form for some and some positive continuous sublinear function on

Proof

Let be an open convex subset of If then let and otherwise let be arbitrary. Let be the Minkowski functional of which is a continuous sublinear function on since is convex, absorbing, and open ( however is not necessarily a seminorm since was not assumed to be balanced). From it follows that It will be shown that which will complete the proof. One of the known properties of Minkowski functionals guarantees where since is convex and contains the origin. Thus as desired.

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.

Computer science definition

In computer science, a function is called sublinear if or in asymptotic notation (notice the small ). Formally, if and only if, for any given there exists an such that for [8] That is, 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 can be upper-bounded by a concave function of sublinear growth.[9]

See also

Notes

Proofs

  1. ^ Let The triangle inequality and symmetry imply Substituting for and then subtracting from both sides proves that Thus which implies
  2. ^ If and then nonnegative homogeneity implies that Consequently, which is only possible if
  3. ^ which happens if and only if Substituting and gives which implies (positive homogeneity is not needed; the triangle inequality suffices).
  4. ^ Let and It remains to show that The triangle inequality implies Since as desired.

References

  1. ^ a b c d e f g h i Narici & Beckenstein 2011, pp. 177–220.
  2. ^ a b c Schechter 1996, pp. 313–315.
  3. ^ a b c d e Narici & Beckenstein 2011, pp. 120–121.
  4. ^ Kubrusly 2011, p. 200.
  5. ^ a b Narici & Beckenstein 2011, pp. 177–221.
  6. ^ Rudin 1991, pp. 56–62.
  7. ^ a b c d e Narici & Beckenstein 2011, pp. 192–193.
  8. ^ 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.{{cite book}}: CS1 maint: multiple names: authors list (link)
  9. ^ Ceccherini-Silberstein, Tullio; Salvatori, Maura; Sava-Huss, Ecaterina (2017-06-29). Groups, graphs, and random walks. Cambridge. Lemma 5.17. ISBN 9781316604403. OCLC 948670194.{{cite book}}: CS1 maint: location missing publisher (link)

Bibliography

Read other articles:

Finland-Soviet Union war, 1939–1940 Winter War Articles Background Timeline Foreign support Aerial warfare Naval warfare Aftermath Related topics Popular culture Finnish evacuation Mannerheim Line Plans for Franco-British intervention vte The background of the Winter War covers the period before the outbreak of the Winter War between Finland and the Soviet Union (1939–1940), which stretches from the Finnish Declaration of Independence in 1917 to the Soviet-Finnish negotiations in 1938–1...

 

Đối với các định nghĩa khác, xem Mỹ Đông. Mỹ Đông Phường Phường Mỹ Đông Hành chínhQuốc gia Việt NamVùngDuyên hải Nam Trung BộTỉnhNinh ThuậnThành phốPhan Rang – Tháp ChàmThành lập2001[1]Địa lýTọa độ: 11°32′55″B 109°01′07″Đ / 11,548534°B 109,018483°Đ / 11.548534; 109.018483 Mỹ Đông Vị trí phường Mỹ Đông trên bản đồ Việt Nam Diện tích2,51 km²Dân số (2019)Tổ...

 

سالومون نظر (بالإسبانية: José Salomón Nazar Ordóñez)‏  معلومات شخصية الميلاد 7 أغسطس 1953 (العمر 70 سنة)هندوراس  مركز اللعب حارس مرمى الجنسية هندوراس  المسيرة الاحترافية1 سنوات فريق م. (هـ.) 1972–1984 Pumas UNAH [الإنجليزية]‏ 201 (0) 1979–1980 نادي ديبورتيفو أوليمبيا 5 (0) 1980–1981 نادي كرة القدم

Basisdaten (Stand 1994) Bestandszeitraum: 1952–1994 Bezirk: Suhl Verwaltungssitz: Ilmenau Fläche: 346,82 km² Einwohner: 67.912 (31. Dez. 1989) Bevölkerungsdichte: 196 Einwohner je km² Kfz-Kennzeichen: O (1953–1990) OG, OH, OI (1974–1990)IL (1991–1995) Postleitzahlen: 63xx (alt) Kreisgliederung: 28 Gemeinden (31. Dez. 1989) Lage des Kreises in der DDR Karte Kreiskarte Der Kreis Ilmenau war ein Landkreis im Bezirk Suhl der DDR. Von 1990 bis 1994 bestand er als Lan...

 

Ferrocarril Central del Chubut Estación Boca de Zanja con las vías de 75 cmLugarUbicación  Chubut, ArgentinaDescripciónTipo Carga y pasajerosInauguración 1888Clausura 1961Inicio Puerto MadrynFin Las Plumas y Playa UniónCaracterísticas técnicasLongitud 260 kmEstaciones 22Muelles 1 en Puerto MadrynAncho de vía 750 mmVelocidad máxima 60 km/hPropietario Estado NacionalExplotaciónEstado DesmanteladoFlota 1 0-4-0T Orenstein17 Baldwin 2-8-2/4-435 Henschel 2-8-2/4-4? Fives Lille 2-6-0...

 

آرثر جورج كلاين (بالإنجليزية: Arthur George Klein)‏    معلومات شخصية الميلاد 8 أغسطس 1904  نيويورك  الوفاة 20 فبراير 1968 (63 سنة)   نيويورك[1]  مواطنة الولايات المتحدة  مناصب عضوة سابقة[2]   في المنصب1935  – 1941  [2]   تولى المنصب1957  الحياة العملية المدرسة

Tradition of picture Bibles Not to be confused with Poor Man's Bible. Three episodes from a block-book Biblia Pauperum illustrating typological correspondences between the Old and New Testaments: Eve and the serpent, the Annunciation, Gideon's miracle The Biblia pauperum (Latin for Paupers' Bible) was a tradition of picture Bibles beginning probably with Ansgar, and a common printed block-book in the later Middle Ages to visualize the typological correspondences between the Old and New Testam...

 

Teile dieses Artikels scheinen seit 2000 nicht mehr aktuell zu sein. Bitte hilf uns dabei, die fehlenden Informationen zu recherchieren und einzufügen. Wikipedia:WikiProjekt Ereignisse/Vergangenheit/fehlend Lage der Stadt im Bundesstaat Rio de Janeiro Rio de Janeiro gliedert sich in 33 Verwaltungsregionen (Regiões Administrativas). Diese sind 8 Unterpräfekturen und statistisch 5 Planungsgebieten (Áreas de Planejamento) zugeordnet. Die Verwaltungsregionen unterteilen sich in 161 Stadtviert...

 

16th–18th-century European architectural style Baroque architectureClockwise from top left: Church of Saint Ignatius of Loyola in Italy, Church of Santa Prisca de Taxco in Mexico, Smolny Cathedral in Russia, St-Gervais-et-St-Protais in FranceYears activelate 16th–18th centuries Baroque architecture is a highly decorative and theatrical style which appeared in Italy in the early 17th century and gradually spread across Europe. It was originally introduced by the Catholic Church, particular...

Nonprofit organization Keep America Beautiful cleanup volunteers in 2021 Keep America Beautiful is a nonprofit organization founded in 1953. It is the largest community improvement organization in the United States, with more than 700 state and community-based affiliate organizations and more than 1,000 partner organizations.[1] Keep America Beautiful aims to end littering, to improve recycling, and to beautify American communities.[2] The organization's narrow focus on litter...

 

Sporting event delegationIceland at the2016 Summer OlympicsIOC codeISLNOCNational Olympic and Sports Association of IcelandWebsitewww.isi.is (in Icelandic)in Rio de JaneiroCompetitors8 in 4 sportsFlag bearer Þormóður Jónsson[1]Medals Gold 0 Silver 0 Bronze 0 Total 0 Summer Olympics appearances (overview)190819121920–1932193619481952195619601964196819721976198019841988199219962000200420082012201620202024 Iceland competed at the 2016 Summer Olympics in Rio de Janeiro, Br...

 

For the lower house, see Bihar Legislative Assembly. Upper house of the bicameral legislature of the state of Bihar in India Bihar Legislative Council Bihar Vidhan ParishadTypeTypeUpper house of the Bihar Legislature Term limits6 yearsLeadershipChairmanDevesh Chandra Thakur, JD(U) since 24 August 2022 Deputy ChairmanRam Chandra Purve, RJD since 26 August 2022 Leader of the House (Chief Minister)Nitish Kumar, JD(U) since 27 July 2017 Deputy Leader of HouseRabri Devi, RJD since ...

ليام ديك معلومات شخصية الميلاد 19 أغسطس 1995 (العمر 28 سنة)[1]إستيرلينغ  الطول 1.83 م (6 قدم 0 بوصة) مركز اللعب مدافع الجنسية المملكة المتحدة  معلومات النادي النادي الحالي ريث روفرز الرقم 3 المسيرة الاحترافية1 سنوات فريق م. (هـ.) 2011–2016 فالكيرك 15 (0) 2015–2016 → Stranraer F.C. [...

 

Edgware bus stationThe bus station in 2011General informationLocationStation Road, EdgwareLondon Borough of BarnetOperated byTransport for LondonBus routes32, 79, 107, 113, 142, 186, 204, 221, 240, 251, 288, 292, 303, 340, 384, 606, 642, N5, N32 and N113Bus stands5Bus operators Arriva London Metroline London Sovereign Sullivan Buses ConnectionsEdgware Underground station Edgware Bus Station serves the Edgware suburb of the London Borough of Barnet, Greater London, England. The station is owne...

 

Birds of the order Charadriiformes This article is about a group of charadriiform birds. For the waterproof hip boots or fishing trousers, see Waders (footwear). For the group that refers to storks, ibises and herons by North American birders, see Wader (American). Shorebirds redirects here. For the punk rock music band, see Shorebirds (band). WadersTemporal range: Late Oligocene to recent Semipalmated sandpiper (Calidris pusilla) Scientific classification Domain: Eukaryota Kingdom: Animalia ...

Usman PamuntjakKebangsaan IndonesiaPekerjaanTeknokrat, profesionalDikenal atasDirektur Utama (Dirut) PT. Freeport Indonesia Usman Pamuntjak adalah seorang ahli pertambangan dan profesional Indonesia. Ia pernah dipercaya sebagai pimpinan PT. Freeport Indonesia dengan jabatan direktur utama pada perusahaan modal asing pertama pada zaman Orde Baru itu. Ia menjabat posisi tersebut sejak tahun 1985 setelah menggantikan direktur utama sebelumnya, Ali Budiardjo, yang merupakan direktur utama pertama...

 

Исламская революцияперс. انقلاب اسلامی‎ Место Иран Дата с 7 января 1978 года по 11 февраля 1979 года Причины Недовольство населения Ирана политикой правления Шаха Мохаммада Резы Пехлеви,Притеснения со стороны государства религиозных шиитов и высылка аятоллы Рухоллы Хоме...

 

Закон історичної (соціально-екологічної) незворотності полягає у незворотності розвитку суспільно-економічної формацій, які закономірно взаємодіють з природним середовищем. Закон сформулював М. Ф. Реймерс. Процес розвитку людства як цілого не може йти від більш пізніх ...

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Heart of Hearts – news · newspapers · books · scholar · JSTOR (January 2010) (Learn how and when to remove this template message) 1975 studio album by Bobby VintonHeart of HeartsStudio album by Bobby VintonReleasedJuly 1975GenrePopLabelABCProducerBob Mo...

 

Process of converting liquefied natural gas Regasification terminal of Tokyo Gas in Yokohama Regasification is a process of converting liquefied natural gas (LNG) at −162 °C (−260 °F) temperature back to natural gas at atmospheric temperature. LNG gasification plants can be located on land as well as on floating barges, i.e. a Floating Storage and Regasification Unit (FSRU). Floating barge mounted plants have the advantage that they can be towed to new offshore locations for better usag...

 

Strategi Solo vs Squad di Free Fire: Cara Menang Mudah!