text: bound is strong in the sense that it holds for arbitrary graphs containing a forest of a given size. A Theorem 6 For any positive constant c and an adaptive deterministic c-correct algorithm that is able to ﬁnd spanning forests in simple graphs, and for any positive integer m that is suﬃciently large depending on c, and for any simple forest G with m edges, there is such a strategy of an A adversary to activate stations that forces algorithm to perform Ω(m log m) steps on the input G if run against the strategy. (cid:98) (cid:99) Proof: For the number m to be suﬃciently large, the property c < lg(m/4) suﬃces, as will be seen A in the proof, where lg x is the logarithm of x to base 2. We partition an execution of algorithm (cid:98) (cid:99) (cid:98) (cid:99) into m/8 stages, each lasting for lg(m/4) consecutive steps. The adversary activates at least two, and up to four, stations holding speciﬁc edges precisely at the start of each stage. The chosen stations and edges are to have the following property: none of these at least two edges is broadcast successfully during the stage when they are activated. ≤ (cid:98) (cid:99) Consider the beginning of the kth stage, where k m/8 , and suppose that during the previous − stages the execution has proceeded as required. In particular, a total of at most 4(k 1) stations (cid:98) (cid:99) have been activated, and none of the edges activated lg(m/4) steps ago, when the previous − stage k 1 started, has been heard by this step. The algorithm has not terminated yet because (cid:98) (cid:99) it is c-correct, the inequality c < lg(m/4) holds and the edges recently activated have to be in a spanning forest of the input. Prior to the beginning of a stage, we need a pool of passive stations holding edges to choose the ones to activate from. The speciﬁc fractions of m we use serve the purpose of the proof for the following reason: each stage has at most four new edges activated, for a total of m/2 edges after − m/8 stages, and before each stage there are at least m m/2 = m/2 edges to choose from. ≤ ≤ (cid:98) (cid:99) Let the next consecutive queries be Q , for 1 i lg(m/4) . They are determined uniquely i if we assume that there are no successful broadcasts of edges that have not been activated prior to this point. This property will be guaranteed by the construction. We proceed by considering sets ≤ ≤ (cid:98) (cid:99) S and E , for 0 i lg(m/4) . Initialize the set S to the IDs of the stations still passive at i i 0 this point, and the set E to the edges held by these stations. The sets S and E are determined 0 i i inductively. Suppose S and E have already been determined, then S and E are deﬁned | ∩ i| ≥ | |i ∩ i+1 i+1 − as follows. If Q S S /2, then set S := Q S , otherwise set S := Q S . | i+∩1 | ≥i | | i i+1 ∩i+1 i i+1 −i+1 i Similarly, if Q E E /2, then set E := Q E , otherwise set E := Q E . The i+1 i (cid:98) i (cid:99) i+1 i+1 i i+1 i+1 i sets S and E , for i = lg(m/4) , contain at least two elements each. Choose any two stations in i i the ﬁnal set S and any two stations in the ﬁnal set E to activate in the next stage. i i When the last stage has been completed, there are still at least two stations that have been activated prior to the last c steps and they hold edges that have to be in a spanning forest of the graph with edges held by all the stations active by this step. This means that the algorithm still (cid:3) needs to perform at least two more steps. Theorem 6 can be strengthened to hold for any graph that contains a forest of m edges, a proof is a straightforward modiﬁcation, details are omitted. Next we give a deterministic adaptive algorithm DetAdversarial, whose performance matches the lower bound of Theorem 6. The design principle under which it operates is similar to that of the adaptive algorithm for the static case. The main diﬀerence is that now new stations can wake up at arbitrary steps and they need to be incorporated into an execution. When a station is activated after the start of an execution, it pauses and listens to the channel until it hears a special update 18

text: bound

text: is

text: strong

text: in

text: the

text: sense

text: that

text: it

text: holds

text: for

text: arbitrary

text: graphs

text: containing

text: a

text: forest

text: of

text: a

text: given

text: size.

text: A

text: Theorem

text: For

text: any

text: positive

text: constant

text: c

text: and

text: an

text: adaptive

text: deterministic

text: c-correct

text: algorithm

text: that

text: is

text: able

text: to

text: ﬁnd

text: spanning

text: forests

text: in

text: simple

text: graphs,

text: and

text: for

text: any

text: positive

text: integer

text: m

text: that

text: is

text: suﬃciently

text: large

text: depending

text: on

text: c,

text: and

text: for

text: any

text: simple

text: forest

text: G

text: with

text: m

text: edges,

text: there

text: is

text: such

text: a

text: strategy

text: of

text: an

text: A

text: adversary

text: to

text: activate

text: stations

text: that

text: forces

text: algorithm

text: to

text: perform

text: Ω(m

text: log

text: m)

text: steps

text: on

text: the

text: input

text: G

text: if

text: run

text: against

text: the

text: strategy.

text: Proof:

text: For

text: the

text: number

text: m

text: to

text: be

text: suﬃciently

text: large,

text: the

text: property

text: c

text: suﬃces,

text: as

text: will

text: be

text: seen

text: A

text: in

text: the

text: proof,

text: where

text: lg

text: x

text: is

text: the

text: logarithm

text: of

text: x

text: to

text: base

text: We

text: partition

text: an

text: execution

text: of

text: algorithm

text: into

text: stages,

text: each

text: lasting

text: for

text: consecutive

text: steps.

text: The

text: adversary

text: activates

text: at

text: least

text: two,

text: and

text: up

text: to

text: four,

text: stations

text: holding

text: speciﬁc

text: edges

text: precisely

text: at

text: the

text: start

text: of

text: each

text: stage.

text: The

text: chosen

text: stations

text: and

text: edges

text: are

text: to

text: have

text: the

text: following

text: property:

text: of

text: these

text: at

text: least

text: two

text: edges

text: is

text: broadcast

text: successfully

text: during

text: the

text: stage

text: when

text: they

text: are

text: activated.

text: Consider

text: the

text: beginning

text: of

text: the

text: kth

text: stage,

text: where

text: k

text: and

text: suppose

text: that

text: during

text: the

text: previous

text: stages

text: the

text: execution

text: has

text: proceeded

text: as

text: required.

text: In

text: particular,

text: a

text: total

text: of

text: at

text: most

text: stations

text: have

text: been

text: activated,

text: and

text: of

text: the

text: edges

text: activated

text: steps

text: ago,

text: when

text: the

text: previous

text: stage

text: k

text: started,

text: has

text: been

text: heard

text: by

text: this

text: step.

text: The

text: algorithm

text: has

text: not

text: terminated

text: yet

text: because

text: it

text: is

text: c-correct,

text: the

text: inequality

text: c

text: holds

text: and

text: the

text: edges

text: recently

text: activated

text: have

text: to

text: be

text: in

text: a

text: spanning

text: forest

text: of

text: the

text: input.

text: Prior

text: to

text: the

text: beginning

text: of

text: a

text: stage,

text: we

text: need

text: a

text: pool

text: of

text: passive

text: stations

text: holding

text: edges

text: to

text: choose

text: the

text: ones

text: to

text: activate

text: from.

text: The

text: speciﬁc

text: fractions

text: of

text: m

text: we

text: use

text: serve

text: the

text: purpose

text: of

text: the

text: proof

text: for

text: the

text: following

text: reason:

text: each

text: stage

text: has

text: at

text: most

text: four

text: new

text: edges

text: activated,

text: for

text: a

text: total

text: of

text: edges

text: after

text: stages,

text: and

text: before

text: each

text: stage

text: there

text: are

text: at

text: least

text: m

text: edges

text: to

text: choose

text: from.

text: Let

text: the

text: next

text: consecutive

text: queries

text: be

text: Q

text: for

text: i

text: They

text: are

text: determined

text: uniquely

text: i

text: if

text: we

text: assume

text: that

text: there

text: are

text: no

text: successful

text: broadcasts

text: of

text: edges

text: that

text: have

text: not

text: been

text: activated

text: prior

text: to

text: this

text: point.

text: This

text: property

text: will

text: be

text: guaranteed

text: by

text: the

text: construction.

text: We

text: proceed

text: by

text: considering

text: sets

text: S

text: and

text: E

text: for

text: i

text: Initialize

text: the

text: set

text: S

text: to

text: the

text: IDs

text: of

text: the

text: stations

text: still

text: passive

text: at

text: i

text: i

text: this

text: point,

text: and

text: the

text: set

text: E

text: to

text: the

text: edges

text: held

text: by

text: these

text: stations.

text: The

text: sets

text: S

text: and

text: E

text: are

text: determined

text: i

text: i

text: inductively.

text: Suppose

text: S

text: and

text: E

text: have

text: already

text: been

text: determined,

text: then

text: S

text: and

text: E

text: are

text: deﬁned

text: i|

text: |i

text: as

text: follows.

text: If

text: Q

text: S

text: S

text: then

text: set

text: S

text: Q

text: S

text: otherwise

text: set

text: S

text: Q

text: S

text: ≥i

text: i

text: i

text: i

text: Similarly,

text: if

text: Q

text: E

text: E

text: then

text: set

text: E

text: Q

text: E

text: otherwise

text: set

text: E

text: Q

text: E

text: The

text: i

text: i

text: i

text: i

text: sets

text: S

text: and

text: E

text: for

text: i

text: contain

text: at

text: least

text: two

text: elements

text: each.

text: Choose

text: any

text: two

text: stations

text: in

text: i

text: i

text: the

text: ﬁnal

text: set

text: S

text: and

text: any

text: two

text: stations

text: in

text: the

text: ﬁnal

text: set

text: E

text: to

text: activate

text: in

text: the

text: next

text: stage.

text: i

text: i

text: When

text: the

text: last

text: stage

text: has

text: been

text: completed,

text: there

text: are

text: still

text: at

text: least

text: two

text: stations

text: that

text: have

text: been

text: activated

text: prior

text: to

text: the

text: last

text: c

text: steps

text: and

text: they

text: hold

text: edges

text: that

text: have

text: to

text: be

text: in

text: a

text: spanning

text: forest

text: of

text: the

text: graph

text: with

text: edges

text: held

text: by

text: all

text: the

text: stations

text: active

text: by

text: this

text: step.

text: This

text: means

text: that

text: the

text: algorithm

text: still

text: needs

text: to

text: perform

text: at

text: least

text: two

text: more

text: steps.

text: Theorem

text: can

text: be

text: strengthened

text: to

text: hold

text: for

text: any

text: graph

text: that

text: contains

text: a

text: forest

text: of

text: m

text: edges,

text: a

text: proof

text: is

text: a

text: straightforward

text: modiﬁcation,

text: details

text: are

text: omitted.

text: Next

text: we

text: give

text: a

text: deterministic

text: adaptive

text: algorithm

text: DetAdversarial,

text: whose

text: performance

text: matches

text: the

text: lower

text: bound

text: of

text: Theorem

text: The

text: design

text: principle

text: under

text: which

text: it

text: operates

text: is

text: similar

text: to

text: that

text: of

text: the

text: adaptive

text: algorithm

text: for

text: the

text: static

text: case.

text: The

text: main

text: diﬀerence

text: is

text: that

text: now

text: new

text: stations

text: can

text: wake

text: up

text: at

text: arbitrary

text: steps

text: and

text: they

text: need

text: to

text: be

text: incorporated

text: into

text: an

text: execution.

text: When

text: a

text: station

text: is

text: activated

text: after

text: the

text: start

text: of

text: an

text: execution,

text: it

text: pauses

text: and

text: listens

text: to

text: the

text: channel

text: until

text: it

text: hears

text: a

text: special

text: update


text: Input: the number n of graph vertices ; edge e ; p ∅ ∅ Initialization: Revealed := , Cycle := , e is waiting ; p if this is the start of an execution then participate in Resolve to elect a leader else begin wait for the ﬁrst update message ; update Revealed ; adjust the status of e p end ; repeat if e is waiting then broadcast a dummy message ; p if ( silence was heard in the previous step ) and ( p is a leader ) then broadcast a termination signal ; { } e := Resolve ( Waiting ) ; move edge e from Waiting to Revealed ; if ( e is waiting ) and ( there is a cycle in the graph induced by e p p and the edges in Revealed ) then move e from Waiting to Cycle ; p if p is a leader then broadcast an update message ; until a termination signal was heard Output: all the revealed edges. Figure 4: Algorithm DetAdversarial. Code for the station p that holds the input edge e . p 19 ##LTLine## ##LTLine##

text: Input:

label: paragraph

text: the

text: number

text: n

text: of

text: graph

text: vertices

text: edge

text: e

text: p

text: Initialization:

text: Revealed

text: Cycle

text: e

text: is

text: waiting

text: p

text: if

text: this

text: is

