text: gentle one. Hence, the ratchet in Fig. 1 has counterclockwise chirality. In the following analytical and numerical simulation results, under the RDDF, the net rotation of the ratchet tends to be the same as the chirality. In the numerical simulations, we examine only the case of I = 0 and we treat the eﬃciency as γLω η = . (3.6) P h In this paper, we consider a ratchet system in a thermal bath under a weak and slow external ﬁeld, and we impose the following requirements: 1) the typical magnitudes of V (x, t) and I (which are denoted by O(h) and O(I), respectively, in an energetic dimension) h are smaller than the energy barrier ∆V [see Eq. (2.9)] to a suﬃcient extent, it being assumed hereinafter that O(I) ∼ O(h); 2) the mean switching time of the RDDF (T ≡ 2π) is longer p Ω than the typical relaxation time T of a trajectory to a suﬃcient extent, i.e., ΩT (cid:28) 1, where r r − T 1 is related to the curvature of V (x) at the minima [or more likely is governed by the r 0 smallest eigenvalue of Gˆ (x )]. 0 σ In a previous paper [25], we proposed a framework for obtaining approximate expressions for the performance indexes (L, ω, and P ) using a master equation for coarse-grained states h under the assumptions mentioned above. For a self-contained description, we brieﬂy intro- duce the basic construction of the master equation and its applications to the computation of L, ω, and P in Secs. III A and . In Sec. III C, we show the ﬁnal expressions for L, ω, and h P that we use in later sections. h A. Coarse-grained states and related deﬁnitions As shown in Fig. 2, we denote O, x , and xµ (σ ∈ {+, −} and µ ∈ {+, −}) as the origin, σ the local minimum, and the saddle, respectively, determined by ∂ V (x) = 0. Hereinafter, x 0 the signs “+” and “−” are identical with +1 and −1, thereby x = σx and xµ = µx+, σ + where x and x+ lie in x > 0 and y > 0, respectively. Furthermore, B (Bµ) denotes the + σ ridge curve running from O through x (xµ) outward; Dµ denotes the domain surrounded σ σ by B and Bµ; C denotes the potential valley of V (x). σ 0 We extend these static ridge curves to temporally varying ridge curves on the basis of the function I V (x, t) ≡ V (x) + V (x, t) + θ(x) (3.7) 0 h 2π 12 ##LTLine## ##LTLine## ##LTLine##

text: gentle

text: one.

text: Hence,

text: the

text: ratchet

text: in

text: Fig.

text: has

text: counterclockwise

text: chirality.

text: In

text: the

text: following

text: analytical

text: and

text: numerical

text: simulation

text: results,

text: under

text: the

text: RDDF,

text: the

text: net

text: rotation

text: of

text: the

text: ratchet

text: tends

text: to

text: be

text: the

text: same

text: as

text: the

text: chirality.

text: In

text: the

text: numerical

text: simulations,

text: we

text: examine

text: only

text: the

text: case

text: of

text: I

text: and

text: we

text: treat

text: the

text: eﬃciency

text: as

text: γLω

text: η

text: P

text: h

text: In

text: this

text: paper,

text: we

text: consider

text: a

text: ratchet

text: system

text: in

text: a

text: thermal

text: bath

text: under

text: a

text: weak

text: and

text: slow

text: external

text: ﬁeld,

text: and

text: we

text: impose

text: the

text: following

text: requirements:

text: the

text: typical

text: magnitudes

text: of

text: V

text: (x,

text: t)

text: and

text: I

text: (which

text: are

text: denoted

text: by

text: O(h)

text: and

text: O(I),

text: respectively,

text: in

text: an

text: energetic

text: dimension)

text: h

text: are

text: smaller

text: than

text: the

text: energy

text: barrier

text: ∆V

