text: (cid:88) the 2D signal can be rewritten into a compact form K x = c zn1 zn2 . n1n2 k 1,k 2,k k=1 { } { } And our aim is still to estimate the poles z and z of the signal from { } 1,k 2,k the samples x − that we receive. n1n2 n1=0,1,...,N1−1 n2=0,1,...,N2 1 Denote matrix X = (x ) × . Then we construct a BHHB tensor H n1n2 N1 N2 × × with the generating matrix X of a ﬁxed order m, size (I J ) (I J ) · · · × × × · · · × 1 1 2 2 (I J ), and block size I I I . The order m can be selected m m 1 2 m arbitrarily and the size I and J of each dimension should be no less than p H p K. Then the BHHB tensor has the level-2 Vandermonde decomposition H C × (cid:11) (cid:62) × (cid:11) (cid:62) · · · × (cid:11) (cid:62) = (Z Z ) (Z Z ) (Z Z ) , 1 2,1 1,1 2 2,2 1,2 m 2,m 1,m C { } where is a diagonal tensor with diagonal entries c K , each Z or Z k k=1 1,p 2,p is a Vandermonde matrix      · · · −   · · · −  1 z z2 zIp 1 1 z z2 zJp 1  1,1 1,1 · · · 1,1−   2,1 2,1 · · · 2,1−  (cid:62) 1 z1,2 z12,2 z1Ip,2 1 (cid:62) 1 z2,2 z22,2 z2J,p2 1 Z = . . . . . , Z = . . . . . , 1,p . . . . . 2,p . . . . . . . . . . . . . . . · · · − · · · − 1 z z2 zIp 1 1 z z2 zJp 1 1,K 1,K 1,K 2,K 2,K 2,K (cid:11) and the notation “ ” denotes the column-wise Kronecker product of two matrices with the same column sizes, i.e., (cid:11) ⊗ (A B)(:, j) = A(:, j) B(:, j). So the target will be attained, if we obtain the level-2 Vandermonde decom- H position of this BHHB tensor . We can use HOOI as well to compute the best rank-(K, K, . . . , K) ap- H proximation of the BHHB tensor H S × (cid:62) × (cid:62) · · · × (cid:62) = U U U , 1 1 2 2 m m S ∈ C × ×···× ∈ C × where K K K is the core tensor and U (IpJp) K has orthogonal p columns. Note that the tensor-vector products in HOOI should be computed by our fast algorithm for BHHB tensor-vector products in Section 3. Then (cid:11) U and Z Z have the common column space, which is equivalent to p 2,p 1,p that there is a nonsingular matrix T such that (cid:11) Z Z = U T. 2,p 1,p p 15

text: the

text: signal

text: can

text: be

text: rewritten

text: into

text: a

text: compact

text: form

text: K

text: x

text: c

text: k

text: And

text: our

text: aim

text: is

text: still

text: to

text: estimate

text: the

text: poles

text: z

text: and

text: z

text: of

text: the

text: signal

text: from

text: the

text: samples

text: x

text: that

text: we

text: receive.

text: Denote

text: matrix

text: X