text: the

text: start

text: of

text: an

text: execution

text: then

text: participate

text: in

text: Resolve

text: to

text: elect

text: a

text: leader

text: else

text: begin

text: wait

text: for

text: the

text: ﬁrst

text: update

text: message

text: update

text: Revealed

text: adjust

text: the

text: status

text: of

text: e

text: p

text: end

text: repeat

text: if

text: e

text: is

text: waiting

text: then

text: broadcast

text: a

text: dummy

text: message

text: p

text: if

text: silence

text: was

text: heard

text: in

text: the

text: previous

text: step

text: and

text: p

text: is

text: a

text: leader

text: then

text: broadcast

text: a

text: termination

text: signal

text: e

text: Resolve

text: Waiting

text: move

text: edge

text: e

text: from

text: Waiting

text: to

text: Revealed

text: if

text: e

text: is

text: waiting

text: and

text: there

text: is

text: a

text: cycle

text: in

text: the

text: graph

text: induced

text: by

text: e

text: p

text: p

text: and

text: the

text: edges

text: in

text: Revealed

text: then

text: move

text: e

text: from

text: Waiting

text: to

text: Cycle

text: p

text: if

text: p

text: is

text: a

text: leader

text: then

text: broadcast

text: an

text: update

text: message

text: until

text: a

text: termination

text: signal

text: was

text: heard

text: Output:

text: all

text: the

text: revealed

text: edges.

text: Figure

text: Algorithm

text: DetAdversarial.

text: Code

text: for

text: the

text: station

text: p

text: that

text: holds

text: the

text: input

text: edge

text: e

text: p

text: ##LTLine##

text: ##LTLine##


text: References [1] Norman M. Abramson. Development of the ALOHANET. IEEE Transactions on Information Theory, 31(2):119–123, 1985. [2] Baruch Awerbuch. Optimal distributed algorithms for minimum weight spanning tree, count- ing, leader election and related problems. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC), pages 230–240, 1987. [3] Dmitri Bertsekas and Robert Gallager. Data Networks. Prentice Hall, second edition, 1992. [4] Bogdan S. Chlebus. Randomized communication in radio networks. In Panos M. Pardalos, Sanguthevar Rajasekaran, John H. Reif, and Jose D. P. Rolim, editors, Handbook of Random- ized Computing, volume I, pages 401–456. Kluwer Academic Publishers, 2001. [5] Bogdan S. Chlebus, K. Go(cid:32)lab, and Dariusz R. Kowalski. Broadcasting spanning forests on a (cid:44) multiple-access channel. Theory of Computing Systems, 36(6):711–733, 2003. [6] Bogdan S. Chlebus, Karol Go(cid:32)lab, and Dariusz R. Kowalski. Finding spanning forests by (cid:44) broadcasting. In Proceedings of the 9th International Colloquium on Structural Information and Communication Complexity (SIROCCO), volume 13 of Proceedings in Informatics, pages 41–56. Carleton Scientiﬁc, 2002. [7] Bogdan S. Chlebus, Dariusz R. Kowalski, and Andrzej Lingas. Performing work in broadcast networks. Distributed Computing, 18(6):435–451, 2006. [8] Andrea E. F. Clementi, Angelo Monti, and Riccardo Silvestri. Optimal F -reliable protocols for the Do-All problem on single-hop wireless networks. In Proceedings of the 13th Interna- tional Symposium on Algorithms and Computation (ISAAC), volume 2518 of Lecture Notes in Computer Science, pages 320–331. Springer, 2002. [9] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Cliﬀord Stein. Introduction to Algorithms. The MIT Press, third edition, 2009. [10] Cynthia Dwork, Joseph Y. Halpern, and Orli Waarts. Performing work eﬃciently in the presence of faults. SIAM Journal on Computing, 27(5):1457–1491, 1998. [11] Michalis Faloutsos and Mart Molle. Optimal distributed algorithm for minimum spanning trees revisited. In Proceedings of the Fourteenth Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 231–237, 1995. [12] Robert G. Gallager. A perspective on multiaccess channels. IEEE Transactions on Information Theory, 31(2):124–142, 1985. [13] Robert G. Gallager, Pierre A. Humblet, and Philip M. Spira. A distributed algorithm for minimum-weight spanning trees. ACM Transactions on Programming Languages and Systems, 5(1):66–77, 1983. [14] Juan A. Garay, Shay Kutten, and David Peleg. A sublinear time distributed algorithm for minimum-weight spanning trees. SIAM Journal on Computing, 27(1):302–316, 1998. 21

text: References

label: reference

text: Norman

text: M.

text: Abramson.

text: Development

text: of

text: the

text: ALOHANET.

text: IEEE

text: Transactions

text: on

text: Information

text: Theory,

text: Baruch

text: Awerbuch.

text: Optimal

text: distributed

text: algorithms

text: for

text: minimum

text: weight

text: spanning

text: tree,

text: count-

text: ing,

text: leader

text: election

text: and

text: related

text: problems.

text: In

text: Proceedings

text: of

text: the

text: Annual

text: ACM

text: Symposium

text: on

text: Theory

text: of

text: Computing

text: (STOC),

text: pages

text: Dmitri

text: Bertsekas

text: and

text: Robert

text: Gallager.

text: Data

text: Networks.

text: Prentice

text: Hall,

text: second

text: edition,

text: Bogdan

text: S.

text: Chlebus.

text: Randomized

text: communication

text: in

text: radio

text: networks.

text: In

text: Panos

text: M.

text: Pardalos,

text: Sanguthevar

text: Rajasekaran,

text: John

text: H.

text: Reif,

text: and

text: Jose

text: D.

text: P.

text: Rolim,

text: editors,

text: Handbook

text: of

text: Random-

text: ized

text: Computing,

text: volume

text: I,

text: pages

text: Kluwer

text: Academic

text: Publishers,

text: Bogdan

text: S.

text: Chlebus,

text: K.

text: and

text: Dariusz

text: R.

text: Kowalski.

text: Broadcasting

text: spanning

text: forests

text: on

text: a

text: multiple-access

text: channel.

text: Theory

text: of

text: Computing

text: Systems,

text: Bogdan

text: S.

text: Chlebus,

text: Karol

text: and

text: Dariusz

text: R.

text: Kowalski.

text: Finding

text: spanning

text: forests

text: by

text: broadcasting.

text: In

text: Proceedings

text: of

text: the

text: International

text: Colloquium

text: on

text: Structural

text: Information

text: and

text: Communication

text: Complexity

text: (SIROCCO),

text: volume

text: of

text: Proceedings

text: in

text: Informatics,

text: pages

text: Carleton

text: Scientiﬁc,

text: Bogdan

text: S.

text: Chlebus,

text: Dariusz

text: R.

text: Kowalski,

text: and

text: Andrzej

text: Lingas.

text: Performing

text: work

text: in

text: broadcast

text: networks.

text: Distributed

text: Computing,

text: Andrea

text: E.

text: F.

text: Clementi,

text: Angelo

text: Monti,

text: and

text: Riccardo

text: Silvestri.

text: Optimal

text: F

text: -reliable

text: protocols

text: for

text: the

text: Do-All

text: problem

text: on

text: single-hop

text: wireless

text: networks.

text: In

text: Proceedings

text: of

text: the

text: Interna-

text: tional

text: Symposium

text: on

text: Algorithms

text: and

text: Computation

text: (ISAAC),

text: volume

text: of

text: Lecture

text: Notes

text: in

text: Computer

text: Science,

text: pages

text: Springer,

text: Thomas

text: H.

text: Cormen,

text: Charles

text: E.

text: Leiserson,

text: Ronald

text: L.

text: Rivest,

text: and

text: Cliﬀord

text: Stein.

text: Introduction

text: to

text: Algorithms.

text: The

text: MIT

text: Press,

text: third

text: edition,

text: Cynthia

text: Dwork,

text: Joseph

text: Y.

text: Halpern,

text: and

text: Orli

text: Waarts.

text: Performing

text: work

text: eﬃciently

text: in

text: the

text: presence

text: of

text: faults.

text: SIAM

text: Journal

text: on

text: Computing,

text: Michalis

text: Faloutsos

text: and

text: Mart

text: Molle.

text: Optimal

text: distributed

text: algorithm

text: for

text: minimum

text: spanning

text: trees

text: revisited.

text: In

text: Proceedings

text: of

text: the

text: Fourteenth

text: Annual

text: ACM

text: Symposium

text: on

text: Principles

text: of

text: Distributed

text: Computing

text: (PODC),

text: pages

text: Robert

text: G.

text: Gallager.

text: A

text: perspective

text: on

text: multiaccess

text: channels.

text: IEEE

text: Transactions

text: on

text: Information

text: Theory,

text: Robert

text: G.

text: Gallager,

text: Pierre

text: A.

text: Humblet,

text: and

text: Philip

text: M.

text: Spira.

text: A

text: distributed

text: algorithm

text: for

text: minimum-weight

text: spanning

text: trees.

text: ACM

text: Transactions

text: on

text: Programming

text: Languages

text: and

text: Systems,

text: Juan

text: A.

text: Garay,

text: Shay

text: Kutten,

text: and

text: David

text: Peleg.

text: A

text: sublinear

text: time

text: distributed

text: algorithm

text: for

text: minimum-weight

text: spanning

text: trees.

text: SIAM

text: Journal

text: on

text: Computing,


text: Revealed: the edges already revealed on the channel, each of them is called revealed ; Cycle: the edges that would make a cycle if added to those in Revealed, each of them is called cycle ; Waiting: the remaining edges, called waiting . Each of the waiting edges could be added to Revealed and still the property that Revealed is a forest would be maintained. A station holding a revealed, cycle or waiting edge is called a revealed, cycle or waiting station, respectively. Initially the sets Revealed and Cycle are empty, and the set Waiting consists of all the input edges. During one iteration, the procedure Resolve (Waiting) is called, and the edge eventually heard on the channel is added to Revealed. Each of the remaining waiting stations checks to see if it is now in Cycle, and if this is the case, then it will never attempt to perform a broadcast in this execution. A pseudocode of the algorithm is given in Figure 1. Correctness. The correctness of algorithm DetSimple is guaranteed by the following invariant maintained in each iteration: the edges in Revealed make a forest on the set of vertices [1..n]. O | | Performance. The overall cost of algorithm DetSimple to ﬁnd a spanning forest T is ( T log m) | | since Resolve is called T times. O General algorithm. We give an algorithm that works in time (m) if m = o(n log n), it op- erates as follows. The algorithm DetSimple is run during the odd-numbered steps. During the even-numbered steps, the stations broadcast their edges on the channel one by one, in the order of their IDs. If there is a silence heard during an even-numbered step, then this is interpreted as a termination signal, since all the stations have revealed their edges by this step. The two pro- cesses, run during the odd-numbered and the even-numbered steps, do not aﬀect one another, in particular the edges broadcast in the even-numbered steps are not treated as revealed in algorithm DetSimple. The following theorem follows directly from the design of this general algorithm: Theorem 1 There is a deterministic adaptive algorithm for the static model that ﬁnds a spanning O | | forest T of a simple graph in time ( min [ m , T log m ] ). 3.2 Randomized Algorithm We present a randomized algorithm RandSimple that ﬁnds a spanning forest in a graph in expected time proportional to its size. The algorithm is similar in structure to the deterministic one, and we use the same terminology. The main diﬀerence and advantage is that the expected time to reveal a waiting edge is constant. A pseudo code of the algorithm is in Figure 2. The algorithm uses a variable denoted a, which is maintained by all the stations, to approximate the number of waiting stations during an execution. The stations broadcast with the probability 1/a. They update the estimate a if silence or noise is heard. If an edge is heard, then all the sets Revealed, Waiting and Cycle are updated as in the algorithm DetSimple. Correctness. The correctness of algorithm RandSimple follows from the following two facts. First, the output is a superset of a spanning forest. This follows from the observation that as long 6

text: Revealed:

text: the

text: edges

text: already

text: revealed

text: on

text: the

text: channel,

text: each

text: of

text: them

text: is

text: called

text: revealed

text: Cycle:

text: the

text: edges

text: that

text: would

text: make

text: a

text: cycle

text: if

text: added

text: to

text: those

text: in

text: Revealed,

text: each

text: of

text: them

text: is

text: called

text: cycle

text: Waiting:

text: the

text: remaining

text: edges,

text: called

text: waiting

text: Each

text: of

text: the

text: waiting

text: edges

text: could

text: be

text: added

text: to

text: Revealed

text: and

text: still

text: the

text: property

text: that

text: Revealed

text: is

text: a

text: forest

text: would

text: be

text: maintained.

text: A

text: station

text: holding

text: a

text: revealed,