text: [see

text: Eq.

text: to

text: a

text: suﬃcient

text: extent,

text: it

text: being

text: assumed

text: hereinafter

text: that

text: O(I)

text: O(h);

text: the

text: mean

text: switching

text: time

text: of

text: the

text: RDDF

text: (T

text: is

text: longer

text: p

text: Ω

text: than

text: the

text: typical

text: relaxation

text: time

text: T

text: of

text: a

text: trajectory

text: to

text: a

text: suﬃcient

text: extent,

text: i.e.,

text: ΩT

text: where

text: r

text: r

text: T

text: is

text: related

text: to

text: the

text: curvature

text: of

text: V

text: (x)

text: at

text: the

text: minima

text: [or

text: more

text: likely

text: is

text: governed

text: by

text: the

text: r

text: smallest

text: eigenvalue

text: of

text: Gˆ

text: (x

text: σ

text: In

text: a

text: previous

text: paper

text: we

text: proposed

text: a

text: framework

text: for

text: obtaining

text: approximate

text: expressions

text: for

text: the

text: performance

text: indexes

text: (L,

text: ω,

text: and

text: P

text: using

text: a

text: master

text: equation

text: for

text: coarse-grained

text: states

text: h

text: under

text: the

text: assumptions

text: mentioned

text: above.

text: For

text: a

text: self-contained

text: description,

text: we

text: brieﬂy

text: intro-

text: duce

text: the

text: basic

text: construction

text: of

text: the

text: master

text: equation

text: and

text: its

text: applications

text: to

text: the

text: computation

text: of

text: L,

text: ω,

text: and

text: P

text: in

text: Secs.

text: III

text: A

text: and

text: In

text: Sec.

text: III

text: C,

text: we

text: show

text: the

text: ﬁnal

text: expressions

text: for

text: L,

text: ω,

text: and

text: h

text: P

text: that

text: we

text: use

text: in

text: later

text: sections.

text: h

text: A.

text: Coarse-grained

text: states

text: and

text: related

text: deﬁnitions

text: As

text: shown

text: in

text: Fig.

text: we

text: denote

text: O,

text: x

text: and

text: xµ

text: (σ

text: and

text: µ

text: as

text: the

text: origin,

text: σ

text: the

text: local

text: minimum,

text: and

text: the

text: saddle,

text: respectively,

text: determined

text: by

text: V

text: (x)

text: Hereinafter,

text: x

text: the

text: signs

text: and

text: are

text: identical

text: with

text: and

text: thereby

text: x

text: σx

text: and

text: xµ

text: µx+,

text: σ

text: where

text: x

text: and

text: x+

text: lie

text: in

text: x

text: and

text: y

text: respectively.

text: Furthermore,

text: B

text: (Bµ)

text: denotes

text: the

text: σ

text: ridge

text: curve

text: running

text: from

text: O

text: through

text: x

text: (xµ)

text: outward;

text: Dµ

text: denotes

text: the

text: domain

text: surrounded

text: σ

text: σ

text: by

text: B

text: and

text: Bµ;

text: C

text: denotes

text: the

text: potential

text: valley

text: of

text: V

text: (x).

text: σ

text: We

text: extend

text: these

text: static

text: ridge

text: curves

text: to

text: temporally

text: varying

text: ridge

text: curves

text: on

text: the

text: basis

text: of

text: the

text: function

text: I

text: V

text: (x,

text: t)

text: V

text: (x)

text: V

text: (x,

text: t)

text: θ(x)

text: h

text: 2π

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: we decompose Eq. (2.3) in two directions as m − τ · ∂ v (x) [1 − {v (x)}m] {v (x)}m 1 = −K v x 1 , (2.5) 0 0 2 |∂ v (x)| x 0 n · ∂ v (x) = 0. (2.6) v x 1 When taking the limit m → ∞ in Eqs. (2.5) and (2.6), the minima and the saddles, {x , xµ}, satisfy σ n · ∂ v (x) = 0, x ∈ C∞. (2.7) v x 1 For a geometrical interpretation of Eq. (2.7), let us deﬁne E : {x | v (x) = E} as a family 1 of curves speciﬁed by the parameter E. Then, Eq. (2.7) means that with certain values of E, the curves E and C∞ have tangent points at x ∈ {x , xµ} at which n is tangent σ v to both curves. As shown in Fig. 1, there are two cases of tangency depending on E; let E : {x | v (x) = E } [ E+ : {x | v (x) = E+}] be a curve that is tangent to C∞ at x = x + 1 + 1 σ [x = xµ] as E reaches E [E+]. Since we choose K > 0, we have E+ ≤ E . Therefore, E + + + is externally tangent to C∞, and E+ is internally tangent to C∞. However, these describe only the local relationships between v (x) and v (x) at x = x (E = E+) and xµ (E+) as 0 1 σ they contact; the global relationships between them remain undeﬁned. As global conditions − in which E (E+) contacts with C∞ only at two points x = x and x− (x = x+ and x ), + + we insist that all points on C∞ satisfy E+ ≤ v (x) ≤ E , (2.8) 1 + where equal cases of the left and right sides hold at x = xµ and x , respectively. In this σ case, letting ∆V be the diﬀerence of V (x) [Eq. (1.10)] between the saddle and the local 0 minimum, we have ∆V = K(E − E+). (2.9) + B. Hessian matrix The Hessian matrix Gˆ (x) ≡ ∂ ∂TV (x) is diagonalized approximately for m (cid:29) 1. We 0 x x 0 denote its eigenvectors by n(x) and τ (x), i.e., 9 ##LTLine## ##LTLine##

text: we

label: paragraph

text: decompose

text: Eq.

text: in

text: two

text: directions

text: as

text: m

text: τ

text: v

text: (x)

text: {v

text: (x)}m]

text: {v

text: (x)}m

text: −K

text: v

text: x

text: v

text: (x)|

text: x

text: n

text: v

text: (x)

text: v

text: x

text: When

text: taking

text: the

text: limit

text: m

text: in

text: Eqs.

text: and

text: the

text: minima

text: and

text: the

text: saddles,

text: {x

text: xµ},

text: satisfy

text: σ

text: n

text: v

text: (x)

text: x

text: C∞.

text: v

text: x

text: For

text: a

text: geometrical

text: interpretation

text: of

text: Eq.

text: let

text: us

text: deﬁne

text: E

text: {x

text: v

text: (x)

text: E}

text: as

text: a

text: family

text: of

text: curves

text: speciﬁed

text: by

text: the

text: parameter

text: E.

text: Then,

text: Eq.

text: means

text: that

text: with

text: certain

text: values

text: of

text: E,

text: the

text: curves

text: E

text: and

text: C∞

text: have

text: tangent

text: points

text: at

text: x

text: {x

text: xµ}

text: at

text: which

text: n

text: is

text: tangent

text: σ

text: v

text: to

text: both

text: curves.

text: As

text: shown

text: in

text: Fig.

text: there

text: are

text: two

text: cases

text: of

text: tangency

text: depending

text: on

text: E;

text: let

text: E

text: {x

text: v

text: (x)

text: E

text: E+

text: {x

text: v

text: (x)

text: E+}]

text: be

text: a

text: curve

text: that

text: is

text: tangent

text: to

text: C∞

text: at

text: x

text: x

text: σ

text: [x

text: xµ]

text: as

text: E

text: reaches

text: E

text: [E+].

text: Since

text: we

text: choose

text: K

text: we

text: have

text: E+

text: E

text: Therefore,

text: E

text: is

text: externally

text: tangent

text: to

text: C∞,

text: and

text: E+

text: is

text: internally

text: tangent

text: to

text: C∞.

text: However,

text: these

text: describe

text: only

text: the

text: local

text: relationships

text: between

text: v

text: (x)

text: and

text: v

text: (x)

text: at

text: x

text: x

text: (E

text: E+)

text: and

text: xµ

text: (E+)

text: as

text: σ

text: they

text: contact;

text: the

text: global

text: relationships

text: between

text: them

text: remain

text: undeﬁned.

text: As

text: global

text: conditions

text: in

text: which

text: E

text: (E+)

text: contacts

text: with

text: C∞

text: only

text: at

text: two

text: points

text: x

text: x

text: and

text: x−

text: (x

text: x+

text: and

text: x

text: we

text: insist

text: that

text: all

text: points

text: on

text: C∞

text: satisfy

text: E+

text: v

text: (x)

text: E

text: where

text: equal

text: cases

text: of

text: the

text: left

text: and

text: right

text: sides

text: hold

text: at

text: x

text: xµ

text: and

text: x

text: respectively.

text: In

text: this

text: σ

text: case,

text: letting

text: ∆V

text: be

text: the

text: diﬀerence

text: of

text: V

text: (x)

text: [Eq.

text: between

text: the

text: saddle

text: and

text: the

text: local

text: minimum,

text: we

text: have

text: ∆V

text: K(E

text: E+).

text: B.

text: Hessian

text: matrix

text: The

text: Hessian

text: matrix

text: Gˆ

text: (x)

text: ∂TV

text: (x)

text: is

text: diagonalized

text: approximately

text: for

text: m

text: We

text: x

text: x

text: denote

text: its

text: eigenvectors

text: by

text: n(x)

text: and

text: τ

text: (x),

text: i.e.,

text: ##LTLine##

text: ##LTLine##


text: n/2 edges). (This fact was independently proved by many people, such as Zykov [Zyk49], Erd˝os [Erd62], Sauer [Sau71], Hadˇziivanov [Had76], and Roman [Rom76]. For a recent simple proof, see Cutler and Radcliﬀe [CR11].) (cid:101) The number of minimum hitting sets is O(2n/2). Since the number of edges in a graph of n − vertices is at most n2/2, the maximum correlation per size is Θ(2 n/2). Moreover, depth-3 circuit size and depth-3 formula with bottom fan-in 2 are the same up to a factor of O(n2) (e.g., see [PSZ00, Proposition 2.2]). Thus, the minimum circuit size is equal to 2n/2 up to a polynomial (cid:3) factor. We remark that the same quantitative bound can be obtained by using the techniques of [HJP95]. Proposition 12 merely gives its alternative proof from the techniques of the diﬀerent literature. 4 Approximating Monotone Functions by Depth-2 Formulas It is reasonable to conjecture that an analog of Proposition 10 holds for nonmonotone CNF formulas: that is, we conjecture that the uniform distribution on S(cid:100)n (cid:101) is close to the hardest n/2 distribution of CNF formulas approximating Maj . And it is tempting to guess that, since Maj n n is a monotone function, an optimal CNF formula approximating Maj should be a monotone CNF n formula. This is true when exact complexity of computing monotone function is concerned, by Quine’s theorem [Qui54]. It is, however, not true when approximation is concerned: Blais, H˚astad, Servedio and Tan [BHST14] showed that there is a monotone function on n variables that can be approximated by some CNF formula of size O(n), but cannot be approximated by any monotone CNF formula of size less than n2. Here we signiﬁcantly improve their bounds: N → Theorem 13 (Theorem 3, restated formally). There exists a function (cid:15): (0, 1) and a family of { { } → { }} { } monotone Boolean functions f = f : 0, 1 n 0, 1 ∈N and a family of distributions µ ∈N − n n n n on f 1(1) such that n • { } − ⊆ − there is some CNF formula ϕ ∈N of size at most nO(1) satisfying ϕ 1(1) f 1(1) and ≤ n n n n Pr ∼ [ϕ (x) = 1] (cid:15)(n), whereas x µn n • { } − ⊆ − any monotone CNF formula ϕ+ ∈N satisfying (ϕ+) 1(1) f 1(1) and Pr ∼ [ϕ+(x) = ≤ n n n n x µn n 1] (cid:15)(n) requires size 2nΩ(1). In fact, this theorem is an immediate consequence of our duality theorem together with recently improved Ajtai-Gurevich’s theorem [AG87]. Theorem 14 (Chen, Oliveira and Servedio [COS15]). There exists a family of monotone functions { { } → { }} f = f : 0, 1 n 0, 1 ∈N such that n n 1. L (f ) = nO(1), and 3 n 2. any monotone depth-d circuit6 computing f requires size 2nΩ(1/d). 6In fact, their result gives a lower bound for monotone majority circuits. For our purpose, it is suﬃcient to use a ◦ ◦ lower bound for monotone OR AND OR circuits. 13 ##LTLine##

text: edges).

text: (This

text: fact

text: was

text: independently

text: proved

text: by

text: many

text: people,

text: such

text: as

text: Zykov

text: Erd˝os

text: Sauer

text: Hadˇziivanov

text: and

text: Roman

text: For

text: a

text: recent

text: simple

text: proof,

text: see

text: Cutler

text: and

text: Radcliﬀe

text: The

text: number

text: of

text: minimum

text: hitting

text: sets

text: is

text: Since

text: the

text: number

text: of

text: edges

text: in

text: a

text: graph

text: of

text: n

text: vertices

text: is

text: at

text: most

text: the

text: maximum

text: correlation

text: per

text: size

text: is

text: Moreover,

text: circuit

text: size

text: and

text: formula

text: with

text: bottom

text: fan-in

text: are

text: the

text: same

text: up

text: to

text: a

text: factor

text: of

text: (e.g.,

text: see

text: Proposition

text: Thus,

text: the

text: minimum

text: circuit

text: size

text: is

text: equal

text: to

text: up

text: to

text: a

text: polynomial

text: factor.

text: We

text: remark

text: that

text: the

text: same

text: quantitative

text: bound

text: can

text: be

text: obtained

text: by

text: using

text: the

text: techniques

text: of

text: Proposition

text: merely

text: gives

text: its

text: alternative

text: proof

text: from

text: the

text: techniques

text: of

text: the

text: diﬀerent

text: literature.

text: Approximating

text: Monotone

text: Functions

text: by

text: Formulas

text: It

text: is

text: reasonable

text: to

text: conjecture

text: that

text: an

text: analog

text: of

text: Proposition

text: holds

text: for

text: nonmonotone

text: CNF

text: formulas:

text: that

text: is,

text: we

text: conjecture

text: that

text: the

text: uniform

text: distribution

text: on

text: is

text: close

text: to

text: the

text: hardest

text: distribution

text: of

text: CNF

text: formulas

text: approximating

text: Maj

text: And

text: it

text: is

text: tempting

text: to

text: guess

text: that,

text: since

text: Maj

text: n

text: n

text: is

text: a

text: monotone

text: function,

text: an

text: optimal

text: CNF

text: formula

text: approximating

text: Maj

text: should

text: be

text: a

text: monotone

text: CNF

text: n

text: formula.

text: This

text: is

text: true

text: when

text: exact

text: complexity

text: of

text: computing

text: monotone

text: function

text: is

text: concerned,

text: by

text: Quine’s

text: theorem

text: It

text: is,

text: however,

text: not

text: true

text: when

text: approximation

text: is

text: concerned:

text: Blais,

text: H˚astad,

text: Servedio

text: and

text: Tan

text: showed

text: that

text: there

text: is

text: a

text: monotone

text: function

text: on

text: n

text: variables

text: that

text: can

text: be

text: approximated

text: by

text: some

text: CNF

text: formula

text: of

text: size

text: O(n),

text: but

text: cannot

text: be

text: approximated

text: by

text: any

text: monotone

text: CNF

text: formula

text: of

text: size

text: less

text: than

text: Here

text: we

text: signiﬁcantly

text: improve

text: their

text: bounds:

text: N

text: Theorem

text: (Theorem

text: restated

text: formally).

text: There

text: exists

text: a

text: function

text: and

text: a

text: family

text: of

text: monotone

text: Boolean

text: functions

text: f

text: f

text: n

text: ∈N

text: and

text: a

text: family

text: of

text: distributions

text: µ

text: ∈N

text: n

text: n

text: n

text: n

text: on

text: f

text: such

text: that

text: n

text: there

text: is

text: some

text: CNF

text: formula

text: ϕ

text: ∈N

text: of

text: size

text: at

text: most

text: satisfying

text: ϕ

text: f

text: and

text: n

text: n

text: n

text: n

text: Pr

text: [ϕ

text: (x)

text: whereas

text: x

text: µn

text: n

text: any

text: monotone

text: CNF

text: formula

text: ϕ+

text: ∈N

text: satisfying

text: (ϕ+)

text: f

text: and

text: Pr

text: [ϕ+(x)

text: n

text: n

text: n

text: n

text: x

text: µn

text: n

text: requires

text: size

text: In

text: fact,

text: this

text: theorem

text: is

text: an

text: immediate

text: consequence

text: of

text: our

text: duality

text: theorem

text: together

text: with

text: recently

text: improved

text: Ajtai-Gurevich’s

text: theorem

text: Theorem

text: (Chen,

text: Oliveira

text: and

text: Servedio

text: There

text: exists

text: a

text: family

text: of

text: monotone

text: functions

text: f

text: f

text: n

text: ∈N

text: such

text: that

text: n

text: n

text: L

text: (f

text: and

text: n

text: any

text: monotone

text: depth-d

text: computing

text: f

text: requires

text: size

text: fact,

text: their

text: result

text: gives

text: a

text: lower

text: bound

text: for

text: monotone

text: majority

text: circuits.

text: For

text: our

text: purpose,

text: it

text: is

text: suﬃcient

text: to

text: use

text: a

text: lower

text: bound

text: for

text: monotone

text: OR

text: AND

text: OR

text: circuits.

text: ##LTLine##


text: Similarly, the techniques of O’Donnell and Wimmer [OW07] who studied approximation of the majority function by DNF formulas (under the uniform distribution) might be helpful for studying T (n, n/2) and the depth-3 circuit size of majority. We believe that the explicit link established between depth-3 formula size and the complexity of approximation by depth-2 is useful to advance both of these lines of research further. Can one ﬁnd another application of the duality? References [AG87] Mikl´os Ajtai and Yuri Gurevich. Monotone versus positive. J. ACM, 34(4):1004–1015, 1987. [Ajt83] Mikl´os Ajtai. Σ1-formulae on ﬁnite structures. Annals of pure and applied logic, 24(1):1– 1 48, 1983. [BHST14] Eric Blais, Johan H˚astad, Rocco A. Servedio, and Li-Yang Tan. On DNF approximators for monotone boolean functions. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP), Part I, pages 235–246, 2014. [BIS12] Paul Beame, Russell Impagliazzo, and Srikanth Srinivasan. Approximating AC0 by small height decision trees and a deterministic algorithm for #AC0SAT. In Proceedings of the 27th Conference on Computational Complexity (CCC), pages 117–125, 2012. [BT15] Eric Blais and Li-Yang Tan. Approximating boolean functions with depth-2 circuits. SIAM J. Comput., 44(6):1583–1600, 2015. [Chv79] Vasek Chvatal. A greedy heuristic for the set-covering problem. Math. Oper. Res., 4(3):233–235, 1979. [CIP06] Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi. A duality between clause width and clause density for SAT. In Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC), pages 252–260, 2006. [COS15] Xi Chen, Igor Carboni Oliveira, and Rocco A. Servedio. Addition is exponentially harder than counting for shallow monotone circuits. CoRR, abs/1508.03061, 2015. [CR11] Jonathan Cutler and A. J. Radcliﬀe. Extremal problems for independent set enumera- tion. Electr. J. Comb., 18(1), 2011. [DH09] Evgeny Dantsin and Edward A. Hirsch. Worst-case upper bounds. In Armin Biere, Marijn Heule, Hans van Maaren, and Toby Walsh, editors, Handbook of Satisﬁability, chapter 12, pages 359–380. IOS Press, 2009. [Erd62] Paul Erd˝os. On the number of complete subgraphs contained in certain graphs. Magyar Tud. Akad. Mat. Kutat´o Int. K¨ozl, 7:459–464, 1962. [Fil10] Yuval Filmus. Smolensky’s lower bound. 2010. [Fre95] Yoav Freund. Boosting a weak learning algorithm by majority. Inf. Comput., 121(2):256–285, 1995. 20

text: Similarly,

text: the

text: techniques

text: of

text: O’Donnell

text: and

text: Wimmer

text: who

text: studied

text: approximation

text: of

text: the

text: majority

text: function

text: by

text: DNF

text: formulas

text: (under

text: the

text: uniform

text: distribution)

text: might

text: be

text: helpful

text: for

text: studying

text: T

text: (n,

text: and

text: the

text: circuit

text: size

text: of

text: majority.

text: We

text: believe

text: that

text: the

text: explicit

text: link

text: established

text: between

text: formula

text: size

text: and

text: the

text: complexity

text: of

text: approximation

text: by

text: is

text: useful

text: to

text: advance

text: both

text: of

text: these

text: lines

text: of

text: research

text: further.

text: Can

text: one

text: ﬁnd

text: another

text: application

text: of

text: the

text: duality?

text: References

label: reference

text: Mikl´os

text: Ajtai

text: and

text: Yuri

text: Gurevich.

text: Monotone

text: versus

text: positive.

text: J.

text: ACM,

text: Mikl´os

text: Ajtai.

text: on

text: ﬁnite

text: structures.

text: Annals

text: of

text: pure

text: and

text: applied

text: logic,

text: Eric

text: Blais,

text: Johan

text: H˚astad,

text: Rocco

text: A.

text: Servedio,

text: and

text: Li-Yang

text: Tan.

text: On

text: DNF

text: approximators

text: for

text: monotone

text: boolean

text: functions.

text: In

text: Proceedings

text: of

text: the

text: International

text: Colloquium

text: on

text: Automata,

text: Languages,

text: and

text: Programming

text: (ICALP),

text: Part

text: I,

text: pages

text: Paul

text: Beame,

text: Russell

text: Impagliazzo,

text: and

text: Srikanth

text: Srinivasan.

text: Approximating

text: by

text: small

text: height

text: decision

text: trees

text: and

text: a

text: deterministic

text: algorithm

text: for

text: In

text: Proceedings

text: of

text: the

text: Conference

text: on

text: Computational

text: Complexity

text: (CCC),

text: pages

text: Eric

text: Blais

text: and

text: Li-Yang

text: Tan.

text: Approximating

text: boolean

text: functions

text: with

text: circuits.

text: SIAM

text: J.

text: Comput.,

text: Vasek

text: Chvatal.

text: A

text: greedy

text: heuristic

text: for

text: the

text: set-covering

text: problem.

text: Math.

text: Oper.

text: Res.,

text: Chris

text: Calabro,

text: Russell

text: Impagliazzo,

text: and

text: Ramamohan

text: Paturi.

text: A

text: duality

text: between

text: clause

text: width

text: and

text: clause

text: density

text: for

text: SAT.

text: In

text: Proceedings

text: of

text: the

text: Annual

text: IEEE

text: Conference

text: on

text: Computational

text: Complexity

text: (CCC),

text: pages

text: Xi

text: Chen,

text: Igor

text: Carboni

text: Oliveira,

text: and

text: Rocco

text: A.

text: Servedio.

text: Addition

text: is

text: exponentially

text: harder

text: than

text: counting

text: for

text: shallow

text: monotone

text: circuits.

text: CoRR,

text: Jonathan

text: Cutler

text: and

text: A.

text: J.

text: Radcliﬀe.

text: Extremal

text: problems

text: for

text: independent

text: set

text: enumera-

text: tion.

text: Electr.

text: J.

text: Comb.,

text: Evgeny

text: Dantsin

text: and

text: Edward

text: A.

text: Hirsch.

text: Worst-case

text: upper

text: bounds.

text: In

text: Armin

text: Biere,

text: Marijn

text: Heule,

text: Hans

text: van

text: Maaren,

text: and

text: Toby

text: Walsh,

text: editors,

text: Handbook

text: of

text: Satisﬁability,

text: chapter

text: pages

text: IOS

text: Press,

text: Paul

text: Erd˝os.

text: On

text: the

text: number

text: of

text: complete

text: subgraphs

text: contained

text: in

text: certain

text: graphs.

text: Magyar

text: Tud.

text: Akad.

text: Mat.

text: Kutat´o

text: Int.

text: K¨ozl,

text: Yuval

text: Filmus.

text: Smolensky’s

text: lower

text: bound.

text: Yoav

text: Freund.

text: Boosting

text: a

text: weak

text: learning

text: algorithm

text: by

text: majority.

text: Inf.

text: Comput.,


text: 2 TIM AUSTIN AND MOUMAN(cid:83)TI PODDER F Suppose ﬁrst that the set of particles V is also ﬁnite. Let be a family of → −∞ ∞ subsets of V . An interaction is a function Φ : ∈F AS [ , ). The Gibbs (cid:40) S(cid:41) measure µΦ with respect to Φ is deﬁned(cid:88)as 1 ∈ µΦ(ξ) = exp Φ(ξ ) , ξ AV , (1.1) ZΦ ∈F S S where ξ is the projection of ξ to coordinates in S, and ZΦ is the partition S (cid:40) (cid:41) function deﬁned as (cid:88) (cid:88) ZΦ = exp Φ(ξ ) . (1.2) S (cid:80) ξ∈AV S∈F ∈ This Gibbs measure is well deﬁned if at least one ξ AV has ﬁnite energy, i.e. −∞ ∈F Φ(ξ ) > , and in this case µ is supported only on those conﬁgurations ξ S S that have this property. We assume that at least one such ξ exists, in the rest of the paper. If V is inﬁnite, this direct deﬁnition is not available, since the sums inside the exponentials above are generally also inﬁnite. In that case we deﬁne associated F (cid:83) Gibbs states as follows. Suppose now that is a family of ﬁnite subsets of V which is locally ﬁnite (that is, every element of V lies in only ﬁnitely many members F → −∞ ∞ of ). Consider again an interaction Φ : ∈F AS [ , ). In order to S F encompass models with hard-core constraints, we allow some sets F in and ∈ −∞ certain conﬁgurations ξ AF such that Φ(ξ ) = . Let Ω be the set of all F F ∈ F conﬁgurations ξ in AV such that they have ﬁnite local energies, i.e. for every F , −∞ (cid:88) we have Φ(ξ ) > . It follows that in this case, for every positive integer s, we F have −∞ Φ(ξ ) > . F ∈F ⊆ F ,F Td(s) Then a probability measure σ on AV is a Gibbs state for Φ if it is supported on Ω ⊆ (cid:90) and for every ﬁnite S V one has σ = µ σ \ (dη), (1.3) S S,η V S \ AV S where σ is the image of σ under the projection map from AV to AS, and µ S S,η   is deﬁned as  (cid:88) (cid:88)    ∝ ∨ ∀ ∈ µ (ξ) exp Φ(ξ ) + Φ((ξ η) ) ξ AS. (1.4) S,η F F ∈F ⊆ ∈F F ,F S ∩ (cid:54) F∅ ∩ (cid:54) ∅ F S= ,F Sc= ∨ In the last formula, ξ η is the element in AV which equals ξ when restricted to S and equals η when restricted to Sc. The expression in (1.4) makes sense because ∈ ⊆ we only consider η Ω ASc, where Ω is the projection of Ω onto ASc. The ∨ Sc ∨ Sc ∈ quantity (ξ η) is the restriction of ξ η to F. Since η Ω , there exists at least ∈ F Sc one ξ AS for which the sum inside the exponential in (1.4) is ﬁnite. ##LTLine##

text: TIM

text: AUSTIN

text: AND

text: PODDER

text: F

text: Suppose

text: ﬁrst

text: that

text: the

text: set

text: of

text: particles

text: V

text: is

text: also

text: ﬁnite.

text: Let

text: be

text: a

text: family

text: of

text: subsets

text: of

text: V

text: An

text: interaction

text: is

text: a

text: function

text: Φ

text: ∈F

text: AS

text: The

text: Gibbs

label: equation

text: measure

text: µΦ

text: with

text: respect

text: to

text: Φ

text: is

text: µΦ(ξ)

text: exp

text: Φ(ξ

text: ξ

text: AV

text: ZΦ

text: ∈F

text: S

text: S

text: where

text: ξ

text: is

text: the

text: projection

text: of

text: ξ

text: to

text: coordinates

text: in

text: S,

text: and

text: ZΦ

text: is

text: the

text: partition

text: S

text: function

text: deﬁned

text: as

text: ZΦ

text: exp

text: Φ(ξ

text: S

text: ξ∈AV

text: S∈F

text: This

text: Gibbs

text: measure

text: is

text: well

text: deﬁned

text: if

text: at

text: least

text: one

text: ξ

text: AV

text: has

text: ﬁnite

text: energy,

text: i.e.

text: ∈F

text: Φ(ξ

text: and

text: in

text: this

text: case

text: µ

text: is

text: supported

text: only

text: on

text: those

text: conﬁgurations

text: ξ

text: S

text: S

text: that

text: have

text: this

text: property.

text: We

text: assume

text: that

text: at

text: least

text: one

text: such

text: ξ

text: exists,

text: in

text: the

text: rest

text: of

text: the

text: paper.

text: If

text: V

text: is

text: inﬁnite,

text: this

text: direct

text: deﬁnition

text: is

text: not

text: available,

text: since

text: the

text: sums

text: inside

text: the

text: exponentials

text: above

text: are

text: generally

text: also

text: inﬁnite.

text: In

text: that

text: case

text: we

text: deﬁne

text: associated

text: F

text: Gibbs

text: states

text: as

text: follows.

text: Suppose

text: now

text: that

text: is

text: a

text: family

text: of

text: ﬁnite

text: subsets

text: of

text: V

text: which

text: is

text: locally

text: ﬁnite

text: (that

text: is,

text: every

text: element

text: of

text: V

text: lies

text: in

text: only

text: ﬁnitely

text: many

text: members

text: F

text: of

text: Consider

text: again

text: an

text: interaction

text: Φ

text: ∈F

text: AS

text: In

text: order

text: to

text: S

text: F

text: encompass

text: models

text: with

text: hard-core

text: constraints,

text: we

text: allow

text: some

text: sets

text: F

text: in

text: and

text: certain

text: conﬁgurations

text: ξ

text: AF

text: such

text: that

text: Φ(ξ

text: Let

text: Ω

text: be

text: the

text: set

text: of

text: all

text: F

text: F

text: F

text: conﬁgurations

text: ξ

text: in

text: AV

text: such

text: that

text: they

text: have

text: ﬁnite

text: local

text: energies,

text: i.e.

text: for

text: every

text: F

text: we

text: have

text: Φ(ξ

text: It

text: follows

text: that

text: in

text: this

text: case,

text: for

text: every

text: positive

text: integer

text: s,

text: we

text: F

text: have

text: Φ(ξ

text: F

text: ∈F

text: F

text: ,F

text: Td(s)

text: Then

text: a

text: probability

text: measure

text: σ

text: on

text: AV

text: is

text: a

text: Gibbs

text: state

text: for

text: Φ

text: if

text: it

text: is

text: supported

text: on

text: Ω

text: and

text: for

text: every

text: ﬁnite

text: S

text: V

text: one

text: has

text: σ

text: µ

text: σ

text: (dη),

text: S

text: S,η

text: V

text: S

text: AV

text: S

text: where

text: σ

text: is

text: the

text: image

text: of

text: σ

text: under

text: the

text: projection

text: map

text: from

text: AV

text: to

text: AS,

text: and

text: µ

text: S

text: S,η

text: is

text: deﬁned

text: as

text: µ

text: (ξ)

text: exp

text: Φ(ξ

text: Φ((ξ

text: η)

text: ξ

text: AS.

text: S,η

text: F

text: F

text: ∈F

text: ∈F

text: F

text: ,F

text: S

text: F∅

text: F

text: S=

text: ,F

text: Sc=

text: In

text: the

text: last

text: formula,

text: ξ

text: η

text: is

text: the

text: element

text: in

text: AV

text: which

text: equals

text: ξ

text: when

text: restricted

text: to

text: S

text: and

text: equals

text: η

text: when

text: restricted

text: to

text: Sc.

text: The

text: expression

text: in

text: makes

text: sense

text: because

text: we

text: only

text: consider

text: η

text: Ω

text: ASc,

text: where

text: Ω

text: is

text: the

text: projection

text: of

text: Ω

text: onto

text: ASc.

text: The

text: Sc

text: Sc

text: quantity

text: (ξ

text: η)

text: is

text: the

text: restriction

text: of

text: ξ

text: η

text: to

text: F.

text: Since

text: η

text: Ω

text: there

text: exists

text: at

text: least

text: F

text: Sc

text: one

text: ξ

text: AS

text: for

text: which

text: the

text: sum

text: inside

text: the

text: exponential

text: in

text: is

text: ﬁnite.

text: ##LTLine##


text: 4 TIM AUSTIN AND MOUMANTI PODDER notion of soﬁc entropy for actions of free groups, but we believe it does not agree with soﬁc entropy in such generality.) Our main result shows that percolative entropy is always an upper bound for the growth rate of the ﬁnitary Shannon entropies, and that they are equal in case the model exhibits strong spatial mixing (recalled in Deﬁnition 1.2 below). ∈ N Theorem 1.1. Let µ denote the Gibbs measure on G derived from Φ for n , −−→∗ n n lw and assume µ µ. Then n 1 ≤ lim sup | |H(µ ) H . (1.6) →∞ V n perc n n If, moreover, Φ exhibits strong spatial mixing, then 1 lim | |H(µ ) = H . (1.7) n→∞ Vn n perc Several diﬀerent deﬁnitions of strong spatial mixing already appear in the liter- ature. Most works deﬁne it only for one or another speciﬁc model. In order to use the thermodynamic formalism, we give a deﬁnition for general interactions. Consider again a graph G = (V, E) and a ﬁnite set A. Let Φ be an interaction { ∈ } → R over V . Another collection of functions Ψ = Ψ : v V , where Ψ : A , is v v called a self-interaction (or, in some settings, an external ﬁeld): it may be identiﬁed with an interaction with the special property that it is nonzero only for singleton subsets of V . Here we allow (cid:40)Ψ to take only ﬁnite values. By Φ + Ψ we mean the interaction deﬁned by { } ∈ Φ(ξ ) + Ψ(ξ ) if S = v , for v V, (Φ + Ψ)(ξ ) = v v | | S Φ(ξ ) if S > 1, S ∈ F for S , where we abuse notation slightly by writing ξ{ } as ξ . Let T (r) denote v v d the closed ball of radius r about the root in the graph T , and let T (r)c denote its d d complement in V (T ). d Deﬁnition 1.2. A translation-invariant interaction Φ on T exhibits strong spatial d mixing if the (cid:12)following condition is satisﬁed: (cid:12) (cid:12) (cid:12) − → → ∞ max µ (σ = a) µ (σ = a) 0 as r (1.8) η,τ∈ΩTd(r)c Φ+Ψ,Td(r),η φ Φ+Ψ,Td(r),τ φ ∈ for every a A, uniformly in Ψ. Here µ (similarly µ ) is the Φ+Ψ,Td(r),η Φ+Ψ,Td(r),τ conditional Gibbs measure corresponding to the interaction Φ + Ψ with boundary conditions η (correspondingly τ), as deﬁned in (1.4). We consider η and τ only in Ω so that the conditional Gibbs measures in Td(r)c (1.8) are well deﬁned. Several well-known models exhibit strong spatial mixing. These include the Ising and Potts models at suﬃciently high temperatures. Other examples are independent-set and various colouring models, again in their uniqueness regimes. Some of these examples are discussed in more detail in Section . ##LTLine## ##LTLine##

text: TIM

text: AUSTIN

text: AND

text: MOUMANTI

text: PODDER

text: notion

text: of

text: soﬁc

text: entropy

text: for

text: actions

text: of

text: free

text: groups,

text: but

text: we

text: believe

text: it

text: does

text: not

text: agree

text: with

text: soﬁc

text: entropy

text: in

text: such

text: generality.)

text: Our

text: main

text: result

text: shows

text: that

text: percolative

text: entropy

text: is

text: always

text: an

text: upper

text: bound

text: for

text: the

text: growth

text: rate

text: of

text: the

text: ﬁnitary

text: Shannon

text: entropies,

text: and

text: that

text: they

text: are

text: equal

text: in

text: case

text: the

text: model

text: exhibits

text: strong

text: spatial

text: mixing

text: (recalled

text: in

text: Deﬁnition

text: below).

text: N

text: Theorem

text: Let

text: µ

text: denote

text: the

text: Gibbs

text: measure

text: on

text: G

text: derived

text: from

text: Φ

text: for

text: n

text: n

text: n

text: lw

text: and

text: assume

text: µ

text: µ.

text: Then

text: n

text: lim

text: sup

text: |H(µ

text: H

text: V

text: n

text: perc

text: n

text: n

text: If,

text: moreover,

text: Φ

text: exhibits

text: strong

text: spatial

text: mixing,

text: then

text: lim

text: |H(µ

text: H

text: n→∞

text: Vn

text: n

text: perc

text: Several

text: diﬀerent

text: deﬁnitions

text: of

text: strong

text: spatial

text: mixing

text: already

text: appear

text: in

text: the

text: liter-

text: ature.

text: Most

text: works

text: deﬁne

text: it

text: only

text: for

text: one

text: or

text: another

text: speciﬁc

text: model.

text: In

text: order

text: to

text: use

text: the

text: thermodynamic

text: formalism,

text: we

text: give

text: a

text: deﬁnition

text: for

text: general

text: interactions.

text: Consider

text: again

text: a

text: graph

text: G

text: (V,

text: E)

text: and

text: a

text: ﬁnite

text: set

text: A.

text: Let

text: Φ

text: be

text: an

text: interaction

text: R

text: over

text: V

text: Another

text: collection

text: of

text: functions

text: Ψ

text: Ψ

text: v

text: V

text: where

text: Ψ

text: A

text: is

text: v

text: v

text: called

text: a

text: self-interaction

text: (or,

text: in

text: some

text: settings,

text: an

text: external

text: ﬁeld):

text: it

text: may

text: be

text: identiﬁed

text: with

text: an

text: interaction

text: with

text: the

text: special

text: property

text: that

text: it

text: is

text: nonzero

text: only

text: for

text: singleton

text: subsets

text: of

text: V

text: Here

text: we

text: allow

text: to

text: take

text: only

text: ﬁnite

text: values.

text: By

text: Φ

text: Ψ

text: we

text: mean

text: the

text: interaction

text: deﬁned

text: by

text: Φ(ξ

text: Ψ(ξ

text: if

text: S

text: v

text: for

text: v

text: V,

text: (Φ

text: Ψ)(ξ

text: v

text: v

text: S

text: Φ(ξ

text: if

text: S

text: S

text: F

text: for

text: S

text: where

text: we

text: abuse

text: notation

text: slightly

text: by

text: writing

text: ξ{

text: as

text: ξ

text: Let

text: T

text: (r)

text: denote

text: v

text: v

text: d

text: the

text: closed

text: ball

text: of

text: radius

text: r

text: about

text: the

text: root

text: in

text: the

text: graph

text: T

text: and

text: let

text: T

text: (r)c

text: denote

text: its

text: d

text: d

text: complement

text: in

text: V

text: (T

text: d

text: Deﬁnition

text: A

text: translation-invariant

text: interaction

text: Φ

text: on

text: T

text: exhibits

text: strong

text: spatial

text: d

text: mixing

text: if

text: the

text: condition

text: is

text: satisﬁed:

text: max

text: µ

text: (σ

text: a)

text: µ

text: (σ

text: a)

text: as

text: r

text: η,τ∈ΩTd(r)c

text: Φ+Ψ,Td(r),η

text: φ

text: Φ+Ψ,Td(r),τ

text: φ

text: for

text: every

text: a

text: A,

text: uniformly

text: in

text: Ψ.

text: Here

text: µ

text: (similarly

text: µ

text: is

text: the

text: Φ+Ψ,Td(r),η

text: Φ+Ψ,Td(r),τ

text: conditional

text: Gibbs

text: measure

text: corresponding

text: to

text: the

text: interaction

text: Φ

text: Ψ

text: with

text: boundary

text: conditions

text: η

text: (correspondingly

text: τ),

text: as

text: deﬁned

text: in

text: We

text: consider

text: η

text: and

text: τ

text: only

text: in

text: Ω

text: so

text: that

text: the

text: conditional

text: Gibbs

text: measures

text: in

text: Td(r)c

text: are

text: well

text: deﬁned.

text: Several

text: well-known

text: models

text: exhibit

text: strong

text: spatial

text: mixing.

text: These

text: include

text: the

text: Ising

text: and

text: Potts

text: models

text: at

text: suﬃciently

text: high

text: temperatures.

text: Other

text: examples

text: are

text: independent-set

text: and

text: various

text: colouring

text: models,

text: again

text: in

text: their

text: uniqueness

text: regimes.

text: Some

text: of

text: these

text: examples

text: are

text: discussed

text: in

text: more

text: detail

text: in

text: Section

text: ##LTLine##

text: ##LTLine##


text: PERCOLATIVE ENTROPY OVER INFINITE REGULAR TREES 9 (cid:34) (cid:35) (cid:88) (cid:0) (cid:1) 1 1 n |{ } |V |H(µn) =|V |E(cid:88)X1,...,Xn (cid:2)Hµn (cid:0)σvi σvj : Xj < Xi (cid:1)(cid:3) n n i=1 1 n |{ } =|V | (cid:88) EX1,(cid:2)...,Xn Hµn σvi σvj :(cid:2)Xj <(cid:0)Xi (cid:1)(cid:3)(cid:3) n i=1 1 n |{ } =|V | EXi EX1,...Xi−1,Xi+1,...Xn Hµn σvi σvj : Xj < Xi . n i=1 (3.2) Beware that the summation from 1 to n in (3.2) is in the ﬁxed order of v , . . . , 1 v , not the order speciﬁed by the values X . n i Let us write θ for the law of a random subset of any given ground set which p contains each vertex independently with probability p. The particular ground set in question will always be speciﬁed separately. When we condition on X = p, the { } { } \ i set v : X < X = v : X < p has the same distribution as S v when S is j j i j j i drawn from θp with ground set V(cid:88)n. H(cid:90) en(cid:90)ce (3.2) lea(cid:0)ds to: (cid:1) 1 (cid:90)1 (cid:90) n 1 | |V |H(µn) =|V | (cid:2)⊆ H(cid:0)µn σvi (cid:1)σ(cid:3)S\vi dθpdp n n i=1 0 S Vn 1 | = E H σ σ \ dθ dp, (3.3) ⊆ I µn I S I p 0 S Vn where I is a random vertex with distribution U . ∈ N n Now let r be arbitrary. By the data-processing inequality, we have | ≤ | H (σ σ \ ) H (σ σ ∩ \ ). (3.4) µn I S I µn I (S B(I,r)) I (cid:90) (cid:90) Substituting into (3.3) this gives (cid:2) (cid:0) (cid:1)(cid:3) 1 ≤ (cid:90) 1 (cid:34)(cid:90) | (cid:35) | |H(µ ) E H σ σ ∩ \ dθ dp V n ⊆ I µn I (S B(I,r)) I p n 0 S Vn 1 | = E H (σ σ ) dθ dp. (3.5) (cid:101) I ⊆ \ µn I S p 0 S B(I,r) I ∼ Let V (r) be the subset of vertices v of G (cid:101)such that B(v, r) = T (r). As described n n d in Section , if this isomorphism exists, it may be chosen uniquely so as to respect the ∈ colours and directions of the edges. If v V (r), then we may use that isomorphism n (cid:90) (cid:90) to write | (cid:16) (cid:17) | ⊆ \ Hµn(σv σS)dθp = ⊆ \ H(Πγvn(cid:101),r)∗µn(σφ σS)dθp. (3.6) S B(v,r) v S Td(r) φ − Since G converges locally to T , we have U V (r) = 1 o(1). We may n d n n therefore substitute (3.6) into (3.5) to obtain ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: PERCOLATIVE

text: ENTROPY

text: OVER

text: INFINITE

text: REGULAR

text: TREES

text: n

text: |V

text: |H(µn)

text: =|V

text: σvj

text: Xj

text: Xi

text: n

text: n

text: n

text: =|V

text: Hµn

text: σvi

text: σvj

text: n

text: n

text: =|V

text: EXi

text: Hµn

text: σvi

text: σvj

text: Xj

text: Xi

text: n

text: Beware

text: that

text: the

text: summation

text: from

text: to

text: n

text: in

text: is

text: in

text: the

text: ﬁxed

text: order

text: of

text: v

text: v

text: not

text: the

text: order

text: speciﬁed

text: by

text: the

text: values

text: X

text: n

text: i

text: Let

text: us

text: write

text: θ

text: for

text: the

text: law

text: of

text: a

text: random

text: subset

text: of

text: any

text: given

text: ground

text: set

text: which

text: p

text: contains

text: each

text: vertex

text: independently

text: with

text: probability

text: p.

text: The

text: particular

text: ground

text: set

text: in

text: question

text: will

text: always

text: be

text: speciﬁed

text: separately.

text: When

text: we

text: condition

text: on

text: X

text: p,

text: the

text: i

text: set

text: v

text: X

text: X

text: v

text: X

text: p

text: has

text: the

text: same

text: distribution

text: as

text: S

text: v

text: when

text: S

text: is

text: j

text: j

text: i

text: j

text: j

text: i

text: drawn

text: from

text: θp

text: with

text: ground

text: set

text: to:

text: n

text: |V

text: |H(µn)

text: =|V

text: σvi

text: dθpdp

text: n

text: n

text: S

text: Vn

text: E

text: H

text: σ

text: σ

text: dθ

text: dp,

text: I

text: µn

text: I

text: S

text: I

text: p

text: S

text: Vn

text: where

text: I

text: is

text: a

text: random

text: vertex

text: with

text: distribution

text: U

text: N

text: n

text: Now

text: let

text: r

text: be

text: arbitrary.

text: By

text: the

text: data-processing

text: inequality,

text: we

text: have

text: H

text: (σ

text: σ

text: H

text: (σ

text: σ

text: µn

text: I

text: S

text: I

text: µn

text: I

text: (S

text: B(I,r))

text: I

text: Substituting

text: into

text: this

text: gives

text: |H(µ

text: E

text: H

text: σ

text: σ

text: dθ

text: dp

text: V

text: n

text: I

text: µn

text: I

text: (S

text: B(I,r))

text: I

text: p

text: n

text: S

text: Vn

text: E

text: H

text: (σ

text: σ

text: dθ

text: dp.

text: I

text: µn

text: I

text: S

text: p

text: S

text: B(I,r)

text: I

text: Let

text: V

text: (r)

text: be

text: the

text: subset

text: of

text: vertices

text: v

text: of

text: G

text: that

text: B(v,

text: r)

text: T

text: (r).

text: As

text: described

text: n

text: n

text: d

text: in

text: Section

text: if

text: this

text: isomorphism

text: exists,

text: it

text: may

text: be

text: chosen

text: uniquely

text: so

text: as

text: to

text: respect

text: the

text: colours

text: and

text: directions

text: of

text: the

text: edges.

text: If

text: v

text: V

text: (r),

text: then

text: we

text: may

text: use

text: that

text: isomorphism

text: n

text: to

text: write

text: Hµn(σv

text: σS)dθp

text: σS)dθp.

text: S

text: B(v,r)

text: v

text: S

text: Td(r)

text: φ

text: Since

text: G

text: converges

text: locally

text: to

text: T

text: we

text: have

text: U

text: V

text: (r)

text: We

text: may

text: n

text: d

text: n

text: n

text: therefore

text: substitute

text: into

text: to

text: obtain

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Collaborative Descriptors: Convolutional Maps for Preprocessing Hirokatsu Kataoka, Yutaka Satoh Kaori Abe AIST AIST, Tokyo Denki University { } hirokatsu.kataoka, yu.satou @aist.go.jp abe.keroko@aist.go.jp Akio Nakamura Tokyo Denki University nkmr-a@cck.dendai.ac.jp Abstract The paper presents a novel concept for collaborative descriptors between deeply learned and hand-crafted fea- tures. To achieve this concept, we apply convolutional maps for pre-processing, namely the convovlutional maps Figure 1. The 1st, 2nd and 3rd AI booms and winters: (1st boom) are used as input of hand-crafted features. We recorded perceptron, (1st winter) edge/line detection, (2nd boom) neocog- an increase in the performance rate of +17.06% (multi- nitron, (2nd winter) HOG/SIFT/BoF/SVM, (3rd boom [now]) class object recognition) and +24.71% (car detection) from deep learning. Here we anticipate a next framework after 3rd AI. grayscale input to convolutional maps. Although the frame- work is straight-forward, the concept should be inherited for an improved representation. rectly access the convolutional maps in order to improve the performance rate of hand-crafted features. We try to evaluate several hand-crafted features such as scale invari- 1. Introduction ant feature transform (SIFT) and bag-of-words (BoW) [2] (object recognition) and higher-order local autocorrelation Neural networks computationally mirror the architecture (HLAC) [4] (car detection). Then, the recognition rates for of the human brain. Recent architectures have been made all hand-crafted features are compared using convolutional deeper in order to provide higher-level representations of maps and grayscale images that have the same settings for object. Especially in computer vision, deep convolutional the image description. neural networks (DCNN) are becoming increasingly widely 2. Convolutional maps for preprocessing used for image recognition and object detection. Represen- tative deep models such as VGGNet [5] have been proposed Here, we introduce a framework for combining convolu- in the ﬁeld of computer vision. tional maps and hand-crafted features. Figure 2 shows the The use of neural net and hand-crafted feature is repeated process for using convolutional maps as a preprocessor. We in the computer vision ﬁeld (see Figure 1). The sugges- employ hand-crafted features, namely SIFT+BoW [2] and tive knowledge motivates us to study an advanced hand- HLAC [4]. crafted feature after the DCNN in the recent 3rd AI. We Given a convolutional map M with VGG [5] for kernel k anticipate that the hand-crafted feature should collaborate k, our goal is to extract a feature vector V from the map with deeply learned parameters since an outstanding per- and deﬁne a classiﬁcation label L as a function of SVM, formance is achieved with the automatic feature learning. L = f (V ). We use VGGNet to create convolutional svm In the paper, we present a novel concept for collabora- maps. tive descriptors which jointly work both DCNN and hand- The 2nd max-pooling layer is used as a convolutional × × crafted feature. We apply convolutional maps for pre- map that contains the 56 56 128 feature map. We can × processing as a ﬁrst implementation. The framework is handle 128 maps with dimensions of 56 56 [pixel]. The simple, but it is effective for recognition tasks. We di- patch and kernel sizes are suitable for balanced feature ex- 1 ##LTFigure## ##LTFigure##

text: Collaborative

label: title

text: Descriptors:

text: Convolutional

text: Maps

text: for

text: Preprocessing

text: Hirokatsu

label: author

text: Kataoka,

text: Yutaka

text: Satoh

text: Kaori

text: Abe

text: AIST

text: AIST,

text: Tokyo

text: Denki

text: University

text: hirokatsu.kataoka,

font: AFIBTF+NimbusMonL-Regu

text: yu.satou

text: @aist.go.jp

text: abe.keroko@aist.go.jp

text: Akio

text: Nakamura

text: Tokyo

text: Denki

text: University

text: nkmr-a@cck.dendai.ac.jp

text: Abstract

text: The

label: abstract

text: paper

text: presents

text: a

text: novel

text: concept

text: for

text: collaborative

text: descriptors

text: between

text: deeply

text: learned

text: and

text: hand-crafted

text: fea-

text: tures.

text: To

text: achieve

text: this

text: concept,

text: we

text: apply

text: convolutional

text: maps

text: for

text: pre-processing,

text: namely

text: the

text: convovlutional

text: maps

text: Figure

text: The

label: caption

text: and

text: AI

text: booms

text: and

text: winters:

text: boom)

text: are

text: used

text: as

text: input

text: of

text: hand-crafted

text: features.

text: We

text: recorded

text: perceptron,

text: winter)

text: edge/line

text: detection,

text: boom)

text: neocog-

text: an

text: increase

text: in

text: the

text: performance

text: rate

text: of

text: (multi-

text: nitron,

text: winter)

text: HOG/SIFT/BoF/SVM,

text: boom

text: [now])

text: class

text: object

text: recognition)

text: and

text: (car

text: detection)

text: from

text: deep

text: learning.

text: Here

text: we

text: anticipate

text: a

text: next

text: framework

text: after

text: AI.

text: grayscale

text: input

text: to

text: convolutional

text: maps.

text: Although

text: the

text: frame-

text: work

text: is

text: straight-forward,

text: the

text: concept

text: should

text: be

text: inherited

text: for

text: an

text: improved

text: representation.

text: rectly

text: access

text: the

text: convolutional

text: maps

text: in

text: order

text: to

text: improve

text: the

text: performance

text: rate

text: of

text: hand-crafted

text: features.

text: We

text: try

text: to

text: evaluate

text: several

text: hand-crafted

text: features

text: such

text: as

text: scale

text: invari-

text: Introduction

text: ant

text: feature

text: transform

text: (SIFT)

text: and

text: bag-of-words

text: (BoW)

text: (object

text: recognition)

text: and

text: higher-order

text: local

text: autocorrelation

text: Neural

text: networks

text: computationally

text: mirror

text: the

text: architecture

text: (HLAC)

text: (car

text: detection).

text: Then,

text: the

text: recognition

text: rates

text: for

text: of

text: the

text: human

text: brain.

text: Recent

text: architectures

text: have

text: been

text: made

text: all

text: hand-crafted

text: features

text: are

text: compared

text: using

text: convolutional

text: deeper

text: in

text: order

text: to

text: provide

text: higher-level

text: representations

text: of

text: maps

text: and

text: grayscale

text: images

text: that

text: have

text: the

text: same

text: settings

text: for

text: object.

text: Especially

text: in

text: computer

text: vision,

text: deep

text: convolutional

text: the

text: image

text: description.

text: neural

text: networks

text: (DCNN)

text: are

text: becoming

text: increasingly

text: widely

text: Convolutional

text: maps

text: for

text: preprocessing

text: used

text: for

text: image

text: recognition

text: and

text: object

text: detection.

text: Represen-

text: tative

text: deep

text: models

text: such

text: as

text: VGGNet

text: have

text: been

text: proposed

text: Here,

text: we

text: introduce

text: a

text: framework

text: for

text: combining

text: convolu-

text: in

text: the

text: ﬁeld

text: of

text: computer

text: vision.

text: tional

text: maps

text: and

text: hand-crafted

text: features.

text: Figure

text: shows

text: the

text: The

text: use

text: of

text: neural

text: net

text: and

text: hand-crafted

text: feature

text: is

text: repeated

text: process

text: for

text: using

text: convolutional

text: maps

text: as

text: a

text: preprocessor.

text: We

text: in

text: the

text: computer

text: vision

text: ﬁeld

text: (see

text: Figure

text: The

text: sugges-

text: employ

text: hand-crafted

text: features,

text: namely

text: SIFT+BoW

text: and

text: tive

text: knowledge

text: motivates

text: us

text: to

text: study

text: an

text: advanced

text: hand-

text: HLAC

text: crafted

text: feature

text: after

text: the

text: DCNN

text: in

text: the

text: recent

text: AI.

text: We

text: Given

text: a

text: convolutional

text: map

text: M

text: with

text: VGG

text: for

text: kernel

text: k

text: anticipate

text: that

text: the

text: hand-crafted

text: feature

text: should

text: collaborate

text: k,

text: our

text: goal

text: is

text: to

text: extract

text: a

text: feature

text: vector

text: V

text: from

text: the

text: map

text: with

text: deeply

text: learned

text: parameters

text: since

text: an

text: outstanding

text: per-

text: and

text: deﬁne

text: a

text: classiﬁcation

text: label

text: L

text: as

text: a

text: function

text: of

text: SVM,

text: formance

text: is

text: achieved

text: with

text: the

text: automatic

text: feature

text: learning.

text: L

text: f

text: (V

text: We

text: use

text: VGGNet

text: to

text: create

text: convolutional

text: svm

text: In

text: the

text: paper,

text: we

text: present

text: a

text: novel

text: concept

text: for

text: collabora-

text: maps.

text: tive

text: descriptors

text: which

text: jointly

text: work

text: both

text: DCNN

text: and

text: hand-

text: The

text: max-pooling

text: layer

text: is

text: used

text: as

text: a

text: convolutional

text: crafted

text: feature.

text: We

text: apply

text: convolutional

text: maps

text: for

text: pre-

text: map

text: that

text: contains

text: the

text: feature

text: map.

text: We

text: can

text: processing

text: as

text: a

text: ﬁrst

text: implementation.

text: The

text: framework

text: is

text: handle

text: maps

text: with

text: dimensions

text: of

text: [pixel].

text: The

text: simple,

text: but

text: it

text: is

text: effective

text: for

text: recognition

text: tasks.

text: We

text: di-

text: patch

text: and

text: kernel

text: sizes

text: are

text: suitable

text: for

text: balanced

text: feature

text: ex-

text: ##LTFigure##

text: ##LTFigure##


text: 2 ANDREW DOUGLAS AND JOE REPKA List of Tables 1 One-dimensional (solvable) subalgebras of C 8 2 2 Two-dimensional (solvable) subalgebras of C 9 2 3 Three-dimensional solvable subalgebras of C 10 2 4 Four-dimensional solvable subalgebras of C 11 2 5 Five- and six-dimensional solvable subalgebras of C 12 2 6 Semisimple and Levi decomposable subalgebras of C 13 2 7 One- and two-dimensional (solvable) subalgebras of A 16 2 8 Three-, four-, and ﬁve-dimensional solvable subalgebras of A 17 2 9 Semisimple and Levi decomposable subalgebras of A 18 2 × 10 Solvable subalgebras of A A 21 1 1 × 11 Semisimple and Levi decomposable subalgebras of A A 22 1 1 12 One-dimensional (solvable) subalgebras of G 25 2 13 Two-dimensional (solvable) subalgebras of G 26 2 14 Regular three-dimensional solvable subalgebras of G 27 2 15 Non-regular three-dimensional solvable subalgebras of G 28 2 16 Regular four-dimensional solvable subalgebras of G 29 2 17 Non-regular four-dimensional solvable subalgebras of G 30 2 18 Five-dimensional solvable subalgebras of G 31 2 19 Six-dimensional solvable subalgebras of G 32 2 20 Seven- and eight-dimensional solvable subalgebras of G 33 2 21 Semisimple subalgebras of G 33 2 22 Levi decomposable subalgebras of G 34 2 1. Introduction In this expository article, we describe the classiﬁcation of the subal- gebras of the rank 2 semisimple Lie algebras. Speciﬁcally, we describe the subalgebras of the symplectic algebra C , the special linear algebra 2 × A , the semisimple–and not simple–Lie algebra A A , and the excep- 2 1 1 tional Lie algebra G . The classiﬁcation is up to inner automorphism, 2 and the ground ﬁeld is the complex numbers. We omit virtually all proofs in this article, as they may be found in the literature, which we cite. But, we do outline techniques, strategy, and theory employed in proofs for one case–the subalgebras of C . 2

text: ANDREW

text: DOUGLAS

text: AND

text: JOE

text: REPKA

text: List

text: of

text: Tables

text: One-dimensional

text: (solvable)

text: subalgebras

text: of

text: C

text: Two-dimensional

text: (solvable)

text: subalgebras

text: of

text: C

text: Three-dimensional

text: solvable

text: subalgebras

text: of

text: C

text: Four-dimensional

text: solvable

text: subalgebras

text: of

text: C

text: Five-

text: and

text: six-dimensional

text: solvable

text: subalgebras

text: of

text: C

text: Semisimple

text: and

text: Levi

text: decomposable

text: subalgebras

text: of

text: C

text: One-

text: and

text: two-dimensional

text: (solvable)

text: subalgebras

text: of

text: A

text: Three-,

text: four-,

text: and

text: ﬁve-dimensional

text: solvable

text: subalgebras

text: of

text: A

text: Semisimple

text: and

text: Levi

text: decomposable

text: subalgebras

text: of

text: A

text: Solvable

text: subalgebras

text: of

text: A

text: A

text: Semisimple

text: and

text: Levi

text: decomposable

text: subalgebras

text: of

text: A

text: A

text: One-dimensional

text: (solvable)

text: subalgebras

text: of

text: G

text: Two-dimensional

text: (solvable)

text: subalgebras

text: of

text: G

text: Regular

text: three-dimensional

text: solvable

text: subalgebras

text: of

text: G

text: Non-regular

text: three-dimensional

text: solvable

text: subalgebras

text: of

text: G

text: Regular

text: four-dimensional

text: solvable

text: subalgebras

text: of

text: G

text: Non-regular

text: four-dimensional

text: solvable

text: subalgebras

text: of

text: G

text: Five-dimensional

text: solvable

text: subalgebras

text: of

text: G

text: Six-dimensional

text: solvable

text: subalgebras

text: of

text: G

text: Seven-

text: and

text: eight-dimensional

text: solvable

text: subalgebras

text: of

text: G

text: Semisimple

text: subalgebras

text: of

text: G

text: Levi

text: decomposable

text: subalgebras

text: of

text: G

text: Introduction

text: In

text: this

text: expository

text: article,

text: we

text: describe

text: the

text: classiﬁcation

text: of

text: the

text: subal-

text: gebras

text: of

text: the

text: rank

text: semisimple

text: Lie

text: algebras.

text: Speciﬁcally,

text: we

text: describe

text: the

text: subalgebras

text: of

text: the

text: symplectic

text: algebra

text: C

text: the

text: special

text: linear

text: algebra

text: A

text: the

text: semisimple–and

text: not

text: simple–Lie

text: algebra

text: A

text: A

text: and

text: the

text: excep-

text: tional

text: Lie

text: algebra

text: G

text: The

text: classiﬁcation

text: is

text: up

text: to

text: inner

text: automorphism,

text: and

text: the

text: ground

text: ﬁeld

text: is

text: the

text: complex

text: numbers.

text: We

text: omit

text: virtually

text: all

text: proofs

text: in

text: this

text: article,

text: as

text: they

text: may

text: be

text: found

text: in

text: the

text: literature,

text: which

text: we

text: cite.

text: But,

text: we

text: do

text: outline

text: techniques,

text: strategy,

text: and

text: theory

text: employed

text: in

text: proofs

text: for

text: one

text: case–the

text: subalgebras

text: of

text: C


text: Representative Conditions Equivalences Isomorphism Class Containing a Cartan Subalgebra (cid:104) (cid:105) ⊕ h, X n s α 1,1 2,1 (cid:104) (cid:105) ⊕ h, X n s β 1,1 2,1 Containing a Regular Semisimple Element but not a Cartan Subalgebra (cid:104) (cid:105) (cid:54) ± − T , X , X a = 0, 1, 3 s √ a,1 α α+β 3,1,A=1+2α−+ 1+4α − 2α where α = 2(a + 1)/(a + 3)2 (cid:104) (cid:105) T− , X , X s − 3,1 α α+β 3,1,A= 1 (cid:104) (cid:105) (cid:54) ± (cid:104) (cid:105) ∼ (cid:104) (cid:105) T , X , X a = 0, 1 T , X , X T − , X , X s √ a,1 α α+2β a,1 α α+2β a 1,1 α α+2β 3,1,A=1+2α−+ 1+4α − 2α where α = a/(a + 1)2 (cid:104) (cid:105) T , X + X , X s 3,1 α β α+2β 3,1,A=1/3 Containing a Non-regular Semisimple Element but not a Cartan Subalgebra (cid:104) (cid:105) ⊕ T , X , X n s 1,0 α α+β 1,1 2,1 (cid:104) (cid:105) ⊕ T , X , X n s 1,0 α α+2β 1,1 2,1 (cid:104) (cid:105) T , X , X s 1,0 α+β α+2β 3,1,A=1/2 (cid:104) (cid:105) ⊕ T − , X , X n s 1, 1 α+β α+2β 1,1 2,1 (cid:104) (cid:105) T − , X , X s − 1, 1 α α+2β 3,1,A= 1 (cid:104) (cid:105) T − , X , X s 1, 1 β α+2β 3,1,A=1 (cid:104) (cid:105) T , X , X s 1,1 α α+2β 3,1,A=1 Containing no Semisimple Elements but not Nilpotent (cid:104) (cid:105) T + X , X , X s 1,1 β α+β α+2β 3,2 (cid:104) (cid:105) T − + X , X , X s − 1, 1 α+β α α+2β 3,1,A= 1 (cid:104) (cid:105) T + X , X , X s 1,0 α α+β α+2β 3,1,A=1/2 Nilpotent (cid:104) (cid:105) X , X , X 3n α α+β α+2β 1,1 (cid:104) (cid:105) X , X , X n β α+β α+2β 3,1 (cid:104) (cid:105) X + X , X , X n α β α+β α+2β 3,1 Table 3. Three-dimensional solvable subalgebras of C 2 SUBALGEBRAS OF SEMISIMPLE LIE ALGEBRAS 11 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Representative

label: table

text: Conditions

text: Equivalences

text: Isomorphism

text: Class

text: Containing

text: a

text: Cartan

text: Subalgebra

text: h,

text: X

text: n

text: s

text: α

text: h,

text: X

text: n

text: s

text: β

text: Containing

text: a

text: Regular

text: Semisimple

text: Element

text: but

text: not

text: a

text: Cartan

text: Subalgebra

font: default

text: T

text: X

text: X

text: a

text: s

text: α

text: α+β

text: 2α

text: where

text: α

text: T−

text: X

text: X

text: s

text: α

text: α+β

text: T

text: X

text: X

text: a

text: T

text: X

text: X

text: T

text: X

text: X

text: s

text: α

text: α+2β

text: α

text: α+2β

text: a

text: α

text: α+2β

text: 2α

text: where

text: α

text: a/(a

text: T

text: X

text: X

text: X

text: s

text: α

text: β

text: α+2β

text: Containing

text: a

text: Non-regular

text: Semisimple

text: Element

text: but

text: not

text: a

text: Cartan

text: Subalgebra

text: T

text: X

text: X

text: n

text: s

text: α

text: α+β

text: T

text: X

text: X

text: n

text: s

text: α

text: α+2β

text: T

text: X

text: X

text: s

text: α+β

text: α+2β

text: T

text: X

text: X

text: n

text: s

text: α+β

text: α+2β

text: T

text: X

text: X

text: s

text: α

text: α+2β

text: T

text: X

text: X

text: s

text: β

text: α+2β

text: T

text: X

text: X

text: s

text: α

text: α+2β

text: Containing

text: no

text: Semisimple

text: Elements

text: but

text: not

text: Nilpotent

text: T

text: X

text: X

text: X

text: s

text: β

text: α+β

text: α+2β

text: T

text: X

text: X

text: X

text: s

text: α+β

text: α

text: α+2β

text: T

text: X

text: X

text: X

text: s

text: α

text: α+β

text: α+2β

text: Nilpotent

text: X

text: X

text: X

text: α

text: α+β

text: α+2β

text: X

text: X

text: X

text: n

text: β

text: α+β

text: α+2β

text: X

text: X

text: X

text: X

text: n

text: α

text: β

text: α+β

text: α+2β

text: Table

text: Three-dimensional

text: solvable

text: subalgebras

text: of

text: C

text: SUBALGEBRAS

text: OF

text: SEMISIMPLE

text: LIE

text: ALGEBRAS

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 16 ANDREW DOUGLAS AND JOE REPKA               1 0 0   0 0 0      − Hα = 0 1 0 , Hβ = 0 1 0 , − 0 0 0 0 0 1                  0 1 0   0 0 0      Xα = 0 0 0 , Yα = 1 0 0 , 0 0 0 0 0 0     (14)              0 0 0   0 0 0      Xβ = 0 0 1 , Yβ = 0 0 0 , 0 0 0 0 1 0              −     0 0 1   0 0 0      Xα+β = 0 0 0 , Yα+β = 0 0 0 . − 0 0 0 1 0 0 H and H are the coroots; X , X , and X are the positive root α β α β α+β vectors; and Y , Y , and Y are the negative root vectors. α β α+β We highlight three distinguished subalgebras: A Cartan subalgebra (cid:104) (cid:105) (cid:104) (cid:105) h = H , H ; a Borel subalgebra b = H , H , X , X , X ; and the α β (cid:104) α β α (cid:105)β α+β nilradical of the Borel subalgebra n = X , X , X . α β α+β The Lie group corresponding to A , under its identiﬁcation with C 2 C × sl(3, ), is the special linear group SL(3, ). It is the Lie group of 3 3 matrices with complex entries and determinant 1. The classiﬁcation and identiﬁcation of the subalgebras of A are de- 2 scribed in the following tables. The classiﬁcation is from [DR16b], and the identiﬁcation was established as part of the present article. The classiﬁcation is organized by dimension. Tables 7-8 contain the classiﬁcation and identiﬁcation of the solvable subalgebras, and Table

text: ANDREW

text: DOUGLAS

text: AND

text: JOE

text: REPKA

text: Hα

text: Hβ

text: Xα

text: Yα

text: Xβ

text: Yβ

text: Xα+β

text: Yα+β

text: H

text: and

text: H

text: are

text: the

text: coroots;

text: X

text: X

text: and

text: X

text: are

text: the

text: positive

text: root

text: α

text: β

text: α

text: β

text: α+β

text: vectors;

text: and

text: Y

text: Y

text: and

text: Y

text: are

text: the

text: negative

text: root

text: vectors.

text: α

text: β

text: α+β

text: We

text: highlight

text: three

text: distinguished

text: subalgebras:

text: A

text: Cartan

text: subalgebra

text: h

text: H

text: H

text: a

text: Borel

text: subalgebra

text: b

text: H

text: H

text: X

text: X

text: X

text: and

text: the

text: α

text: β

text: α

text: β

text: α

text: α+β

text: nilradical

text: of

text: the

text: Borel

text: subalgebra

text: n

text: X

text: X

text: X

text: α

text: β

text: α+β

text: The

text: Lie

text: group

text: corresponding

text: to

text: A

text: under

text: its

text: identiﬁcation

text: with

text: C

text: C

text: is

text: the

text: special

text: linear

text: group

text: It

text: is

text: the

text: Lie

text: group

text: of

text: matrices

text: with

text: complex

text: entries

text: and

text: determinant

text: The

text: classiﬁcation

text: and

text: identiﬁcation

text: of

text: the

text: subalgebras

text: of

text: A

text: are

text: de-

text: scribed

text: in

text: the

text: following

text: tables.

text: The

text: classiﬁcation

text: is

text: from

text: and

text: the

text: identiﬁcation

text: was

text: established

text: as

text: part

text: of

text: the

text: present

text: article.

text: The

text: classiﬁcation

text: is

text: organized

text: by

text: dimension.

text: Tables

text: contain

text: the

text: classiﬁcation

text: and

text: identiﬁcation

text: of

text: the

text: solvable

text: subalgebras,

text: and

text: Table


text: 20 ANDREW DOUGLAS AND JOE REPKA × 4. The subalgebras of A A 1 1 × The semisimple, and not simple, Lie algebra A A may be realized C ×1 1 as the special orthogonal algebra so(4, ) of 4 4 complex matrices − satisfying Xt = X. It is isomorphic to the semisimple Lie algebra C ⊕ C C sl(2, ) sl(2, ), where sl(2, ) is the special linear algebra of traceless × 2 2 matrices with complex entries. The root system associated with × A A is depicted in Figure 3. 1 1 × Figure 3. The root system of A A 1 1 C ⊕ It has positive roots α and β. Under the identiﬁcation with sl(2, ) C × sl(2, ), A A has a Chevalley basis 1 1 { } (15) H , H , X , X , Y , Y , α β α β α β where ##LTFigure##

text: ANDREW

text: DOUGLAS

text: AND

text: JOE

text: REPKA

label: section

text: The

text: subalgebras

text: of

text: A

text: A

text: The

text: semisimple,

text: and

text: not

text: simple,

text: Lie

text: algebra

text: A

text: A

text: may

text: be

text: realized

text: C

text: ×1

text: as

text: the

text: special

text: orthogonal

text: algebra

text: of

text: complex

text: matrices

text: satisfying

text: Xt

text: X.

text: It

text: is

text: isomorphic

text: to

text: the

text: semisimple

text: Lie

text: algebra

text: C

text: C

text: C

text: where

text: is

text: the

text: special

text: linear

text: algebra

text: of

text: traceless

text: matrices

text: with

text: complex

text: entries.

text: The

text: root

text: system

text: associated

text: with

text: A

text: A

text: is

text: depicted

text: in

text: Figure

text: Figure

text: The

text: root

text: system

text: of

text: A

text: A

text: C

text: It

text: has

text: positive

text: roots

text: α

text: and

text: β.

text: Under

text: the

text: identiﬁcation

text: with

text: C

text: A

text: A

text: has

text: a

text: Chevalley

text: basis

text: H

text: H

text: X

text: X

text: Y

text: Y

text: α

text: β

text: α

text: β

text: α

text: β

text: where

text: ##LTFigure##


text: 36 ANDREW DOUGLAS AND JOE REPKA Acknowledgements The work of A.D. is partially supported by a research grant from the Professional Staﬀ Congress/City University of New York (Grant No. TRADA-47-36). The work of J.R. is partially supported by the Natural Sciences and Engineering Research Council (Grant No. 3166-09). We also greatly thank Matthew Wu who checked our computations in the G case. 2 References [Bia98] Bianchi, L.,“Sugli spazii a tre dimensioni che ammettono un grouppo con- tinuo di movimenti,” Soc. Ital. Sci. Mem. di Mat. 11 (1898), 267-352. [CS09] Campamor-Strusberg, R.: Structural data and invariants of nine- dimensional real Lie algebras with nontrivial Levi decomposition. Nova Science Publishers Inc., New York, 2009. [Car33] Cartan, E´.: Sur la structure des groupes des transformations ﬁnis et con- tinus, 2nd ed., (Vuibert, Paris, 1933). [CM93] Collingwood, D.H. and McGovern, W.M.: Nilpotent orbits in semisimple Lie algebras (Van Nostrand Reinhold, New York, 1983). [DKLW86] David, D., Kamran, N., Levi, D., and Winternitz ,P., “Symmetry re- duction for the Kadomtsev-Petviashvili equation using a loop algebra,” J. Math. Phys. 27 1225, (1986). [dGr05] de Graaf, W.A. “Classiﬁcation of solvable Lie algebras,” Experiment. Math. Volume 14, Issue 1, 15-25 (2005). [dGr09] de Graaf, W.A.: SLA-computing with Simple Lie algebras. a GAP package, (2009). http://www.science.unitn.it/degraaf/sla.html [dGr11] de Graaf, W.A., “Constructing semisimple subalgebras of semisimple Lie algebras,” J. Algebra, 325, 416-430 (2011). [ORWZ90] del Olmo, M.A., Rodriguez, M.A., Winternitz, P., and Zassenhaus, H., “Maximal abelian subalgebras of pseudounitary Lie algebras,” Linear Algebra Appl. 135 (1990) 79-151. [DR15] Douglas, A. and Repka, J., “The Levi decomposable subalgebras of C ,” J. 2 Math. Phys., 56 051703, (2015). C [DR16a] Douglas, A. and Repka, J., “The subalgebras of so(4, ),” Comm. Algebra, 44(12), (2016) 5269-5286. [DR16b] Douglas, A. and Repka, J., “A classiﬁcation of the subalgebras of A ,” J. 2 Pure Appl. Algebra, 220(6), (2016) 2389-2413. [DR17] Douglas, A. and Repka, J., “The subalgebras of the rank two symplectic Lie algebra,” Linear Algebra Appl., 527, (2017) 303-348. [Dyn52a] Dynkin, E.B., “Semisimple subalgebras of semisimple Lie algebras,” Mat. Sbornik N.S., 30(72): 349-462 (1952). English translation in: Amer. Math. Soc. Transl. (6), 111-244 (1957). [Dyn52b] Dynkin, E.B., “Maximal subgroups of the classical groups.” Trudy Moskov. Mat. Obˇsˇc., 1:39-166, 1952. English translation in: Amer. Math. Soc. Transl. (6), (1957), 245-378. [GHP84] Grundland, A.M., Harnad, J., and Winternitz, P., “Symmetry reduction for nonlinear relativistically invariant equations,” J. Math. Phys. 25 (1984), no. 4, 786-790.

text: ANDREW

text: DOUGLAS

text: AND

text: JOE

text: REPKA

text: Acknowledgements

text: The

text: work

text: of

text: A.D.

text: is

text: partially

text: supported

text: by

text: a

text: research

text: grant

text: from

text: the

text: Professional

text: Staﬀ

text: Congress/City

text: University

text: of

text: New

text: York

text: (Grant

text: No.

text: The

text: work

text: of

text: J.R.

text: is

text: partially

text: supported

text: by

text: the

text: Natural

text: Sciences

text: and

text: Engineering

text: Research

text: Council

text: (Grant

text: No.

text: We

text: also

text: greatly

text: thank

text: Matthew

text: Wu

text: who

text: checked

text: our

text: computations

text: in

text: the

text: G

text: case.

text: References

text: Bianchi,

text: L.,“Sugli

text: spazii

text: a

text: tre

text: dimensioni

text: che

text: ammettono

text: un

text: grouppo

text: con-

text: tinuo

text: di

text: movimenti,”

text: Soc.

text: Ital.

text: Sci.

text: Mem.

text: di

text: Mat.

text: Campamor-Strusberg,

text: R.:

text: Structural

text: data

text: and

text: invariants

text: of

text: nine-

text: dimensional

text: real

text: Lie

text: algebras

text: with

text: nontrivial

text: Levi

text: decomposition.

text: Nova

text: Science

text: Publishers

text: Inc.,

text: New

text: York,

text: Cartan,

text: E´.:

text: Sur

text: la

text: structure

text: des

text: groupes

text: des

text: transformations

text: ﬁnis

text: et

text: con-

text: tinus,

text: ed.,

text: (Vuibert,

text: Paris,

text: Collingwood,

text: D.H.

text: and

text: McGovern,

text: W.M.:

text: Nilpotent

text: orbits

text: in

text: semisimple

text: Lie

text: algebras

text: (Van

text: Nostrand

text: Reinhold,

text: New

text: York,

text: David,

text: D.,

text: Kamran,

text: N.,

text: Levi,

text: D.,

text: and

text: Winternitz

text: ,P.,

text: “Symmetry

text: re-

text: duction

text: for

text: the

text: Kadomtsev-Petviashvili

text: equation

text: using

text: a

text: loop

text: algebra,”

text: J.

text: Math.

text: Phys.

text: de

text: Graaf,

text: W.A.

text: “Classiﬁcation

text: of

text: solvable

text: Lie

text: algebras,”

text: Experiment.

text: Math.

text: Volume

text: Issue

text: de

text: Graaf,

text: W.A.:

text: SLA-computing

text: with

text: Simple

text: Lie

text: algebras.

text: a

text: GAP

text: package,

text: de

text: Graaf,

text: W.A.,

text: “Constructing

text: semisimple

text: subalgebras

text: of

text: semisimple

text: Lie

text: algebras,”

text: J.

text: Algebra,

text: del

text: Olmo,

text: M.A.,

text: Rodriguez,

text: M.A.,

text: Winternitz,

text: P.,

text: and

text: Zassenhaus,

text: H.,

text: “Maximal

text: abelian

text: subalgebras

text: of

text: pseudounitary

text: Lie

text: algebras,”

text: Linear

text: Algebra

text: Appl.

text: Douglas,

text: A.

text: and

text: Repka,

text: J.,

text: “The

text: Levi

text: decomposable

text: subalgebras

text: of

text: C

text: J.

text: Math.

text: Phys.,

text: C

text: Douglas,

text: A.

text: and

text: Repka,

text: J.,

text: “The

text: subalgebras

text: of

text: Comm.

text: Algebra,

text: Douglas,

text: A.

text: and

text: Repka,

text: J.,

text: “A

text: classiﬁcation

text: of

text: the

text: subalgebras

text: of

text: A

text: J.

text: Pure

text: Appl.

text: Algebra,

text: Douglas,

text: A.

text: and

text: Repka,

text: J.,

text: “The

text: subalgebras

text: of

text: the

text: rank

text: two

text: symplectic

text: Lie

text: algebra,”

text: Linear

text: Algebra

text: Appl.,

text: Dynkin,

text: E.B.,

text: “Semisimple

text: subalgebras

text: of

text: semisimple

text: Lie

text: algebras,”

text: Mat.

text: Sbornik

text: N.S.,

text: English

text: translation

text: in:

text: Amer.

text: Math.

text: Soc.

text: Transl.

text: Dynkin,

text: E.B.,

text: “Maximal

text: subgroups

text: of

text: the

text: classical

text: groups.”

text: Trudy

text: Moskov.

text: Mat.

text: Obˇsˇc.,

text: English

text: translation

text: in:

text: Amer.

text: Math.

text: Soc.

text: Transl.

text: Grundland,

text: A.M.,

text: Harnad,

text: J.,

text: and

text: Winternitz,

text: P.,

text: “Symmetry

text: reduction

text: for

text: nonlinear

text: relativistically

text: invariant

text: equations,”

text: J.

text: Math.

text: Phys.

text: no.


text: NONUNIFORMITY OF P-VALUES 3 R} is a family of distributions in the regular exponential family with disper- ∈ ∞ · · · sion parameter φ (0, ), and θ = (θ , , θ )T = Xβ. As is common in 1 n GLM, the function b(θ) in (1) is implicitly assumed to be twice continuously (cid:48)(cid:48) diﬀerentiable with b (θ) always positive. Popularly used GLMs include the linear regression model, logistic regression model, and Poisson regression model for continuous, binary, and count data of responses, respectively. The key innovation of our paper is the formal justiﬁcation that the conven- tional p-values in nonlinear models of GLMs can become invalid in diverg- ing dimensions and such a breakdown can occur much earlier than in linear models, which spells out a fundamental diﬀerence between linear models and nonlinear models. To begin the journey of p-values in diverging-dimensional GLMs, let us gain some insights into this problem by looking at the speciﬁc case of logistic regression. Recently, [7] established an interesting phase tran- sition phenomenon of perfect hyperplane separation for high-dimensional classiﬁcation with an elegant probabilistic argument. Suppose we are given ∼ ⊗ a random design matrix X N(0, I I ) and arbitrary binary y ’s that n p i are not all the same. The phase transition of perfect hyperplane separation happens at the point p/n = 1/2. With such a separating hyperplane, there ∗ ∈ R ∈ R ∗ exist some β p and t such that xT β > t for all cases y = 1 and ∗ i i xT β < t for all controls y = 0. Let us ﬁt a logistic regression model with an i i − ∗ intercept. It is easy to show that multiplying the vector ( t, (β )T )T by a di- vergence sequence of positive numbers c, we can obtain a sequence of logistic · · · regression ﬁts with the ﬁtted response vector approaching y = (y , , y )T → ∞ 1 n as c . As a consequence, the MLE algorithm can return a pretty wild estimate that is close to inﬁnity in topology when the algorithm is set to stop. Clearly, in such a case the p-value of the MLE is no longer justiﬁed and meaningful. The results in [7] motivate us to characterize the break- ∼ down point of p-values in nonlinear GLMs with p nα0 in the regime of ∈ α [0, 1). 0 It is worth mentioning that our work is diﬀerent in goals from the limited but growing literature on p-values for high-dimensional nonlinear models, and makes novel contributions to such a problem. The key distinction is that existing work has focused primarily on identifying the scenarios in which conventional p-values or their modiﬁcations continue to be valid with some sparsity assumption limiting the growth of intrinsic dimensions. For exam- ple, [11] established the oracle property including the asymptotic normality for nonconcave penalized likelihood estimators in the scenario of p = o(n1/5), while [9] extended their results to the GLM setting of non-polynomial (NP) dimensionality. In the latter work, the p-values were proved to be valid un- der the assumption that the intrinsic dimensionality s = o(n1/3). More re-

text: NONUNIFORMITY

text: OF

text: P-VALUES

text: R}

text: is

text: a

text: family

text: of

text: distributions

text: in

text: the

text: regular

text: exponential

text: family

text: with

text: disper-

text: sion

text: parameter

text: φ

text: and

text: θ

text: (θ

text: θ

text: )T

text: Xβ.

text: As

text: is

text: common

text: in

text: n

text: GLM,

text: the

text: function

text: b(θ)

text: in

text: is

text: implicitly

text: assumed

text: to

text: be

text: twice

text: continuously

text: diﬀerentiable

text: with

text: b

text: (θ)

text: always

text: positive.

text: Popularly

text: used

text: GLMs

text: include

text: the

text: linear

text: regression

text: model,

text: logistic

text: regression

text: model,

text: and

text: Poisson

text: regression

text: model

text: for

text: continuous,

text: binary,

text: and

text: count

text: data

text: of

text: responses,

text: respectively.

text: The

text: key

text: innovation

text: of

text: our

text: paper

text: is

text: the

text: formal

text: justiﬁcation

text: that

text: the

text: conven-

text: tional

text: p-values

text: in

text: nonlinear

text: models

text: of

text: GLMs

text: can

text: become

text: invalid

text: in

text: diverg-

text: ing

text: dimensions

text: and

text: such

text: a

text: breakdown

text: can

text: occur

text: much

text: earlier

text: than

text: in

text: linear

text: models,

text: which

text: spells

text: out

text: a

text: fundamental

text: diﬀerence

text: between

text: linear

text: models

text: and

text: nonlinear

text: models.

text: To

text: begin

text: the

text: journey

text: of

text: p-values

text: in

text: diverging-dimensional

text: GLMs,

text: let

text: us

text: gain

text: some

text: insights

text: into

text: this

text: problem

text: by

text: looking

text: at

text: the

text: speciﬁc

text: case

text: of

text: logistic

text: regression.

text: Recently,

text: established

text: an

text: interesting

text: phase

text: tran-

text: sition

text: phenomenon

text: of

text: perfect

text: hyperplane

text: separation

text: for

text: high-dimensional

text: classiﬁcation

text: with

text: an

text: elegant

text: probabilistic

text: argument.

text: Suppose

text: we

text: are

text: given

text: a

text: random

text: design

text: matrix

text: X

text: I

text: I

text: and

text: arbitrary

text: binary

text: y

text: ’s

text: that

text: n

text: p

text: i

text: are

text: not

text: all

text: the

text: same.

text: The

text: phase

text: transition

text: of

text: perfect

text: hyperplane

text: separation

text: happens

text: at

text: the

text: point

text: p/n

text: With

text: such

text: a

text: separating

text: hyperplane,

text: there

text: R

text: R

text: exist

text: some

text: β

text: p

text: and

text: t

text: such

text: that

text: xT

text: β

text: t

text: for

text: all

text: cases

text: y

text: and

text: i

text: i

text: xT

text: β

text: t

text: for

text: all

text: controls

text: y

text: Let

text: us

text: ﬁt

text: a

text: logistic

text: regression

text: model

text: with

text: an

text: i

text: i

text: intercept.

text: It

text: is

text: easy

text: to

text: show

text: that

text: multiplying

text: the

text: vector

text: t,

text: (β

text: )T

text: )T

text: by

text: a

text: di-

text: vergence

text: sequence

text: of

text: positive

text: numbers

text: c,

text: we

text: can

text: obtain

text: a

text: sequence

text: of

text: logistic

text: regression

text: ﬁts

text: with

text: the

text: ﬁtted

text: response

text: vector

text: approaching

text: y

text: (y

text: y

text: )T

text: n

text: as

text: c

text: As

text: a

text: consequence,

text: the

text: MLE

text: algorithm

text: can

text: return

text: a

text: pretty

text: wild

text: estimate

text: that

text: is

text: close

text: to

text: inﬁnity

text: in

text: topology

text: when

text: the

text: algorithm

text: is

text: set

text: to

text: stop.

text: Clearly,

text: in

text: such

text: a

text: case

text: the

text: p-value

text: of

text: the

text: MLE

text: is

text: no

text: longer

text: justiﬁed

text: and

text: meaningful.

text: The

text: results

text: in

text: motivate

text: us

text: to

text: characterize

text: the

text: break-

text: down

text: point

text: of

text: p-values

text: in

text: nonlinear

text: GLMs

text: with

text: p

text: in

text: the

text: regime

text: of

text: α

text: It

text: is

text: worth

text: mentioning

text: that

text: our

text: work

text: is

text: diﬀerent

text: in

text: goals

text: from

text: the

text: limited

text: but

text: growing

text: literature

text: on

text: p-values

text: for

text: high-dimensional

text: nonlinear

text: models,

text: and

text: makes

text: novel

text: contributions

text: to

text: such

text: a

text: problem.

text: The

text: key

text: distinction

text: is

text: that

text: existing

text: work

text: has

text: focused

text: primarily

text: on

text: identifying

text: the

text: scenarios

text: in

text: which

text: conventional

text: p-values

text: or

text: their

text: modiﬁcations

text: continue

text: to

text: be

text: valid

text: with

text: some

text: sparsity

text: assumption

text: limiting

text: the

text: growth

text: of

text: intrinsic

text: dimensions.

text: For

text: exam-

text: ple,

text: established

text: the

text: oracle

text: property

text: including

text: the

text: asymptotic

text: normality

text: for

text: nonconcave

text: penalized

text: likelihood

text: estimators

text: in

text: the

text: scenario

text: of

text: p

text: while

text: extended

text: their

text: results

text: to

text: the

text: GLM

text: setting

text: of

text: non-polynomial

text: (NP)

text: dimensionality.

text: In

text: the

text: latter

text: work,

text: the

text: p-values

text: were

text: proved

text: to

text: be

text: valid

text: un-

text: der

text: the

text: assumption

text: that

text: the

text: intrinsic

text: dimensionality

text: s

text: More

text: re-


text: 6 Y. FAN, E. DEMIRKAYA AND J. LV Condi(cid:13)(cid:13)t(cid:2)ion 1. The (cid:3)des(cid:13)(cid:13)ign matrix X satisﬁes (cid:13) (cid:13) (8) XT Σ (θ ) X −1 (cid:2) = O(b(cid:8)n−1), (cid:12)(cid:12) (cid:12)(cid:12)(cid:9) (cid:3) 0 ∞ n | | ◦ (cid:48)(cid:48) (9) max maxp λ XT diag x µ (Xβ) X = O(n) ∈N j=1 max j β 0 ◦ with denoting the Hadamard product and derivatives understood compo- (cid:107) (cid:107) { } nentwise. Assume that maxp x ∞ < c1/2 n/(log n) 1/2 if the responses j=1 j 1 are unbounded. (cid:80) − Condition 2. The eigenvalues of n 1A are bounded away from 0 and ∞ − n | − (cid:48) | , n (zT A 1z )3/2 = o(1), and maxn E y b (θ ) 3 = O(1), where i=1 i n i · · · i=1 i 0,i A = XT Σ(θ )X and (z , , z )T = X. n 0 1 n Conditions 1 and 2 put some basic restrictions on the design matrix X and a moment condition on the responses. For the case of linear model, bound (cid:107) − (cid:107) (8) becomes (XT X) 1 ∞ = O(b /n) and bound (9) holds automatically (cid:48)(cid:48)(cid:48) ≡ n since b (θ) 0. Condition 2 is related to the Lyapunov condition. (cid:98) Theorem 1 (Asymptotic normality). Assume that Conditions 1–2 and ≤ ≤ probability bound (6) hold. Then the MLE β satisﬁes that for each 1 j p, (cid:98) (10) (A−1)−1/2(β − β ) −D→ N(0, φ), n jj j 0,j − where A = XT Σ(θ )X and (A 1) denotes the jth diagonal entry. n 0 n jj Theorem 1 establishes the asymptotic normality of the MLE and conse- quently justiﬁes the validity of the conventional p-values in low dimensions. Note that for simplicity, we present here only the marginal asymptotic nor- mality, and the joint asymptotic normality also holds for the projection of the MLE onto any ﬁxed-dimensional subspace. This result can also be ex- tended to the case of misspeciﬁed models; see, for example, [17]. As mentioned in the Introduction, the asymptotic normality was shown in [9] for nonconcave penalized MLE having intrinsic dimensionality s =

text: Y.

text: FAN,

text: E.

text: DEMIRKAYA

text: AND

text: J.

text: LV

text: The

text: matrix

text: X

text: satisﬁes

text: XT

text: Σ

text: (θ

text: X

text: −1

text: n

text: max

text: maxp

text: λ

text: XT

text: diag

text: x

text: µ

text: (Xβ)

text: X

text: O(n)

text: ∈N

text: max

text: j

text: β

text: with

text: denoting

text: the

text: Hadamard

text: product

text: and

text: derivatives

text: understood

text: compo-

text: nentwise.

text: Assume

text: that

text: maxp

text: x

text: n/(log

text: n)

text: if

text: the

text: responses

text: j

text: are

text: unbounded.

text: Condition

text: The

text: eigenvalues

text: of

text: n

text: are

text: bounded

text: away

text: from

text: and

text: n

text: n

text: (zT

text: A

text: and

text: maxn

text: E

text: y

text: b

text: (θ

text: where

text: i

text: n

text: i

text: i

text: A

text: XT

text: Σ(θ

text: )X

text: and

text: (z

text: z

text: )T

text: X.

text: n

text: n

text: Conditions

text: and

text: put

text: some

text: basic

text: restrictions

text: on

text: the

text: design

text: matrix

text: X

text: and

text: a

text: moment

text: condition

text: on

text: the

text: responses.

text: For

text: the

text: case

text: of

text: linear

text: model,

text: bound

text: becomes

text: (XT

text: X)

text: O(b

text: /n)

text: and

text: bound

text: holds

text: automatically

text: n

text: since

text: b

text: (θ)

text: Condition

text: is

text: related

text: to

text: the

text: Lyapunov

text: condition.

text: Theorem

text: (Asymptotic

text: normality).

text: Assume

text: that

text: Conditions

text: and

text: probability

text: bound

text: hold.

text: Then

text: the

text: MLE

text: β

text: satisﬁes

text: that

text: for

text: each

text: j

text: p,

text: β

text: −D→

text: φ),

text: n

text: jj

text: j

text: where

text: A

text: XT

text: Σ(θ

text: )X

text: and

text: (A

text: denotes

text: the

text: jth

text: diagonal

text: entry.

text: n

text: n

text: jj

text: Theorem

text: establishes

text: the

text: asymptotic

text: normality

text: of

text: the

text: MLE

text: and

text: conse-

text: quently

text: justiﬁes

text: the

text: validity

text: of

text: the

text: conventional

text: p-values

text: in

text: low

text: dimensions.

text: Note

text: that

text: for

text: simplicity,

text: we

text: present

text: here

text: only

text: the

text: marginal

text: asymptotic

text: nor-

text: mality,

text: and

text: the

text: joint

text: asymptotic

text: normality

text: also

text: holds

text: for

text: the

text: projection

text: of

text: the

text: MLE

text: onto

text: any

text: ﬁxed-dimensional

text: subspace.

text: This

text: result

text: can

text: also

text: be

text: ex-

text: tended

text: to

text: the

text: case

text: of

text: misspeciﬁed

text: models;

text: see,

text: for

text: example,

text: As

text: mentioned

text: in

text: the

text: Introduction,

text: the

text: asymptotic

text: normality

text: was

text: shown

text: in

text: for

text: nonconcave

text: penalized

text: MLE

text: having

text: intrinsic

text: dimensionality

text: s