Seite - 292 - in Differential Geometrical Theory of Statistics

Entropy2016,18, 442 We call these bounds CELB and CEUB for Combinatorial Envelope Lower and Upper Bounds,respectively. 2.1. TighterAdaptiveBounds We shall now consider shape-dependent bounds improving over the additive logk+ logk′ non-adaptive bounds. This ismadepossible by adecomposition of the lse function explained as follows. Let ti(x1,. . . ,xk)= log ( ∑kj=1e xj−xi ) . By translation identityof the lse function, lse(x1,. . . ,xk)= xi+ ti(x1,. . . ,xk) (13) for all i∈ [k]. Since exj−xi = 1 if j= i, and exj−xi > 0,wehavenecessarily ti(x1,. . . ,xk)> 0 for any i ∈ [k]. SinceEquation (13) is an identity for all i ∈ [k], weminimize the residual ti(x1,. . . ,xk)by maximizing xi. Denotingby x(1), . . . ,x(k) the sequenceofnumbers sorted innon-decreasingorder, thedecomposition lse(x1,. . . ,xk)= x(k)+ t(k)(x1,. . . ,xk) (14) yields thesmallest residual. Sincex(j)−x(k)≤0forall j∈ [k],wehave t(k) (x1,. . . ,xk)= log ( 1+ k−1 ∑ j=1 ex(j)−x(k) ) ≤ logk. Thisshowstheboundsintroducedearliercanindeedbeimprovedbyamoreaccuratecomputation of theresidual term t(k) (x1,. . . ,xk). When considering 1D GMMs, let us now bound t(k)(x1,. . . ,xk) in a combinatorial range Ir=(ar,ar+1). Letδ= δ(r) denote the index of the dominating weighted component in this range.Then, ∀x∈ Ir,∀i, exp ( −logσi− (x−μi) 2 2σ2i + logwi ) ≤exp ( −logσδ− (x−μδ) 2 2σ2δ + logwδ ) . Thuswehave: logm(x)= log wδ σδ √ 2π − (x−μδ) 2 2σ2δ + log ( 1+∑ i =δ exp ( −(x−μi) 2 2σ2i + log wi σi + (x−μδ)2 2σ2δ − logwδ σδ )) . Nowconsider theratio term: ρi,δ(x)= exp ( −(x−μi) 2 2σ2i + log wiσδ wδσi + (x−μδ)2 2σ2δ ) . It ismaximizedin Ir=(ar,ar+1)bymaximizingequivalently the followingquadraticequation: li,δ(x)=−(x−μi) 2 2σ2i + log wiσδ wδσi + (x−μδ)2 2σ2δ . Setting thederivative tozero (l′i,δ(x)=0),weget theroot (whenσi =σδ) xi,δ= ( μδ σ2δ − μi σ2i )/( 1 σ2δ − 1 σ2i ) . Ifxi,δ∈ Ir, theratioρi,δ(x)canbeboundedin theslab Irbyconsidering theextremevaluesof the threeelementset{ρi,δ(ar),ρi,δ(xi,δ),ρi,δ(ar+1)}.Otherwiseρi,δ(x) ismonotonic in Ir, itsbounds in Ir 292