Seite - 290 - in Differential Geometrical Theory of Statistics

Entropy2016,18, 442 canalso lowerboundthe lse functionbylog l+min{xi}li=1.Wewriteequivalently that for lpositive numbersx1, . . . ,xl, max { logmax{xi}li=1,log l+ logmin{xi}li=1 } ≤ log l ∑ i=1 xi≤ log l+ logmax{xi}li=1. (5) Inpractice,weseekmatching lowerandupperboundsthatminimize theboundgap.Thegap of thatham-sandwich inequality inEquation (5) ismin{logmaxi ximini xi , log l},which isupperbounded bylog l. Amixturemodel∑k ′ j=1w ′ jp ′ j(x)mustsatisfy max { max{logw′jp′j(x)}k ′ j=1, logk ′+min{logw′jp′j(x)}k ′ j=1 } ≤ log ( k′ ∑ j=1 w′jp ′ j(x) ) ≤ logk′+max{logw′jp′j(x)}k ′ j=1 (6) point-wiselyforanyx∈X . Thereforeweshallboundtheintegral term∫Xm(x) log(∑k′j=1w′jp′j(x))dx inEquation(3)usingpiecewise lse inequalitieswhere theminandmaxarekeptunchanged.Weget L×(m :m′)=− ∫ X m(x)max{logw′jp′j(x)}k ′ j=1dx− logk′, (7) U×(m :m′)=− ∫ X m(x)max { min{logw′jp′j(x)}k ′ j=1+ logk ′, max{logw′jp′j(x)}k ′ j=1 } dx. (8) Inorder to calculate L×(m :m′) andU×(m :m′) efficientlyusing closed-formformula, let us compute the upper and lower envelopes of the k′ real-valued functions {w′jp′j(x)}k ′ j=1 defined on the supportX , that is,EU(x) =max{w′jp′j(x)}k ′ j=1 andEL(x) =min{w′jp′j(x)}k ′ j=1. These envelopes can be computed exactly using techniques of computational geometry [22,23] provided that we can calculate the roots of the equationw′rp′r(x) = w′sp′s(x), wherew′rp′r(x) andw′sp′s(x) are a pair ofweighted components. (Although this amounts to solve quadratic equations for Gaussian or Rayleigh distributions, the rootsmay not always be available in closed form, e.g. in the case of Weibulldistributions.) Let the envelopes be combinatorially described by elementary interval pieces in the form Ir=(ar,ar+1)partitioning thesupportX =unionmulti r=1Ir (with a1=minX and a +1=maxX). Observe thatoneach interval Ir, themaximumofthefunctions{w′jp′j(x)}k ′ j=1 isgivenbyw ′ δ(r)p ′ δ(r)(x),where δ(r) indicates theweightedcomponentdominatingall theothers, i.e., theargmaxof{w′jp′j(x)}k ′ j=1 for anyx∈ Ir, andtheminimumof{w′jp′j(x)}k ′ j=1 isgivenbyw ′ (r)p ′ (r)(x). To fix ideas, whenmixture components are univariateGaussians, the upper envelope EU(x) amounts to find equivalently the lower envelope of k′ parabolas (see Figure 1)which has linear complexity,andcanbecomputedinO(k′ logk′)-time[24],or inoutput-sensitive timeO(k′ log ) [25], where denotes the number of parabola segments in the envelope. When theGaussianmixture componentshaveall thesameweightandvariance(e.g.,kerneldensityestimators), theupperenvelope amounts tofindalowerenvelopeofcones:minj |x−μ′j| (aVoronoidiagraminarbitrarydimension). 290