text: cycle

text: or

text: waiting

text: edge

text: is

text: called

text: a

text: revealed,

text: cycle

text: or

text: waiting

text: station,

text: respectively.

text: Initially

text: the

text: sets

text: Revealed

text: and

text: Cycle

text: are

text: empty,

text: and

text: the

text: set

text: Waiting

text: consists

text: of

text: all

text: the

text: input

text: edges.

text: During

text: one

text: iteration,

text: the

text: procedure

text: Resolve

text: (Waiting)

text: is

text: called,

text: and

text: the

text: edge

text: eventually

text: heard

text: on

text: the

text: channel

text: is

text: added

text: to

text: Revealed.

text: Each

text: of

text: the

text: remaining

text: waiting

text: stations

text: checks

text: to

text: see

text: if

text: it

text: is

text: now

text: in

text: Cycle,

text: and

text: if

text: this

text: is

text: the

text: case,

text: then

text: it

text: will

text: never

text: attempt

text: to

text: perform

text: a

text: broadcast

text: in

text: this

text: execution.

text: A

text: pseudocode

text: of

text: the

text: algorithm

text: is

text: given

text: in

text: Figure

text: Correctness.

text: The

text: correctness

text: of

text: algorithm

text: DetSimple

text: is

text: guaranteed

text: by

text: the

text: following

text: invariant

text: maintained

text: in

text: each

text: iteration:

text: the

text: edges

text: in

text: Revealed

text: make

text: a

text: forest

text: on

text: the

text: set

text: of

text: vertices

text: O

text: Performance.

text: The

text: overall

text: cost

text: of

text: algorithm

text: DetSimple

text: to

text: ﬁnd

text: a

text: spanning

text: forest

text: T

text: is

text: T

text: log

text: m)

text: since

text: Resolve

text: is

text: called

text: T

text: times.

text: O

text: General

text: algorithm.

text: We

text: give

text: an

text: algorithm

text: that

text: works

text: in

text: time

text: (m)

text: if

text: m

text: o(n

text: log

text: n),

text: it

text: op-

text: erates

text: as

text: follows.

text: The

text: algorithm

text: DetSimple

text: is

text: run

text: during

text: the

text: odd-numbered

text: steps.

text: During

text: the

text: even-numbered

text: steps,

text: the

text: stations

text: broadcast

text: their

text: edges

text: on

text: the

text: channel

text: one

text: by

text: one,

text: in

text: the

text: order

text: of

text: their

text: IDs.

text: If

text: there

text: is

text: a

text: silence

text: heard

text: during

text: an

text: even-numbered

text: step,

text: then

text: this

text: is

text: interpreted

text: as

text: a

text: termination

text: signal,

text: since

text: all

text: the

text: stations

text: have

text: revealed

text: their

text: edges

text: by

text: this

text: step.

text: The

text: two

text: pro-

text: cesses,

text: run

text: during

text: the

text: odd-numbered

text: and

text: the

text: even-numbered

text: steps,

text: do

text: not

text: aﬀect

text: one

text: another,

text: in

text: particular

text: the

text: edges

text: broadcast

text: in

text: the

text: even-numbered

text: steps

text: are

text: not

text: treated

text: as

text: revealed

text: in

text: algorithm

text: DetSimple.

text: The

text: following

text: theorem

text: follows

text: directly

text: from

text: the

text: design

text: of

text: this

text: general

text: algorithm:

text: Theorem

text: There

text: is

text: a

text: deterministic

text: adaptive

text: algorithm

text: for

text: the

text: static

text: model

text: that

text: ﬁnds

text: a

text: spanning

text: O

text: forest

text: T

text: of

text: a

text: simple

text: graph

text: in

text: time

text: min

text: m

text: T

text: log

text: m

text: Randomized

text: Algorithm

text: We

text: present

text: a

text: randomized

text: algorithm

text: RandSimple

text: that

text: ﬁnds

text: a

text: spanning

text: forest

text: in

text: a

text: graph

text: in

text: expected

text: time

text: proportional

text: to

text: its

text: size.

text: The

text: algorithm

text: is

text: similar

text: in

text: structure

text: to

text: the

text: deterministic

text: one,

text: and

text: we

text: use

text: the

text: same

text: terminology.

text: The

text: main

text: diﬀerence

text: and

text: advantage

text: is

text: that

text: the

text: expected

text: time

text: to

text: reveal

text: a

text: waiting

text: edge

text: is

text: constant.

text: A

text: pseudo

text: code

text: of

text: the

text: algorithm

text: is

text: in

text: Figure

text: The

text: algorithm

text: uses

text: a

text: variable

text: denoted

text: a,

text: which

text: is

text: maintained

text: by

text: all

text: the

text: stations,

text: to

text: approximate

text: the

text: number

text: of

text: waiting

text: stations

text: during

text: an

text: execution.

text: The

text: stations

text: broadcast

text: with

text: the

text: probability

text: They

text: update

text: the

text: estimate

text: a

text: if

text: silence

text: or

text: noise

text: is

text: heard.

text: If

text: an

text: edge

text: is

text: heard,

text: then

text: all

text: the

text: sets

text: Revealed,

text: Waiting

text: and

text: Cycle

text: are

text: updated

text: as

text: in

text: the

text: algorithm

text: DetSimple.

text: Correctness.

text: The

text: correctness

text: of

text: algorithm

text: RandSimple

text: follows

text: from

text: the

text: following

text: two

text: facts.

text: First,

text: the

text: output

text: is

text: a

text: superset

text: of

text: a

text: spanning

text: forest.

text: This

text: follows

text: from

text: the

text: observation

text: that

text: as

text: long


text: 2 SALVADOR PE´REZ-ESTEVA AND ALEJANDRO URIBE As a motivation for the type of operators we consider in this article, let dσ be the measure induced on Γ by Lebesgue measure and L2(Γ) the corresponding L2 space. Let R B → : L2(Γ) k k be the restriction operator, which is bounded, and let R∗ → B : L2(Γ) k k be its adjoint. Then the self-adjoint operator R∗ ◦ R B → B (2) T := : Γ k k is an example of what we will call a singular Toeplitz operator, since it can be considered as a Toeplitz operator with a multiplier that is a distribution supported on Γ, as the following lemma shows: B Lemma 1.1. Let Π (z, w) be the reproducing ke(cid:90)rnel for , that is, the Schwartz kernel of the C →k B k projection Π L2( ) . Then k k ∀ ∈ B ψ T (ψ)(z) = Π (z, w) ψ(w) dσ(w). k Γ k Γ (cid:90) R∗ ∈ ∈ B Proof. We compute . Let ϕ L2(Γ) and ψ . Then k (cid:104)R∗ (cid:105) (cid:104) (cid:105) (ϕ) , ψ = ϕ , R(ψ) = ϕ(ζ)ψ(ζ) dσ(ζ). (cid:90) Γ Now use the reproducing property: ψ(ζ) = Π (ζ, w)ψ(w) dL(w), C k (cid:90) N (cid:18)(cid:90) (cid:19) and using Fubini’s theorem we get that (cid:104)R∗ (cid:105) (ϕ) , ψ = ψ(w) ϕ(ζ)Π (ζ, w) dσ(ζ) dL(w). C k N Γ (cid:90) Since this is true for all ψ, R∗ (3) (ϕ)(w) = ϕ(ζ)Π (w, ζ) dσ(ζ), k Γ (cid:3) as desired. More generally, in this paper we consider the following operators: → C (cid:90) B → B Deﬁnition 1.2. Let a : Γ be a smooth function of compact support. Then T : is adσ k k the operator T (ψ)(z) = Π (z, w) ψ(w) a(w) dσ(w). adσ k Γ ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: SALVADOR

text: PE´REZ-ESTEVA

text: AND

text: ALEJANDRO

text: URIBE

text: As

text: a

text: motivation

text: for

text: the

text: type

text: of

text: operators

text: we

text: consider

text: in

text: this

text: article,

text: let

text: dσ

text: be

text: the

text: measure

text: induced

text: on

text: Γ

text: by

text: Lebesgue

text: measure

text: and

text: the

text: corresponding

text: space.

text: Let

text: R

text: B

text: k

text: k

text: be

text: the

text: restriction

text: operator,

text: which

text: is

text: bounded,

text: and

text: let

text: R∗

text: B

text: k

text: k

text: be

text: its

text: adjoint.

text: Then

text: the

text: self-adjoint

text: operator

text: R∗

label: equation

text: R

text: B

text: B

text: T

text: Γ

text: k

text: k

text: is

text: an

text: example

text: of

text: what

text: we

text: will

text: call

text: a

text: singular

text: Toeplitz

text: operator,

text: since

text: it

text: can

text: be

text: considered

text: as

text: a

text: Toeplitz

text: operator

text: with

text: a

text: multiplier

text: that

text: is

text: a

text: distribution

text: supported

text: on

text: Γ,

text: as

text: the

text: following

text: lemma

text: shows:

text: B

text: Lemma

text: Let

text: Π

text: (z,

text: w)

text: be

text: the

text: reproducing

text: for

text: that

text: is,

text: the

text: Schwartz

text: kernel

text: of

text: the

text: C

text: →k

text: B

text: k

text: projection

text: Π

text: Then

text: k

text: k

text: B

text: ψ

text: T

text: (ψ)(z)

text: Π

text: (z,

text: w)

text: ψ(w)

text: dσ(w).

text: k

text: Γ

text: k

text: Γ

text: R∗

text: B

text: Proof.

text: We

text: compute

text: Let

text: ϕ

text: and

text: ψ

text: Then

text: k

text: (ϕ)

text: ψ

text: ϕ

text: R(ψ)

text: ϕ(ζ)ψ(ζ)

text: dσ(ζ).

text: Γ

text: Now

text: use

text: the

text: reproducing

text: property:

text: ψ(ζ)

text: Π

text: (ζ,

text: w)ψ(w)

text: dL(w),

text: C

text: k

text: N

text: and

text: using

text: Fubini’s

text: theorem

text: we

text: get

text: that

text: (ϕ)

text: ψ

text: ψ(w)

text: ϕ(ζ)Π

text: (ζ,

text: w)

text: dσ(ζ)

text: dL(w).

text: C

text: k

text: N

text: Γ

text: Since

text: this

text: is

text: true

text: for

text: all

text: ψ,

text: R∗

text: (ϕ)(w)

text: ϕ(ζ)Π

text: (w,

text: ζ)

text: dσ(ζ),

text: k

text: Γ

text: as

text: desired.

text: More

text: generally,

text: in

text: this

text: paper

text: we

text: consider

text: the

text: following

text: operators:

text: C

text: B

text: B

text: Deﬁnition

text: Let

text: a

text: Γ

text: be

text: a

text: smooth

text: function

text: of

text: compact

text: support.

text: Then

text: T

text: is

text: adσ

text: k

text: k

text: the

text: operator

text: T

text: (ψ)(z)

text: Π

text: (z,

text: w)

text: ψ(w)

text: a(w)

text: dσ(w).

text: adσ

text: k

text: Γ

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 18 SALVADOR PE´REZ-ESTEVA AND ALEJANDRO URIBE (cid:90) (cid:90) If we choose kr2 = 1 we obtain that for a constant C > 0 | | − | | ≤ (cid:107) (cid:107) − | | − | | f(z) 2e k z 2dµ(z) C a ∞kN d/2 f(u) 2e k u 2dv(u), C C hence (cid:104) (cid:105) ≤ (cid:107) (cid:107) − (cid:107) (cid:107) T ψ, ψ C a ∞ kN d/2 ψ 2B adσ ∈ B k (cid:3) for every ψ and the proposition follows. k 4. Proof of the Szego¨ limit theorem The proof of Theorem 1.7 begins with the proof of Theorem 1.4. After that we show that the traces of the S operators are bounded, and a ﬁnal argument concludes the proof. The starting point of the proo(cid:18)f is(cid:19)the(cid:90)exp(cid:32)ression (41) fo(cid:89)r the tra(cid:33)ce of Υ, which we recall for convenience: · · · k Nn ··· n · · · (41) Tr(T T ) = eikΦ(ζ1 ,ζn) a (ζ ) dσ(ζ ) σ(ζ ), a1dσ andσ (cid:0) π Γn (cid:1) i=1 i i 1 n where · · · i | − | · · · | − | · · · Φ(ζ , , ζ ) = ζ ζ 2 + + ζ ζ 2 + ω(ζ , ζ ) + + ω(ζ , ζ ). 1 n 2 1 2 n 1 1 2 n 1 We will estimate this trace using the method of stationary phase. Note ﬁrst that the imaginary part of Φ is non-negative and is zero precisely on the diagonal { ∈ · · · } Γ∆ := (ζ , . . . , ζ ) Γn ; ζ = ζ = = ζ . 1 n 1 2 n For this reason one can easily show that the integrand of (41), integrated over the complement of any neighborhood of Γ∆, is exponentially decreasing. Therefore, asymptotically to all polynomial orders we can restrict our attention to a small neighborhood of Γ∆. In addition we will show that ∗ ( ) Γ∆ is a non-degenerate manifold of critical points of Φ. In particular, in a suﬃciently small neighborhood of Γ∆ any critical point of Φ is in Γ∆. ⊂ → U ⊂ Let γ : B(0; 1) Rd Γ be a parametrization of an open set Γ. The notation ∂γ ∈ R (45) (cid:126)γ := 2N j ∂t (cid:112) j · will be useful in the proof. Let G(t) = (g (t)) be the metric of Γ, that is g (t) = (cid:126)γ (t) (cid:126)γ (t), ij ij i j and let dµ(t)dt = det(G) dt denote the volume element on Γ. · · · R ∈ R Let t, s , s − be variables in d so that, for example s = (ui , . . . , ui ) d, and deﬁne 1 → Rn 1 i 1 d Ξ : B(0, (cid:15))n ( 2N)n by · · · · · · (46) Ξ(t, s , s − ) = (γ(t), γ(t + s ), , γ(t + s − )). 1 n 1 1 n 1 ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: SALVADOR