text: (x

text: Then

text: we

text: construct

text: a

text: BHHB

text: tensor

text: H

text: with

text: the

text: generating

text: matrix

text: X

text: of

text: a

text: ﬁxed

text: order

text: m,

text: size

text: (I

text: J

text: (I

text: J

text: (I

text: J

text: and

text: block

text: size

text: I

text: I

text: I

text: The

text: order

text: m

text: can

text: be

text: selected

text: m

text: m

text: m

text: arbitrarily

text: and

text: the

text: size

text: I

text: and

text: J

text: of

text: each

text: dimension

text: should

text: be

text: no

text: less

text: than

text: p

text: H

text: p

text: K.

text: Then

text: the

text: BHHB

text: tensor

text: has

text: the

text: Vandermonde

text: decomposition

text: H

text: C

text: (Z

text: Z

text: (Z

text: Z

text: (Z

text: Z

text: m

text: C

text: where

text: is

text: a

text: diagonal

text: tensor

text: with

text: diagonal

text: entries

text: c

text: K

text: each

text: Z

text: or

text: Z

text: k

text: is

text: a

text: Vandermonde

text: matrix

text: 1

text: z

text: zIp

text: 1

text: 1

text: z

text: zJp

text: 1

text: 1

text: 1

text: 1

text: 1

text: Z

text: Z

text: z

text: zIp

text: z

text: zJp

text: and

text: the

text: notation

text: denotes

text: the

text: column-wise

text: Kronecker

text: product

text: of

text: two

text: matrices

text: with

text: the

text: same

text: column

text: sizes,

text: i.e.,

text: (A

text: B)(:,

text: j)

text: A(:,

text: j)

text: B(:,

text: j).

text: So

text: the

text: target

text: will

text: be

text: attained,

text: if

text: we

text: obtain

text: the

text: Vandermonde

text: decom-

text: H

text: position

text: of

text: this

text: BHHB

text: tensor

text: We

text: can

text: use

text: HOOI

text: as

text: well

text: to

text: compute

text: the

text: best

text: rank-(K,

text: K,

text: K)

text: ap-

text: H

text: proximation

text: of

text: the

text: BHHB

text: tensor

text: H

text: S

text: U

text: U

text: U

text: m

text: m

text: S

text: C

text: C

text: where

text: K

text: K

text: K

text: is

text: the

text: core

text: tensor

text: and

text: U

text: (IpJp)

text: K

text: has

text: orthogonal

text: p

text: columns.

text: Note

text: that

text: the

text: tensor-vector

text: products

text: in

text: HOOI

text: should

text: be

text: computed

text: by

text: our

text: fast

text: algorithm

text: for

text: BHHB

text: tensor-vector

text: products

text: in

text: Section

text: Then

text: U

text: and

text: Z

text: Z

text: have

text: the

text: common

text: column

text: space,

text: which

text: is

text: equivalent

text: to

text: p

text: that

text: there

text: is

text: a

text: nonsingular

text: matrix

text: T

text: such

text: that

text: Z

text: Z

text: U

text: T.

text: p


text: [16] M. K. Ng, Iterative Methods for Toeplitz Systems, Oxford University Press, 2004. [17] V. Olshevsky, Structured Matrices in Mathematics, Computer Science, and Engineering. II, Contemporary Mathematics, vol. 281. American Mathemat- ical Society, Providence, RI, 2001. [18] J.-M. Papy, L. De Lathauwer, and S. Van Huffel, Exponential data ﬁtting using multilinear algebra: The single-channel and multi-channel case, Numerical Linear Algebra with Applications, 12 (2005), pp. 809–826. [19] , Exponential data ﬁtting using multilinear algebra: The decimative case, Journal of Chemometrics, 23 (2009), pp. 341–351. [20] V. Pereyra and G. Scherer, Exponential Data Fitting and its Applica- tions, Bentham Science Publishers, 2010. [21] L. Qi, Eigenvalues of a real supersymmetric tensor, Journal of Symbolic Com- putation, 40 (2005), pp. 1302–1324. [22] , Eigenvalues and invariants of tensors, Journal of Mathematical Anal- ysis and Applications, 325 (2007), pp. 1363–1377. [23] , Hankel tensors: Associated Hankel matrices and Vandermonde decom- position, arXiv preprint arXiv:1310.5470, (2013). [24] S. Qiao, G. Liu, and W. Xu, Block Lanczos tridiagonalization of complex symmetric matrices, in Advanced Signal Processing Algorithms, Architec- tures, and Implementations XV, Proceedings of the SPIE, vol. 5910, SPIE, 2005, pp. 285–295. [25] Y. Song and L. Qi, Inﬁnite and ﬁnite dimensional Hilbert tensors, arXiv preprint arXiv:1401.4966, (2014). [26] W. Xu and S. Qiao, A fast symmetric SVD algorithm for square Hankel matrices, Linear Algebra and its Applications, 428 (2008), pp. 550–563. 20 ##LTLine## ##LTLine## ##LTLine##

label: reference

text: M.

text: K.

text: Ng,

text: Iterative

text: Methods

text: for

text: Toeplitz

text: Systems,

text: Oxford

text: University

text: Press,

text: V.

text: Olshevsky,

text: Structured

text: Matrices

text: in

text: Mathematics,

text: Computer

text: Science,

text: and

text: Engineering.

text: II,

text: Contemporary

text: Mathematics,

text: vol.

text: American

text: Mathemat-

text: ical

text: Society,

text: Providence,

text: RI,

text: J.-M.

text: Papy,

text: L.

text: De

text: Lathauwer,

text: and

text: S.

text: Van

text: Huffel,

text: Exponential

text: data

text: ﬁtting

text: using

text: multilinear

text: algebra:

text: The

text: single-channel

text: and

text: multi-channel

text: case,

text: Numerical

text: Linear

text: Algebra

text: with

text: Applications,

text: pp.

text: Exponential

text: data

text: ﬁtting

text: using

text: multilinear

text: algebra:

text: The

text: decimative

text: case,

text: Journal

text: of

text: Chemometrics,

text: pp.

text: V.

text: Pereyra

text: and

text: G.

text: Scherer,

text: Exponential

text: Data

text: Fitting

text: and

text: its

text: Applica-

text: tions,

text: Bentham

text: Science

text: Publishers,

text: L.

text: Qi,

text: Eigenvalues

text: of

text: a

text: real

text: supersymmetric

text: tensor,

text: Journal

text: of

text: Symbolic

text: Com-

text: putation,

text: pp.

text: Eigenvalues

text: and

text: invariants

text: of

text: tensors,

text: Journal

text: of

text: Mathematical

text: Anal-

text: ysis

text: and

text: Applications,

text: pp.

text: Hankel

text: tensors:

text: Associated

text: Hankel

text: matrices

text: and

text: Vandermonde

text: decom-

text: position,

text: arXiv

text: preprint

text: S.

text: Qiao,

text: G.

text: Liu,

text: and

text: W.

text: Xu,

text: Block

text: Lanczos

text: tridiagonalization

text: of

text: complex

text: symmetric

text: matrices,

text: in

text: Advanced

text: Signal

text: Processing

text: Algorithms,

text: Architec-

text: tures,

text: and

text: Implementations

text: XV,

text: Proceedings

text: of

text: the

text: SPIE,

text: vol.

text: SPIE,

text: pp.

text: Y.

text: Song

text: and

text: L.

text: Qi,

text: Inﬁnite

text: and

text: ﬁnite

text: dimensional

text: Hilbert

text: tensors,

text: arXiv

text: preprint

text: W.

text: Xu

text: and

text: S.

text: Qiao,

text: A

text: fast

text: symmetric

text: SVD

text: algorithm

text: for

text: square

text: Hankel

text: matrices,

text: Linear

text: Algebra

text: and

text: its

text: Applications,

text: pp.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: so that the Hankel tensor-vector products can be realized by multiplying a larger anti-circulant tensor by some augmented vectors. Therefore, the fast H × · · · × procedure for computing y =(cid:124) (cid:123)(cid:122)2 x(cid:125)2 m xm is (cid:0)(cid:62) (cid:62) (cid:1)  x˜p = [xp , 0, 0, . . . , 0] , p = 2, 3, . . . , m,  − dH ∗np ∗ · · · ∗ y˜ = ﬀt iﬀt(h). ﬀt(x˜ ). . ﬀt(x˜ ) , − 2 m y = y˜(0 : n 1), 1  H × × · · · × and the fast procedure for computing α = x x x is (cid:124) (cid:123)(cid:122) (cid:125) 1 1 2 2 m m  (cid:62) (cid:0) (cid:62) (cid:1) x˜ = [x , 0, 0, . . . , 0] , p = 1, 2, . . . , m, p p − (cid:62)dH np ∗ ∗(cid:0) · · · ∗ (cid:1) α = iﬀt(h) ﬀt(x˜ ). ﬀt(x˜ ). . ﬀt(x˜ ) . 1 2 m O Moreover, the computational complexity is (m + 1)dH log dH . When the O Hankel tensor is a square tensor, the complexity is at the level (m2n log mn), O which is much smaller than the complexity (nm) of non-structured prod- ucts. Apart from the low computational complexity, our algorithm for Han- kel tensor-vector products has two advantages. One is that this scheme is compact, that is, there is no redundant element in the procedure. It is not required to form the Hankel tensor explicitly. Just the generating vector is needed. Another advantage is that our algorithm treats the tensor as an ensemble instead of multiplying the tensor by vectors mode by mode. H Example 3.1. We choose 3th-order square Hankel tensors of diﬀerent H − sizes. We compute the tensor-vector products xm 1 by using our fast algo- rithm and the non-structured algorithm directly based on the deﬁnition. The comparison of the running times is shown in Figure 2. From the results, we can see that the running time of our algorithm increases far slowly than that of the non-structured algorithm just as the theoretical analysis. Moreover, the diﬀerence in running times is not only the low computational complexity, but also the absence of forming the Hankel tensor explicitly in our algorithm. For BAAB and BHHB cases, we also have fast algorithms for the tensor- C vector products. Let be a BAAB tensor of order m with the compressed ∈ C × C ⊗ generating matrix C n N. Since can be diagonalized by F F , i.e., N n C D ⊗ = (F F )m, N n (cid:0) (cid:1) ∈ C we have for vectors x , x , . . . , x nN 2 3 m C × · · · × ⊗ D × ⊗ · · · × ⊗ y = x x = (F F ) (F F )x (F F )x . 2 2 m m N n 2 N n 2 m N n m 9

text: so

label: paragraph

text: that

text: the

text: Hankel

text: tensor-vector

text: products

text: can

text: be

text: realized

text: by

text: multiplying

text: a

text: larger

text: anti-circulant

text: tensor

text: by

text: some

text: augmented

text: vectors.

text: Therefore,

text: the

text: fast

text: H

text: procedure

text: for

text: computing

text: y

text: m

text: xm

text: is

text: x˜p

text: [xp

text: p

text: m,

text: dH

text: ∗np

text: y˜

text: ﬀt

text: iﬀt(h).

text: ﬀt(x˜

text: ﬀt(x˜

text: m

text: y

text: n

text: H

text: and

text: the

text: fast

text: procedure

text: for

text: computing

text: α

text: x

text: x

text: x

text: is

text: m

text: m

text: x˜

text: [x

text: p

text: m,

text: p

text: p

text: np

text: α

text: iﬀt(h)

text: ﬀt(x˜

text: ﬀt(x˜

text: ﬀt(x˜

text: m

text: O

text: Moreover,

text: the

text: computational

text: complexity

text: is

text: (m

text: log

text: dH

text: When

text: the

text: O

text: Hankel

text: tensor

text: is

text: a

text: square

text: tensor,

text: the

text: complexity

text: is

text: at

text: the

text: level

text: log

text: mn),

text: O

text: which

text: is

text: much

text: smaller

text: than

text: the

text: complexity

text: (nm)

text: of

text: non-structured

text: prod-

text: ucts.

text: Apart

text: from

text: the

text: low

text: computational

text: complexity,

text: our

text: algorithm

text: for

text: Han-

text: kel

text: tensor-vector

text: products

text: has

text: two

text: advantages.

text: One

text: is

text: that

text: this

text: scheme

text: is

text: compact,

text: that

text: is,

text: there

text: is

text: no

text: redundant

text: element

text: in

text: the

text: procedure.

text: It

text: is

text: not

text: required

text: to

text: form

text: the

text: Hankel

text: tensor

text: explicitly.

text: Just

text: the

text: generating

text: vector

text: is

text: needed.

text: Another

text: advantage

text: is

text: that

text: our

text: algorithm

text: treats

text: the

text: tensor

text: as

text: an

text: ensemble

text: instead

text: of

text: multiplying

text: the

text: tensor

text: by

text: vectors

text: mode

text: by

text: mode.

text: H

text: Example

text: We

text: choose

text: square

text: Hankel

text: tensors

text: of

text: diﬀerent

text: H

text: sizes.

text: We

text: compute

text: the

text: tensor-vector

text: products

text: xm

text: by

text: using

text: our

text: fast

text: algo-

text: rithm

text: and

text: the

text: non-structured

text: algorithm

text: directly

text: based

text: on

text: the

text: deﬁnition.

text: The

text: comparison

text: of

text: the

text: running

text: times

text: is

text: shown

text: in

text: Figure

text: From

text: the

text: results,

text: we

text: can

text: see

text: that

text: the

text: running

text: time

text: of

text: our

text: algorithm

text: increases

text: far

text: slowly

text: than

text: that

text: of

text: the

text: non-structured

text: algorithm

text: just

text: as

text: the

text: theoretical

text: analysis.

text: Moreover,

text: the

text: diﬀerence

text: in

text: running

text: times

text: is

text: not

text: only

text: the

text: low

text: computational

text: complexity,

text: but

text: also

text: the

text: absence

text: of

text: forming

text: the

text: Hankel

text: tensor

text: explicitly

text: in

text: our

text: algorithm.

text: For

text: BAAB

text: and

text: BHHB

text: cases,

text: we

text: also

text: have

text: fast

text: algorithms

text: for

text: the

text: tensor-

text: C

text: vector

text: products.

text: Let

text: be

text: a

text: BAAB

text: tensor

text: of

text: order

text: m

text: with

text: the

text: compressed

text: C

text: C

text: generating

text: matrix

text: C

text: n

text: N.

text: Since

text: can

text: be

text: diagonalized

text: by

text: F

text: F

text: i.e.,

text: N

text: n

text: C

text: D

text: (F

text: F

text: )m,

text: N

text: n

text: C

text: we

text: have

text: for

text: vectors

text: x

text: x

text: x

text: nN

text: m

text: C

text: D

text: y

text: x

text: x

text: (F

text: F

text: (F

text: F

text: )x

text: (F

text: F

text: )x

text: m

text: m

text: N

text: n

text: N

text: n

text: m

text: N

text: n

text: m


text: 13 − ≤ with conﬁdence 1 δ, there exists a constant C depending Noting further that r d, we obtain (cid:88) 2 ∈ G only on d such that for all g R E − E ≤ − − 1 m ≤ 1 log(4/δ) (πMfz,σ,sλ,n) (fρ) Cm 2r2+rd+ε log 4δ. Eg m g(zi) 2Eg + Cη + C(M + 1)2 m . Noticing the identity (cid:90) i=1 Here ∞ E −E {E −E } η = {16M2}22−+pp Cp2,+2νp,dm−2+2p σ p−22(1+ν)d2+2p R22+pp . Eρm( (fρ) (fz,λ,q)) = 0 Pm (fρ) (fz,λ,q) > ε dε, Hence, we obtain direct computation yields the upper bound of (13). The lower (cid:88) bound can be found in [8, Chap.3]. This ﬁnishes the proof of Theorem 3. Eg − m1 m g(zi) ≤ 12Eg + {16(M + 1)2}22−+pp Cp2,+2νp,d i=1 × m−2+2p σ p−22(1+ν)d2+2p R22+pp log 4. VI. CONCLUSIONS δ The ELM-like learning provides a powerful computational burden reduction technique that adjusts only the output con- Now we turn to estimate R. It follows form the deﬁnition nections. Numerous experiments and applications have demon- of f that z,σ,s,λ,n strated the effectiveness and efﬁciency of ELM. The aim of ≤ E · ≤ λΩ(f ) (0) + λ 0 M2. our study is to provide theoretical fundamentals of it. After z,σ,s,λ,n z ≤ analyzing the pros and cons of ELM, we found that the theo- Thus, we obtain that for arbitrary 0 < p 2 and arbitrary retical performance of ELM depends heavily on the activation ν > 0, there exists a constant C depending only on d, ν, p function and randomness mechanism. In the previous cousin and M such that paper [18], we have provided the advantages of ELM in theory, that is, with appropriately selected activation function, ELM S ≤ 1{E − E } reduces the computation burden without sacriﬁcing the gener- (π f ) (f ) 2 2 M z,σ,sλ,n ρ alization capability in the expectation sense. In this paper, we + C log 4m−2+2p σ (p−22)+(1p+ν)d λ−2+2pp (29) discussed certain disadvantages of ELM. Via rigorous proof, δ we found that ELM suffered from both the uncertainty and generalization degradation problem. Indeed, we proved that, − with conﬁdence at least 1 δ (with respect to ρm). for the widely used Gaussian-type activation function, ELM 2 From (25) to (29), we obtain degraded the generalization capability. To facilitate the use of ELM, some remedies of the aforementioned two problem are (cid:18) E − E also recommended. That is, multiple times trials can avoid (πMfz,σ,sλ,n) (fρ) the uncertainty problem and the l2 coefﬁcient regularization ≤ log 4 technique can essentially improve the generalization capability C σ2r + σ2d + λ/n + δ 3m of ELM. All these results reveal the essential characteristics (cid:19) 1{E − E } of ELM learning and give a feasible guidance concerning how + (π f ) (f ) 2 M z,σ,sλ,n ρ to use ELM . 4 − 2 (p−2)(1+ν)d −2p We conclude this paper with a crucial question about ELM + log δ m 2+p σ 2+p λ2+p learning. Question 1: As is shown in [18] and the current paper, − × − {− } holds with conﬁdence at least (1 δ) (1 2 exp cnσ2d ) the performance of ELM depends heavily on the activation × (with respect to ρm µn). function. For appropriately selected activation function, ELM Set σ = m−2r1+d+ε, n = m2r2+dd , λ = m−a := m−42rr+−2dd , does not degrade the generalization capability, while there also ν = ε and exists an activation function such that the degradation exists. 2d(2r+d) As it is impossible to enumerate all the activation functions − 2d + 2ε(2r + d) 2(1 + ν) + 2(2r + d)ε(1 + ν)d and study the generalization capabilities of the corresponding p = − − . (2r + d)(2a + dε + νdε ε) + 2r (1 + ν)d ELM, we are asked for a general condition on the activation ≥ ≤ function, under which the corresponding ELM degrade (or Since r d/2, it is easy to check that ν > 0, and 0 < p 2. doesn’t degrade) the generalization capability. In other words, Then, we get we are interested in a criterion to classify the the activation functions into two classes. With the ﬁrst class, ELM degrades E − E ≤ − (πMfz,σ,sλ,n) (fρ) Cm 2r2+rd+ε log 4δ the generalization capability and with the other class, ELM − − does not degrades the generalization capability. We will keep + m 2r2+dd+ε + log 4δm 24rr++3dd . working on this interesting project, and report our progress in a future publication. ##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: with

text: conﬁdence

text: δ,

text: there

text: exists

text: a

text: constant

text: C

text: depending

text: Noting

text: further

text: that

text: r

text: d,

text: we

text: obtain

text: G

text: only

text: on

text: d

text: such

text: that

text: for

text: all

text: g

text: R

text: E

text: E

text: m

text: (πMfz,σ,sλ,n)

text: (fρ)

text: Cm

text: log

text: Eg

text: m

text: g(zi)

text: Cη

text: C(M

text: m

text: Noticing

text: the

text: identity

text: Here

text: E

text: −E

text: {E

text: −E

text: η

text: σ

text: Eρm(

text: (fρ)

text: (fz,λ,q))

text: Pm

text: (fρ)

text: (fz,λ,q)

text: ε

text: dε,

text: Hence,

text: we

text: obtain

text: direct

text: computation

text: yields

text: the

text: upper

text: bound

text: of

text: The

text: lower

text: bound

text: can

text: be

text: found

text: in

text: This

text: ﬁnishes

text: the

text: proof

text: of

text: Theorem

text: Eg

text: m

text: g(zi)

text: σ

text: log

text: VI.

text: CONCLUSIONS

text: δ

text: The

text: ELM-like

text: learning

text: provides

text: a

text: powerful

text: computational

text: burden

text: reduction

text: technique

text: that

text: adjusts

text: only

text: the

text: output

text: con-

text: Now

text: we

text: turn

text: to

text: estimate

text: R.

text: It

text: follows

text: form

text: the

text: deﬁnition

text: nections.

text: Numerous

text: experiments

text: and

text: applications

text: have

text: demon-

text: of

text: f

text: that

text: z,σ,s,λ,n

text: strated

text: the

text: effectiveness

text: and

text: efﬁciency

text: of

text: ELM.

text: The

text: aim

text: of

text: E

text: λΩ(f

text: λ

text: our

text: study

text: is

text: to

text: provide

text: theoretical

text: fundamentals

text: of

text: it.

text: After

text: z,σ,s,λ,n

text: z

text: analyzing

text: the

text: pros

text: and

text: cons

text: of

text: ELM,

text: we

text: found

text: that

text: the

text: theo-

text: Thus,

text: we

text: obtain

text: that

text: for

text: arbitrary

text: p

text: and

text: arbitrary

text: retical

text: performance

text: of

text: ELM

text: depends

text: heavily

text: on

text: the

text: activation

text: ν

text: there

text: exists

text: a

text: constant

text: C

text: depending

text: only

text: on

text: d,

text: ν,

text: p

text: function

text: and

text: randomness

text: mechanism.

text: In

text: the

text: previous

text: cousin

text: and

text: M

text: such

text: that

text: paper

text: we

text: have

text: provided

text: the

text: advantages

text: of

text: ELM

text: in

text: theory,

text: that

text: is,

text: with

text: appropriately

text: selected

text: activation

text: function,

text: ELM

text: S

text: E

text: reduces

text: the

text: computation

text: burden

text: without

text: sacriﬁcing

text: the

text: gener-

text: (π

text: f

text: (f

text: M

text: z,σ,sλ,n

text: ρ

text: alization

text: capability

text: in

text: the

text: expectation

text: sense.

text: In

text: this

text: paper,

text: we

text: C

text: log

text: σ

text: discussed

text: certain

text: disadvantages

text: of

text: ELM.

text: Via

text: rigorous

text: proof,

text: δ

text: we

text: found

text: that

text: ELM

text: suffered

text: from

text: both

text: the

text: uncertainty

text: and

text: generalization

text: degradation

text: problem.

text: Indeed,

text: we

text: proved

text: that,

text: with

text: conﬁdence

text: at

text: least

text: δ

text: (with

text: respect

text: to

text: ρm).

text: for

text: the

text: widely

text: used

text: Gaussian-type

text: activation

text: function,

text: ELM

text: From

text: to

text: we

text: obtain

text: degraded

text: the

text: generalization

text: capability.

text: To

text: facilitate

text: the

text: use

text: of

text: ELM,

text: some

text: remedies

text: of

text: the

text: aforementioned

text: two

text: problem

text: are

text: E

text: E

text: also

text: recommended.

text: That

text: is,

text: multiple

text: times

text: trials

text: can

text: avoid

text: (πMfz,σ,sλ,n)

text: (fρ)

text: the

text: uncertainty

text: problem

text: and

text: the

text: coefﬁcient

text: regularization

text: log

text: technique

text: can

text: essentially

text: improve

text: the

text: generalization

text: capability

text: C

text: λ/n

text: δ

text: of

text: ELM.

text: All

text: these

text: results

text: reveal

text: the

text: essential

text: characteristics

text: E

text: of

text: ELM

text: learning

text: and

text: give

text: a

text: feasible

text: guidance

text: concerning

text: how

text: (π

text: f

text: (f

text: M

text: z,σ,sλ,n

text: ρ

text: to

text: use

text: ELM

text: We

text: conclude

text: this

text: paper

text: with

text: a

text: crucial

text: question

text: about

text: ELM

text: log

text: δ

text: m

text: σ

text: learning.

text: Question

text: As

text: is

text: shown

text: in

text: and

text: the

text: current

text: paper,

text: holds

text: with

text: conﬁdence

text: at

text: least

text: δ)

text: exp

text: the

text: performance

text: of

text: ELM

text: depends

text: heavily

text: on

text: the

text: activation

text: (with

text: respect

text: to

text: ρm

text: µn).

text: function.

text: For

text: appropriately

text: selected

text: activation

text: function,

text: ELM

text: Set

text: σ

text: n

text: λ

text: m−a

text: does

text: not

text: degrade

text: the

text: generalization

text: capability,

text: while

text: there

text: also

text: ν

text: ε

text: and

text: exists

text: an

text: activation

text: function

text: such

text: that

text: the

text: degradation

text: exists.

text: As

text: it

text: is

text: impossible

text: to

text: enumerate

text: all

text: the

text: activation

text: functions

text: d)

text: ν)

text: ν)d

text: and

text: study

text: the

text: generalization

text: capabilities

text: of

text: the

text: corresponding

text: p

text: dε

text: νdε

text: ε)

text: ν)d

text: ELM,

text: we

text: are

text: asked

text: for

text: a

text: general

text: condition

text: on

text: the

text: activation

text: function,

text: under

text: which

text: the

text: corresponding

text: ELM

text: degrade

text: (or

text: Since

text: r

text: it

text: is

text: easy

text: to

text: check

text: that

text: ν

text: and

text: p

text: doesn’t

text: degrade)

text: the

text: generalization

text: capability.

text: In

text: other

text: words,

text: Then,

text: we

text: get

text: we

text: are

text: interested

text: in

text: a

text: criterion

text: to

text: classify

text: the

text: the

text: activation

text: functions

text: into

text: two

text: classes.

text: With

text: the

text: ﬁrst

text: class,

text: ELM

text: degrades

text: E

text: E

text: (πMfz,σ,sλ,n)

text: (fρ)

text: Cm

text: log

text: 4δ

text: the

text: generalization

text: capability

text: and

text: with

text: the

text: other

text: class,

text: ELM

text: does

text: not

text: degrades

text: the

text: generalization

text: capability.

text: We

text: will

text: keep

text: m

text: log

text: working

text: on

text: this

text: interesting

text: project,

text: and

text: report

text: our

text: progress

text: in

text: a

text: future

text: publication.

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: 6 where C is a constant depending only on d and p. To state the next lemma, we need introduce the following p X Proof: Since we model the sampling set Ξ is a sequence deﬁnitions. Let be a ﬁnite dimensional vector space with (cid:107) · (cid:107) Z ⊂ X∗ Z of i.i.d. random variables in J, the sampling points are a norm X , and be a ﬁnite set. We say that X X → sequence of functions θ = θ (ω) on some probability space is a norm generating set for if the mapping TZ : j j (cid:107) (cid:107) Z (Ω, P). Without loss of generality, we assume T = 1 for RCard( ) deﬁned by TZ(x) = (z(x)) ∈Z is injective, where arbitrary(cid:88)ﬁxed p. If we set ξp(T )(cid:88)= |T (θ )|p, theln pwe have Card(Z) is the cardinality of the set Zzand TZ is named as the j l l j X sampling operator. Let W := TZ( ) be the range of TZ, then n1 n |Tl(θi)|p − Eξjp = n1 n |Tl(θi)|p − (cid:107)Tl(cid:107)pp, tRheCainrdje(Zct)ivhiatyveoaf nToZrmim(cid:107)p·l(cid:107)ies thatZT,Z−w1it:hW(cid:107)·(cid:107)→ X eZxi∗stsb.eLinegt i=(cid:90)1 (cid:90) i=1 Z R∗ Card( ) RCard( ) its dual norm on RCard( ) . Equipping W with the induced where we use the equality (cid:107) − (cid:107) (cid:107) − (cid:107) K norm, and let TZ 1 := TZ 1 →X . In addition, let be Z W ∈ + Z Eξp = |T (η(ω ))|pdω = |T (θ)|pdθ = (cid:107)T (cid:107)p = 1. the positive c≥one of RCard( ): that is, all (rz) RCard( ) j l j j l l p for which r 0. Then the following Lemma 6 can be found Ω (cid:12) J (cid:12) z (cid:12) (cid:12) in [20]. Furthermore, Z X Lemma 6: Let be a norm generating set for , with TZ |ξjp − Eξjp| ≤ su∈p |Tl(θ(ω))|p − (cid:107)Tl(cid:107)pp ≤ (cid:107)Tl(cid:107)p∞ − (cid:107)Tl(cid:107)pp. b(cid:107)ei(cid:107)ng th≤e corresponding sampling operat{or. }If y ∈ X∗ with ω Ω y X∗ A, then there exist r(cid:88)eal numbers a ∈Z, depending ∈ X z z It follows from Lemma 3 that only on y such that for every x , (cid:107) (cid:107) ≤ (cid:107) (cid:107) Tl ∞ Clpd Tl p = Cldp . y(x) = azz(x), ∈Z Hence z | − | ≤ − ξp Eξp (Cld 1). and j j (cid:107) (cid:107) ≤ (cid:107) − (cid:107) (a ) Z ∗ A TZ 1 . On the other hand, we have z RCard( ) ∈ K Also, if W contains an interior point v and if γ2 = E(cid:90) ((ξp)2) − (E(ξp))2(cid:18)(cid:90) (cid:19) y(TUZ−si1nvg)L≥em0mwahe6navnd∈LVem∩Km+a ,5t,hwenewcaenmda0eyduccheootsh+ee afozl≥low0-. ξ j j | | − | | 2 ing probabilistic numerical integral formula for trigonometric = Tl(θ(ω)) 2pdω Tl(θ(ω)) pdω polynomials. (cid:107)Ω (cid:107) − (cid:107) (cid:107) Ω Lemma 7: Let J be a compact subset of Rd. If Ξ = {θ }n = T 2p T 2p. i i=1 l 2p l p are i.i.d. random variables drawn according to arbitrary distri- (cid:90) { } bution µ, then there exists(cid:88)a set of real numbers c n such i i=1 Then using Lemma 3 again, there holds that n ∀ ∈ T γξ2 ≤ Cl2dp(p1−21p)(cid:107)Tl(cid:107)2pp − (cid:107)Tl(cid:107)2pp = (Cld − 1). J Tl(x)dx = i=1(cid:26)ciTl(θi),(cid:27) Tl ld Thus it follows from(cid:40)Lemma 4 that with(cid:41)conﬁdence at least holds with conﬁdence at least (cid:0) (cid:1) − −C n 1 − 2exp (cid:40)− nε2 (cid:41) 1 (cid:88)2exp l1d , 2 (cid:0)γ2 + 13Mξε (cid:1) subject to ≥ − − nε2 n | | ≤ 1 2exp − − , ci 2 C/n, 2 (Cld 1) + 1(Cld 1)ε (cid:12) (cid:12)3 i=1 there holds (cid:12)(cid:12) (cid:88) (cid:12)(cid:12) where C1 and C are constants depXendingT onl(cid:107)y o(cid:107)n d. (cid:107) (cid:107) (cid:12)(cid:12) (cid:12)(cid:12) ZProof: In Lemma 6, we take = ld, Tl X {= T}l p, 1 n | | − (cid:107) (cid:107) ≤ and to be the(cid:40)set of point evaluation functionals δ n . T (θ ) p T p ε. (cid:0) (cid:80) (cid:1) (cid:55)→ | θi i=1 n l i l p The operator TZ is then the restriction map Tl Tl Ξ, with i=1 Tthheins tmheeaMnsatrhciantkiifewXicizs-Za(cid:88)ysgeqmuuenndceinoefqiu.ia.ldit.yrandom variables, (cid:107)f(cid:107)pΞ,p := sn1up ≤ni=≤1 |f{(|fθi()θ|p)|}p1,, 0 <p =p <∞∞. , 1 i n i (cid:26) (cid:27) − (cid:107) (cid:107) ≤ 1 n | | ≤ (cid:107) (cid:107) It follows from Lemma 5 with p = 2 that with conﬁdence at (1 ε) T p T (θ ) p (1 + ε) T p l p n l i l p least i=1(cid:26) (cid:27) − −Cn 1 2exp holds with probability at least ld (cid:90) 1 − 2exp − cnε2 . there holds (cid:107)TZ−1(cid:107) ≤ 2. We now take y to be the functional ld(1 + ε) (cid:55)→ y : T T (x)dx. Then (16) is veriﬁed by setting ε = 1. l l 2 J ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: where

text: C

text: is

text: a

text: constant

text: depending

text: only

text: on

text: d

text: and

text: p.

text: To

text: state

text: the

text: next

text: lemma,

text: we

text: need

text: introduce

text: the

text: following

text: p

text: X

text: Proof:

text: Since

text: we

text: model

text: the

text: sampling

text: set

text: Ξ

text: is

text: a

text: sequence

text: deﬁnitions.

text: Let

text: be

text: a

text: ﬁnite

text: dimensional

text: vector

text: space

text: with

text: Z

text: X∗

text: Z

text: of

text: i.i.d.

text: random

text: variables

text: in

text: J,

text: the

text: sampling

text: points

text: are

text: a

text: norm

text: X

text: and

text: be

text: a

text: ﬁnite

text: set.

text: We

text: say

text: that

text: X

text: X

text: sequence

text: of

text: functions

text: θ

text: θ

text: (ω)

text: on

text: some

text: probability

text: space

text: is

text: a

text: norm

text: generating

text: set

text: for

text: if

text: the

text: mapping

text: TZ

text: j

text: j

text: Z

text: (Ω,

text: P).

text: Without

text: loss

text: of

text: generality,

text: we

text: assume

text: T

text: for

text: RCard(

text: deﬁned

text: by

text: TZ(x)

text: (z(x))

text: ∈Z

text: is

text: injective,

text: where

text: p.

text: If

text: we

text: set

text: ξp(T

text: |T

text: (θ

text: )|p,

text: theln

text: pwe

text: have

text: Card(Z)

text: is

text: the

text: cardinality

text: of

text: the

text: set

text: Zzand

text: TZ

text: is

text: named

text: as

text: the

text: j

text: l

text: l

text: j

text: X

text: sampling

text: operator.

text: Let

text: W

text: TZ(

text: be

text: the

text: range

text: of

text: TZ,

text: then

text: n

text: |Tl(θi)|p

text: Eξjp

text: n

text: |Tl(θi)|p

text: tRheCainrdje(Zct)ivhiatyveoaf

text: X

text: eZxi∗stsb.eLinegt

text: Z

text: R∗

text: Card(

text: RCard(

text: its

text: dual

text: norm

text: on

text: RCard(

text: Equipping

text: W

text: with

text: the

text: induced

text: where

text: we

text: use

text: the

text: equality

text: K

text: norm,

text: and

text: let

text: TZ

text: TZ

text: →X

text: In

text: addition,

text: let

text: be

text: Z

text: W

text: Z

text: Eξp

text: |T

text: (η(ω

text: ))|pdω

text: |T

text: (θ)|pdθ

text: the

text: positive

text: c≥one

text: of

text: RCard(

text: that

text: is,

text: all

text: (rz)

text: RCard(

text: j

text: l

text: j

text: j

text: l

text: l

text: p

text: for

text: which

text: r

text: Then

text: the

text: following

text: Lemma

text: can

text: be

text: found

text: Ω

text: J

text: z

text: in

text: Furthermore,

text: Z

text: X

text: Lemma

text: Let

text: be

text: a

text: norm

text: generating

text: set

text: for

text: with

text: TZ

text: |ξjp

text: Eξjp|

text: su∈p

text: |Tl(θ(ω))|p

text: th≤e

text: corresponding

text: sampling

text: operat{or.

text: }If

text: y

text: X∗

text: with

text: ω

text: Ω

text: y

text: X∗

text: A,

text: then

text: there

text: exist

text: numbers

text: a

text: ∈Z,

text: depending

text: X

text: z

text: z

text: It

text: follows

text: from

text: Lemma

text: that

text: only

text: on

text: y

text: such

text: that

text: for

text: every

text: x

text: Tl

text: Clpd

text: Tl

text: p

text: Cldp

text: y(x)

text: azz(x),

text: ∈Z

text: Hence

text: z

text: ξp

text: Eξp

text: (Cld

text: and

text: j

text: j

text: (a

text: Z

text: A

text: TZ

text: On

text: the

text: other

text: hand,

text: we

text: have

text: z

text: RCard(

text: K

text: Also,

text: if

text: W

text: contains

text: an

text: interior

text: point

text: v

text: and

text: if

text: γ2

text: ξ

text: j

text: j

text: ing

text: probabilistic

text: numerical

text: integral

text: formula

text: for

text: trigonometric

text: Tl(θ(ω))

text: Tl(θ(ω))

text: pdω

text: polynomials.

text: Ω

text: Lemma

text: Let

text: J

text: be

text: a

text: compact

text: subset

text: of

text: Rd.

text: If

text: Ξ

text: {θ

text: }n

text: T

text: T

text: i

text: l

text: l

text: p

text: are

text: i.i.d.

text: random

text: variables

text: drawn

text: according

text: to

text: arbitrary

text: distri-

text: bution

text: µ,

text: then

text: there

text: set

text: of

text: real

text: numbers

text: c

text: n

text: such

text: i

text: Then

text: using

text: Lemma

text: again,

text: there

text: holds

text: that

text: n

text: T

text: γξ2

text: (Cld

text: J

text: Tl(x)dx

text: Tl

text: ld

text: Thus

text: it

text: follows

text: that

text: at

text: least

text: holds

text: with

text: conﬁdence

text: at

text: least

text: −C

text: n

text: subject

text: to

text: n

text: ci

text: C/n,

text: (Cld

text: there

text: holds

text: where

text: and

text: C

text: are

text: constants

text: depXendingT

text: d.

text: ZProof:

text: In

text: Lemma

text: we

text: take

text: ld,

text: Tl

text: X

text: T}l

text: p,

text: n

text: and

text: to

text: be

text: of

text: point

text: evaluation

text: functionals

text: δ

text: n

text: T

text: (θ

text: p

text: T

text: p

text: ε.

text: θi

text: n

text: l

text: i

text: l

text: p

text: The

text: operator

text: TZ

text: is

text: then

text: the

text: restriction

text: map

text: Tl

text: Tl

text: Ξ,

text: with

text: Tthheins

text: variables,

text: <p

text: =p

text: i

text: n

text: i

text: n

text: It

text: follows

text: from

text: Lemma

text: with

text: p

text: that

text: with

text: conﬁdence

text: at

text: ε)

text: T

text: p

text: T

text: (θ

text: p

text: ε)

text: T

text: p

text: l

text: p

text: n

text: l

text: i

text: l

text: p

text: least

text: −Cn

text: holds

text: with

text: probability

text: at

text: least

text: ld

text: there

text: holds

text: We

text: now

text: take

text: y

text: to

text: be

text: the

text: functional

text: ε)

text: y

text: T

text: T

text: (x)dx.

text: Then

text: is

text: veriﬁed

text: by

text: setting

text: ε

text: l

text: l

text: J

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: 10 C. Proof of Theorem 2 x1, x2, . .≤. , xr≤in Q and (cid:88)nonzero real numbers a1, a2, . . . , ar, The main tool to prove Theorem 2 is the following Lemma where 1 r n, such that 12, which can be found in [8, Chap.11]. r ∈ L(s) = a s(x ), s S Lemma 12: Let f be deﬁned as in (4). Then i i z,σ,s,n (cid:8) i=1 (cid:9) (cid:88) and (cid:90) E (cid:107)π f − f (cid:107)2 ≤ CM2 (log m + 1)n (cid:107) (cid:107) | | ∈ (cid:107) (cid:107) ≤ r | | ρm M z,σ,s,n ρ ρ m L = sup L(s) : s S, s Q 1 = ai . | − | + 8 inf f(x) f (x) 2dρ (21) i=1 ∈H ρ X By using Lemmas 13 and 10, we can obtain the following f σ,s,n X Bernstein inequality for ELM with Gaussian kernel in the for some universal constant C. metric of L2 . Now, we use Proposition 1 and Lemma 12 to prove Theorem Lemma 1ρ4X: Let d = 1, s = 1, and σ ≥ n−1/2. Then, for ∈ H 2. arbitrary g , there holds n σ,s,n H Proof of Theorem 2: Since σ,s,n is a n-dimensional (cid:107)g(cid:48) (cid:107) ≤ Cn1/2(cid:107)g (cid:107) , linear space, then Lemma 12 yields that n ρ n ρ where C is an absolute constant. Eρm(cid:107)πMf(cid:90)z,σ,s,n − fρ(cid:107)2ρ ≤ CM2 (log mm+ 1)n Hσ,s,Pnr,oaonf:d WL(es)ap=plsy(cid:48)(1L)e.mImt faol1lo3wws iftrhomQL=em[m1/a21,01],thaSt = + 8 ∈Hinf |f(x) − fρ(x)|2dρ. (cid:107)L(cid:107) = |s(cid:48)(1)| ≤ Cn1/2|s(1)| = C1n1/2. (22) f σ,s,n X (cid:90) We deduce tha(cid:80)t there are v , v , . .(cid:12). , v in (cid:12)[1/2, 1] and Therefore, it sufﬁces to bound ∈ 1 (cid:88)2 ∈(cid:12) Hr (cid:12) a , a , . . . , a I1 so that for every s (cid:12) ,(cid:12) 1 2 r (cid:12) σ,s,n (cid:12) | − | ≤ (cid:107) − (cid:107) | (cid:48) | | | inf f(x) f (x) 2 inf f f 2 . s (1) r a s(v ) ≤ r a | | f∈Hσ,s,n X ρ (cid:0) f∈Hσ,s,n ρ X(cid:1) C1n1/2 = iC=11n1(cid:12)i/2 i (cid:12) C1ni1/2 s(vi) From Theorem 1, it follows that ≤ ≤ (cid:88) (cid:12) (cid:12) i=1 with 1 r n. By (22) (cid:12)we have(cid:12) (cid:107) − (cid:107) ≤ (cid:107) (cid:107) (cid:12) (cid:12) g∈Hinσf,s,n g fρ X C ωs,Id(fρ, σ) + fρ σd r ai ≤ 1. (cid:80) − {− } ≤ C1n1/2 hsoalndds wfρith∈pFrorb,awbiiltihtypartobleaabsitli1ty a2telxe(cid:0)past 1c−nσ22dex(cid:1).pN{−otcinngσ2rd}, So there is a sequencie=1of nu(cid:88)mbers {ci} with ri=1 |ci| = 1 there holds such that | (cid:48) | s (1) ≤ r | || | (cid:107) − (cid:107) ≤ c s(v ) . inf f f 2 C σ2r + σ2d . C n1/2 i i f∈Hσ,s,n ρ X ∞1 → ∞i=1 − Now l(cid:18)et φ : [0(cid:19), ) (cid:88)[0, ) be a n(cid:88)ondecreasing convex Setting−σ = n({−1+ε)/}(2d), we o(cid:16)bserve that with proba(cid:17)bility at function. Using monotonicity and convexity, we have least 1 2 exp nε , there holds | (cid:48) | s (1) ≤ r | | ≤ r | | | | inf (cid:107)f − f (cid:104)(cid:107)2 ≤ C(cid:105) n−r/d+rε/d + n−1+ε . φ C n1/2 φ( cis(vi) ) ci φ( s(vi) ). f∈Hσ,s,n ρ X 1 i=1 i=1 − ∈ H Applying th(cid:18)is inequal(cid:19)ity with s(t) = g (t + u 1) , (cid:88) n σ,s,n Finally, choosing n = mr+dd (cid:16), we obtain that with probabili(cid:17)ty we get − {− } at least 1 2 exp nε , there holds |g(cid:48) (u)| ≤ r | | | − | φ n c φ( P(v + u b) ) Eρm(cid:107)πMfz,σ,s,n −fρ(cid:107)2ρ ≤ C m−(1r−+εd)r log m + m−d(r1+−dε) . ∈CH1n1/2 i=∈1 i i ∈ for every P and u [1/2, 1]. Since x [1/2, 1] and This ﬁnishes the proof of Theorem 2. ∈ σ,s,n − ∈ i u [1/2, 1], then v + u 1 [0, 1] for each i = 1, 2, . . . , r. i Integrating(cid:90)on the(cid:18)interval [(cid:19)1/2, 1] with respect to u, we obtain D. Proof of Proposition 2 | (cid:48) | 1 (cid:90) g (u) To prove Proposition 2, we need the following three lem- (cid:88) φ n dρ (u) mas. The ﬁrst one is the interpolation theorem of linear 1/2 C1n1/2 X functionals, which can be found in [1, P.385]. ≤ r (cid:90) 1 | | | − | (cid:90) (cid:88) c φ( g (v + u 1) )dρ (u) Lemma 13: Let C(Q) be the set of real valued continuous i n i X functions on the compact Hausdorff space Q. Let S be an n- i=1 1/2 dimensional linear subspace of C(Q) over R. Let L (cid:54)= 0 be ≤ r 1 | | | | ≤ 1 | | c φ( g (t) )dρ (t) φ( g (t) )dt, i n X n a real-valued linear functional on S. Then there exist points i=1 0 0 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: C.

label: section

text: Proof

text: of

text: Theorem

text: xr≤in

text: Q

text: and

text: real

text: numbers

text: ar,

text: The

text: main

text: tool

text: to

text: prove

text: Theorem

text: is

text: the

text: following

text: Lemma

text: where

text: r

text: n,

text: such

text: that

text: which

text: can

text: be

text: found

text: in

text: r

text: L(s)

text: a

text: s(x

text: s

text: S

text: Lemma

text: Let

text: f

text: be

text: deﬁned

text: as

text: in

text: Then

text: i

text: i

text: z,σ,s,n

text: and

label: equation

text: E

text: f

text: f

text: (log

text: m

text: r

text: ρm

text: M

text: z,σ,s,n

text: ρ

text: ρ

text: m

text: L

text: sup

text: L(s)

text: s

text: S,

text: s

text: Q

text: ai

text: inf

text: f(x)

text: f

text: (x)

text: ∈H

text: ρ

text: X

text: By

text: using

text: Lemmas

text: and

text: we

text: can

text: obtain

text: the

text: following

text: f

text: σ,s,n

text: X

text: Bernstein

text: inequality

text: for

text: ELM

text: with

text: Gaussian

text: kernel

text: in

text: the

text: for

text: some

text: universal

text: constant

text: C.

text: metric

text: of

text: Now,

text: we

text: use

text: Proposition

text: and

text: Lemma

text: to

text: prove

text: Theorem

text: Lemma

text: Let

text: d

text: s

text: and

text: σ

text: Then,

text: for

text: H

text: arbitrary

text: g

text: there

text: holds

text: n

text: σ,s,n

text: H

text: Proof

text: of

text: Theorem

text: Since

text: σ,s,n

text: is

text: a

text: n-dimensional

text: linear

text: space,

text: then

text: Lemma

text: yields

text: that

text: n

text: ρ

text: n

text: ρ

text: where

text: C

text: is

text: an

text: absolute

text: constant.

text: (log

text: mm+

text: Hσ,s,Pnr,oaonf:d

text: ∈Hinf

text: |f(x)

text: f

text: σ,s,n

text: X

text: We

text: deduce

text: there

text: are

text: v

text: v

text: v

text: in

text: and

text: Therefore,

text: it

text: sufﬁces

text: to

text: bound

text: Hr

text: a

text: a

text: a

text: so

text: that

text: for

text: every

text: s

text: r

text: σ,s,n

text: inf

text: f(x)

text: f

text: (x)

text: inf

text: f

text: f

text: s

text: r

text: a

text: s(v

text: r

text: a

text: f∈Hσ,s,n

text: X

text: ρ

text: f∈Hσ,s,n

text: ρ

text: i

text: s(vi)

text: From

text: Theorem

text: it

text: follows

text: that

text: with

text: r

text: n.

text: By

text: g∈Hinσf,s,n

text: g

text: fρ

text: X

text: C

text: ωs,Id(fρ,

text: σ)

text: fρ

text: σd

text: r

text: ai

text: hsoalndds

text: So

text: there

text: is

text: a

text: {ci}

text: with

text: |ci|

text: there

text: holds

text: such

text: that

text: s

text: r

text: c

text: s(v

text: inf

text: f

text: f

text: C

text: C

text: i

text: i

text: f∈Hσ,s,n

text: ρ

text: X

text: ∞1

text: Now

text: φ

text: be

text: a

text: convex

text: Setting−σ

text: we

text: that

text: with

text: at

text: function.

text: Using

text: monotonicity

text: and

text: convexity,

text: we

text: have

text: least

text: exp

text: nε

text: there

text: holds

text: s

text: r

text: r

text: inf

text: f

text: n−r/d+rε/d

text: φ

text: C

text: φ(

text: cis(vi)

text: ci

text: φ(

text: s(vi)

text: f∈Hσ,s,n

text: ρ

text: X

text: H

text: Applying

text: with

text: s(t)

text: g

text: (t

text: u

text: n

text: σ,s,n

text: Finally,

text: choosing

text: n

text: mr+dd

text: we

text: obtain

text: that

text: with

text: we

text: get

text: at

text: least

text: exp

text: nε

text: there

text: holds

text: (u)|

text: r

text: φ

text: n

text: c

text: φ(

text: P(v

text: u

text: b)

text: C

text: log

text: m

text: i

text: i

text: for

text: every

text: P

text: and

text: u

text: Since

text: x

text: and

text: This

text: ﬁnishes

text: the

text: proof

text: of

text: Theorem

text: σ,s,n

text: i

text: u

text: then

text: v

text: u

text: for

text: each

text: i

text: r.

text: i

text: with

text: respect

text: to

text: u,

text: we

text: obtain

text: D.

text: Proof

text: of

text: Proposition

text: g

text: (u)

text: To

text: prove

text: Proposition

text: we

text: need

text: the

text: following

text: three

text: lem-

text: φ

text: n

text: dρ

text: (u)

text: mas.

text: The

text: ﬁrst

text: one

text: is

text: the

text: interpolation

text: theorem

text: of

text: linear

text: X

text: functionals,

text: which

text: can

text: be

text: found

text: in

text: r

text: c

text: φ(

text: g

text: (v

text: u

text: )dρ

text: (u)

text: Lemma

text: Let

text: C(Q)

text: be

text: the

text: set

text: of

text: real

text: valued

text: continuous

text: i

text: n

text: i

text: X

text: functions

text: on

text: the

text: compact

text: Hausdorff

text: space

text: Q.

text: Let

text: S

text: be

text: an

text: n-

text: dimensional

text: linear

text: subspace

text: of

text: C(Q)

text: over

text: R.

text: Let

text: L

text: be

text: r

text: c

text: φ(

text: g

text: (t)

text: )dρ

text: (t)

text: φ(

text: g

text: (t)

text: )dt,

text: i

text: n

text: X

text: n

text: a

text: real-valued

text: linear

text: functional

text: on

text: S.

text: Then

text: there

text: exist

text: points

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: 20 ANDREY SARANTSEV V 1 θ 1 n 1 v 1 n 2 v 2 V ξ θ 2 2 Figure 1. A two-dimensional wedge. Angles θ and θ are counted toward the vertex of the wedge 1 2 Here, n and n are normal vectors, v and v are reﬂection vectors 1 2 1 2 − − − 1/2 1/2 = a a [r a + r a 2a ] = 0. ii jj ij jj ji ii ij (cid:3) The converse statement is proved similarly. A particular case of a polyhedral domain is a two-dimensional wedge (see Fig. 1), considered in [57], [58], [59], [60]: V { | ≤ ∞ ≤ ≤ } := (r cos θ, r sin θ) 0 r < , ξ θ ξ . 2 1 − V Here, ξ < ξ < ξ + π. Its angle is deﬁned as ξ := ξ ξ . Its boundary ∂ consists of two edges 2 1 2 1 2 V { | ≤ ∞} := (r cos ξ , r sin ξ ) 0 r < , i = 1, 2. i i i V V The edge is called the upper edge, and the edge is called the lower edge. The diﬀerence between 1 V 2 V them is as follows: the shorter way to rotate to get is clockwise rather than counterclockwise. V 1 2 ∈ − On each edge , there is a reﬂection vector v , which forms the angle θ ( π/2, π/2) with the i i i inward unit normal vector n . i V These angles are signed: positive angles θ , θ are measured toward the vertex of (the origin). 1 2 In other words, θ is the angle between n and v , measured clockwise in the direction from n to 1 1 1 1 v . This means the following: if the shorter way to rotate the direction of n to get the direction of 1 1 v is clockwise, then θ > 0; and if it is counterclockwise, then θ < 0. If v and n have the same 1 1 1 1 1 direction, then θ = 0. Simlarly, θ is the angle between n and v , measured counterclockwise 1 2 2 2 from n to v . 2 2 We are interested in whether a reﬂected Brownian motion with zero drift vector and identity covariance matrix in this wedge hits the corner. A necessary and suﬃcient condition is established in [57, Theorem 2.2]. ≥ V Proposition 3.22. Consider an SRBM Z = (Z(t), t 0) in the wedge with µ = 0 and A = I , ∈ V \ V 2 starting from a point x ∂ . (i) If θ + θ > 0, then a.s. there exists t > 0 such that Z(t) = 0. 1 2 ≤ (ii) If θ + θ 0, then a.s. there does not exist t > 0 such that Z(t) = 0. 1 2 (cid:3) Proof. Follows from Lemma 3.17, Proposition 3.14, and Theorem 2.2 from [57]. ##LTLine## ##LTLine##

text: ANDREY

text: SARANTSEV

text: V

text: θ

text: n

text: v

text: n

text: v

text: V

text: ξ

text: θ

text: Figure

text: A

text: two-dimensional

text: wedge.

text: Angles

text: θ

text: and

text: θ

text: are

text: counted

text: toward

text: the

text: vertex

text: of

text: the

text: wedge

text: Here,

text: n

text: and

text: n

text: are

text: normal

text: vectors,

text: v

text: and

text: v

text: are

text: reﬂection

text: vectors

text: a

text: a

text: [r

text: a

text: r

text: a

text: ii

text: jj

text: ij

text: jj

text: ji

text: ii

text: ij

text: The

text: converse

text: statement

text: is

text: proved

text: similarly.

text: A

text: particular

text: case

text: of

text: a

text: polyhedral

text: domain

text: is

text: a

text: two-dimensional

text: wedge

text: (see

text: Fig.

text: considered

text: in

text: V

text: (r

text: cos

text: θ,

text: r

text: sin

text: θ)

text: r

text: ξ

text: θ

text: ξ

text: V

text: Here,

text: ξ

text: ξ

text: ξ

text: π.

text: Its

text: angle

text: is

text: deﬁned

text: as

text: ξ

text: ξ

text: ξ

text: Its

text: boundary

text: consists

text: of

text: two

text: edges

text: V

text: (r

text: cos

text: ξ

text: r

text: sin

text: ξ

text: r

text: i

text: i

text: i

text: i

text: V

text: V

text: The

text: edge

text: is

text: called

text: the

text: upper

text: edge,

text: and

text: the

text: edge

text: is

text: called

text: the

text: lower

text: edge.

text: The

text: diﬀerence

text: between

text: V

text: V

text: them

text: is

text: as

text: follows:

text: the

text: shorter

text: way

text: to

text: rotate

text: to

text: get

text: is

text: clockwise

text: rather

text: than

text: counterclockwise.

text: V

text: On

text: each

text: edge

text: there

text: is

text: a

text: reﬂection

text: vector

text: v

text: which

text: forms

text: the

text: angle

text: θ

text: with

text: the

text: i

text: i

text: i

text: inward

text: unit

text: normal

text: vector

text: n

text: i

text: V

text: These

text: angles

text: are

text: signed:

text: positive

text: angles

text: θ

text: θ

text: are

text: measured

text: toward

text: the

text: vertex

text: of

text: (the

text: origin).

text: In

text: other

text: words,

text: θ

text: is

text: the

text: angle

text: between

text: n

text: and

text: v

text: measured

text: clockwise

text: in

text: the

text: direction

text: from

text: n

text: to

text: v

text: This

text: means

text: the

text: following:

text: if

text: the

text: shorter

text: way

text: to

text: rotate

text: the

text: direction

text: of

text: n

text: to

text: get

text: the

text: direction

text: of

text: v

text: is

text: clockwise,

text: then

text: θ

text: and

text: if

text: it

text: is

text: counterclockwise,

text: then

text: θ

text: If

text: v

text: and

text: n

text: have

text: the

text: same

text: direction,

text: then

text: θ

text: Simlarly,

text: θ

text: is

text: the

text: angle

text: between

text: n

text: and

text: v

text: measured

text: counterclockwise

text: from

text: n

text: to

text: v

text: We

text: are

text: interested

text: in

text: whether

text: a

text: reﬂected

text: Brownian

text: motion

text: with

text: zero

text: drift

text: vector

text: and

text: identity

text: covariance

text: matrix

text: in

text: this

text: wedge

text: hits

text: the

text: corner.

text: A

text: necessary

text: and

text: suﬃcient

text: condition

text: is

text: established

text: in

text: Theorem

text: V

text: Proposition

text: Consider

text: an

text: SRBM

text: Z

text: (Z(t),

text: t

text: in

text: the

text: wedge

text: with

text: µ

text: and

text: A

text: I

text: V

text: V

text: starting

text: from

text: a

text: point

text: x

text: (i)

text: If

text: θ

text: θ

text: then

text: a.s.

text: there

text: exists

text: t

text: such

text: that

text: Z(t)

text: (ii)

text: If

text: θ

text: θ

text: then

text: a.s.

text: there

text: does

text: not

text: exist

text: t

text: such

text: that

text: Z(t)

text: Proof.

text: Follows

text: from

text: Lemma

text: Proposition

text: and

text: Theorem

text: from

text: ##LTLine##

text: ##LTLine##


text: TRIPLE AND SIMULTANEOUS COLLISIONS OF COMPETING BROWNIAN PARTICLES 23 By Lemma 3.6, without loss of generality we can assume an SRBM starts from some point ∈ \ x S ∂S, and µ = 0. First, we prove (i) in the case of the skew-symmetry condition (13), then move to the general case (12). Then we prove (ii) in the case d = 2, and proceed to the case of the general dimension. ∈ \ Lemma 3.24. Take an SRBM in the orthant S, starting from x S ∂S. Suppose it satisﬁes the skew-symmetry condition (13). Then the statement of Theorem 2.12(i) is true. ≥ Proof. Apply the linear transformation (20) to Z = (Z(t), t 0) = SRBMd(R, 0, A). By Lemma 3.18, ≥ S − we get an SRBM Z = (Z(t), t 0) in the polyhedron = A 1/2S, given by (21) with zero drift and identity covariance matrix. It was shown in Lemma 3.21 that the skew-symmetry condition (24) is true. Therefore, by Proposition 3.20 the process Z a.s. does not hit non-smooth parts of the S boundary ∂ at any moment t > 0. Thus, the process Z a.s. does not hit non-smooth parts of the (cid:3) boundary ∂S at any moment t > 0. ∈ \ Lemma 3.25. Take an SRBM in the orthant S, starting from x S ∂S. Suppose it satisﬁes the condition (12). Then the statement of Theorem 2.12(i) is true. M ≥ Proof. Let us ﬁnd another reﬂection nonsingular -matrix R˜ = (r˜ ) ≤ ≤ such that R R˜, and ij 1 i,j d the skew-symmetry condition (13) is true for an SRBMd(R˜, 0, A). We need: (30) r˜ a + r˜ a = 2a , i, j = 1, . . . , d. ij jj ji ii ij Let r˜ = 1 for i = j. Then (30) is true for i = j. Let ij 1 − ≤ ≤ r˜ = [2a r a ] , r˜ = r , 1 i < j d. ij ij ji ii ji ji a jj ≤ This is well deﬁned, since a > 0 (because the matrix A is positive deﬁnite). Also, r˜ r , ≥ jj ≤ ≤ (cid:54) Z ij ij because r a + r a 2a . Since r˜ r 0 for i = j, R˜ is a -matrix, so condition (30) ij jj ji ii ij ij ij M holds. Therefore, by [30, Theorem 2.5] (compare conditions 12 and 16), R˜ is a nonsingular - matrix. Consider two processes Z = SRBMd(R, µ, A), Z˜ = SRBMd(R˜, µ, A), starting from the ∈ \ × M same initial condition x S ∂S. Then we have: R and R˜ are d d reﬂection nonsingular - ≥ matrices, and R R˜. By Proposition 3.9, we have: Z˜ is stochastically smaller than Z. By [35, ≤ Theorem 5], we can claim that a.s. for all t > 0 we have: Z˜(t) Z(t) (possibly after changing the probability space). By Lemma 3.24, the process Z˜ a.s. does not hit non-smooth parts of the ≤ ≤ boundary at any time t > 0. In other words, for every 1 i < j d, we have: a.s. Z˜ (t)+Z˜ (t) > 0 i j for all t > 0. Therefore, a.s. Z (t) + Z (t) > 0 for all t > 0. Thus, with probability one the process i j (cid:3) Z does not hit non-smooth parts of the boundary at any time t > 0. Now, let us prove part (ii) of Theorem 2.12. We start with the case d = 2, then move to the general case. ∈ \ Lemma 3.26. Suppose we start an SRBM in two dimensions from a point x S ∂S in the interior of S. Then the statement of Theorem 2.12 (ii) is valid. ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: TRIPLE

text: AND

text: SIMULTANEOUS

text: COLLISIONS

text: OF

text: COMPETING

text: BROWNIAN

text: PARTICLES

text: By

text: Lemma

text: without

text: loss

text: of

text: generality

text: we

text: can

text: assume

text: an

text: SRBM

text: starts

text: from

text: some

text: point

text: x

text: S

text: ∂S,

text: and

text: µ

text: First,

text: we

text: prove

text: (i)

text: in

text: the

text: case

text: of

text: the

text: skew-symmetry

text: condition

text: then

text: move

text: to

text: the

text: general

text: case

text: Then

text: we

text: prove

text: (ii)

text: in

text: the

text: case

text: d

text: and

text: proceed

text: to

text: the

text: case

text: of

text: the

text: general

text: dimension.

text: Lemma

text: Take

text: an

text: SRBM

text: in

text: the

text: orthant

text: S,

text: starting

text: from

text: x

text: S

text: ∂S.

text: Suppose

text: it

text: satisﬁes

text: the

text: skew-symmetry

text: condition

text: Then

text: the

text: statement

text: of

text: Theorem

text: is

text: true.

text: Proof.

text: Apply

text: the

text: linear

text: transformation

text: to

text: Z

text: (Z(t),

text: t

text: SRBMd(R,

text: A).

text: By

text: Lemma

text: S

text: we

text: get

text: an

text: SRBM

text: Z

text: (Z(t),

text: t

text: in

text: the

text: polyhedron

text: A

text: given

text: by

text: with

text: zero

text: drift

text: and

text: identity

text: covariance

text: matrix.

text: It

text: was

text: shown

text: in

text: Lemma

text: that

text: the

text: skew-symmetry

text: condition

text: is

text: true.

text: Therefore,

text: by

text: Proposition

text: the

text: process

text: Z

text: a.s.

text: does

text: not

text: hit

text: non-smooth

text: parts

text: of

text: the

text: S

text: boundary

text: at

text: any

text: moment

text: t

text: Thus,

text: the

text: process

text: Z

text: a.s.

text: does

text: not

text: hit

text: non-smooth

text: parts

text: of

text: the

text: boundary

text: ∂S

text: at

text: any

text: moment

text: t

text: Lemma

text: Take

text: an

text: SRBM

text: in

text: the

text: orthant

text: S,

text: starting

text: from

text: x

text: S

text: ∂S.

text: Suppose

text: it

text: satisﬁes

text: the

text: condition

text: Then

text: the

text: statement

text: of

text: Theorem

text: is

text: true.

text: M

text: Proof.

text: Let

text: us

text: ﬁnd

text: another

text: reﬂection

text: nonsingular

text: -matrix

text: R˜

text: (r˜

text: such

text: that

text: R

text: R˜,

text: and

text: ij

text: i,j

text: d

text: the

text: skew-symmetry

text: condition

text: is

text: true

text: for

text: an

text: SRBMd(R˜,

text: A).

text: We

text: need:

text: r˜

text: a

text: r˜

text: a

text: i,

text: j

text: d.

text: ij

text: jj

text: ji

text: ii

text: ij

text: Let

text: r˜

text: for

text: i

text: j.

text: Then

text: is

text: true

text: for

text: i

text: j.

text: Let

text: ij

text: r˜

text: r

text: a

text: r˜

text: r

text: i

text: j

text: d.

text: ij

text: ij

text: ji

text: ii

text: ji

text: ji

text: a

text: jj

text: This

text: is

text: well

text: deﬁned,

text: since

text: a

text: (because

text: the

text: matrix

text: A

text: is

text: positive

text: deﬁnite).

text: Also,

text: r˜

text: r

text: jj

text: Z

text: ij

text: ij

text: because

text: r

text: a

text: r

text: a

text: Since

text: r˜

text: r

text: for

text: i

text: j,

text: R˜

text: is

text: a

text: -matrix,

text: so

text: condition

text: ij

text: jj

text: ji

text: ii

text: ij

text: ij

text: ij

text: M

text: holds.

text: Therefore,

text: by

text: Theorem

text: (compare

text: conditions

text: and

text: R˜

text: is

text: a

text: nonsingular

text: matrix.

text: Consider

text: two

text: processes

text: Z

text: SRBMd(R,

text: µ,

text: A),

text: Z˜

text: SRBMd(R˜,

text: µ,

text: A),

text: starting

text: from

text: the

text: M

text: same

text: initial

text: condition

text: x

text: S

text: ∂S.

text: Then

text: we

text: have:

text: R

text: and

text: R˜

text: are

text: d

text: d

text: reﬂection

text: nonsingular

text: matrices,

text: and

text: R

text: R˜.

text: By

text: Proposition

text: we

text: have:

text: Z˜

text: is

text: stochastically

text: smaller

text: than

text: Z.

text: By

text: Theorem

text: we

text: can

text: claim

text: that

text: a.s.

text: for

text: all

text: t

text: we

text: have:

text: Z˜(t)

text: Z(t)

text: (possibly

text: after

text: changing

text: the

text: probability

text: space).

text: By

text: Lemma

text: the

text: process

text: Z˜

text: a.s.

text: does

text: not

text: hit

text: non-smooth

text: parts

text: of

text: the

text: boundary

text: at

text: any

text: time

text: t

text: In

text: other

text: words,

text: for

text: every

text: i

text: j

text: d,

text: we

text: have:

text: a.s.

text: Z˜

text: (t)+Z˜

text: (t)

text: i

text: j

text: for

text: all

text: t

text: Therefore,

text: a.s.

text: Z

text: (t)

text: Z

text: (t)

text: for

text: all

text: t

text: Thus,

text: with

text: probability

text: one

text: the

text: process

text: i

text: j

text: Z

text: does

text: not

text: hit

text: non-smooth

text: parts

text: of

text: the

text: boundary

text: at

text: any

text: time

text: t

text: Now,

text: let

text: us

text: prove

text: part

text: (ii)

text: of

text: Theorem

text: We

text: start

text: with

text: the

text: case

text: d

text: then

text: move

text: to

text: the

text: general

text: case.

text: Lemma

text: Suppose

text: we

text: start

text: an

text: SRBM

text: in

text: two

text: dimensions

text: from

text: a

text: point

text: x

text: S

text: ∂S

text: in

text: the

text: interior

text: of

text: S.

text: Then

text: the

text: statement

text: of

text: Theorem

text: (ii)

text: is

text: valid.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: TRIPLE AND SIMULTANEOUS COLLISIONS OF COMPETING BROWNIAN PARTICLES 27 The third term in the last sum is nondecreasing. Indeed, for each j = 1, . . . , m, the process L is ∈ P · ∇ ≥ j nondecreasing, and it can increase only when Z(s) . But in this case, v f(Z(s)) 0. The j j rest is trivial. Acknoweldgements I would like to thank Ioannis Karatzas, Soumik Pal and Ruth Williams, as well as an anonymous referee, for help and useful discussion. This research was partially supported by NSF grants DMS 1007563, DMS 1308340, and DMS 1405210. References [1] Adrian D. Banner, Robert Fernholz, Tomoyuki Ichiba, Ioannis Karatzas, and Vassilios Papathanakos. Hybrid atlas models. Ann. Appl. Probab., 21(2):609–644, 2011. [2] Adrian D. Banner, Robert Fernholz, and Ioannis Karatzas. Atlas models of equity markets. Ann. Appl. Probab., 15(4):2296– 2330, 2005. [3] Adrian D. Banner and Raouf Ghomrasni. Local times of ranked continuous semimartingales. Stochastic Process. Appl., 118(7):1244–1253, 2008. [4] R. F. Bass and E´. Pardoux. Uniqueness for diﬀusions with piecewise constant coeﬃcients. Probab. Theory Related Fields, 76(4):557–572, 1987. [5] Andrei N. Borodin and Paavo Salminen. Handbook of Brownian motion—facts and formulae. Probability and its Applica- tions. Birkh¨auser Verlag, Basel, second edition, 2002. [6] Maury Bramson, J. G. Dai, and J. Michael Harrison. Positive recurrence of reﬂecting Brownian motion in three dimensions. Ann. Appl. Probab., 20(2):753–783, 2010. [7] Amarjit Budhiraja and Chihoon Lee. Long time asymptotics for constrained diﬀusions in polyhedral domains. Stochastic Process. Appl., 117(8):1014–1036, 2007. [8] Emmanuel C´epa and Dominique L´epingle. Diﬀusing particles with electrostatic repulsion. Probability Theory and Related Fields, 107(4):429–449, 1997. [9] Sourav Chatterjee and Soumik Pal. A phase transition behavior for Brownian motions interacting through their ranks. Probab. Theory Related Fields, 147(1-2):123–159, 2010. [10] Hong Chen. A suﬃcient condition for the positive recurrence of a semimartingale reﬂecting Brownian motion in an orthant. Ann. Appl. Probab., 6(3):758–765, 1996. [11] J. G. Dai and J. Michael Harrison. Reﬂected Brownian motion in an orthant: numerical methods for steady-state analysis. Ann. Appl. Probab., 2(1):65–86, 1992. [12] J. G. Dai and J. Michael Harrison. Reﬂecting Brownian motion in three dimensions: a new proof of suﬃcient conditions for positive recurrence. Math. Methods Oper. Res., 75(2):135–147, 2012. [13] J. G. Dai and Thomas Kurtz. Characterization of the stationary distribution for a semimartingale reﬂecting brownian motion in a convex polyhedron. 2003. Unpublished Manuscript. [14] J. G. Dai and R.J. Williams. Existence and uniqueness of semimartingale reﬂecting Brownian motions in convex polyhedra. Teor. Veroyatnost. i Primenen., 40(1):3–53, 1995. [15] Paul Dupuis and R.J. Williams. Lyapunov functions for semimartingale reﬂecting Brownian motions. Ann. Probab., 22(2):680–702, 1994. [16] Robert Fernholz. Stochastic portfolio theory, volume 48 of Applications of Mathematics (New York). Springer-Verlag, New York, 2002. Stochastic Modelling and Applied Probability. [17] Robert Fernholz, Tomoyuki Ichiba, and Ioannis Karatzas. A second-order stock market model. Annals of Finance, 9(3):439– 454, 2013. [18] Robert Fernholz, Tomoyuki Ichiba, and Ioannis Karatzas. Two Brownian particles with rank-based characteristics and skew-elastic collisions. Stochastic Process. Appl., 123(8):2999–3026, 2013. [19] Robert Fernholz and Ioannis Karatzas. Stochastic portfolio theory: an overview. Handbook of Numerical Analysis, 15:89– 167, 2009. [20] Patrik L. Ferrari, Herbert Spohn, and Thomas Weiss. Scaling limit for brownian motions with one-sided collisions. 2013. Preprint. Avaliable at arXiv:1306.5095. [21] Avner Friedman. Nonattainability of a set by a diﬀusion process. Trans. Amer. Math. Soc., 197:245–271, 1974. [22] Avner Friedman. Stochastic diﬀerential equations and applications. Dover Publications, Inc., Mineola, NY, 2006. Two volumes bound as one, Reprint of the 1975 and 1976 original published in two volumes. [23] Jean-Paul Haddad, Ravi R. Mazumdar, and Francisco J. Piera. Pathwise comparison results for stochastic ﬂuid networks. Queueing Syst., 66(2):155–168, 2010. [24] J. Michael Harrison. The diﬀusion approximation for tandem queues in heavy traﬃc. Adv. in Appl. Probab., 10(4):886–905, 1978.

text: TRIPLE

text: AND

text: SIMULTANEOUS

text: COLLISIONS

text: OF

text: COMPETING

text: BROWNIAN

text: PARTICLES

text: The

text: third

text: term

text: in

text: the

text: last

text: sum

text: is

text: nondecreasing.

text: Indeed,

text: for

text: each

text: j

text: m,

text: the

text: process

text: L

text: is

text: P

text: j

text: nondecreasing,

text: and

text: it

text: can

text: increase

text: only

text: when

text: Z(s)

text: But

text: in

text: this

text: case,

text: v

text: f(Z(s))

text: The

text: j

text: j

text: rest

text: is

text: trivial.

text: Acknoweldgements

text: I

text: would

text: like

text: to

text: thank

text: Ioannis

text: Karatzas,

text: Soumik

text: Pal

text: and

text: Ruth

text: Williams,

text: as

text: well

text: as

text: an

text: anonymous

text: referee,

text: for

text: help

text: and

text: useful

text: discussion.

text: This

text: research

text: was

text: partially

text: supported

text: by

text: NSF

text: grants

text: DMS

text: DMS

text: and

text: DMS

text: References

text: Adrian

text: D.

text: Banner,

text: Robert

text: Fernholz,

text: Tomoyuki

text: Ichiba,

text: Ioannis

text: Karatzas,

text: and

text: Vassilios

text: Papathanakos.

text: Hybrid

text: atlas

text: models.

text: Ann.

text: Appl.

text: Probab.,

text: Adrian

text: D.

text: Banner,

text: Robert

text: Fernholz,

text: and

text: Ioannis

text: Karatzas.

text: Atlas

text: models

text: of

text: equity

text: markets.

text: Ann.

text: Appl.

text: Probab.,

text: Adrian

text: D.

text: Banner

text: and

text: Raouf

text: Ghomrasni.

text: Local

text: times

text: of

text: ranked

text: continuous

text: semimartingales.

text: Stochastic

text: Process.

text: Appl.,

text: R.

text: F.

text: Bass

text: and

text: E´.

text: Pardoux.

text: Uniqueness

text: for

text: diﬀusions

text: with

text: piecewise

text: constant

text: coeﬃcients.

text: Probab.

text: Theory

text: Related

text: Fields,

text: Andrei

text: N.

text: Borodin

text: and

text: Paavo

text: Salminen.

text: Handbook

text: of

text: Brownian

text: motion—facts

text: and

text: formulae.

text: Probability

text: and

text: its

text: Applica-

text: tions.

text: Birkh¨auser

text: Verlag,

text: Basel,

text: second

text: edition,

text: Maury

text: Bramson,

text: J.

text: G.

text: Dai,

text: and

text: J.

text: Michael

text: Harrison.

text: Positive

text: recurrence

text: of

text: reﬂecting

text: Brownian

text: motion

text: in

text: three

text: dimensions.

text: Ann.

text: Appl.

text: Probab.,

text: Amarjit

text: Budhiraja

text: and

text: Chihoon

text: Lee.

text: Long

text: time

text: asymptotics

text: for

text: constrained

text: diﬀusions

text: in

text: polyhedral

text: domains.

text: Stochastic

text: Process.

text: Appl.,

text: Emmanuel

text: C´epa

text: and

text: Dominique

text: L´epingle.

text: Diﬀusing

text: particles

text: with

text: electrostatic

text: repulsion.

text: Probability

text: Theory

text: and

text: Related

text: Fields,

text: Sourav

text: Chatterjee

text: and

text: Soumik

text: Pal.

text: A

text: phase

text: transition

text: behavior

text: for

text: Brownian

text: motions

text: interacting

text: through

text: their

text: ranks.

text: Probab.

text: Theory

text: Related

text: Fields,

text: Hong

text: Chen.

text: A

text: suﬃcient

text: condition

text: for

text: the

text: positive

text: recurrence

text: of

text: a

text: semimartingale

text: reﬂecting

text: Brownian

text: motion

text: in

text: an

text: orthant.

text: Ann.

text: Appl.

text: Probab.,

text: J.

text: G.

text: Dai

text: and

text: J.

text: Michael

text: Harrison.

text: Reﬂected

text: Brownian

text: motion

text: in

text: an

text: orthant:

text: numerical

text: methods

text: for

text: steady-state

text: analysis.

text: Ann.

text: Appl.

text: Probab.,

text: J.

text: G.

text: Dai

text: and

text: J.

text: Michael

text: Harrison.

text: Reﬂecting

text: Brownian

text: motion

text: in

text: three

text: dimensions:

text: a

text: new

text: proof

text: of

text: suﬃcient

text: conditions

text: for

text: positive

text: recurrence.

text: Math.

text: Methods

text: Oper.

text: Res.,

text: J.

text: G.

text: Dai

text: and

text: Thomas

text: Kurtz.

text: Characterization

text: of

text: the

text: stationary

text: distribution

text: for

text: a

text: semimartingale

text: reﬂecting

text: brownian

text: motion

text: in

text: a

text: convex

text: polyhedron.

text: Unpublished

text: Manuscript.

text: J.

text: G.

text: Dai

text: and

text: R.J.

text: Williams.

text: Existence

text: and

text: uniqueness

text: of

text: semimartingale

text: reﬂecting

text: Brownian

text: motions

text: in

text: convex

text: polyhedra.

text: Teor.

text: Veroyatnost.

text: i

text: Primenen.,

text: Paul

text: Dupuis

text: and

text: R.J.

text: Williams.

text: Lyapunov

text: functions

text: for

text: semimartingale

text: reﬂecting

text: Brownian

text: motions.

text: Ann.

text: Probab.,

text: Robert

text: Fernholz.

text: Stochastic

text: portfolio

text: theory,

text: volume

text: of

text: Applications

text: of

text: Mathematics

text: (New

text: York).

text: Springer-Verlag,

text: New

text: York,

text: Stochastic

text: Modelling

text: and

text: Applied

text: Probability.

text: Robert

text: Fernholz,

text: Tomoyuki

text: Ichiba,

text: and

text: Ioannis

text: Karatzas.

text: A

text: second-order

text: stock

text: market

text: model.

text: Annals

text: of

text: Finance,

text: Robert

text: Fernholz,

text: Tomoyuki

text: Ichiba,

text: and

text: Ioannis

text: Karatzas.

text: Two

text: Brownian

text: particles

text: with

text: rank-based

text: characteristics

text: and

text: skew-elastic

text: collisions.

text: Stochastic

text: Process.

text: Appl.,

text: Robert

text: Fernholz

text: and

text: Ioannis

text: Karatzas.

text: Stochastic

text: portfolio

text: theory:

text: an

text: overview.

text: Handbook

text: of

text: Numerical

text: Analysis,

text: Patrik

text: L.

text: Ferrari,

text: Herbert

text: Spohn,

text: and

text: Thomas

text: Weiss.

text: Scaling

text: limit

text: for

text: brownian

text: motions

text: with

text: one-sided

text: collisions.

text: Preprint.

text: Avaliable

text: at

text: Avner

text: Friedman.

text: Nonattainability

text: of

text: a

text: set

text: by

text: a

text: diﬀusion

text: process.

text: Trans.

text: Amer.

text: Math.

text: Soc.,

text: Avner

text: Friedman.

text: Stochastic

text: diﬀerential

text: equations

text: and

text: applications.

text: Dover

text: Publications,

text: Inc.,

text: Mineola,

text: NY,

text: Two

text: volumes

text: bound

text: as

text: one,

text: Reprint

text: of

text: the

text: and

text: original

text: published

text: in

text: two

text: volumes.

text: Jean-Paul

text: Haddad,

text: Ravi

text: R.

text: Mazumdar,

text: and

text: Francisco

text: J.

text: Piera.

text: Pathwise

text: comparison

text: results

text: for

text: stochastic

text: ﬂuid

text: networks.

text: Queueing

text: Syst.,

text: J.

text: Michael

text: Harrison.

text: The

text: diﬀusion

text: approximation

text: for

text: tandem

text: queues

text: in

text: heavy

text: traﬃc.

text: Adv.

text: in

text: Appl.

text: Probab.,


text: (cid:80) − − Since f and g are continuously differentiable, the Fritz-John where the inequality is because 1 α < 0 and (K 1 + ∗ − (cid:31) necessary conditions [20, Deﬁnition 5.2.1] hold: there exist L B ) 1 0. This completes the proof of the existence ≥ ∗ i=1 i µ, λ 0 for the local minima b such that of KKT conditions for the non-convex optimization problem RBT (d). − ∇ ∗ ∇ ∗ ∈ ∗ ∗ (µ f(b ) + λ g(b )) TB(b ) , (87) APPENDIX C PROOF OF INEQUALITY (b) IN (73) ∗ B ∗ ∗ ∗ We shall show that where TB(b ) is the tangent cone of at b and TB(b ) is its polar cone. A∗s ∗B∩i, i = ∗1,∗2∩, . .· .· ,· L∩ are ∗no∗nempty convex sets such that J(X|Mi+(cid:88)1, . .(cid:0). , ML) (cid:1) ri(b ) ri(b ) ri(b ) is nonempty, it follows [20, Prob1lem 4.23]2 and [20, PropoLsition 4.63] that (cid:22)K−1 + L Σ−1 − Σ−1 cov(Y |X, M , Q)Σ−1 (90) j j j j j ∗ ∗ ∗ ∗ ∗ ∗ · · · ∗ ∗ TB(b ) = TB (b ) + TB (b ) + + TB (b ) . j=i+1 1 2 L (cid:88) Note that As in [13, Section B], it can be veriﬁed that L (cid:44) ∗ ∗ ∩ A ⊆ { − X = AjYj + Z X¯ + Z, TB (b ) column concatenation of (O, . . . , Ψ , i (cid:23) { ∗} } i j=i+1 . . . , O) : Ψi 0, tr ΨiBi = 0 (88) where Z(cid:80)is a Gaussian random vector, independent of (cid:44) (Y , . . . , Y ), with mean zero and covariance matrix K in which A is the set of vectors constructed by concatenating (Ki−+11 + Lj=Li+1 Σ−j 1)−1, and Aj (cid:44) KZΣ−j 1. UsingZthe complementary relationship between Fisher information and the columns of L symmetric matrices. A MSE in Lemma 2, we have Since l.h.s of equation (87) is also in , to complete the proof of the existence of KKT conditions, we need to show µ (cid:54)= 0. As in [11, Appendix IV], we will verify the constraint J(X|M , . . . , M ) i+1 L qualiﬁcations (CQ5a in [20, Section 5.4]), i.e., there exists a ((cid:22)a) | vector J(X M , . . . , M , Q) i+1 L | d ∈ TB(b∗) = TB (b∗) ∩ TB (b∗) ∩ · · · ∩ TB (b∗), =J(X¯ + Z Mi+1, . . . , ML, Q) such that ∇g(b∗)T d <10. 2 L =K−Z1 − K(cid:88)−Z1 cov(X¯ |X¯ + Z, Mi+1, . . . , ML, Q)K−Z1 Given any α > 1, l(cid:18)et’s deﬁne a set of m(cid:19)2 × 1 vectors (=b)K−Z1 − (cid:88)L Σ(cid:0) −j 1 cov(Yj|X, Mj, Q)Σ−j 1 (cid:1) − j=i+1 b = vec (B ) (cid:44) vec αB∗ + α 1K−1 , i = 1, 2, . . . , L. − L − − − | − i i i L =K 1 + Σj 1 Σj 1 cov(Yj X, Mj, Q)Σj 1 , (89) j=i+1 (91) · Here vec( ) is the vectorization operator. It can be seen that b ∈ B since B (cid:23) 0. We denote d = b −(b∗) , where (b∗) where (a) is from the data processing inequality in Lemma daneindo[t2es0i ,thPeroitphosLiit-icoonm4p.o6n.2e]n,tswien hba∗iv.eBdyii[2∈0,TDBeiiﬁ(bn∗it)i.onN4o.w6.1di] 4(Yajn,dM(bj)) ↔is d(uXe,tQo)th↔e f(aYct{jth}ca,tMfo{rj}acn)yhjo,ldths.e Markov chain can be constructed by REFERENCES d = vec(d , d , . . . , d ). 1 2 L [1] T. Berger, Z. Zhang, and H. Viswanathan, “The CEO problem,” IEEE ∇ ∗ In this w(cid:40)ay, the expression of g(b )T d(cid:41)can be written as Trans. Inf. Theory, vol. 42, no. 3, pp. 887 –902, May 1996. (cid:88) (cid:88) [2] Y. Oohama, “The rate-distortion function for the quadratic Gaussian CEO problem,” IEEE Trans. Inf. Theory, vol. 43, no. 11, pp. 1912 – 1923, Nov. 1997. (cid:88)L tr (cid:40)(K−1 + (cid:88)L B∗i )−2 ((cid:18)B∗i − Bi) (cid:19)(cid:41) [3] —sys—te,m“sRwatieth-dsisetvoerrtaiolnsitdheeoinryfofromraGtioaunsasitatnhemdueltciotedremr,i”naIEl EsoEurTcreancso.dIinnfg. i=1 i=1 Theory, vol. 51, no. 7, pp. 2577 –2593, Jul. 2005. L (cid:40)− L ∗ − (cid:41)− ∗ − α − 1 − [4] V. Prabhakaran, D. Tse, and K. Ramachandran, “Rate region of the = tr (K 1 + (cid:88)B ) 2 (1 α)B K 1 quadratic Gaussian CEO problem,” in Proc. IEEE Int. Symp. Inf. Theory, i i L Jun. 2004, p. 119. i=1 i=1 [5] S. Tavildar and P. Viswanath, “On the sum-rate of the vector Gaussian − − L ∗ − CEO problem,” in Proc. 39th Asilomar Conf. on Signal, Syst. and =(1 α) tr (K 1 + B ) 1 Comput., 2005, pp. 3–7. i [6] G. Zhang and W. Kleijn, “Bounding the rate region of the two-terminal i=1 vector Gaussian CEO problem,” in Proc. Data Comp. Conf., Mar. 2011, < 0, p. 488. [7] J. Chen and J. Wang, “On the vector Gaussian CEO problem,” in Proc. IEEE Int. Symp. Inf. Theory, Aug. 2011, pp. 2050 –2054. 13 ##LTLine## ##LTLine##

text: Since

text: f

text: and

text: g

text: are

text: continuously

text: differentiable,

text: the

text: Fritz-John

text: where

text: the

text: inequality

text: is

text: because

text: α

text: and

text: (K

text: necessary

text: conditions

text: Deﬁnition

text: hold:

text: there

text: exist

text: L

text: B

text: This

text: completes

text: the

text: proof

text: of

text: the

text: existence

text: i

text: µ,

text: λ

text: for

text: the

text: local

text: minima

text: b

text: such

text: that

text: of

text: KKT

text: conditions

text: for

text: the

text: non-convex

text: optimization

text: problem

text: RBT

text: (d).

text: (µ

text: f(b

text: λ

text: g(b

text: TB(b

text: APPENDIX

text: C

text: PROOF

text: OF

text: INEQUALITY

text: (b)

text: IN

text: B

text: We

text: shall

text: show

text: that

text: where

text: TB(b

text: is

text: the

text: tangent

text: cone

text: of

text: at

text: b

text: and

text: TB(b

text: is

text: its

text: polar

text: cone.

text: A∗s

text: ∗B∩i,

text: i

text: L∩

text: are

text: ∗no∗nempty

text: convex

text: sets

text: such

text: that

text: ML)

text: ri(b

text: ri(b

text: ri(b

text: is

text: nonempty,

text: it

text: follows

text: and

text: PropoLsition

text: that

text: L

text: Σ−1

text: Σ−1

text: cov(Y

text: |X,

text: M

text: j

text: j

text: j

text: j

text: j

text: TB(b

text: TB

text: (b

text: TB

text: (b

text: TB

text: (b

text: L

text: Note

text: that

text: As

text: in

text: Section

text: B],

text: it

text: can

text: be

text: veriﬁed

text: that

text: L

text: A

text: X

text: AjYj

text: Z

text: X¯

text: Z,

text: TB

text: (b

text: column

text: concatenation

text: of

text: (O,

text: Ψ

text: i

text: i

text: O)

text: Ψi

text: tr

text: ΨiBi

text: where

text: a

text: Gaussian

text: random

text: vector,

text: independent

text: of

text: (Y

text: Y

text: with

text: mean

text: zero

text: and

text: covariance

text: matrix

text: K

text: in

text: which

text: A

text: is

text: the

text: set

text: of

text: vectors

text: constructed

text: by

text: concatenating

text: Σ−j

text: and

text: Aj

text: KZΣ−j

text: UsingZthe

text: complementary

text: relationship

text: between

text: Fisher

text: information

text: and

text: the

text: columns

text: of

text: L

text: symmetric

text: matrices.

text: A

text: MSE

text: in

text: Lemma

text: we

text: have

text: Since

text: l.h.s

text: of

text: equation

text: is

text: also

text: in

text: to

text: complete

text: the

text: proof

text: of

text: the

text: existence

text: of

text: KKT

text: conditions,

text: we

text: need

text: to

text: show

text: µ

text: As

text: in

text: Appendix

text: IV],

text: we

text: will

text: verify

text: the

text: constraint

text: J(X|M

text: M

text: L

text: qualiﬁcations

text: in

text: Section

text: i.e.,

text: there

text: exists

text: a

text: vector

text: J(X

text: M

text: M

text: Q)

text: L

text: d

text: TB(b∗)

text: TB

text: (b∗)

text: TB

text: (b∗)

text: TB

text: (b∗),

text: =J(X¯

text: Z

text: ML,

text: Q)

text: such

text: that

text: ∇g(b∗)T

text: d

text: L

text: cov(X¯

text: |X¯

text: Z,

text: ML,

text: Given

text: any

text: α

text: deﬁne

text: a

text: set

text: of

text: vectors

text: −j

text: cov(Yj|X,

text: Mj,

text: Q)Σ−j

text: b

text: vec

text: (B

text: vec

text: αB∗

text: α

text: i

text: L.

text: L

text: i

text: i

text: i

text: L

text: =K

text: Σj

text: Σj

text: cov(Yj

text: X,

text: Mj,

text: Q)Σj

text: Here

text: vec(

text: is

text: the

text: vectorization

text: operator.

text: It

text: can

text: be

text: seen

text: that

text: b

text: B

text: since

text: B

text: We

text: denote

text: d

text: b

text: −(b∗)

text: where

text: (b∗)

text: where

text: (a)

text: is

text: from

text: the

text: data

text: processing

text: inequality

text: in

text: Lemma

text: ↔is

text: d(uXe,tQo)th↔e

text: f(aYct{jth}ca,tMfo{rj}acn)yhjo,ldths.e

text: Markov

text: chain

text: can

text: be

text: constructed

text: by

text: REFERENCES

text: d

text: vec(d

text: d

text: d

text: L

text: T.

text: Berger,

text: Z.

text: Zhang,

text: and

text: H.

text: Viswanathan,

text: “The

text: CEO

text: problem,”

text: IEEE

text: In

text: this

text: the

text: expression

text: of

text: g(b

text: )T

text: be

text: written

text: as

text: Trans.

text: Inf.

text: Theory,

text: vol.

text: no.

text: pp.

text: May

text: Y.

text: Oohama,

text: “The

text: rate-distortion

text: function

text: for

text: the

text: quadratic

text: Gaussian

text: CEO

text: problem,”

text: IEEE

text: Trans.

text: Inf.

text: Theory,

text: vol.

text: no.

text: pp.

text: Nov.

text: tr

text: B∗i

text: Bi)

text: EsoEurTcreancso.dIinnfg.

text: Theory,

text: vol.

text: no.

text: pp.

text: Jul.

text: L

text: L

text: α

text: V.

text: Prabhakaran,

text: D.

text: Tse,

text: and

text: K.

text: Ramachandran,

text: “Rate

text: region

text: of

text: the

text: tr

text: (K

text: α)B

text: K

text: quadratic

text: Gaussian

text: CEO

text: problem,”

text: in

text: Proc.

text: IEEE

text: Int.

text: Symp.

text: Inf.

text: Theory,

text: i

text: i

text: L

text: Jun.

text: p.

text: S.

text: Tavildar

text: and

text: P.

text: Viswanath,

text: “On

text: the

text: sum-rate

text: of

text: the

text: vector

text: Gaussian

text: L

text: CEO

text: problem,”

text: in

text: Proc.

text: Asilomar

text: Conf.

text: on

text: Signal,

text: Syst.

text: and

text: α)

text: tr

text: (K

text: B

text: Comput.,

text: pp.

text: i

text: G.

text: Zhang

text: and

text: W.

text: Kleijn,

text: “Bounding

text: the

text: rate

text: region

text: of

text: the

text: two-terminal

text: vector

text: Gaussian

text: CEO

text: problem,”

text: in

text: Proc.

text: Data

text: Comp.

text: Conf.,

text: Mar.

text: p.

text: J.

text: Chen

text: and

text: J.

text: Wang,

text: “On

text: the

text: vector

text: Gaussian

text: CEO

text: problem,”

text: in

text: Proc.

text: IEEE

text: Int.

text: Symp.

text: Inf.

text: Theory,

text: Aug.

text: pp.

text: ##LTLine##

text: ##LTLine##


text: (cid:80) In view of (29), e , e , . . . , e are also the eigen- (cid:31) (cid:22) veiegcetonvrsaluoefs mbeaitnrigx dCnn12+1+1=1, dnn1(+K1+2−2, .1. +. , dmm.Lj=O2nBt∗jh)e−o1thwerithhanthde, WW11TT ∆C22WW11 (cid:23) 00;; VV2T2TC∆22VV22(cid:23) 00;; WW1T1TC∆22VV22==00.; ((3356)) we can conclude that We can further reﬁne the spectral decomposition form of UT1 C2V1 = UT1 C1V1 = 0. (30) ∆ and C : 2 2 Subtracting (12) from the ﬁrst equation in KKT conditions ∆ = U UT ∆ U UT + V VT ∆ V VT (13) and invoking (20) gives 2 1 1 2 1 1 1 1 2 1 1 − =U1UT1 ∆2U1UT1 + W1W1T ∆2W1W1T µ µ ∆2 = 1 2 2 C2 + ∆1. (31) + V2V2T ∆2V2V2T (37) Combining equations (30) and (31) with UT ∆ V = 0, 1 1 1 we see C = U UT C U UT + V VT C V VT 2 2 2 2 2 2 2 2 2 2 2 UT1 ∆2V1 = 0. (32) =U1UT1 C2U1UT1 + W1W1T C2W1W1T + V2V2T C2V2(V382T) Thus we may give matrix ∆2 the following spectral repre- Following the similar steps as in the derivation of (26), we sentation: obtain ∆2 = U1UT1 ∆2U1UT1 + V1V1T ∆2V1V1T . (33) B∗2V2 = 0. (39) (cid:31) From equation (31), we have ∆ ∆ and consequently 2 1 (cid:31) (cid:31) VT C V = VT C V . (40) UT ∆ U UT ∆ U 0. 2 2 2 2 3 2 1 2 1 1 1 1 On the other hand, Repeating this procedure L times yields the following theorem. R =Vµ11(cid:88)V−2 1Tµ∆2 V2V1V1V1T C1T 2V1V1T +(cid:16)V1V1T ∆1V1V(cid:17) 1T t{hWoTgh1oe,noWarle2mm, .a2.tr:.i,cIWens1L:−m{1,U},t1hs,euUrec2h,e.xt.his.at,tUtthhLree}e,fo{sleVltos1w,oiVnfg2c,op.l.ruo.mp, VenrtLoie}rs-, − hold: = (cid:88)m (cid:18)µ1 2 µ2 dnene(cid:19)Tn + λd2n − µ21 dn eneTn 1) [Spectrum of Ci] n=n1+1 m − d = λd2 µ n e eT . (34) C = U UT C U UT + V VT C V VT , i = 1, . . . , L. n 2 2 n n i i i i i i i i i i i (41) n=n1+1 Now we are at the same situation as treating equation (21), and 2) [Spectrum of ∆ ] i correspondingly the reﬁned spectral representation of matrix ∆ can be obtained through a procedure similar to that for 2 ∆ = U UT ∆ U UT + V VT ∆ V VT , (42) ∆ . Here we may divide the subspace spanned by the column 1 1 1 1 1 1 1 1 1 1 1 1 vector of V into two orthogonal subspaces, according to the 1 − sign of ∆ ’s eigenvalues λd2 µ d /2, n = n + 1, n + 2 n 2 n 1 1 × 2, . . . , m. Speciﬁcally, we partition the matrix V into a m (n − n ) matrix W (cid:44) (e , e , . . . , e 1) and a m × ∆i+1 = UiUTi ∆i+1UiUTi + ViViT ∆i+1ViViT (m2− n21) matrix V21(cid:44) (en2n+1+1,1en2n+1+2,2. . . , emn)2, in which n2 = UiUTi ∆i+1UiUTi + WiWiT ∆i+1WiWiT represents the critical number such that + V VT ∆ V VT , − ≤ i+1 i+1 i+1 i+1 i+1 − λd2 µ d /2 > 0, n < n n i = 1, . . . , L 1. n 2 n 1 2 (43) − ≤ ≤ λd2 µ d /2 0, n < n m. n 2 n 2 3) [Positive/Negative deﬁniteness] On the other hand, combining U and W will form a new × (cid:44) 1 1 m n2 matrix U2 (e1, e2, . . . , en2). It is straightforward 1 One m×n dimensional (m ≥ n) matrix A is called column orthogonal to verify that iff ATA = I. 5 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: In

text: view

text: of

text: e

text: e

text: e

text: are

text: also

text: the

text: eigen-

text: veiegcetonvrsaluoefs

text: mbeaitnrigx

text: we

text: can

text: conclude

text: that

text: We

text: can

text: further

text: reﬁne

text: the

text: spectral

text: decomposition

text: form

text: of

text: and

text: C

text: Subtracting

text: from

text: the

text: ﬁrst

text: equation

text: in

text: KKT

text: conditions

text: U

text: UT

text: U

text: UT

text: V

text: VT

text: V

text: VT

text: and

text: invoking

text: gives

text: µ

text: µ

text: ∆2

text: Combining

text: equations

text: and

text: with

text: UT

text: V

text: we

text: see

text: C

text: U

text: UT

text: C

text: U

text: UT

text: V

text: VT

text: C

text: V

text: VT

text: Thus

text: we

text: may

text: give

text: matrix

text: ∆2

text: the

text: following

text: spectral

text: repre-

text: Following

text: the

text: similar

text: steps

text: as

text: in

text: the

text: derivation

text: of

text: we

text: sentation:

text: obtain

text: ∆2

text: From

text: equation

text: we

text: have

text: and

text: consequently

text: VT

text: C

text: V

text: VT

text: C

text: V

text: UT

text: U

text: UT

text: U

text: On

text: the

text: other

text: hand,

text: Repeating

text: this

text: procedure

text: L

text: times

text: yields

text: the

text: following

text: theorem.

text: R

text: VenrtLoie}rs-,

text: hold:

text: µ2

text: dn

text: eneTn

text: [Spectrum

text: of

text: Ci]

text: m

text: d

text: µ

text: n

text: e

text: eT

text: C

text: U

text: UT

text: C

text: U

text: UT

text: V

text: VT

text: C

text: V

text: VT

text: i

text: L.

text: n

text: n

text: n

text: i

text: i

text: i

text: i

text: i

text: i

text: i

text: i

text: i

text: i

text: i

text: Now

text: we

text: are

text: at

text: the

text: same

text: situation

text: as

text: treating

text: equation

text: and

text: [Spectrum

text: of

text: i

text: correspondingly

text: the

text: reﬁned

text: spectral

text: representation

text: of

text: matrix

text: can

text: be

text: obtained

text: through

text: a

text: procedure

text: similar

text: to

text: that

text: for

text: U

text: UT

text: U

text: UT

text: V

text: VT

text: V

text: VT

text: Here

text: we

text: may

text: divide

text: the

text: subspace

text: spanned

text: by

text: the

text: column

text: vector

text: of

text: V

text: into

text: two

text: orthogonal

text: subspaces,

text: according

text: to

text: the

text: sign

text: of

text: ’s

text: eigenvalues

text: µ

text: d

text: n

text: n

text: n

text: n

text: n

text: m.

text: Speciﬁcally,

text: we

text: partition

text: the

text: matrix

text: V

text: into

text: a

text: m

text: (n

text: n

text: matrix

text: W

text: (e

text: e

text: e

text: and

text: a

text: m

text: UiUTi

text: ViViT

text: matrix

text: in

text: which

text: UiUTi

text: WiWiT

text: represents

text: the

text: critical

text: number

text: such

text: that

text: V

text: VT

text: V

text: VT

text: µ

text: d

text: n

text: n

text: n

text: i

text: L

text: n

text: n

text: µ

text: d

text: n

text: n

text: m.

text: n

text: n

text: [Positive/Negative

text: deﬁniteness]

text: On

text: the

text: other

text: hand,

text: combining

text: U

text: and

text: W

text: will

text: form

text: a

text: new

text: m

text: matrix

text: It

text: is

text: straightforward

text: One

text: m×n

text: dimensional

text: (m

text: n)

text: matrix

text: A

text: is

text: called

text: column

text: orthogonal

text: to

text: verify

text: that

text: iff

text: ATA

text: I.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##