text: PE´REZ-ESTEVA

text: AND

text: ALEJANDRO

text: URIBE

text: If

text: we

text: choose

text: we

text: obtain

text: that

text: for

text: a

text: constant

text: C

text: f(z)

text: k

text: z

text: C

text: a

text: ∞kN

text: f(u)

text: k

text: u

text: C

text: C

text: hence

text: T

text: ψ,

text: ψ

text: C

text: a

text: kN

text: ψ

text: adσ

text: B

text: k

text: for

text: every

text: ψ

text: and

text: the

text: proposition

text: follows.

text: k

label: section

text: Proof

text: of

text: the

text: Szego¨

text: limit

text: theorem

text: The

text: proof

text: of

text: Theorem

text: begins

text: with

text: the

text: proof

text: of

text: Theorem

text: After

text: that

text: we

text: show

text: that

text: the

text: traces

text: of

text: the

text: S

text: operators

text: are

text: bounded,

text: and

text: a

text: ﬁnal

text: argument

text: concludes

text: the

text: proof.

text: The

text: starting

text: point

text: of

text: the

text: the

text: of

text: Υ,

text: which

text: we

text: recall

text: for

text: convenience:

text: k

text: Nn

text: n

text: Tr(T

text: T

text: ,ζn)

text: a

text: (ζ

text: dσ(ζ

text: σ(ζ

text: andσ

text: π

text: Γn

text: i

text: i

text: n

text: where

text: i

text: Φ(ζ

text: ζ

text: ζ

text: ζ

text: ζ

text: ζ

text: ω(ζ

text: ζ

text: ω(ζ

text: ζ

text: n

text: n

text: n

text: We

text: will

text: estimate

text: this

text: trace

text: using

text: the

text: method

text: of

text: stationary

text: phase.

text: Note

text: ﬁrst

text: that

text: the

text: imaginary

text: part

text: of

text: Φ

text: is

text: non-negative

text: and

text: is

text: zero

text: precisely

text: on

text: the

text: diagonal

text: Γ∆

text: (ζ

text: ζ

text: Γn

text: ζ

text: ζ

text: ζ

text: n

text: n

text: For

text: this

text: reason

text: one

text: can

text: easily

text: show

text: that

text: the

text: integrand

text: of

text: integrated

text: over

text: the

text: complement

text: of

text: any

text: neighborhood

text: of

text: Γ∆,

text: is

text: exponentially

text: decreasing.

text: Therefore,

text: asymptotically

text: to

text: all

text: polynomial

text: orders

text: we

text: can

text: restrict

text: our

text: attention

text: to

text: a

text: small

text: neighborhood

text: of

text: Γ∆.

text: In

text: addition

text: we

text: will

text: show

text: that

text: Γ∆

text: is

text: a

text: non-degenerate

text: manifold

text: of

text: critical

text: points

text: of

text: Φ.

text: In

text: particular,

text: in

text: a

text: suﬃciently

text: small

text: neighborhood

text: of

text: Γ∆

text: any

text: critical

text: point

text: of

text: Φ

text: is

text: in

text: Γ∆.

text: U

text: Let

text: γ

text: Rd

text: Γ

text: be

text: a

text: parametrization

text: of

text: an

text: open

text: set

text: Γ.

text: The

text: notation

text: ∂γ

text: R

text: j

text: ∂t

text: j

text: will

text: be

text: useful

text: in

text: the

text: proof.

text: Let

text: G(t)

text: (g

text: (t))

text: be

text: the

text: metric

text: of

text: Γ,

text: that

text: is

text: g

text: (t)

text: (t)

text: (t),

text: ij

text: ij

text: i

text: j

text: and

text: let

text: dµ(t)dt

text: det(G)

text: dt

text: denote

text: the

text: volume

text: element

text: on

text: Γ.

text: R

text: R

text: Let

text: t,

text: s

text: s

text: be

text: variables

text: in

text: d

text: so

text: that,

text: for

text: example

text: s

text: (ui

text: ui

text: d,

text: and

text: deﬁne

text: Rn

text: i

text: d

text: Ξ

text: by

text: Ξ(t,

text: s

text: s

text: (γ(t),

text: γ(t

text: s

text: γ(t

text: s

text: n

text: n

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: SZEGO¨ LIMIT THEOREMS FOR SINGULAR BEREZIN-TOEPLITZ OPERATORS 21 In conclusion, the Hessian of the full phase ψ = iψ + ψ with respect to the s variables is the 1 2 block tri-diagonal Toeplitz matrix Hess − (t) = iS − (t) n 1 n 1 where   (59)    − −   2G(t) G(t) iH(t) 0 . . . 0  − − −   G(t) + iH(t) 2G(t) G(t) iH(t) . . . 0   −   0 G(t) + iH(t) 2G(t) . . . 0    S − (t) = . n 1 0 . . . ... ... −G(t) − iH(t) − 0 . . . G(t) + iH(t) 2G(t) (cid:18) (cid:19) It is shown in the appendix (see (110)) that 1 − (60) det Hess − = det(G)n 1 ∆2. i n 1 n In particular the determinant of this matrix is positive. Since the s variables are variables normal ∗ to Γ∆, this proves the claim ( ). (cid:90) Choose (cid:15) > 0 so that s = 0 is the only critical point of the phase with respect to the s variables ◦ and let h (t, s) = χ Ξ(t, s). Then, by the stationary phase method, χ · · ·   · · · (cid:18) e(cid:19)ikψ(t,s) a (γ(t)) a (γ(t + s )) a (γ(t + s − )) h (t, s dµ(t + s ) dµ(t + s − )) ds 1 2 1 n (cid:89) n 1 χ 1 n 1 − B(0,(cid:15))n 1   − = 2kπ d(n 1)/2(cid:18)[det((cid:19)−iHessn−1)(t)]−1(cid:89)/2 n aj(γ(t)) hχ(t, 0) dµ(t)n−1 (1 + O(1/k))  j=1  − = 2π(cid:112) d(n 1)/2 ∆−1 n a (γ(t)) h (t, 0) (1 + O(1/k)) . k n j χ j=1 − Notice that the factor of det(G)n 1 in the square root of (60) cancels the Jacobian factors dµ(t). Integrating the last exp(cid:18)ress(cid:19)ion on B(0, (cid:15)) with(cid:90)res(cid:89)pect to dµ(t)dt we obtain − − k n(N d/2)+d/2 − n (61) Iχ(k) = 2dn2 1 π ∆n1 aj(ζ) χ∆(ζ) dσ(ζ) (1 + O(1/k)) Γ j=1 (cid:80) where χ∆(ζ) = χ(ζ, ζ, . . . , ζ). (cid:81) { } ≡ We now let χ denote a partition of unit of a neighborhood of Γ∆ in Γn so that χ 1 α α α in a neighborhood of the support of n a (ζ ), subordinated to a cover for which the previous j=1(cid:88)j j calculations apply. Then −∞ (62) Tr(Υ) = I (k) + O(k ), χα α ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: SZEGO¨

text: LIMIT

text: THEOREMS

text: FOR

text: SINGULAR

text: BEREZIN-TOEPLITZ

text: OPERATORS

text: In

text: conclusion,

text: the

text: Hessian

text: of

text: the

text: full

text: phase

text: ψ

text: iψ

text: ψ

text: with

text: respect

text: to

text: the

text: s

text: variables

text: is

text: the

text: block

text: tri-diagonal

text: Toeplitz

text: matrix

text: Hess

text: (t)

text: iS

text: (t)

text: n

text: n

text: where

text: G(t)

text: iH(t)

text: G(t)

text: iH(t)

text: G(t)

text: iH(t)

text: G(t)

text: iH(t)

text: S

text: (t)

text: n

text: −G(t)

text: iH(t)

text: G(t)

text: iH(t)

text: It

text: is

text: shown

text: in

text: the

text: appendix

text: (see

text: that

text: det

text: Hess

text: det(G)n

text: i

text: n

text: n

text: In

text: particular

text: the

text: determinant

text: of

text: this

text: matrix

text: is

text: positive.

text: Since

text: the

text: s

text: variables

text: are

text: variables

text: normal

text: to

text: Γ∆,

text: this

text: proves

text: the

text: claim

text: Choose

text: so

text: that

text: s

text: is

text: the

text: only

text: critical

text: point

text: of

text: the

text: phase

text: with

text: respect

text: to

text: the

text: s

text: variables

text: and

text: let

text: h

text: (t,

text: s)

text: χ

text: Ξ(t,

text: s).

text: Then,

text: by

text: the

text: stationary

text: phase

text: method,

text: χ

text: a

text: (γ(t))

text: a

text: (γ(t

text: s

text: a

text: (γ(t

text: s

text: h

text: (t,

text: s

text: dµ(t

text: s

text: dµ(t

text: s

text: ds

text: n

text: n

text: χ

text: n

text: d(n

text: n

text: aj(γ(t))

text: hχ(t,

text: d(n

text: ∆−1

text: n

text: a

text: (γ(t))

text: h

text: (t,

text: k

text: n

text: j

text: χ

text: Notice

text: that

text: the

text: factor

text: of

text: det(G)n

text: in

text: the

text: square

text: root

text: of

text: cancels

text: the

text: Jacobian

text: factors

text: dµ(t).

text: Integrating

text: the

text: last

text: on

text: to

text: dµ(t)dt

text: we

text: obtain

text: k

text: n(N

text: n

text: Iχ(k)

text: π

text: aj(ζ)

text: χ∆(ζ)

text: dσ(ζ)

text: Γ

text: where

text: χ∆(ζ)

text: χ(ζ,

text: ζ,

text: ζ).

text: We

text: now

text: let

text: χ

text: denote

text: a

text: partition

text: of

text: unit

text: of

text: a

text: neighborhood

text: of

text: Γ∆

text: in

text: Γn

text: so

text: that

text: χ

text: α

text: α

text: α

text: in

text: a

text: neighborhood

text: of

text: the

text: support

text: of

text: n

text: a

text: (ζ

text: subordinated

text: to

text: a

text: cover

text: for

text: which

text: the

text: previous

text: j

text: calculations

text: apply.

text: Then

text: Tr(Υ)

text: I

text: (k)

text: O(k

text: χα

text: α

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: SZEGO¨ LIMIT THEOREMS FOR SINGULAR BEREZIN-TOEPLITZ OPERATORS 23 ◦ Recall that r is half the rank of K, and since T Γ and T Γ have complementary dimension the w w dimension of Γ must equal d = N + r. (cid:48) − In particular r is constant. Note that d = N r. To continue we need a lemma from linear algebra: Lemma 4.2. If V is co-isotropic, the image E of K is the maximal complex subspace of V : ∩ (67) E = J(V ) V. ⊃ ∈ Proof. The inclusion is obvious. To prove the reverse inclusion, let v = Π(J(u)) with u V . ∈ ⊥ ◦ ∃ ∈ ◦ Then v = J(u) + w with w V = J(V ). Therefore a V such that w = J(a) and ﬁnally ∈ (cid:3) v = J(u + a) with u + a V . ⊕ ◦ → Therefore V = E V and the mapping K : V V is diagonal with respect to this decomposi- ◦ tion. It is zero on V and agrees with J on E. Therefore, there exists a basis of V where the matrix   for the transformation K is the canonical one, namely   − 0 I 0 r (68) W = I 0 0 . can r 0 0 0 In particular all the eigenvalues λ are equal to one, and one computes (cid:96) ∀ − − (cid:48) − − (69) n = 1, 2, . . . ∆n = nN2 r 2r(n 1) = nd /2 2(n 1)(d N). − − It follows that 2n(d N) = 2d(cid:48) N and (cid:18) (cid:19) (cid:32)(cid:90) (cid:81) (cid:33) ∆n nd /2 (70) Tr(Sa1dσ · · · Sandσ) = 2d−N 2kπ d/2 (cid:0) (cid:1) nj=n1d(cid:48)a/j2(w) dσ(cid:0)+ O(cid:1) (1/k) . Γ As the constant in front of the integral is 2d/2−N k d/2 = 2−d(cid:48)/2 k d/2 , the proposition is π π (cid:3) proved. · · · O Taking a = a = = a = a, using the linearity of the trace and since − (sn)(t) = tn , 1 2 n n/2 nd/2 we immediately obtain: Corollary 4.3. The Szeg¨o limit Theorem 1.7 holds for ϕ a polynomial without constant term. ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: SZEGO¨

text: LIMIT

text: THEOREMS

text: FOR

text: SINGULAR

text: BEREZIN-TOEPLITZ

text: OPERATORS

text: Recall

text: that

text: r

text: is

text: half

text: the

text: rank

text: of

text: K,

text: and

text: since

text: T

text: Γ

text: and

text: T

text: Γ

text: have

text: complementary

text: dimension

text: the

text: w

text: w

text: dimension

text: of

text: Γ

text: must

text: equal

text: d

text: N

text: r.

text: In

text: particular

text: r

text: is

text: constant.

text: Note

text: that

text: d

text: N

text: r.

text: To

text: continue

text: we

text: need

text: a

text: lemma

text: from

text: linear

text: algebra:

text: Lemma

text: If

text: V

text: is

text: co-isotropic,

text: the

text: image

text: E

text: of

text: K

text: is

text: the

text: maximal

text: complex

text: subspace

text: of

text: V

text: E

text: J(V

text: V.

text: Proof.

text: The

text: inclusion

text: is

text: obvious.

text: To

text: prove

text: the

text: reverse

text: inclusion,

text: let

text: v

text: Π(J(u))

text: with

text: u

text: V

text: Then

text: v

text: J(u)

text: w

text: with

text: w

text: V

text: J(V

text: Therefore

text: a

text: V

text: such

text: that

text: w

text: J(a)

text: and

text: ﬁnally

text: v

text: J(u

text: a)

text: with

text: u

text: a

text: V

text: Therefore

text: V

text: E

text: V

text: and

text: the

text: mapping

text: K

text: V

text: V

text: is

text: diagonal

text: with

text: respect

text: to

text: this

text: decomposi-

text: tion.

text: It

text: is

text: zero

text: on

text: V

text: and

text: agrees

text: with

text: J

text: on

text: E.

text: Therefore,

text: there

text: exists

text: a

text: basis

text: of

text: V

text: where

text: the

text: matrix

text: for

text: the

text: transformation

text: K

text: is

text: the

text: canonical

text: one,

text: namely

text: I

text: r

text: W

text: I

text: can

text: r

text: In

text: particular

text: all

text: the

text: eigenvalues

text: λ

text: are

text: equal

text: to

text: one,

text: and

text: one

text: computes

text: n

text: ∆n

text: r

text: nd

text: N).

text: It

text: follows

text: that

text: N)

text: N

text: and

text: ∆n

text: nd

text: Sandσ)

text: Γ

text: As

text: the

text: constant

text: in

text: front

text: of

text: the

text: integral

text: is

text: k

text: k

text: the

text: proposition

text: is

text: π

text: π

text: proved.

text: O

text: Taking

text: a

text: a

text: a

text: a,

text: using

text: the

text: linearity

text: of

text: the

text: trace

text: and

text: since

text: (sn)(t)

text: tn

text: n

text: we

text: immediately

text: obtain:

text: Corollary

text: The

text: Szeg¨o

text: limit

text: Theorem

text: holds

text: for

text: ϕ

text: a

text: polynomial

text: without

text: constant

text: term.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: SZEGO¨ LIMIT THEOREMS FOR SINGULAR BEREZIN-TOEPLITZ OPERATORS 27 (cid:16) (cid:17) ≥ Lemma 4.8. Let a 0 and p > 0. Let f be a polynomial without a constant term. Then (cid:48) π d/2 F lim 2d /2 Tr[Spf(S)] = (tpf(t)). →∞ k k Proof. Let [0, R] be an interval containing the spectra of S for all k, and let (g ) a sequence of adσ j polynomials such that lim g (t) = tp uniformly on [0, R]. →∞ j j (cid:12) (cid:12) We can estimate (cid:12) (cid:16) (cid:17) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:48) π d/2 − F ≤ (74) 2d /2 Tr[Spf(S)] (tpf(t)) I + II + III k(cid:12)(cid:12) (cid:16) (cid:17) (cid:12)(cid:12) (cid:12) (cid:12) (cid:12) (cid:12) where (cid:12) (cid:12) I(cid:12)(cid:12)(cid:12)= 2d(cid:48)(cid:16)/2 (cid:17)πk d/2 Tr [(Sp − gj(S)) f(S)] , (cid:12)(cid:12)(cid:12) (cid:48) π d/2 − F II = 2d /2 Tr[g (S)f(S)] (g (t)f(t)) , k j j and (cid:16) (cid:17) III = |F(g (t)f(t)) − tpf(t))| . j Let f˜ be the polynomial whose coeﬃcients are the absolute values of the coeﬃcients of f. Then | | ≤ Tr ( f(S) ) Tr f˜(S) and therefore, using the Szeg¨o theorem for polynomials (or just the esti- mates for the traces of power(cid:16)s o(cid:17)f S), we have ≤ (cid:48) π d/2 | | (cid:107) − (cid:107) ≤ (cid:107) − (cid:107) (75) I 2d /2 Tr ( f(S) ) Sp g (S) C Sp g (S) k j j for some C > 0 and all k. Let (cid:15) > 0. There exists j large enough so that (cid:107) − (cid:107) (cid:15) (cid:15) Sp g (S) < and III < . j 3C 3 The ﬁrst of these conditions together with (75) implies that I < (cid:15)/3. Now for each j the quantity → ∞ II tends to zero as k , by Corollary 4.3. Therefore the left-hand side of (74) is less than (cid:15) if k (cid:3) is large enough. ∈ C ∈ End of the proof of Theorem 1.7. Let ϕ , that is, for some p (0, 1), the function ϕ(t) ψ(t) := tp is continuous on [0, R]. In the argument below p can be arbitrary in (0, 1). Therefore, without loss of generality we can assume that ψ(0) = 0. Let (f ) be a sequence of polynomials such that (cid:96) lim f (t) = ψ(t) uniformly on [0, R]. →∞ (cid:96) (cid:96) Without loss of generality we can assume that f (0) = 0 for all (cid:96). We have that (cid:96) ϕ(S) = Sp lim f (S) →∞ (cid:96) (cid:96) ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: SZEGO¨

text: LIMIT

text: THEOREMS

text: FOR

text: SINGULAR

text: BEREZIN-TOEPLITZ

text: OPERATORS

text: Lemma

text: Let

text: a

text: and

text: p

text: Let

text: f

text: be

text: a

text: polynomial

text: without

text: a

text: constant

text: term.

text: Then

text: π

text: F

text: lim

text: Tr[Spf(S)]

text: (tpf(t)).

text: k

text: k

text: Proof.

text: Let

text: R]

text: be

text: an

text: interval

text: containing

text: the

text: spectra

text: of

text: S

text: for

text: all

text: k,

text: and

text: let

text: (g

text: a

text: sequence

text: of

text: adσ

text: j

text: polynomials

text: such

text: that

text: lim

text: g

text: (t)

text: tp

text: uniformly

text: on

text: R].

text: j

text: j

text: We

text: can

text: estimate

text: π

text: F

text: Tr[Spf(S)]

text: (tpf(t))

text: I

text: II

text: III

text: where

text: Tr

text: [(Sp

text: gj(S))

text: f(S)]

text: π

text: F

text: II

text: Tr[g

text: (S)f(S)]

text: (g

text: (t)f(t))

text: k

text: j

text: j

text: and

text: III

text: |F(g

text: (t)f(t))

text: tpf(t))|

text: j

text: Let

text: f˜

text: be

text: the

text: polynomial

text: whose

text: coeﬃcients

text: are

text: the

text: absolute

text: values

text: of

text: the

text: coeﬃcients

text: of

text: f.

text: Then

text: Tr

text: f(S)

text: Tr

text: f˜(S)

text: and

text: therefore,

text: using

text: the

text: Szeg¨o

text: theorem

text: for

text: polynomials

text: (or

text: just

text: the

text: esti-

text: mates

text: for

text: the

text: traces

text: of

text: S),

text: we

text: have

text: π

text: I

text: Tr

text: f(S)

text: Sp

text: g

text: (S)

text: C

text: Sp

text: g

text: (S)

text: k

text: j

text: j

text: for

text: some

text: C

text: and

text: all

text: k.

text: Let

text: There

text: exists

text: j

text: large

text: enough

text: so

text: that

text: Sp

text: g

text: (S)

text: and

text: III

text: j

text: The

text: ﬁrst

text: of

text: these

text: conditions

text: together

text: with

text: implies

text: that

text: I

text: Now

text: for

text: each

text: j

text: the

text: quantity

text: II

text: tends

text: to

text: zero

text: as

text: k

text: by

text: Corollary

text: Therefore

text: the

text: left-hand

text: side

text: of

text: is

text: less

text: than

text: if

text: k

text: is

text: large

text: enough.

text: C

text: End

text: of

text: the

text: proof

text: of

text: Theorem

text: Let

text: ϕ

text: that

text: is,

text: for

text: some

text: p

text: the

text: function

text: ϕ(t)

text: ψ(t)

text: tp

text: is

text: continuous

text: on

text: R].

text: In

text: the

text: argument

text: below

text: p

text: can

text: be

text: arbitrary

text: in

text: Therefore,

text: without

text: loss

text: of

text: generality

text: we

text: can

text: assume

text: that

text: Let

text: (f

text: be

text: a

text: sequence

text: of

text: polynomials

text: such

text: that

text: lim

text: f

text: (t)

text: ψ(t)

text: uniformly

text: on

text: R].

text: Without

text: loss

text: of

text: generality

text: we

text: can

text: assume

text: that

text: f

text: for

text: all

text: We

text: have

text: that

text: ϕ(S)

text: Sp

text: lim

text: f

text: (S)

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: ∈ R R For some polynomials p (z), p (z), . . . p (z) [z] where [z] is used to denote the ring of multivariate poly- 0 1 ∈m R − { } nomials in the optimization variable z m+n 1. We will sometimes use the compact notation p (z) ∈ j j [J] to denote the set of polynomial constraints. This set of constraints deﬁnes a semialgebraic set K of feasible points, which we write as { ∈ R − | ≥ ≥ } K = z m+n 1, p (z) 0, . . . , p (z) 0 (1.20) 1 m ∈ R − ∈ N − For z m+n 1 and α m+n 1, we introduce the multi-index notation zα = zα1zα2 . . . zαn with | | 1 2 n α = α + α + . . . + α , the degree of the monomial zα. We will use zB to denote the sequence 1 2 ∈ Rn − of all monomials in z m+n 1 for some standard ordering (standard monomial basis). Hence zB := (1, z , z , . . . , z2, z z , . . . , zα, . . .). Similarly, let ztB denote the vector of all monomials zα from the stan- 1 2 1 1 2 | | ≤ dard basis with degree bounded by t: α d. (cid:80) In this paper, polynomials will be alternatively be denoted through either of the representations below, • Weigthed sums of monomials p (z) = (p ) zα, where the (p ) thus denotes the coeﬃcient of the i α i α i α monomial zα in p (z). i • Vectors/sequences of coeﬃcients p = ((p ) ) ∈N as p (z) = pT zB i i α α n i i • (cid:104) (cid:105) (cid:82) Matrices of coeﬃcients, P , such that p (z) = P , zBzTB = zTBP zB. In this case we will use the i i i i notation ZB (resp. ZdB) to represent the matrix generated from the standard basis as ZB = zBzTB (resp. Z2Bd = zdB(zdB)T ). The moments matrix M encountered earlier is simply Z2Bddµ when d = 2 and for − 0 the measure dµ = δ(z z )dz. 0 I For the general set of polynomials p (z), p (z), . . . , p (z), we let denote the ideal generated by those poly- 1 2 m nomials. This set is deﬁned as from all the combinations that are generated by multiplying the polynomials ∈ R p (z) by any other polynomials h (z) [z]. i i    (cid:88)    I ∈ R (p , . . . , p ) := p (z)h (z), for polynomials h (z) [z] (1.21) 1 m j j j ∈ j [m] I Equivalently, we will use to denote the truncated ideal, whose maximal degree is bounded by d, d    (cid:88)    I ∈ R ≤ − (p , . . . , p ) := p (z)h (z), h (z) [z], deg(h ) d deg(p ) (1.22) d 1 m j j j j j ∈ j [m] Given the matrix ZdB = zdB(zdB)T used to represent monomials of degree at most 2d, when writing polynomials in matrix form, we will need to access monomials of a given degree. As an example, consider the univariate monomial basis (1, z, z2, z3, . . .). The corresponding matrix for the monomial basis truncated at degree 4 reads 11

text: R

text: R

text: For

text: some

text: polynomials

text: p

text: (z),

text: p

text: (z),

text: p

text: (z)

text: [z]

text: where

text: [z]

text: is

text: used

text: to

text: denote

text: the

text: ring

text: of

text: multivariate

text: poly-

text: ∈m

text: R

text: nomials

text: in

text: the

text: optimization

text: variable

text: z

text: m+n

text: We

text: will

text: sometimes

text: use

text: the

text: compact

text: notation

text: p

text: (z)

text: j

text: j

text: [J]

text: to

text: denote

text: the

text: set

text: of

text: polynomial

text: constraints.

text: This

text: set

text: of

text: constraints

text: deﬁnes

text: a

text: semialgebraic

text: set

text: K

text: of

text: feasible

text: points,

text: which

text: we

text: write

text: as

text: R

text: K

text: z

text: m+n

text: p

text: (z)

text: p

text: (z)

text: m

text: R

text: N

text: For

text: z

text: m+n

text: and

text: α

text: m+n

text: we

text: introduce

text: the

text: multi-index

text: notation

text: zα

text: zαn

text: with

text: n

text: α

text: α

text: α

text: α

text: the

text: degree

text: of

text: the

text: monomial

text: zα.

text: We

text: will

text: use

text: zB

text: to

text: denote

text: the

text: sequence

text: Rn

text: of

text: all

text: monomials

text: in

text: z

text: m+n

text: for

text: some

text: standard

text: ordering

text: (standard

text: monomial

text: basis).

text: Hence

text: zB

text: z

text: z

text: z

text: z

text: zα,

text: Similarly,

text: let

text: ztB

text: denote

text: the

text: vector

text: of

text: all

text: monomials

text: zα

text: from

text: the

text: stan-

text: dard

text: basis

text: with

text: degree

text: bounded

text: by

text: t:

text: α

text: d.

text: In

text: this

text: paper,

text: polynomials

text: will

text: be

text: alternatively

text: be

text: denoted

text: through

text: either

text: of

text: the

text: representations

text: below,

text: Weigthed

text: sums

text: of

text: monomials

text: p

text: (z)

text: (p

text: zα,

text: where

text: the

text: (p

text: thus

text: denotes

text: the

text: coeﬃcient

text: of

text: the

text: i

text: α

text: i

text: α

text: i

text: α

text: monomial

text: zα

text: in

text: p

text: (z).

text: i

text: Vectors/sequences

text: of

text: coeﬃcients

text: p

text: ((p

text: ∈N

text: as

text: p

text: (z)

text: pT

text: zB

text: i

text: i

text: α

text: α

text: n

text: i

text: i

text: Matrices

text: of

text: coeﬃcients,

text: P

text: such

text: that

text: p

text: (z)

text: P

text: zBzTB

text: zTBP

text: zB.

text: In

text: this

text: case

text: we

text: will

text: use

text: the

text: i

text: i

text: i

text: i

text: notation

text: ZB

text: (resp.

text: ZdB)

text: to

text: represent

text: the

text: matrix

text: generated

text: from

text: the

text: standard

text: basis

text: as

text: ZB

text: zBzTB

text: (resp.

text: zdB(zdB)T

text: The

text: moments

text: matrix

text: M

text: encountered

text: earlier

text: is

text: simply

text: when

text: d

text: and

text: for

text: the

text: measure

text: dµ

text: δ(z

text: z

text: )dz.

text: I

text: For

text: the

text: general

text: set

text: of

text: polynomials

text: p

text: (z),

text: p

text: (z),

text: p

text: (z),

text: we

text: let

text: denote

text: the

text: ideal

text: generated

text: by

text: those

text: poly-

text: m

text: nomials.

text: This

text: set

text: is

text: deﬁned

text: as

text: from

text: all

text: the

text: combinations

text: that

text: are

text: generated

text: by

text: multiplying

text: the

text: polynomials

text: R

text: p

text: (z)

text: by

text: any

text: other

text: polynomials

text: h

text: (z)

text: [z].

text: i

text: i

text: I

text: R

text: (p

text: p

text: p

text: (z)h

text: (z),

text: for

text: polynomials

text: h

text: (z)

text: [z]

text: m

text: j

text: j

text: j

text: j

text: [m]

text: I

text: Equivalently,

text: we

text: will

text: use

text: to

text: denote

text: the

text: truncated

text: ideal,

text: whose

text: maximal

text: degree

text: is

text: bounded

text: by

text: d,

text: d

text: I

text: R

text: (p

text: p

text: p

text: (z)h

text: (z),

text: h

text: (z)

text: [z],

text: deg(h

text: d

text: deg(p

text: d

text: m

text: j

text: j

text: j

text: j

text: j

text: j

text: [m]

text: Given

text: the

text: matrix

text: ZdB

text: zdB(zdB)T

text: used

text: to

text: represent

text: monomials

text: of

text: degree

text: at

text: most

text: when

text: writing

text: polynomials

text: in

text: matrix

text: form,

text: we

text: will

text: need

text: to

text: access

text: monomials

text: of

text: a

text: given

text: degree.

text: As

text: an

text: example,

text: consider

text: the

text: univariate

text: monomial

text: basis

text: z,

text: The

text: corresponding

text: matrix

text: for

text: the

text: monomial

text: basis

text: truncated

text: at

text: degree

text: reads


text: 2.2 Sum-of-squares and positive semideﬁnite matrices (cid:80) We call sum-of-squares (SOS) polynomial, any polynomial p(z) for which there exists a decomposition p(z) = m s2(z) for some polynomials s ∈ R[z]. Introducing a polynomial version of proposition 1 j=1 j j requires the following lemma from [37] relating SOS and semideﬁnite programming (SDP). For completeness we al(cid:80)so provide a proof. (cid:88) N ∈ N Proposition 2 (Equivalence between SOS and SDP). Let K denoe the set set of K-tuples α K such ≤ ∈ R 2t that α 2t and let xα = xα1xα2 . . . xαK. Let p(z) [z] with p(z) = p xα be a polynomial of i i 1 2 K α ∈N ≤ α K2t degree 2t, the following assertions are equivalent, [1)] 1. p(z) is a sum-of-squares polynomial 2. There exists a positive semideﬁnite matrix A such that p(z) = zTBAzB, (2.9) ¯ (cid:80) { } Proof. If p(x) is SOS then p(x) = s2(x) for some polynomial s (x). Let d = max deg(s ) denote (cid:80) j j (cid:100) (cid:101) j j the maximum degree of the s (x). Further let δ = d/2 . For each of the s (x), for some ordering of the monomials, construct the corrjesponding vector of coeﬃcients s ∈ Rδ wit(cid:80)h s j(x) = sT xB, then the positive ≥ j j j semideﬁnite matr(cid:80)ix A = s sT satisﬁes xT Ax = p(x) 0 for all x. Conversely, let A be a matrix such j(cid:23)j j ≥ that p(x) = xT Ax. Since A 0, it has the spectral decomposition A = µ v vT for some µ 0. Then j j j j j we write p(x) = µ (xT v )2, which is a sum of squares. j j j It is important to notice that proposition 2 doesn’t provide a strict equivalence between a matrix certiﬁcate and a polynomial certiﬁcate. Observe that the existence of a sum-of-squares polynomial p(x) such that p(x) = µT Aµ doesn’t imply that A is positive semideﬁnite. In other words, not all matrices encoding x x sum-of-squares polynomials are PSD. As an illustration, consider the following example:       Example 1 (sum-of-squares and positive semideﬁniteness).       0 0 0 0 0 1/2 0 0 1/4 A = 0 1 0 , B = 0 0 0 , C = 0 1/2 0 . 0 0 0 1/2 0 0 1/4 0 0 For the vector of monomials zB = (1 z z2). All those matrices are encoding the same SOS polynomial p(z) zTBAzB = zTBBzB = zTBCzB = p(z) = z2. However, only one of them is positive semideﬁnite. The second and third ones can therefore not be used as (cid:104) (cid:105) the matrix form of a SOS-type certiﬁcate. However, note that there exists a matrix ξ such that ξ, Bγ = 0 for all γ, satisfying C + ξ = A or equivalently B + ξ = A. Indeed, for C it suﬃces to take   − 0 0 1/4 ξ = 0 1/2 0 − 1/4 0 0 15 ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Sum-of-squares

text: and

text: positive

text: semideﬁnite

text: matrices

text: We

text: call

text: sum-of-squares

text: (SOS)

text: polynomial,

text: any

text: polynomial

text: p(z)

text: for

text: which

text: there

text: exists

text: a

text: decomposition

text: p(z)

text: m

text: for

text: some

text: polynomials

text: s

text: R[z].

text: Introducing

text: a

text: polynomial

text: version

text: of

text: proposition

text: j

text: j

text: requires

text: the

text: following

text: lemma

text: from

text: relating

text: SOS

text: and

text: semideﬁnite

text: programming

text: (SDP).

text: For

text: completeness

text: we

text: provide

text: a

text: proof.

text: N

text: N

text: Proposition

text: (Equivalence

text: between

text: SOS

text: and

text: SDP).

text: Let

text: K

text: denoe

text: the

text: set

text: set

text: of

text: K-tuples

text: α

text: K

text: such

text: R

text: that

text: α

text: and

text: let

text: xα

text: xαK.

text: Let

text: p(z)

text: [z]

text: with

text: p(z)

text: p

text: xα

text: be

text: a

text: polynomial

text: of

text: i

text: i

text: K

text: α

text: ∈N

text: α

text: degree

text: the

text: following

text: assertions

text: are

text: equivalent,

text: p(z)

text: is

text: a

text: sum-of-squares

text: polynomial

text: There

text: exists

text: a

text: positive

text: semideﬁnite

text: matrix

text: A

text: such

text: that

text: p(z)

text: zTBAzB,

text: Proof.

text: If

text: p(x)

text: is

text: SOS

text: then

text: p(x)

text: for

text: some

text: polynomial

text: s

text: (x).

text: Let

text: d

text: max

text: deg(s

text: denote

text: j

text: j

text: j

text: j

text: the

text: maximum

text: degree

text: of

text: the

text: s

text: (x).

text: Further

text: let

text: δ

text: For

text: each

text: of

text: the

text: s

text: (x),

text: for

text: some

text: ordering

text: of

text: the

text: monomials,

text: construct

text: the

text: corrjesponding

text: vector

text: of

text: coeﬃcients

text: s

text: Rδ

text: s

text: j(x)

text: sT

text: xB,

text: then

text: the

text: positive

text: j

text: j

text: j

text: semideﬁnite

text: A

text: s

text: sT

text: satisﬁes

text: xT

text: Ax

text: p(x)

text: for

text: all

text: x.

text: Conversely,

text: let

text: A

text: be

text: a

text: matrix

text: such

text: j

text: that

text: p(x)

text: xT

text: Ax.

text: Since

text: A

text: it

text: has

text: the

text: spectral

text: decomposition

text: A

text: µ

text: v

text: vT

text: for

text: some

text: µ

text: Then

text: j

text: j

text: j

text: j

text: j

text: we

text: write

text: p(x)

text: µ

text: (xT

text: v

text: which

text: is

text: a

text: sum

text: of

text: squares.

text: j

text: j

text: j

text: It

text: is

text: important

text: to

text: notice

text: that

text: proposition

text: doesn’t

text: provide

text: a

text: strict

text: equivalence

text: between

text: a

text: matrix

text: certiﬁcate

text: and

text: a

text: polynomial

text: certiﬁcate.

text: Observe

text: that

text: the

text: existence

text: of

text: a

text: sum-of-squares

text: polynomial

text: p(x)

text: such

text: that

text: p(x)

text: µT

text: Aµ

text: doesn’t

text: imply

text: that

text: A

text: is

text: positive

text: semideﬁnite.

text: In

text: other

text: words,

text: not

text: all

text: matrices

text: encoding

text: x

text: x

text: sum-of-squares

text: polynomials

text: are

text: PSD.

text: As

text: an

text: illustration,

text: consider

text: the

text: following

text: example:

text: Example

text: (sum-of-squares

text: and

text: positive

text: semideﬁniteness).

text: A

text: B

text: C

text: For

text: the

text: vector

text: of

text: monomials

text: zB

text: z

text: All

text: those

text: matrices

text: are

text: encoding

text: the

text: same

text: SOS

text: polynomial

text: p(z)

text: zTBAzB

text: zTBBzB

text: zTBCzB

text: p(z)

text: However,

text: only

text: one

text: of

text: them

text: is

text: positive

text: semideﬁnite.

text: The

text: second

text: and

text: third

text: ones

text: can

text: therefore

text: not

text: be

text: used

text: as

text: the

text: matrix

text: form

text: of

text: a

text: SOS-type

text: certiﬁcate.

text: However,

text: note

text: that

text: there

text: exists

text: a

text: matrix

text: ξ

text: such

text: that

text: ξ,

text: Bγ

text: for

text: all

text: γ,

text: satisfying

text: C

text: ξ

text: A

text: or

text: equivalently

text: B

text: ξ

text: A.

text: Indeed,

text: for

text: C

text: it

text: suﬃces

text: to

text: take

text: ξ

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: The ﬁrst constraint in formulation (3.1) is simply the (cid:96) norm of the constraints appearing in (2.1). In this 2 ﬁrst constraint, the ﬁrst sum is taken over the diﬀerent noisy polynomials h and the second is taken over (cid:96) all the “shifts” of those polynomials. For a given κ, the corresponding shifted polynomial is simply obtained by multiplying h by the corresponding monomial zκ. (cid:96) It is worth pointing out that formulation (3.1) is not unit-independent, since the moment matrix M mixes diﬀerent powers of the original variables. This can be remedied by assigning dimensional weights w to the γ B matrices – an operation that modiﬁes the numerics and the theory in an obvious way. Formulation (3.1) γ leads to the recovery result of Theorem 2 which is restated below for clari(cid:113)ty. (cid:80) ∈ R − Theorem 2. Let M denote the rank one matrix introduced in (1.14) for z m+n 1. Assume that the 0 0 (cid:107) (cid:107) necessary and suﬃcient conditions of lemma 1 are satisﬁed. Let ε = ∈ ε2 . Let M denote the 2 (i,j) Ω ij solution to the semideﬁnite program (1.16). This solution satisﬁes (cid:107) − (cid:107) M M ≤ (cid:107) (cid:107) (cid:107) (cid:107) 0 F C (m + n)7/2 ε . (1.17) M 0 2 0 F The constant C depends on the entries of X , but not on Ω, m, n, or ε. 0 0 The stability result of Theorem 2 can be improved if a path is known that relates one entry to all the others. O O In this last case, the scalings can be reduced from ((m + n)7/2) to ((m + n)2). This is the point of Corollary 3 which is proved in section 3.2, Corollary 3. Assume that the paths in the bipartite graph relating each of the unknown vertices x (resp. i y ) to the root node y are explicitly given. Then we have the following stability estimate, j (cid:96) (cid:107) − (cid:107) M M ≤ (cid:107) (cid:107) (cid:107) (cid:107) 0 F C (m + n)2 ε . (1.18) M 0 2 0 F The constant C depends on the entries of X , but not on Ω, m, n, or ε. 0 0 P P Let , . . . , denote the sets of constraints that appear along each path between the root node and the 1 P leaf nodes in the sense of (1.4). As explained in section 2.3, the dual certiﬁcate only relies on the monomials (cid:113) appearing along each of the paths multiplied either by the previous missing variable or the next one. For P K each path , let denote the subset of multi-indices corresponding to variables that are multiplying the i i (cid:48) ≥ (cid:107) (cid:107) constraints in the chain in the expression of the certiﬁcate (2.11). Let η ε 1 + sup| |≤ z2α. The 2 α 1 0 formulation for Corollary 3 is obtained by replacing the (cid:96) constraint in (3.1) by a corresponding (cid:96) term 2 2 minimizing the noise along the paths, (cid:118) (cid:117) (cid:12) (cid:12) (cid:117) (cid:12) (cid:12) (cid:117) (cid:88) (cid:88) (cid:12)(cid:88) (cid:12) (cid:116) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12)2 (h˜ ) (cid:104) (cid:105) ≤ (cid:48) (cid:107) (cid:96) ζ(cid:107) M, B η , i = 1, . . . , P. (3.2) κ∈Ki (cid:96)∈Pi ζ Bζ+κ 2F ζ+κ (cid:48) The improvement in the prefactors of Theorem 2 essentially arises from the tighter bound η on the (cid:96) 2 constraints in (3.2). This tighter bound is due to the fact that along a given path, the constraints are always 19 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: The

text: ﬁrst

text: constraint

text: in

text: formulation

text: is

text: simply

text: the

text: norm

text: of

text: the

text: constraints

text: appearing

text: in

text: In

text: this

text: ﬁrst

text: constraint,

text: the

text: ﬁrst

text: sum

text: is

text: taken

text: over

text: the

text: diﬀerent

text: noisy

text: polynomials

text: h

text: and

text: the

text: second

text: is

text: taken

text: over

text: all

text: the

text: “shifts”

text: of

text: those

text: polynomials.

text: For

text: a

text: given

text: κ,

text: the

text: corresponding

text: shifted

text: polynomial

text: is

text: simply

text: obtained

text: by

text: multiplying

text: h

text: by

text: the

text: corresponding

text: monomial

text: zκ.

text: It

text: is

text: worth

text: pointing

text: out

text: that

text: formulation

text: is

text: not

text: unit-independent,

text: since

text: the

text: moment

text: matrix

text: M

text: mixes

text: diﬀerent

text: powers

text: of

text: the

text: original

text: variables.

text: This

text: can

text: be

text: remedied

text: by

text: assigning

text: dimensional

text: weights

text: w

text: to

text: the

text: γ

text: B

text: matrices

text: an

text: operation

text: that

text: modiﬁes

text: the

text: numerics

text: and

text: the

text: theory

text: in

text: an

text: obvious

text: way.

text: Formulation

text: γ

text: leads

text: to

text: the

text: recovery

text: result

text: of

text: Theorem

text: which

text: is

text: restated

text: below

text: for

text: R

text: Theorem

text: Let

text: M

text: denote

text: the

text: rank

text: one

text: matrix

text: introduced

text: in

text: for

text: z

text: m+n

text: Assume

text: that

text: the

text: necessary

text: and

text: suﬃcient

text: conditions

text: of

text: lemma

text: are

text: satisﬁed.

text: Let

text: ε

text: ε2

text: Let

text: M

text: denote

text: the

text: (i,j)

text: Ω

text: ij

text: solution

text: to

text: the

text: semideﬁnite

text: program

text: This

text: solution

text: satisﬁes

text: M

text: M

text: F

text: C

text: (m

text: ε

text: M

text: F

text: The

text: constant

text: C

text: depends

text: on

text: the

text: entries

text: of

text: X

text: but

text: not

text: on

text: Ω,

text: m,

text: n,

text: or

text: ε.

text: The

text: stability

text: result

text: of

text: Theorem

text: can

text: be

text: improved

text: if

text: a

text: path

text: is

text: known

text: that

text: relates

text: one

text: entry

text: to

text: all

text: the

text: others.

text: O

text: O

text: In

text: this

text: last

text: case,

text: the

text: scalings

text: can

text: be

text: reduced

text: from

text: ((m

text: to

text: ((m

text: This

text: is

text: the

text: point

text: of

text: Corollary

text: which

text: is

text: proved

text: in

text: section

text: Corollary

text: Assume

text: that

text: the

text: paths

text: in

text: the

text: bipartite

text: graph

text: relating

text: each

text: of

text: the

text: unknown

text: vertices

text: x

text: (resp.

text: i

text: y

text: to

text: the

text: root

text: node

text: y

text: are

text: explicitly

text: given.

text: Then

text: we

text: have

text: the

text: following

text: stability

text: estimate,

text: j

text: M

text: M

text: F

text: C

text: (m

text: ε

text: M

text: F

text: The

text: constant

text: C

text: depends

text: on

text: the

text: entries

text: of

text: X

text: but

text: not

text: on

text: Ω,

text: m,

text: n,

text: or

text: ε.

text: P

text: P

text: Let

text: denote

text: the

text: sets

text: of

text: constraints

text: that

text: appear

text: along

text: each

text: path

text: between

text: the

text: root

text: node

text: and

text: the

text: P

text: leaf

text: nodes

text: in

text: the

text: sense

text: of

text: As

text: explained

text: in

text: section

text: the

text: dual

text: certiﬁcate

text: only

text: relies

text: on

text: the

text: monomials

text: appearing

text: along

text: each

text: of

text: the

text: paths

text: multiplied

text: either

text: by

text: the

text: previous

text: missing

text: variable

text: or

text: the

text: next

text: one.

text: For

text: P

text: K

text: each

text: path

text: let

text: denote

text: the

text: subset

text: of

text: multi-indices

text: corresponding

text: to

text: variables

text: that

text: are

text: multiplying

text: the

text: i

text: i

text: constraints

text: in

text: the

text: chain

text: in

text: the

text: expression

text: of

text: the

text: certiﬁcate

text: Let

text: η

text: ε

text: sup|

text: The

text: α

text: formulation

text: for

text: Corollary

text: is

text: obtained

text: by

text: replacing

text: the

text: constraint

text: in

text: by

text: a

text: corresponding

text: term

text: minimizing

text: the

text: noise

text: along

text: the

text: paths,

text: (h˜

text: M,

text: B

text: η

text: i

text: P.

text: κ∈Ki

text: ζ

text: Bζ+κ

text: ζ+κ

text: The

text: improvement

text: in

text: the

text: prefactors

text: of

text: Theorem

text: essentially

text: arises

text: from

text: the

text: tighter

text: bound

text: η

text: on

text: the

text: constraints

text: in

text: This

text: tighter

text: bound

text: is

text: due

text: to

text: the

text: fact

text: that

text: along

text: a

text: given

text: path,

text: the

text: constraints

text: are

text: always

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: distinct and that following the discussion in section (2.3), one can express each ﬁrst order monomial that appear in the path from the constraints along the path multiplied by either the ﬁrst or the previous or next missing degree one monomial. This idea is expressed through section 3.2. 3.1 Proof of Theorem 2 (cid:107) (cid:107) (cid:32) (cid:33) Let M p to denote the Schatten p-norm of M, (cid:88) 1/p (cid:107) (cid:107) M = σp . p k k (cid:107) (cid:107) (cid:107) (cid:107) (cid:107) (cid:107) (cid:107) (cid:107) We therefore have M = M ∗ which denotes the nuclear norm of M, M = M which is used to 1 (cid:107) (cid:107) (cid:107) (cid:107) 2 F denote the Frobenius norm of M and M ∞ = M which denotes the operator norm of M. Any solution M to (3.1) reads M = H + M . To prove stability of the recovery, we ﬁrst highlight the 0 following, • ≤ ≤ Tr(M + H) Tr(M ) and therefore Tr(H) 0. 0 0 • Both M and M are feasible points for (3.1), and hence both satisfy the normalization constraint 0 − M = (M ) which can be exactly enforced. As a consequence, H = (M ) M = 0, and all 11 0 11 11 0 11 11 degree zero terms in the constraints h˜ , . . . , h˜ vanish when those constraints are applied to H. We 1 L have (h˜ ) (cid:104) (cid:105) (cid:107) (cid:96) (cid:107)0 H, B = 0, (cid:96) = 1, . . . , L. (3.3) B 2 0 0 F More generally, for both M and M , as η is bounding the vector (ε zκ) | |≤ of weighted residuals, (cid:12) (cid:12) 0 (cid:12) (cid:96) 0(cid:12) (cid:96), κ 2 we must h(cid:88)ave(cid:12)(cid:12),(cid:88) (cid:12)(cid:12) (cid:88) (cid:12)(cid:12)(cid:88) (cid:12)(cid:12) (cid:88) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12)2 (cid:12) (cid:12)2 (cid:104) (cid:105) (cid:104) (cid:105) − ≤ ≤ (h˜ ) B , M = (h ) B , M ε zκ (ε zα)2 η2 (cid:96) ζ ζ+κ (cid:12)0 (cid:96) ζ (cid:12) ζ+κ 0 (cid:96) 0 (cid:96) 0 (cid:12) (cid:12) (cid:96),κ ζ (cid:88) (cid:12)(cid:88) (cid:96),κ ζ (cid:12) (cid:88) (cid:96),κ (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12)2 (cid:104) (cid:105) ≤ ≤ (h˜ ) B , M (ε zα)2 η2 (cid:96) ζ ζ+κ (cid:96) 0 (cid:96),κ ζ (cid:96),κ (cid:118) (cid:118) (cid:117) (cid:12) (cid:12) (cid:117) (cid:12) (cid:12) From tho(cid:117)se relation(cid:12)s we can derive a similar(cid:12)boun(cid:117)d on H, (cid:12) (cid:12) (cid:117)(cid:88) (cid:88) (cid:12)(cid:88) (cid:12) (cid:117)(cid:88) (cid:88) (cid:12)(cid:88) (cid:12) (cid:116) (cid:12) (cid:12) (cid:116) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12)2 (cid:12) (cid:12)2 (h˜ ) (cid:104) (cid:105) (h˜ ) (cid:104) − (cid:105) (cid:107) (cid:96) ζ(cid:107) H, B = (cid:107) (cid:96) ζ(cid:107) M M , B B 2 ζ+κ B 2 0 ζ+κ κ (cid:96) ζ ζ+κ F κ (cid:96) ζ ζ+κ F ≤ 2η. • (cid:23) (cid:104) (cid:105) ≥ (cid:23) ∈ ⊥ Finally, note that H + M 0 implies H + M , W 0 for all W 0 including all W T which (cid:23) 0 0 implies H ⊥ 0. T 20 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: distinct

text: and

text: that

text: following

text: the

text: discussion

text: in

text: section

text: one

text: can

text: express

text: each

text: ﬁrst

text: order

text: monomial

text: that

text: appear

text: in

text: the

text: path

text: from

text: the

text: constraints

text: along

text: the

text: path

text: multiplied

text: by

text: either

text: the

text: ﬁrst

text: or

text: the

text: previous

text: or

text: next

text: missing

text: degree

text: one

text: monomial.

text: This

text: idea

text: is

text: expressed

text: through

text: section

text: Proof

text: of

text: Theorem

text: Let

text: M

text: p

text: to

text: denote

text: the

text: Schatten

text: p-norm

text: of

text: M,

text: M

text: σp

text: p

text: k

text: k

text: We

text: therefore

text: have

text: M

text: M

text: which

text: denotes

text: the

text: nuclear

text: norm

text: of

text: M,

text: M

text: M

text: which

text: is

text: used

text: to

text: F

text: denote

text: the

text: Frobenius

text: norm

text: of

text: M

text: and

text: M

text: M

text: which

text: denotes

text: the

text: operator

text: norm

text: of

text: M.

text: Any

text: solution

text: M

text: to

text: reads

text: M

text: H

text: M

text: To

text: prove

text: stability

text: of

text: the

text: recovery,

text: we

text: ﬁrst

text: highlight

text: the

text: following,

text: Tr(M

text: H)

text: Tr(M

text: and

text: therefore

text: Tr(H)

text: Both

text: M

text: and

text: M

text: are

text: feasible

text: points

text: for

text: and

text: hence

text: both

text: satisfy

text: the

text: normalization

text: constraint

text: M

text: (M

text: which

text: can

text: be

text: exactly

text: enforced.

text: As

text: a

text: consequence,

text: H

text: (M

text: M

text: and

text: all

text: degree

text: zero

text: terms

text: in

text: the

text: constraints

text: h˜

text: h˜

text: vanish

text: when

text: those

text: constraints

text: are

text: applied

text: to

text: H.

text: We

text: L

text: have

text: (h˜

text: H,

text: B

text: L.

text: B

text: F

text: More

text: generally,

text: for

text: both

text: M

text: and

text: M

text: as

text: η

text: is

text: bounding

text: the

text: vector

text: (ε

text: zκ)

text: of

text: weighted

text: residuals,

text: κ

text: we

text: must

text: (h˜

text: B

text: M

text: (h

text: B

text: M

text: ε

text: zκ

text: (ε

text: η2

text: ζ

text: ζ+κ

text: ζ

text: ζ+κ

text: ζ

text: ζ

text: (h˜

text: B

text: M

text: (ε

text: η2

text: ζ

text: ζ+κ

text: ζ

text: From

text: we

text: can

text: derive

text: a

text: on

text: H,

text: (h˜

text: (h˜

text: H,

text: B

text: M

text: M

text: B

text: B

text: ζ+κ

text: B

text: ζ+κ

text: κ

text: ζ

text: ζ+κ

text: F

text: κ

text: ζ

text: ζ+κ

text: F

text: Finally,

text: note

text: that

text: H

text: M

text: implies

text: H

text: M

text: W

text: for

text: all

text: W

text: including

text: all

text: W

text: T

text: which

text: implies

text: H

text: T

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: (cid:13)  (cid:13)  (cid:13) (cid:13) (cid:13) (cid:88) (cid:13) (cid:13)  (cid:13)  (cid:13) (cid:13) (cid:13) (cid:13) (cid:107) (cid:107) (cid:46) (h˜ ) (cid:104) (cid:105) (cid:107) (cid:107) | | y(α,β) 2 (m + n) |(cid:13)(cid:13)(cid:13)(cid:13)(cid:13)ζ|>0(cid:88)(cid:107)B(cid:96)ζ(cid:107)ζ2F HT , Bζ (cid:96) 1 +(cid:13)(cid:13)(cid:13)(cid:13)(cid:13) HT⊥ 1 + y1 (3.40) (cid:13) (cid:13) (cid:46) (h˜ ) (cid:104) (cid:105) (cid:107) (cid:107) (m + n) (cid:107) (cid:96) (cid:107)ζ H , B + H ⊥ (3.41) |ζ|>0 Bζ 2F T ζ T 1 (cid:96) 1 | | | | | − | | | In (3.41), we again use y (m ) = (H ) = H (H ⊥) = (H ⊥) . Combining (3.36) and (3.41), 1 0 1 T 11 11 T 11 T 11 we get the following bound on H , T  (cid:12) (cid:12)  (cid:107) (cid:107) ≤ (cid:107) (cid:107) (cid:107) (cid:107) (cid:88) (cid:12)(cid:12) (cid:88) (cid:12)(cid:12) HT F m0 2 y 2  (cid:12) (cid:12)  (cid:12) (cid:12) (cid:12) (cid:12) ≤ (cid:107) (cid:107) (h˜ ) (cid:104) (cid:105) (cid:107) (cid:107) C m (m + n) (cid:107) (cid:96) (cid:107)ζ H , B + H ⊥ . (3.42) 5 0 2 (cid:96) |ζ|>0 Bζ 2F T ζ T 1 − The second term can be bounded by (3.33). To bound the ﬁrst term, note that we have H = H H ⊥ T T and that the expression obtained by considering the ﬁrst term above and substituting H for H can be T bounded through the (cid:96) constraint in (3.1). We can thus focus on bounding this term when replacing H ⊥ 2 | | T by H . In each ﬁrst order constraint h˜ , there is only one non zero coeﬃcient (h˜ ) for ζ > 0 and each B T O (cid:96) (cid:96) ζ γ only has (1) non zero entries. Moreover none of the constraints in the chain are targeting the same entry ⊥ in H . Let Ω denote the moments matrix deﬁned as (Ω ) = sign(h ) , for a√ll ζ such that there exists a T (cid:54) P P ζ (cid:96) ζ O (cid:96) with (h ) = 0, and 0 otherwise. This matrix has Frobenius norm at most ( m + n). Using this matrix, (cid:96) ζ we can write, (cid:12) (cid:12) (cid:12) (cid:12) (cid:88) (cid:12) (cid:88) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (h˜ ) (cid:104) (cid:105) ≤ (cid:104) ⊥(cid:105) (cid:107) (cid:96) (cid:107)ζ H ⊥, B C Ω , H (3.43) (cid:96) |ζ|>0 Bζ 2F T ζ 6 P T ≤ (cid:107) (cid:107) C (m + n)1/2 H ⊥ (3.44) 6 T F ≤ (cid:107) (cid:107) C (m + n)1/2 H ⊥ (3.45) 6 T 1 O In (3.43), we use H¨older’s inequality, together with the fact that the chain has length (m + n). Using the trace bound (3.33), and substituting (3.45) into (3.42), we ﬁnally get the bound on H as, T  (cid:12) (cid:12) (cid:12) (cid:12) (cid:88) (cid:12)(cid:88) (cid:12)  (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:107) (cid:107) ≤ (cid:107) (cid:107) (cid:107) (cid:107) (h˜ ) (cid:104) (cid:105) (H ) C (m + n) m (cid:18) (m + n)1/2 H ⊥ + (cid:107) (cid:96) (cid:107)(cid:19)ζ H, B (3.46) T F 7 0 2 T 1 B 2 ζ (cid:96) ζ ζ F ≤ (cid:107) (cid:107) (cid:8) |(cid:104) (cid:105)| (cid:9) C (m + n) m (m + n)1/2 H, Y + 2η(m + n)1/2 (3.47) 7 0 2 1 ≤ (cid:107) (cid:107) O (cid:107) (cid:107) (cid:107) (cid:107) C (m + n)3/2 m max (m + n)2η, ((m + n)2) m ε ∞ (3.48) 7 0 2 0 2 ≤ (cid:107) (cid:107) C m 2(m + n)5/2η. (3.49) 7 0 2 27 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: (h˜

text: y(α,β)

text: (m

text: n)

text: HT

text: Bζ

text: 1

text: HT⊥

text: y1

text: (h˜

text: (m

text: n)

text: H

text: B

text: H

text: Bζ

text: T

text: ζ

text: T

text: In

text: we

text: again

text: use

text: y

text: (m

text: (H

text: H

text: (H

text: (H

text: Combining

text: and

text: T

text: T

text: T

text: we

text: get

text: the

text: following

text: bound

text: on

text: H

text: T

text: HT

text: F

text: y

text: (h˜

text: C

text: m

text: (m

text: n)

text: H

text: B

text: H

text: Bζ

text: T

text: ζ

text: T

text: The

text: second

text: term

text: can

text: be

text: bounded

text: by

text: To

text: bound

text: the

text: ﬁrst

text: term,

text: note

text: that

text: we

text: have

text: H

text: H

text: H

text: T

text: T

text: and

text: that

text: the

text: expression

text: obtained

text: by

text: considering

text: the

text: ﬁrst

text: term

text: above

text: and

text: substituting

text: H

text: for

text: H

text: can

text: be

text: T

text: bounded

text: through

text: the

text: constraint

text: in

text: We

text: can

text: thus

text: focus

text: on

text: bounding

text: this

text: term

text: when

text: replacing

text: H

text: T

text: by

text: H

text: In

text: each

text: ﬁrst

text: order

text: constraint

text: h˜

text: there

text: is

text: only

text: one

text: non

text: zero

text: coeﬃcient

text: (h˜

text: for

text: ζ

text: and

text: each

text: B

text: T

text: O

text: ζ

text: γ

text: only

text: has

text: non

text: zero

text: entries.

text: Moreover

text: of

text: the

text: constraints

text: in

text: the

text: chain

text: are

text: targeting

text: the

text: same

text: entry

text: in

text: H

text: Let

text: Ω

text: denote

text: the

text: moments

text: matrix

text: deﬁned

text: as

text: (Ω

text: sign(h

text: for

text: a√ll

text: ζ

text: such

text: that

text: there

text: exists

text: a

text: T

text: P

text: P

text: ζ

text: ζ

text: O

text: with

text: (h

text: and

text: otherwise.

text: This

text: matrix

text: has

text: Frobenius

text: norm

text: at

text: most

text: m

text: n).

text: Using

text: this

text: matrix,

text: ζ

text: we

text: can

text: write,

text: (h˜

text: H

text: B

text: C

text: Ω

text: H

text: Bζ

text: T

text: ζ

text: P

text: T

text: C

text: (m

text: H

text: T

text: F

text: C

text: (m

text: H

text: T

text: O

text: In

text: we

text: use

text: H¨older’s

text: inequality,

text: together

text: with

text: the

text: fact

text: that

text: the

text: chain

text: has

text: length

text: (m

text: n).

text: Using

text: the

text: trace

text: bound

text: and

text: substituting

text: into

text: we

text: ﬁnally

text: get

text: the

text: bound

text: on

text: H

text: as,

text: T

text: (h˜

text: (H

text: C

text: (m

text: n)

text: m

text: (m

text: H

text: H,

text: B

text: T

text: F

text: T

text: B

text: ζ

text: ζ

text: ζ

text: F

text: C

text: (m

text: n)

text: m

text: (m

text: H,

text: Y

text: O

text: C

text: (m

text: m

text: max

text: (m

text: ((m

text: m

text: ε

text: C

text: m

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##