text: Solving Distributed Constraint Optimization Problems Using Logic Programming 5 a a for i < j 1 1 x x Utilities i j 0 0 5 0 1 8 1 0 20 a a 1 1 3 2 2 a a 3 3 (a) Constraint Graph (b) Pseudo-tree (c) Utilities of Constraints xi cons xj with i < j Fig. 1. Example DCOP • A { } = a , a , a ; and • 1 2 3 α maps each variable x to agent a . i i Figure 1(b) shows one possible pseudo-tree, where the dotted line is a back edge. In this { } { } { } { } pseudo-tree, P = a , PP = a , C = a , PC = a , and sep = x , x . 3 2 3 1 1 2 1 3 3 1 2 (cid:104)X D F A (cid:105) ∈ A In a pseudo-tree T of a DCOP , , , , α , given a let RT be the set of F i ai constraints in such that: { ∈ F | ⊆ ∪ ∪ ∧ ∩ (cid:54) ∅} RT = f scp(f) α α α scp(f) α = (5) ai i Pi PPi i In the following, without causing any confusion, we often omit the superscript in RT ai (i.e., R ) if there is only one pseudo-tree mentioned in the context. ai Example 2 Considering again the DCOP in Example 1 and its pseudo-tree in Figure 1(b), we have { } R = x1 cons x3, x2 cons x3 . a3 2.2 The Distributed Pseudo-tree Optimization Procedure The Distributed Pseudo-tree Optimization Procedure (DPOP) (Petcu and Faltings 2005a) is a complete algorithm to solve DCOPs with the following three phases:3 Pseudo- tree generation, UTIL propagation and VALUE propagation. 2.2.1 Phase 1: Pseudo-tree Generation Phase DPOP does not require the use of any speciﬁc algorithm to construct the pseudo-tree. 3 Here we detail an extended version of DPOP described in (Petcu and Faltings 2005a) which removes the assumption that each agent owns exactly one variable. ##LTFigure## ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Solving

text: Distributed

text: Constraint

text: Optimization

text: Problems

text: Using

text: Logic

text: Programming

text: a

text: a

text: for

text: i

text: j

text: x

text: x

text: Utilities

text: i

text: j

text: a

text: a

text: a

text: a

text: (a)

text: Constraint

text: Graph

text: (b)

text: Pseudo-tree

text: (c)

text: Utilities

text: of

text: Constraints

text: xi

text: cons

text: xj

text: with

text: i

text: j

text: Fig.

text: Example

text: DCOP

label: list

text: A

text: a

text: a

text: a

text: and

text: α

text: maps

text: each

text: variable

text: x

text: to

text: agent

text: a

text: i

text: i

text: Figure

text: shows

text: one

text: possible

text: pseudo-tree,

text: where

text: the

text: dotted

text: line

text: is

text: a

text: back

text: edge.

text: In

text: this

text: pseudo-tree,

text: P

text: a

text: PP

text: a

text: C

text: a

text: PC

text: a

text: and

text: sep

text: x

text: x

text: D

text: F

text: A

text: A

text: In

text: a

text: pseudo-tree

text: T

text: of

text: a

text: DCOP

text: α

text: given

text: a

text: let

text: RT

text: be

text: the

text: set

text: of

text: F

text: i

text: ai

text: constraints

text: in

text: such

text: that:

text: F

text: RT

text: f

text: scp(f)

text: α

text: α

text: α

text: scp(f)

text: α

text: ai

text: i

text: Pi

text: PPi

text: i

text: In

text: the

text: following,

text: without

text: causing

text: any

text: confusion,

text: we

text: often

text: omit

text: the

text: superscript

text: in

text: RT

text: ai

text: (i.e.,

text: R

text: if

text: there

text: is

text: only

text: one

text: pseudo-tree

text: mentioned

text: in

text: the

text: context.

text: ai

text: Example

text: Considering

text: again

text: the

text: DCOP

text: in

text: Example

text: and

text: its

text: pseudo-tree

text: in

text: Figure

text: we

text: have

text: R

text: cons

text: cons

text: The

text: Distributed

text: Pseudo-tree

text: Optimization

text: Procedure

text: The

text: Distributed

text: Pseudo-tree

text: Optimization

text: Procedure

text: (DPOP)

text: (Petcu

text: and

text: Faltings

text: is

text: a

text: complete

text: algorithm

text: to

text: solve

text: DCOPs

text: with

text: the

text: following

text: three

text: Pseudo-

text: tree

text: generation,

text: UTIL

text: propagation

text: and

text: VALUE

text: propagation.

text: Phase

text: Pseudo-tree

text: Generation

text: Phase

text: DPOP

text: does

text: not

text: require

text: the

text: use

text: of

text: any

text: speciﬁc

text: algorithm

text: to

text: construct

text: the

text: pseudo-tree.

text: Here

text: we

text: detail

text: an

text: extended

text: version

text: of

text: DPOP

text: described

text: in

text: (Petcu

text: and

text: Faltings

text: which

text: removes

text: the

text: assumption

text: that

text: each

text: agent

text: owns

text: exactly

text: one

text: variable.

text: ##LTFigure##

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Solving Distributed Constraint Optimization Problems Using Logic Programming 47 JAIN, P., GUPTA, S., RANADE, S., AND PONTELLI, E. 2012. Optimum operation of a customer- driven microgrid: A comprehensive approach. In Proc. of PEDES. KAKAS, A., TORRONI, P., AND DEMETRIOU, N. 2004. Agent Planning, negotiation and control of operation. In Proc. of ECAI. KAUFMANN, B., LEONE, N., PERRI, S., AND SCHAUB, T. 2016. Grounding and solving in answer set programming. AI Magazine 37, 3, 25–32. KOWALSKI, R. AND SADRI, F. 1999. Logic programming towards multi-agent systems. Annals of Mathematics and Artiﬁcial Intelligence 25, 3-4, 391–419. KUMAR, A., FALTINGS, B., AND PETCU, A. 2009. Distributed constraint optimization with struc- tured resource constraints. In Proc. of AAMAS. 923–930. KUMAR, A., PETCU, A., AND FALTINGS, B. 2008. H-DPOP: Using hard constraints for search space pruning in DCOP. In Proc. of AAAI. 325–330. LASS, R., KOPENA, J., SULTANIK, E., NGUYEN, D., DUGAN, C., MODI, P., AND REGLI, W. 2008. Coordination of ﬁrst responders under communication and resource constraints (Short Paper). In Proc. of AAMAS. 1409–1413. LE, T., PONTELLI, E., SON, T. C., AND YEOH, W. 2014. Logic and constraint logic programming for distributed constraint optimization. CoRR abs/1405.1734. LE, T., SON, T. C., PONTELLI, E., AND YEOH, W. 2015. Solving distributed constraint optimiza- tion problems with logic programming. In Proc. of AAAI. LE´AUTE´, T. AND FALTINGS, B. 2011. Coordinating logistics operations with privacy guarantees. In Proc. of IJCAI. 2482–2487. LE´AUTE´, T., OTTENS, B., AND SZYMANEK, R. 2009. FRODO 2.0: An open-source framework for distributed constraint optimization. In Proc. of the Distributed Constraint Reasoning Workshop. 160–164. LIU, C., REN, L., LOO, B. T., MAO, Y., AND BASU, P. 2012. Cologne: A declarative distributed constraint optimization platform. Proc. of the VLDB Endowment 5, 8, 752–763. MAHESWARAN, R., PEARCE, J., AND TAMBE, M. 2004. Distributed algorithms for DCOP: A graphical game-based approach. In Proc. of PDCS. 432–439. MAHESWARAN, R., TAMBE, M., BOWRING, E., PEARCE, J., AND VARAKANTHAM, P. 2004. Tak- ing DCOP to the real world: Efﬁcient complete solutions for distributed event scheduling. In Proc. of AAMAS. 310–317. MAILLER, R. AND LESSER, V. 2004. Solving distributed constraint optimization problems using cooperative mediation. In Proc. of AAMAS. 438–445. MAREK, V. AND TRUSZCZYN´ SKI, M. 1999. Stable models and an alternative logic programming paradigm. In The Logic Programming Paradigm: a 25-year Perspective. 375–398. MODI, P., SHEN, W.-M., TAMBE, M., AND YOKOO, M. 2005. ADOPT: Asynchronous distributed constraint optimization with quality guarantees. Artiﬁcial Intelligence 161, 1–2, 149–180. NGUYEN, D. T., YEOH, W., AND LAU, H. C. 2013. Distributed Gibbs: A memory-bounded sampling-based DCOP algorithm. In Proc. of AAMAS. 167–174. NIEMELA¨ , I. 1999. Logic programming with stable model semantics as a constraint programming paradigm. Annals of Mathematics and Artiﬁcial Intelligence 25, 3–4, 241–273. OTTENS, B., DIMITRAKAKIS, C., AND FALTINGS, B. 2012. DUCT: An upper conﬁdence bound approach to distributed constraint optimization problems. In Proc. of AAAI. 528–534. PETCU, A. 2009. A Class of Algorithms for Distributed Constraint Optimization. Frontiers in Arti- ﬁcial Intelligence and Applications, vol. 194. IOS Press. PETCU, A. AND FALTINGS, B. 2005a. A scalable method for multiagent constraint optimization. In Proc. of IJCAI. 1413–1420. PETCU, A. AND FALTINGS, B. 2005b. Superstabilizing, fault-containing multiagent combinatorial optimization. In Proc. of AAAI. 449–454.

text: Solving

label: title

text: Distributed

text: Constraint

text: Optimization

text: Problems

text: Using

text: Logic

text: Programming

label: paragraph

text: JAIN,

label: reference

text: P.,

text: GUPTA,

text: S.,

text: RANADE,

text: S.,

text: AND

text: PONTELLI,

text: E.

text: Optimum

text: operation

text: of

text: a

text: customer-

text: driven

text: microgrid:

text: A

text: comprehensive

text: approach.

text: In

text: Proc.

text: of

text: PEDES.

text: KAKAS,

text: A.,

text: TORRONI,

text: P.,

text: AND

text: DEMETRIOU,

text: N.

text: Agent

text: Planning,

text: negotiation

text: and

text: control

text: of

text: operation.

text: In

text: Proc.

text: of

text: ECAI.

text: KAUFMANN,

text: B.,

text: LEONE,

text: N.,

text: PERRI,

text: S.,

text: AND

text: SCHAUB,

text: T.

text: Grounding

text: and

text: solving

text: in

text: answer

text: set

text: programming.

text: AI

text: Magazine

text: KOWALSKI,

text: R.

text: AND

text: SADRI,

text: F.

text: Logic

text: programming

text: towards

text: multi-agent

text: systems.

text: Annals

text: of

text: Mathematics

text: and

text: Artiﬁcial

text: Intelligence

text: KUMAR,

text: A.,

text: FALTINGS,

text: B.,

text: AND

text: PETCU,

text: A.

text: Distributed

text: constraint

text: optimization

text: with

text: struc-

text: tured

text: resource

text: constraints.

text: In

text: Proc.

text: of

text: AAMAS.

text: KUMAR,

text: A.,

text: PETCU,

text: A.,

text: AND

text: FALTINGS,

text: B.

text: H-DPOP:

text: Using

text: hard

text: constraints

text: for

text: search

text: space

text: pruning

text: in

text: DCOP.

text: In

text: Proc.

text: of

text: AAAI.

text: LASS,

text: R.,

text: KOPENA,

text: J.,

text: SULTANIK,

text: E.,

text: NGUYEN,

text: D.,

text: DUGAN,

text: C.,

text: MODI,

text: P.,

text: AND

text: REGLI,

text: W.

text: Coordination

text: of

text: ﬁrst

text: responders

text: under

text: communication

text: and

text: resource

text: constraints

text: (Short

text: Paper).

text: In

text: Proc.

text: of

text: AAMAS.

text: LE,

text: T.,

text: PONTELLI,

text: E.,

text: SON,

text: T.

text: C.,

text: AND

text: YEOH,

text: W.

text: Logic

text: and

text: constraint

text: logic

text: programming

text: for

text: distributed

text: constraint

text: optimization.

text: CoRR

text: LE,

text: T.,

text: SON,

text: T.

text: C.,

text: PONTELLI,

text: E.,

text: AND

text: YEOH,

text: W.

text: Solving

text: distributed

text: constraint

text: optimiza-

text: tion

text: problems

text: with

text: logic

text: programming.

text: In

text: Proc.

text: of

text: AAAI.

text: LE´AUTE´,

text: T.

text: AND

text: FALTINGS,

text: B.

text: Coordinating

text: logistics

text: operations

text: with

text: privacy

text: guarantees.

text: In

text: Proc.

text: of

text: IJCAI.

text: LE´AUTE´,

text: T.,

text: OTTENS,

text: B.,

text: AND

text: SZYMANEK,

text: R.

text: FRODO

text: An

text: open-source

text: framework

text: for

text: distributed

text: constraint

text: optimization.

text: In

text: Proc.

text: of

text: the

text: Distributed

text: Constraint

text: Reasoning

text: Workshop.

text: LIU,

text: C.,

text: REN,

text: L.,

text: LOO,

text: B.

text: T.,

text: MAO,

text: Y.,

text: AND

text: BASU,

text: P.

text: Cologne:

text: A

text: declarative

text: distributed

text: constraint

text: optimization

text: platform.

text: Proc.

text: of

text: the

text: VLDB

text: Endowment

text: MAHESWARAN,

text: R.,

text: PEARCE,

text: J.,

text: AND

text: TAMBE,

text: M.

text: Distributed

text: algorithms

text: for

text: DCOP:

text: A

text: graphical

text: game-based

text: approach.

text: In

text: Proc.

text: of

text: PDCS.

text: MAHESWARAN,

text: R.,

text: TAMBE,

text: M.,

text: BOWRING,

text: E.,

text: PEARCE,

text: J.,

text: AND

text: VARAKANTHAM,

text: P.

text: Tak-

text: ing

text: DCOP

text: to

text: the

text: real

text: world:

text: Efﬁcient

text: complete

text: solutions

text: for

text: distributed

text: event

text: scheduling.

text: In

text: Proc.

text: of

text: AAMAS.

text: MAILLER,

text: R.

text: AND

text: LESSER,

text: V.

text: Solving

text: distributed

text: constraint

text: optimization

text: problems

text: using

text: cooperative

text: mediation.

text: In

text: Proc.

text: of

text: AAMAS.

text: MAREK,

text: V.

text: AND

text: TRUSZCZYN´

text: SKI,

text: M.

text: Stable

text: models

text: and

text: an

text: alternative

text: logic

text: programming

text: paradigm.

text: In

text: The

text: Logic

text: Programming

text: Paradigm:

text: a

text: Perspective.

text: MODI,

text: P.,

text: SHEN,

text: W.-M.,

text: TAMBE,

text: M.,

text: AND

text: YOKOO,

text: M.

text: ADOPT:

text: Asynchronous

text: distributed

text: constraint

text: optimization

text: with

text: quality

text: guarantees.

text: Artiﬁcial

text: Intelligence

text: NGUYEN,

text: D.

text: T.,

text: YEOH,

text: W.,

text: AND

text: LAU,

text: H.

text: C.

text: Distributed

text: Gibbs:

text: A

text: memory-bounded

text: sampling-based

text: DCOP

text: algorithm.

text: In

text: Proc.

text: of

text: AAMAS.

text: NIEMELA¨

text: I.

text: Logic

text: programming

text: with

text: stable

text: model

text: semantics

text: as

text: a

text: constraint

text: programming

text: paradigm.

text: Annals

text: of

text: Mathematics

text: and

text: Artiﬁcial

text: Intelligence

text: OTTENS,

text: B.,

text: DIMITRAKAKIS,

text: C.,

text: AND

text: FALTINGS,

text: B.

text: DUCT:

text: An

text: upper

text: conﬁdence

text: bound

text: approach

text: to

text: distributed

text: constraint

text: optimization

text: problems.

text: In

text: Proc.

text: of

text: AAAI.

text: PETCU,

text: A.

text: A

text: Class

text: of

text: Algorithms

text: for

text: Distributed

text: Constraint

text: Optimization.

text: Frontiers

text: in

text: Arti-

text: ﬁcial

text: Intelligence

text: and

text: Applications,

text: vol.

text: IOS

text: Press.

text: PETCU,

text: A.

text: AND

text: FALTINGS,

text: B.

text: A

text: scalable

text: method

text: for

text: multiagent

text: constraint

text: optimization.

text: In

text: Proc.

text: of

text: IJCAI.

text: PETCU,

text: A.

text: AND

text: FALTINGS,

text: B.

text: Superstabilizing,

text: fault-containing

text: multiagent

text: combinatorial

text: optimization.

text: In

text: Proc.

text: of

text: AAAI.


text: Solving Distributed Constraint Optimization Problems Using Logic Programming 7 Algorithm 1: DPOP Phase 2 (UTIL Propagation Phase) 1 Each agent ai does: 2 JOINPi = null 3 forall aaci ∈ Ci do 45 wJOaitIfNorPUi =TIJLOaaicINmePs(cid:0)is⊕ageUtToIaLrriav(cid:1)ie/f/rojmoinacUTIL messages from children as they arrive ai ai ac 6 end ⊕ ⊕ 7 JpOaIreNntaP/ipis=eudJoO-pIaNreaPniits f∈Rai f // also join all constraints with ⊥ 8 UTILPaii = JOINaPii αi // use projection to eliminate its owned variables 9 Send UTILPaii message to its parent agent Pi ⊕ Deﬁnition 4 (JOIN Operator) ⊕ U = UTILai UTILai is the join of two UTIL matrices (constraints). U is also a ak al ∪ matrix (constraint) with scp(U) = scp(UTILai ) scp(UTILai) as dimensions. For ak al each possible combination x of values of variables in scp(U), the corresponding value of U(x) is the sum of the corresponding cells in the two source matrices, i.e., U(x) = UasTsigInLmaaike(nxtsUfTrIoLmaaikx)f+orUalTl vIaLraaiailb(xleUsTinILsaacilp)(wUhTeIreLxaiU)TaInLdaaikscapn(dUxTUITLILaiaa)il, areresppeacrttiivaellvya. lue ak al ⊕ Since UTIL messages can be seen as constraints, the operator can be used to join UTIL messages and constraints. Example 3 Given 2 constraints x1 cons x3 and x2 cons x3 in Example 1, let JOINa2 = ⊕ { a}3 x1 cons x3 x2 cons x3. It is possible to see that scp(JOINaa32) = x1, x2, x3 . The utility corresponding to x1 = x2 = x3 = 0 is JOINaa32(x1 = 0, x2 = 0, x3 = 0) = 5 + 5 = 10. Moreover, JOINaa32(x1 = 0, x2 = 0, x3 = 1) = 8 + 8 = 16. ⊥ ⊆ ⊥ For the operator, knowing that αi scp(JOINaPii), JOINaPii αi is the projection through optimization of the JOINaPii matrix along axes representing variables in αi. ⊥ Deﬁnition 5 (PROJECTION Operator) ⊆ Lssicebptl(eαUvi)abl=ueeasccsopem(tJboOifnvIaatNiroiaPanibis)leo\sfαvwaih,reiaarnbedleα(siiii)nfoαsric.epaA(cid:48)(cJhmOpaoItrsNisxiaPbiUile),=vaanlJduOelecItoNXmaPbiiii⊥bneaαtitihoiens sdxeetoﬁfonfveadarlialaspb:ol(esis-) in scp(U), U(x) = maxx(cid:48)∈Xi JOINaPii(x, x ). Example 4 (cid:0) (cid:1) ⊥ C{ onside}ring again JOINaa32 in Example 3, let U = JOINaa32 {x3}. We have scp(U) = x1, x2 , and U(x1 = 0, x2 = 0) = max JOINaa32(x1 = 0, x2 = 0, x3 = 0), JOINaa32(x1 = 0, x2 = 0, x3 = 1) = max(10, 16) = 16. As an example for the computations in Phase 2 (UTIL propagation phase), we consider again the DCOP in Example 1. ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Solving

text: Distributed

text: Constraint

text: Optimization

text: Problems

text: Using

text: Logic

text: Programming

text: Algorithm

text: DPOP

label: caption

text: Phase

text: (UTIL

text: Propagation

text: Phase)

text: Each

text: agent

text: ai

text: does:

text: JOINPi

text: forall

text: aaci

text: Ci

text: do

text: wJOaitIfNorPUi

text: messages

text: from

text: children

text: as

text: they

text: arrive

text: ai

text: ai

text: ac

text: end

text: JpOaIreNntaP/ipis=eudJoO-pIaNreaPniits

text: f∈Rai

text: f

text: also

text: join

text: all

text: constraints

text: with

text: UTILPaii

text: JOINaPii

text: αi

text: use

text: projection

text: to

text: eliminate

text: its

text: owned

text: variables

text: Send

text: UTILPaii

text: message

text: to

text: its

text: parent

text: agent

text: Pi

text: Deﬁnition

text: (JOIN

text: Operator)

text: U

text: UTILai

text: UTILai

text: is

text: the

text: join

text: of

text: two

text: UTIL

text: matrices

text: (constraints).

text: U

text: is

text: also

text: a

text: ak

text: al

text: matrix

text: (constraint)

text: with

text: scp(U)

text: scp(UTILai

text: scp(UTILai)

text: as

text: dimensions.

text: For

text: ak

text: al

text: each

text: possible

text: combination

text: x

text: of

text: values

text: of

text: variables

text: in

text: scp(U),

text: the

text: corresponding

text: value

text: of

text: U(x)

text: is

text: the

text: sum

text: of

text: the

text: corresponding

text: cells

text: in

text: the

text: two

text: source

text: matrices,

text: i.e.,

text: U(x)

text: areresppeacrttiivaellvya.

text: lue

text: ak

text: al

text: Since

text: UTIL

text: messages

text: can

text: be

text: seen

text: as

text: constraints,

text: the

text: operator

text: can

text: be

text: used

text: to

text: join

text: UTIL

text: messages

text: and

text: constraints.

text: Example

text: Given

text: constraints

text: cons

text: and

text: cons

text: in

text: Example

text: let

text: cons

text: cons

text: It

text: is

text: possible

text: to

text: see

text: that

text: The

text: utility

text: corresponding

text: to

text: is

text: Moreover,

text: For

text: the

text: operator,

text: knowing

text: that

text: αi

text: scp(JOINaPii),

text: JOINaPii

text: αi

text: is

text: the

text: projection

text: through

text: optimization

text: of

text: the

text: JOINaPii

text: matrix

text: along

text: axes

text: representing

text: variables

text: in

text: αi.

text: Deﬁnition

text: (PROJECTION

text: Operator)

text: sdxeetoﬁfonfveadarlialaspb:ol(esis-)

text: in

text: scp(U),

text: U(x)

text: JOINaPii(x,

text: x

text: Example

text: C{

text: onside}ring

text: again

text: in

text: Example

text: let

text: U

text: We

text: have

text: scp(U)

text: and

text: max

text: As

text: an

text: example

text: for

text: the

text: computations

text: in

text: Phase

text: (UTIL

text: propagation

text: phase),

text: we

text: consider

text: again

text: the

text: DCOP

text: in

text: Example

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 2 (cid:104) (cid:105) V (r) = 0. This seems to be supported by some of the have a singularity at E = E (unlike in the Dirac problem c available numerical studies of this model [13]. Thus we considered above, E may be diﬀerent from zero). This c could take ρ(0) as the order parameter of the transition can be encoded by the following RG equation satisﬁed by − potentially occurring in this model. However, it is clear the dimensionless disorder strength γ = λξ4 d deﬁned by that ρ(0) cannot be exactly zero at any disorder strength. the correlator Indeed, a ﬂuctuation of disorder which is constant over (cid:104) (cid:48) (cid:105) − (cid:48) some (large) region of space, which one can term a rare V (r)V (r ) = λ δ(r r ), (4) region, shifts the energy of the eigenstates of the Eq. (1) which can be shown to be [20] resulting in some of them shifted towards zero energy, rendering ρ(0) nonzero [25], an eﬀect neglected in Ref. [1]. γ˙ = −(d − 4)γ + Cγ2 + . . . , (5) This invalidates using ρ(0) as the order parameter. In the absence of other suitable candidates, one may conclude where C > 0 is some positive constant (as always, ξ is that there could not be a transition in this problem with the ultraviolet length scale deﬁned precisely below). This a critical density of states. Yet this argument does not equation seemingly shows that at d > 4, weak γ is irrel- unambiguously rule out a genuine singularity in the den- evant and ﬂows to the disorder-free γ = 0 ﬁxed point, sity of states at a critical value of disorder. Despite this, while there exist a value γ = γ which nulliﬁes the right c subsequent numerical studies going beyond [13] together hand side of Eq. (5) and which correspond to the critical with some analytic arguments were able to resolve the ab- point in the renormalization group (as always, Eq. (5) sence of singularity in the density of states [26, 27] and is perturbative in γ, so γ can be extracted from it only − c argue in favor of the crossover replacing the transition in if d 4 is small and γ is small enough for the pertur- c the model Eq. (1). bation theory to work, but usually γ which nulliﬁes the c Note that even if the transition is indeed absent and right-hand-side of Eq. (5) is presumed to exist at any replaced by a crossover, this does not invalidate the prior d > 4). It is at this critical point γ = γ , corresponding − c studies of criticality and multifractality in these models. to λ = λ = γ ξd 4, that we expect the density of states c c It just implies that unlike in genuine critical points, in to be a critical function of energy. these problems as the disorder strength is tuned to what These arguments immediately lead to a striking pre- should be its critical value, the correlation length satu- diction that disagrees with the available literature. It is rates at some maximum value (cid:96) instead of diverging to in- well known the disorder-averaged Green’s function of the ﬁnity. All the critical scaling and multifractality will still problem deﬁned by (3) and (4) is equivalent to the self- be observed at scales below that saturation scale, explain- attracting random walks where λ controls the strength ing why most numerical studies failed to distinguish the of the attraction [28, 29] (while λ < 0 corresponds to the crossover in these models from genuine critical points. In more familiar case of self-repulsive random walks). It is particular, the Anderson transition in the model Eq. (3) tempting to conclude from Eq. (5) that the self-attracting at d > dc = 4 is still governed by the Anderson criti- random walks at d > 4 are equivalent to Brownian mo- cal exponent, however at disorder strength close to what tion for the attraction below critical, and are critical at would have been its critical value, a crossover regime at the critical value of the attraction which nulliﬁes the right E below the mobility edge should exist where the local- hand side of Eq. (5). However, existing studies of self- ization length is governed by the exponent discussed in attractive random walks at d > 4 showed that those are Ref. [20], turning into the conventional Anderson expo- never equivalent to Brownian motion, and do not have nent as E approaches the mobility edge. any special critical value of the strength of the attrac- Here we would like to present quantitative arguments tion [30–32]. By extension, this hints at the absence of showing that in these problems there cannot be a genuine criticality in the random Schr¨odinger equation at d > 4. singularity in the density of states and develop an ana- While adopting the arguments of Refs. [30–32] to the lytic framework to calculate the saturation scale which motion in random potential at d > 4 is possible to ex- controls these crossover phenomena. plain the absence of criticality in Eq. (3), the drawback Let us examine the Schr¨odinger equation with random of this approach is that it is not easy to apply it to other potential at d > dc = 4, deﬁned by the usual Hamiltonian problems such as the one deﬁned by Eq. (1) or discussed in Ref. [21]. − 1 H = ∆ + V (r). (3) We would therefore like to present another argument 2m based on adopting the method of instantons in the replica Ref. [20] argued that since, just like in the Dirac prob- approach to the problem of calculating the density of lem at d = 3 studied in Ref. [1] and in subsequent stud- states. It has long been known that these instantons is ies, the weak disorder here is irrelevant in the RG sense, what produces the so-called Lifshitz tail [33] density of while strong disorder is relevant, there should be a criti- states where there would have been none had the disorder cal disorder strength separating these two phases. At this been absent. We would like to show that these instantons, critical disorder strength, ρ(E) for this problem should when properly resummed, result in the absence of any ##LTLine##

text: V

text: (r)

text: This

text: seems

text: to

text: be

text: supported

text: by

text: some

text: of

text: the

text: have

text: a

text: singularity

text: at

text: E

text: E

text: (unlike

text: in

text: the

text: Dirac

text: problem

text: c

text: available

text: numerical

text: studies

text: of

text: this

text: model

text: Thus

text: we

text: considered

text: above,

text: E

text: may

text: be

text: diﬀerent

text: from

text: zero).

text: This

text: c

text: could

text: take

text: as

text: the

text: order

text: parameter

text: of

text: the

text: transition

text: can

text: be

text: encoded

text: by

text: the

text: following

text: RG

text: equation

text: satisﬁed

text: by

text: potentially

text: occurring

text: in

text: this

text: model.

text: However,

text: it

text: is

text: clear

text: the

text: dimensionless

text: disorder

text: strength

text: γ

text: λξ4

text: d

text: deﬁned

text: by

text: that

text: cannot

text: be

text: exactly

text: zero

text: at

text: any

text: disorder

text: strength.

text: the

text: correlator

text: Indeed,

text: a

text: ﬂuctuation

text: of

text: disorder

text: which

text: is

text: constant

text: over

text: some

text: (large)

text: region

text: of

text: space,

text: which

text: one

text: can

text: term

text: a

text: rare

text: V

text: (r)V

text: (r

text: λ

text: δ(r

text: r

text: region,

text: shifts

text: the

text: energy

text: of

text: the

text: eigenstates

text: of

text: the

text: Eq.

text: which

text: can

text: be

text: shown

text: to

text: be

text: resulting

text: in

text: some

text: of

text: them

text: shifted

text: towards

text: zero

text: energy,

text: rendering

text: nonzero

text: an

text: eﬀect

text: neglected

text: in

text: Ref.

text: γ˙

text: −(d

text: This

text: invalidates

text: using

text: as

text: the

text: order

text: parameter.

text: In

text: the

text: absence

text: of

text: other

text: suitable

text: candidates,

text: one

text: may

text: conclude

text: where

text: C

text: is

text: some

text: positive

text: constant

text: (as

text: always,

text: ξ

text: is

text: that

text: there

text: could

text: not

text: be

text: a

text: transition

text: in

text: this

text: problem

text: with

text: the

text: ultraviolet

text: length

text: scale

text: deﬁned

text: precisely

text: below).

text: This

text: a

text: critical

text: density

text: of

text: states.

text: Yet

text: this

text: argument

text: does

text: not

text: equation

text: seemingly

text: shows

text: that

text: at

text: d

text: weak

text: γ

text: is

text: irrel-

text: unambiguously

text: rule

text: out

text: a

text: genuine

text: singularity

text: in

text: the

text: den-

text: evant

text: and

text: ﬂows

text: to

text: the

text: disorder-free

text: γ

text: ﬁxed

text: point,

text: sity

text: of

text: states

text: at

text: a

text: critical

text: value

text: of

text: disorder.

text: Despite

text: this,

text: while

text: there

text: exist

text: a

text: value

text: γ

text: γ

text: which

text: nulliﬁes

text: the

text: right

text: c

text: subsequent

text: numerical

text: studies

text: going

text: beyond

text: together

text: hand

text: side

text: of

text: Eq.

text: and

text: which

text: correspond

text: to

text: the

text: critical

text: with

text: some

text: analytic

text: arguments

text: were

text: able

text: to

text: resolve

text: the

text: ab-

text: point

text: in

text: the

text: renormalization

text: group

text: (as

text: always,

text: Eq.

text: sence

text: of

text: singularity

text: in

text: the

text: density

text: of

text: states

text: and

text: is

text: perturbative

text: in

text: γ,

text: so

text: γ

text: can

text: be

text: extracted

text: from

text: it

text: only

text: c

text: argue

text: in

text: favor

text: of

text: the

text: crossover

text: replacing

text: the

text: transition

text: in

text: if

text: d

text: is

text: small

text: and

text: γ

text: is

text: small

text: enough

text: for

text: the

text: pertur-

text: c

text: the

text: model

text: Eq.

text: bation

text: theory

text: to

text: work,

text: but

text: usually

text: γ

text: which

text: nulliﬁes

text: the

text: c

text: Note

text: that

text: even

text: if

text: the

text: transition

text: is

text: indeed

text: absent

text: and

text: right-hand-side

text: of

text: Eq.

text: is

text: presumed

text: to

text: exist

text: at

text: any

text: replaced

text: by

text: a

text: crossover,

text: this

text: does

text: not

text: invalidate

text: the

text: prior

text: d

text: It

text: is

text: at

text: this

text: critical

text: point

text: γ

text: γ

text: corresponding

text: c

text: studies

text: of

text: criticality

text: and

text: multifractality

text: in

text: these

text: models.

text: to

text: λ

text: λ

text: γ

text: ξd

text: that

text: we

text: expect

text: the

text: density

text: of

text: states

text: c

text: c

text: It

text: just

text: implies

text: that

text: unlike

text: in

text: genuine

text: critical

text: points,

text: in

text: to

text: be

text: a

text: critical

text: function

text: of

text: energy.

text: these

text: problems

text: as

text: the

text: disorder

text: strength

text: is

text: tuned

text: to

text: what

text: These

text: arguments

text: immediately

text: lead

text: to

text: a

text: striking

text: pre-

text: should

text: be

text: its

text: critical

text: value,

text: the

text: correlation

text: length

text: satu-

text: diction

text: that

text: disagrees

text: with

text: the

text: available

text: literature.

text: It

text: is

text: rates

text: at

text: some

text: maximum

text: value

text: instead

text: of

text: diverging

text: to

text: in-

text: well

text: known

text: the

text: disorder-averaged

text: Green’s

text: function

text: of

text: the

text: ﬁnity.

text: All

text: the

text: critical

text: scaling

text: and

text: multifractality

text: will

text: still

text: problem

text: deﬁned

text: by

text: and

text: is

text: equivalent

text: to

text: the

text: self-

text: be

text: observed

text: at

text: scales

text: below

text: that

text: saturation

text: scale,

text: explain-

text: attracting

text: random

text: walks

text: where

text: λ

text: controls

text: the

text: strength

text: ing

text: why

text: most

text: numerical

text: studies

text: failed

text: to

text: distinguish

text: the

text: of

text: the

text: attraction

text: (while

text: λ

text: corresponds

text: to

text: the

text: crossover

text: in

text: these

text: models

text: from

text: genuine

text: critical

text: points.

text: In

text: more

text: familiar

text: case

text: of

text: self-repulsive

text: random

text: walks).

text: It

text: is

text: particular,

text: the

text: Anderson

text: transition

text: in

text: the

text: model

text: Eq.

text: tempting

text: to

text: conclude

text: from

text: Eq.

text: that

text: the

text: self-attracting

text: at

text: d

text: dc

text: is

text: still

text: governed

text: by

text: the

text: Anderson

text: criti-

text: random

text: walks

text: at

text: d

text: are

text: equivalent

text: to

text: Brownian

text: mo-

text: cal

text: exponent,

text: however

text: at

text: disorder

text: strength

text: close

text: to

text: what

text: tion

text: for

text: the

text: attraction

text: below

text: critical,

text: and

text: are

text: critical

text: at

text: would

text: have

text: been

text: its

text: critical

text: value,

text: a

text: crossover

text: regime

text: at

text: the

text: critical

text: value

text: of

text: the

text: attraction

text: which

text: nulliﬁes

text: the

text: right

text: E

text: below

text: the

text: mobility

text: edge

text: should

text: exist

text: where

text: the

text: local-

text: hand

text: side

text: of

text: Eq.

text: However,

text: existing

text: studies

text: of

text: self-

text: ization

text: length

text: is

text: governed

text: by

text: the

text: exponent

text: discussed

text: in

text: attractive

text: random

text: walks

text: at

text: d

text: showed

text: that

text: those

text: are

text: Ref.

text: turning

text: into

text: the

text: conventional

text: Anderson

text: expo-

text: never

text: equivalent

text: to

text: Brownian

text: motion,

text: and

text: do

text: not

text: have

text: nent

text: as

text: E

text: approaches

text: the

text: mobility

text: edge.

text: any

text: special

text: critical

text: value

text: of

text: the

text: strength

text: of

text: the

text: attrac-

text: Here

text: we

text: would

text: like

text: to

text: present

text: quantitative

text: arguments

text: tion

text: By

text: extension,

text: this

text: hints

text: at

text: the

text: absence

text: of

text: showing

text: that

text: in

text: these

text: problems

text: there

text: cannot

text: be

text: a

text: genuine

text: criticality

text: in

text: the

text: random

text: Schr¨odinger

text: equation

text: at

text: d

text: singularity

text: in

text: the

text: density

text: of

text: states

text: and

text: develop

text: an

text: ana-

text: While

text: adopting

text: the

text: arguments

text: of

text: Refs.

text: to

text: the

text: lytic

text: framework

text: to

text: calculate

text: the

text: saturation

text: scale

text: which

text: motion

text: in

text: random

text: potential

text: at

text: d

text: is

text: possible

text: to

text: ex-

text: controls

text: these

text: crossover

text: phenomena.

text: plain

text: the

text: absence

text: of

text: criticality

text: in

text: Eq.

text: the

text: drawback

text: Let

text: us

text: examine

text: the

text: Schr¨odinger

text: equation

text: with

text: random

text: of

text: this

text: approach

text: is

text: that

text: it

text: is

text: not

text: easy

text: to

text: apply

text: it

text: to

text: other

text: potential

text: at

text: d

text: dc

text: deﬁned

text: by

text: the

text: usual

text: Hamiltonian

text: problems

text: such

text: as

text: the

text: one

text: deﬁned

text: by

text: Eq.

text: or

text: discussed

text: in

text: Ref.

text: H

text: V

text: (r).

text: We

text: would

text: therefore

text: like

text: to

text: present

text: another

text: argument

text: based

text: on

text: adopting

text: the

text: method

text: of

text: instantons

text: in

text: the

text: replica

text: Ref.

text: argued

text: that

text: since,

text: just

text: like

text: in

text: the

text: Dirac

text: prob-

text: approach

text: to

text: the

text: problem

text: of

text: calculating

text: the

text: density

text: of

text: lem

text: at

text: d

text: studied

text: in

text: Ref.

text: and

text: in

text: subsequent

text: stud-

text: states.

text: It

text: has

text: long

text: been

text: known

text: that

text: these

text: instantons

text: is

text: ies,

text: the

text: weak

text: disorder

text: here

text: is

text: irrelevant

text: in

text: the

text: RG

text: sense,

text: what

text: produces

text: the

text: so-called

text: Lifshitz

text: tail

text: density

text: of

text: while

text: strong

text: disorder

text: is

text: relevant,

text: there

text: should

text: be

text: a

text: criti-

text: states

text: where

text: there

text: would

text: have

text: been

text: had

text: the

text: disorder

text: cal

text: disorder

text: strength

text: separating

text: these

text: two

text: phases.

text: At

text: this

text: been

text: absent.

text: We

text: would

text: like

text: to

text: show

text: that

text: these

text: instantons,

text: critical

text: disorder

text: strength,

text: ρ(E)

text: for

text: this

text: problem

text: should

text: when

text: properly

text: resummed,

text: result

text: in

text: the

text: absence

text: of

text: any

text: ##LTLine##


text: O × = (L n) O · · = (nρ ln 1 n), See Subsection. ??. O · δ O = (ln 1 nρ+1)= (nρ+1) δ 5.1.2 Time Complexity Video Indexing Time: For each video sequence, L diﬀerent hash values are computed for L hash tables. × Each hash function is composed of (2λ+1) K unit hash functions. Therefore, the time required to place a single video in suitable positions of L diﬀerent hash O · · tables is ((2λ + 1) K L) O · · · Therefore, the total time requirement for n videos is ((2λ + 1) K L n) O · · · = ((2λ + 1) ( 1 ) lnn L n), See Section. ??. 2λ+1 ln 1 O · · · P2O · = ( lnn nρ ln 1 n)= (nρ+1 lnn) ln 1 δ ln 1 P2 P2 Query Time: (cid:48) In Strategy 1, the search is stopped after reporting L videos. It is shown (cid:48) in ? that the Strategy 1 with L = 3L yields reasonably good result with con- stant error probability. Therefore, in Strategy 1 the query time is bounded by O O · O (3L) = (nρ ln 1)= (nρ). δ In Strategy 2, the query time can be as high as θ(n) in the worst case. However, for many real data sets, the algorithm results in sublinear query time with proper selection of the parameter values ?. 5.2 Video Action Recognition Classifying videos to the relevant action classes is another important task in the video processing pipeline. It is often termed as Human Action Recognition. Immense eﬀort has already been put by the researchers to make video action recognition fast and accurate. The standard and well adopted procedures for classifying video actions often compute a histogram vector of event classes using a procedure known as BoW quantization. This histogram vectors accompanied by the class labels of the videos are used to train a suitably selected classiﬁer. The trained classiﬁer is then applied to the test videos for human action clas- siﬁcation. However, it has been seen that the histogram vector of event classes cannot properly capture the actions or themes of the videos. This is due to fact that the event classes are the groupings of the STIPs having similar motion or shape. They do not directly reﬂect the human actions. For example, there can be diﬀerent event classes for leg movement, hand movement, movement of lips etc. A higher frequency of ‘leg movement’ event class in the histogram vector of a video, cannot say whether it should be classiﬁed as ‘jumping’ or ‘walking’. To get rid of this situation, we have proposed an action classiﬁcation method on the basis of histogram of conLSH values. A conLSH value is capable of cap- turing the theme or action of a context, as it reﬂects all the event classes present in that context in a composite form. The length of the context can be spec- 14 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: O

text: (L

text: n)

text: O

text: (nρ

text: ln

text: n),

text: See

text: Subsection.

text: O

text: δ

text: O

text: (ln

text: δ

label: section

text: Time

text: Complexity

text: Video

text: Indexing

text: Time:

text: For

text: each

text: video

text: sequence,

text: L

text: diﬀerent

text: hash

text: values

text: are

text: computed

text: for

text: L

text: hash

text: tables.

text: Each

text: hash

text: function

text: is

text: composed

text: of

text: K

text: unit

text: hash

text: functions.

text: Therefore,

text: the

text: time

text: required

text: to

text: place

text: a

text: single

text: video

text: in

text: suitable

text: positions

text: of

text: L

text: diﬀerent

text: hash

text: O

text: tables

text: is

text: K

text: L)

text: O

text: Therefore,

text: the

text: total

text: time

text: requirement

text: for

text: n

text: videos

text: is

text: K

text: L

text: n)

text: O

text: lnn

text: L

text: n),

text: See

text: Section.

text: ln

text: O

text: lnn

text: nρ

text: ln

text: n)=

text: lnn)

text: ln

text: δ

text: ln

text: Query

text: Time:

text: In

text: Strategy

text: the

text: search

text: is

text: stopped

text: after

text: reporting

text: L

text: videos.

text: It

text: is

text: shown

text: in

text: that

text: the

text: Strategy

text: with

text: L

text: yields

text: reasonably

text: good

text: result

text: with

text: con-

text: stant

text: error

text: probability.

text: Therefore,

text: in

text: Strategy

text: the

text: query

text: time

text: is

text: bounded

text: by

text: O

text: O

text: O

text: (nρ

text: ln

text: (nρ).

text: δ

text: In

text: Strategy

text: the

text: query

text: time

text: can

text: be

text: as

text: high

text: as

text: θ(n)

text: in

text: the

text: worst

text: case.

text: However,

text: for

text: many

text: real

text: data

text: sets,

text: the

text: algorithm

text: results

text: in

text: sublinear

text: query

text: time

text: with

text: proper

text: selection

text: of

text: the

text: parameter

text: values

text: Video

text: Action

text: Recognition

text: Classifying

text: videos

text: to

text: the

text: relevant

text: action

text: classes

text: is

text: another

text: important

text: task

text: in

text: the

text: video

text: processing

text: pipeline.

text: It

text: is

text: often

text: termed

text: as

text: Human

text: Action

text: Recognition.

text: Immense

text: eﬀort

text: has

text: already

text: been

text: put

text: by

text: the

text: researchers

text: to

text: make

text: video

text: action

text: recognition

text: fast

text: and

text: accurate.

text: The

text: standard

text: and

text: well

text: adopted

text: procedures

text: for

text: classifying

text: video

text: actions

text: often

text: compute

text: a

text: histogram

text: vector

text: of

text: event

text: classes

text: using

text: a

text: procedure

text: known

text: as

text: BoW

text: quantization.

text: This

text: histogram

text: vectors

text: accompanied

text: by

text: the

text: class

text: labels

text: of

text: the

text: videos

text: are

text: used

text: to

text: train

text: a

text: suitably

text: selected

text: classiﬁer.

text: The

text: trained

text: classiﬁer

text: is

text: then

text: applied

text: to

text: the

text: test

text: videos

text: for

text: human

text: action

text: clas-

text: siﬁcation.

text: However,

text: it

text: has

text: been

text: seen

text: that

text: the

text: histogram

text: vector

text: of

text: event

text: classes

text: cannot

text: properly

text: capture

text: the

text: actions

text: or

text: themes

text: of

text: the

text: videos.

text: This

text: is

text: due

text: to

text: fact

text: that

text: the

text: event

text: classes

text: are

text: the

text: groupings

text: of

text: the

text: STIPs

text: having

text: similar

text: motion

text: or

text: shape.

text: They

text: do

text: not

text: directly

text: reﬂect

text: the

text: human

text: actions.

text: For

text: example,

text: there

text: can

text: be

text: diﬀerent

text: event

text: classes

text: for

text: leg

text: movement,

text: hand

text: movement,

text: movement

text: of

text: lips

text: etc.

text: A

text: higher

text: frequency

text: of

text: ‘leg

text: movement’

text: event

text: class

text: in

text: the

text: histogram

text: vector

text: of

text: a

text: video,

text: cannot

text: say

text: whether

text: it

text: should

text: be

text: classiﬁed

text: as

text: ‘jumping’

text: or

text: ‘walking’.

text: To

text: get

text: rid

text: of

text: this

text: situation,

text: we

text: have

text: proposed

text: an

text: action

text: classiﬁcation

text: method

text: on

text: the

text: basis

text: of

text: histogram

text: of

text: conLSH

text: values.

text: A

text: conLSH

text: value

text: is

text: capable

text: of

text: cap-

text: turing

text: the

text: theme

text: or

text: action

text: of

text: a

text: context,

text: as

text: it

text: reﬂects

text: all

text: the

text: event

text: classes

text: present

text: in

text: that

text: context

text: in

text: a

text: composite

text: form.

text: The

text: length

text: of

text: the

text: context

text: can

text: be

text: spec-

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Ryynanen, M. and Klapuri, A. (2008). Query by humming of midi and audio using locality sensitive hashing. In Acoustics, Speech and Signal Processing, 2008. ICASSP 2008. IEEE International Conference on, pages 2249–2252. IEEE. Salton, G. and McGill, M. (1983). Introduction to modern information retrieval. New York: McGraw-Hili. Schu¨ldt, C., Laptev, I., and Caputo, B. (2004). Recognizing human actions: a local svm approach. In Pattern Recognition, 2004. ICPR 2004. Proceedings of the 17th International Conference on, volume 3, pages 32–36. IEEE. Slaney, M., Lifshits, Y., and He, J. (2012). Optimal parameters for locality- sensitive hashing. Proceedings of the IEEE, 100(9), 2604–2623. Smith, T. F. and Waterman, M. S. (1981). Identiﬁcation of common molecular subsequences. J. Mol. Biol., 147, 195–197. Song, J., Yang, Y., Huang, Z., Shen, H. T., and Hong, R. (2011). Multiple feature hashing for real-time large scale near-duplicate video retrieval. In Proceedings of the 19th ACM international conference on Multimedia, pages 423–432. ACM. Soomro, k., Roshan Zamir, A., and Shah, M. (2012). UCF101: A dataset of 101 human actions classes from videos in the wild. In CRCV-TR-12-01. Vijayanarasimhan, S., Jain, P., and Grauman, K. (2013). Hashing hyperplane queries to near points with applications to large-scale active learning. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 36(2), 276–288. Weiss, Y., Torralba, A., and Fergus, R. (2009). Spectral hashing. In Advances in neural information processing systems, pages 1753–1760. Wu, J. (2012). Power mean svm for large scale visual classiﬁcation. In Computer Vision and Pattern Recognition (CVPR), 2012 IEEE Conference on, pages 2344–2351. IEEE. Xia, H., Wu, P., Hoi, S. C., and Jin, R. (2012). Boosting multi-kernel locality- sensitive hashing for scalable image retrieval. In Proceedings of the 35th inter- national ACM SIGIR conference on Research and development in information retrieval, pages 55–64. ACM. Ye, G., Liu, D., Wang, J., and Chang, S.-F. (2013). Large-scale video hashing via structure learning. In The IEEE International Conference on Computer Vision (ICCV). Yeh, M.-C. and Cheng, K.-T. (2009). Video copy detection by fast sequence matching. In Proceedings of the ACM International Conference on Image and Video Retrieval, page 45. ACM. 28

text: Ryynanen,

text: M.

text: and

text: Klapuri,

text: A.

text: Query

text: by

text: humming

text: of

text: midi

text: and

text: audio

text: using

text: locality

text: sensitive

text: hashing.

text: In

text: Acoustics,

text: Speech

text: and

text: Signal

text: Processing,

text: ICASSP

text: IEEE

text: International

text: Conference

text: on,

text: pages

text: IEEE.

text: Salton,

text: G.

text: and

text: McGill,

text: M.

text: Introduction

text: to

text: modern

text: information

text: retrieval.

text: New

text: York:

text: McGraw-Hili.

text: Schu¨ldt,

text: C.,

text: Laptev,

text: I.,

text: and

text: Caputo,

text: B.

text: Recognizing

text: human

text: actions:

text: a

text: local

text: svm

text: approach.

text: In

text: Pattern

text: Recognition,

text: ICPR

text: Proceedings

text: of

text: the

text: International

text: Conference

text: on,

text: volume

text: pages

text: IEEE.

text: Slaney,

text: M.,

text: Lifshits,

text: Y.,

text: and

text: He,

text: J.

text: Optimal

text: parameters

text: for

text: locality-

text: sensitive

text: hashing.

text: Proceedings

text: of

text: the

text: IEEE,

text: Smith,

text: T.

text: F.

text: and

text: Waterman,

text: M.

text: S.

text: Identiﬁcation

text: of

text: common

text: molecular

text: subsequences.

text: J.

text: Mol.

text: Biol.,

text: Song,

text: J.,

text: Yang,

text: Y.,

text: Huang,

text: Z.,

text: Shen,

text: H.

text: T.,

text: and

text: Hong,

text: R.

text: Multiple

text: feature

text: hashing

text: for

text: real-time

text: large

text: scale

text: near-duplicate

text: video

text: retrieval.

text: In

text: Proceedings

text: of

text: the

text: ACM

text: international

text: conference

text: on

text: Multimedia,

text: pages

text: ACM.

text: Soomro,

text: k.,

text: Roshan

text: Zamir,

text: A.,

text: and

text: Shah,

text: M.

text: A

text: dataset

text: of

text: human

text: actions

text: classes

text: from

text: videos

text: in

text: the

text: wild.

text: In

text: Vijayanarasimhan,

text: S.,

text: Jain,

text: P.,

text: and

text: Grauman,

text: K.

text: Hashing

text: hyperplane

text: queries

text: to

text: near

text: points

text: with

text: applications

text: to

text: large-scale

text: active

text: learning.

text: Pattern

text: Analysis

text: and

text: Machine

text: Intelligence,

text: IEEE

text: Transactions

text: on,

text: Weiss,

text: Y.,

text: Torralba,

text: A.,

text: and

text: Fergus,

text: R.

text: Spectral

text: hashing.

text: In

text: Advances

text: in

text: neural

text: information

text: processing

text: systems,

text: pages

text: Wu,

text: J.

text: Power

text: mean

text: svm

text: for

text: large

text: scale

text: visual

text: classiﬁcation.

text: In

text: Computer

text: Vision

text: and

text: Pattern

text: Recognition

text: (CVPR),

text: IEEE

text: Conference

text: on,

text: pages

text: IEEE.

text: Xia,

text: H.,

text: Wu,

text: P.,

text: Hoi,

text: S.

text: C.,

text: and

text: Jin,

text: R.

text: Boosting

text: multi-kernel

text: locality-

text: sensitive

text: hashing

text: for

text: scalable

text: image

text: retrieval.

text: In

text: Proceedings

text: of

text: the

text: inter-

text: national

text: ACM

text: SIGIR

text: conference

text: on

text: Research

text: and

text: development

text: in

text: information

text: retrieval,

text: pages

text: ACM.

text: Ye,

text: G.,

text: Liu,

text: D.,

text: Wang,

text: J.,

text: and

text: Chang,

text: S.-F.

text: Large-scale

text: video

text: hashing

text: via

text: structure

text: learning.

text: In

text: The

text: IEEE

text: International

text: Conference

text: on

text: Computer

text: Vision

text: (ICCV).

text: Yeh,

text: M.-C.

text: and

text: Cheng,

text: K.-T.

text: Video

text: copy

text: detection

text: by

text: fast

text: sequence

text: matching.

text: In

text: Proceedings

text: of

text: the

text: ACM

text: International

text: Conference

text: on

text: Image

text: and

text: Video

text: Retrieval,

text: page

text: ACM.


text: Figure 2: Layered Context based Locality Sensitive Hashing for Video Sequences 31 ##LTFigure## ##LTFigure##

text: Figure

text: Layered

text: Context

text: based

text: Locality

text: Sensitive

text: Hashing

text: for

text: Video

text: Sequences

text: ##LTFigure##

label: figure

font: default

text: ##LTFigure##


text: the query vector. Therefore, there is a need for the second parameter of the ABF, which determines the lowest value of dot product indicating the presence of an element in the ≤ ≤ ﬁlter. Denote this decision threshold parameter as T (0 T k), then an element of the universe q is judged to be a member of the ABF if and only if the dot product between ABF and q is greater than or equal to T. 3.5 Probabilistic characterization of the Autoscaling Bloom Filter When the binarization threshold Θ for the ABF is more than zero, the probability of an empty position in the ABF (denoted as P ) is higher than in the SBF because some 0 of the nonzero positions in the CBF are set to zero. For a given Θ, the expected P is (cid:18) (cid:19) 0 calculated using (8) as fo(cid:88)llows: (cid:88) Θ Θ n − − P = Pr(I = v) = pv(1 p )n v. (13) 0 v 1 1 v=0 v=0 (cid:18) (cid:19) Then the probability of 1 in the ABF ((cid:88)denoted as P ) is: 1 − − Θ n − − P = 1 P = 1 pv(1 p )n v. (14) 1 0 v 1 1 v=0 The expected dot product d¯ for an element x included in the ABF is calculated x as: (cid:88) − m Θ d¯ = k v Pr(I = v). (15) x n v=0 Note that when Θ = 0, d¯ (ABF, x) = k which corresponds to the SBF (see (4)). x In other words, the SBF can be seen as a special case of the ABF. The calculations in (15) when Θ > 0 can be interpreted in the following way. The dot product between SBF and x is k. A position in CBF with value v > 0 contributes 1 to the values of dot products of v stored elements. Thus, if this position is set to zero in the SBF, there will − be v elements with the dot product equal to k 1 while the dot products for rest of the elements still equal k. Then the expected dot product between the ﬁlter and an element is decremented by v/n. In fact, the number of positions with value v is unknown but it is possible to calculate the probability Pr(I = v) of such position in CBF using (8). Then the expected number of such positions in CBF is determined via (11) and equals mPr(I = v). When the ABF suppresses all such positions each of them decrements the expected dot product by v/n. Then the total decrement of the expected dot product by the suppressed positions with value v is expected to be mvPr(I = v)/n. Because the ABF suppresses all positions with values less than or equal to Θ, the decrements of the expected dot product introduced by each value v should be summed up. The expected dot product (denoted d¯ ) between the ABF and an element y which is y not included in the ﬁlter is determined by the number of nonzero positions in the ﬁlter and calculated as: d¯ = kP . (16) y 1 ##LTLine##

text: the

text: query

text: vector.

text: Therefore,

text: there

text: is

text: a

text: need

text: for

text: the

text: second

text: parameter

text: of

text: the

text: ABF,

text: which

text: determines

text: the

text: lowest

text: value

text: of

text: dot

text: product

text: indicating

text: the

text: presence

text: of

text: an

text: element

text: in

text: the

text: ﬁlter.

text: Denote

text: this

text: decision

text: threshold

text: parameter

text: as

text: T

text: T

text: k),

text: then

text: an

text: element

text: of

text: the

text: universe

text: q

text: is

text: judged

text: to

text: be

text: a

text: member

text: of

text: the

text: ABF

text: if

text: and

text: only

text: if

text: the

text: dot

text: product

text: between

text: ABF

text: and

text: q

text: is

text: greater

text: than

text: or

text: equal

text: to

text: T.

text: Probabilistic

text: characterization

text: of

text: the

text: Autoscaling

text: Bloom

text: Filter

text: When

text: the

text: binarization

text: threshold

text: Θ

text: for

text: the

text: ABF

text: is

text: more

text: than

text: zero,

text: the

text: probability

text: of

text: an

text: empty

text: position

text: in

text: the

text: ABF

text: (denoted

text: as

text: P

text: is

text: higher

text: than

text: in

text: the

text: SBF

text: because

text: some

text: of

text: the

text: nonzero

text: positions

text: in

text: the

text: CBF

text: are

text: set

text: to

text: zero.

text: For

text: a

text: given

text: Θ,

text: the

text: expected

text: P

text: is

text: calculated

text: using

text: as

text: Θ

text: Θ

text: n

text: P

text: Pr(I

text: v)

text: p

text: )n

text: v.

text: v

text: Then

text: the

text: probability

text: of

text: in

text: the

text: ABF

text: as

text: P

text: is:

text: Θ

text: n

text: P

text: P

text: p

text: )n

text: v.

text: v

text: The

text: expected

text: dot

text: product

text: d¯

text: for

text: an

text: element

text: x

text: included

text: in

text: the

text: ABF

text: is

text: calculated

text: x

text: as:

text: m

text: Θ

text: d¯

text: k

text: v

text: Pr(I

text: v).

text: x

text: n

text: Note

text: that

text: when

text: Θ

text: d¯

text: (ABF,

text: x)

text: k

text: which

text: corresponds

text: to

text: the

text: SBF

text: (see

text: x

text: In

text: other

text: words,

text: the

text: SBF

text: can

text: be

text: seen

text: as

text: a

text: special

text: case

text: of

text: the

text: ABF.

text: The

text: calculations

text: in

text: when

text: Θ

text: can

text: be

text: interpreted

text: in

text: the

text: following

text: way.

text: The

text: dot

text: product

text: between

text: SBF

text: and

text: x

text: is

text: k.

text: A

text: position

text: in

text: CBF

text: with

text: value

text: v

text: contributes

text: to

text: the

text: values

text: of

text: dot

text: products

text: of

text: v

text: stored

text: elements.

text: Thus,

text: if

text: this

text: position

text: is

text: set

text: to

text: zero

text: in

text: the

text: SBF,

text: there

text: will

text: be

text: v

text: elements

text: with

text: the

text: dot

text: product

text: equal

text: to

text: k

text: while

text: the

text: dot

text: products

text: for

text: rest

text: of

text: the

text: elements

text: still

text: equal

text: k.

text: Then

text: the

text: expected

text: dot

text: product

text: between

text: the

text: ﬁlter

text: and

text: an

text: element

text: is

text: decremented

text: by

text: v/n.

text: In

text: fact,

text: the

text: number

text: of

text: positions

text: with

text: value

text: v

text: is

text: unknown

text: but

text: it

text: is

text: possible

text: to

text: calculate

text: the

text: probability

text: Pr(I

text: v)

text: of

text: such

text: position

text: in

text: CBF

text: using

text: Then

text: the

text: expected

text: number

text: of

text: such

text: positions

text: in

text: CBF

text: is

text: determined

text: via

text: and

text: equals

text: mPr(I

text: v).

text: When

text: the

text: ABF

text: suppresses

text: all

text: such

text: positions

text: each

text: of

text: them

text: decrements

text: the

text: expected

text: dot

text: product

text: by

text: v/n.

text: Then

text: the

text: total

text: decrement

text: of

text: the

text: expected

text: dot

text: product

text: by

text: the

text: suppressed

text: positions

text: with

text: value

text: v

text: is

text: expected

text: to

text: be

text: mvPr(I

text: v)/n.

text: Because

text: the

text: ABF

text: suppresses

text: all

text: positions

text: with

text: values

text: less

text: than

text: or

text: equal

text: to

text: Θ,

text: the

text: decrements

text: of

text: the

text: expected

text: dot

text: product

text: introduced

text: by

text: each

text: value

text: v

text: should

text: be

text: summed

text: up.

text: The

text: expected

text: dot

text: product

text: (denoted

text: d¯

text: between

text: the

text: ABF

text: and

text: an

text: element

text: y

text: which

text: is

text: y

text: not

text: included

text: in

text: the

text: ﬁlter

text: is

text: determined

text: by

text: the

text: number

text: of

text: nonzero

text: positions

text: in

text: the

text: ﬁlter

text: and

text: calculated

text: as:

text: d¯

text: kP

text: y

text: ##LTLine##


text: 2 compression to 0.6 ps with peak powers exceeding 1 MW. Although this represented a new record for GSDs, the pulses remain too long for many ultrafast applications, and their large deviation from the transform- limited duration (¿4x) indicates a lack of control over the pulse. In addition, the system relies on a specially engineered diode, which emits high-quality seed pulses. Here, we demonstrate a scheme for compressing and amplifying pulses from a GSD. Starting with partially ≈ coherent, 10-ps pulses from a commercially-available GSD, we generate 140-fs pulses with energies of 2.4 µJ. These represent the shortest pulses from a GSD at comparable energies, and the highest peak power by an order of magnitude. We achieve these results using a multi-stage system. We ﬁrst use a Mamyshev regenerator to shape the pulses from the GSD, at once compressing them and improving their coherence. The clean pulses that we thereby obtain are then amenable to parabolic pre-shaping, followed by ampliﬁcation and compression to femtosecond durations [13]. By using propagation regimes that eﬀectively leverage nonlinear eﬀects, we are able to compress the ampliﬁed pulses to near the transform limit. To illustrate the nonlinear processes we exploit, we numerically simulate a representative system. The results are shown in Figure 1, corresponding to the locations labeled in Figure 2. We start with an experimentally-motivated model of a pulse from a GSD, comprising a 2.5-nJ, 10-ps, coherent, Gaussian core superimposed on a 2-nJ, broad, incoherent pedestal (Fig. 1a). Various real or artiﬁcial saturable ab- sorbers can diﬀerentiate between these two pulse components to some degree. However, using a Mamyshev regenerator oﬀers a number of particular advantages, including strong and uniform suppression of the inco- herent pedestal and a relatively ﬂat (in the ideal case) transmittance for higher-energy pulses. This stands in contrast to alternatives such as nonlinear optical loop mirrors and nonlinear polarization evolution, which feature oscillatory transfer functions, or semiconductor saturable absorbers, which oﬀer limited modulation. In addition to its uses as a pulse regenerator [12], Mamyshev regeneration has also been demonstrated ex- perimentally as a modelocking mechanism [14–16] and numerically to increase the coherence of a ﬁeld [17]. The key advance we report here is to use a Mamyshev regenerator as a simultaneous pulse compressor and coherence discriminator, and to subsequently use these properties to enable further nonlinear pulse shaping. In our simulated Mamyshev regenerator, the pulse ﬁrst propagates through 63 meters of passive ﬁber (Nufern PM980-XP). Self-phase modulation and optical wavebreaking act on the coherent, high-intensity core to generate a series of new spectral components. Meanwhile, the less-intense pedestal spectrally broad- ens negligibly. Filtering a portion of the newly-created bandwidth therefore isolates part of the coherent component, producing a 0.1-nJ, 3-ps pulse within 40% of its transform-limited duration (Fig. 1b-c). Im- portantly, the pulse is clean and more coherent, making it a good candidate for ampliﬁcation by parabolic pre-shaping [13]. In this technique, an optimized length of normally-dispersive, passive ﬁber is used to parabolically shape the pulse [18], which is then ampliﬁed in the highly nonlinear regime. The parabolic pulse shape converts nonlinear phase into a linear frequency sweep, permitting compression ratios of 30 or more without compromising the pulse quality [13, 19]. Here, we simulate shaping the pulse in 33 meters of passive ﬁber (Nufern PM980-XP; Fig. 1d-e), before amplifying it ﬁrst in a core-pumped ﬁber ampliﬁer (1.4 m Nufern PM-YSF-HI) and then in a 2.3-m double-clad ﬁber ampliﬁer. The latter is modeled after chirally (cid:13) coupled core (3C R ) ﬁber, which uses a large, 34-µm core diameter to manage high-energy ampliﬁcation while a helical, secondary core maintains single-mode behavior [20]. While this is an attractive feature, our system is equally compatible with conventional ﬁber ampliﬁers. The pulse can be ampliﬁed to 3 µJ (Fig. 1f-g) before distortions from gain narrowing and stimulated Raman scattering become noticeable, and dechirps to 140 fs in a realistic grating compressor (Fig. 1h). It is worth remarking that if ampliﬁcation by parabolic pre-shaping is applied directly to the GSD pulse, the pedestal will remain incompressible, causing only a fraction of the total energy to contribute to the peak power. Furthermore, studies indicate that Raman scattering will prevent a 10-ps pulse from being compressed to signiﬁcantly less than 300 fs [19]. Thus, the combination of Mamyshev regeneration and ampliﬁcation by parabolic pre-shaping is critical to obtaining such short, clean pulses from a typical GSD. Encouraged by these results, we design an equivalent experimental system along the lines of Figure 2. Our starting point is a commercial GSD (OneFive Katana-10 LP), which produces pulses similar to those numerically modeled. The repetition rate is continuously tunable from 50 kHz to 10 MHz, and is set at 1 MHz for most of what follows. The autocorrelation at the diode output reveals a prominent, 14-ps peak on top of a broad, complicated background. As in simulations, we use a Mamyshev regenerator with a tunable bandpass ﬁlter to isolate part of the coherent component. The ﬁlter characteristics are experimentally determined, and will be explained later. Figure 3 depicts the resulting eﬀects on the pulse. As expected, the Mamyshev regenerator strips away the incoherent pedestal, and we observe primarily a clean, Gaussian autocorrelation. The 0.1-nJ ﬁltered pulses are 3 ps long, within 40% of the transform limit.

text: compression

text: to

text: ps

text: with

text: peak

text: powers

text: exceeding

text: MW.

text: Although

text: this

text: represented

text: a

text: new

text: record

text: for

text: GSDs,

text: the

text: pulses

text: remain

text: too

text: long

text: for

text: many

text: ultrafast

text: applications,

text: and

text: their

text: large

text: deviation

text: from

text: the

text: transform-

text: limited

text: duration

text: indicates

text: a

text: lack

text: of

text: control

text: over

text: the

text: pulse.

text: In

text: addition,

text: the

text: system

text: relies

text: on

text: a

text: specially

text: engineered

text: diode,

text: which

text: emits

text: high-quality

text: seed

text: pulses.

text: Here,

text: we

text: demonstrate

text: a

text: scheme

text: for

text: compressing

text: and

text: amplifying

text: pulses

text: from

text: a

text: GSD.

text: Starting

text: with

text: partially

text: coherent,

text: pulses

text: from

text: a

text: commercially-available

text: GSD,

text: we

text: generate

text: pulses

text: with

text: energies

text: of

text: µJ.

text: These

text: represent

text: the

text: shortest

text: pulses

text: from

text: a

text: GSD

text: at

text: comparable

text: energies,

text: and

text: the

text: highest

text: peak

text: power

text: by

text: an

text: order

text: of

text: magnitude.

text: We

text: achieve

text: these

text: results

text: using

text: a

text: multi-stage

text: system.

text: We

text: ﬁrst

text: use

text: a

text: Mamyshev

text: regenerator

text: to

text: shape

text: the

text: pulses

text: from

text: the

text: GSD,

text: at

text: once

text: compressing

text: them

text: and

text: improving

text: their

text: coherence.

text: The

text: clean

text: pulses

text: that

text: we

text: thereby

text: obtain

text: are

text: then

text: amenable

text: to

text: parabolic

text: pre-shaping,

text: followed

text: by

text: ampliﬁcation

text: and

text: compression

text: to

text: femtosecond

text: durations

text: By

text: using

text: propagation

text: regimes

text: that

text: eﬀectively

text: leverage

text: nonlinear

text: eﬀects,

text: we

text: are

text: able

text: to

text: compress

text: the

text: ampliﬁed

text: pulses

text: to

text: near

text: the

text: transform

text: limit.

text: To

text: illustrate

text: the

text: nonlinear

text: processes

text: we

text: exploit,

text: we

text: numerically

text: simulate

text: a

text: representative

text: system.

text: The

text: results

text: are

text: shown

text: in

text: Figure

text: corresponding

text: to

text: the

text: locations

text: labeled

text: in

text: Figure

text: We

text: start

text: with

text: an

text: experimentally-motivated

text: model

text: of

text: a

text: pulse

text: from

text: a

text: GSD,

text: comprising

text: a

text: coherent,

text: Gaussian

text: core

text: superimposed

text: on

text: a

text: broad,

text: incoherent

text: pedestal

text: (Fig.

text: Various

text: real

text: or

text: artiﬁcial

text: saturable

text: ab-

text: sorbers

text: can

text: diﬀerentiate

text: between

text: these

text: two

text: pulse

text: components

text: to

text: some

text: degree.

text: However,

text: using

text: a

text: Mamyshev

text: regenerator

text: oﬀers

text: a

text: number

text: of

text: particular

text: advantages,

text: including

text: strong

text: and

text: uniform

text: suppression

text: of

text: the

text: inco-

text: herent

text: pedestal

text: and

text: a

text: relatively

text: ﬂat

text: (in

text: the

text: ideal

text: case)

text: transmittance

text: for

text: higher-energy

text: pulses.

text: This

text: stands

text: in

text: contrast

text: to

text: alternatives

text: such

text: as

text: nonlinear

text: optical

text: loop

text: mirrors

text: and

text: nonlinear

text: polarization

text: evolution,

text: which

text: feature

text: oscillatory

text: transfer

text: functions,

text: or

text: semiconductor

text: saturable

text: absorbers,

text: which

text: oﬀer

text: limited

text: modulation.

text: In

text: addition

text: to

text: its

text: uses

text: as

text: a

text: pulse

text: regenerator

text: Mamyshev

text: regeneration

text: has

text: also

text: been

text: demonstrated

text: ex-

text: perimentally

text: as

text: a

text: modelocking

text: mechanism

text: and

text: numerically

text: to

text: increase

text: the

text: coherence

text: of

text: a

text: ﬁeld

text: The

text: key

text: advance

text: we

text: report

text: here

text: is

text: to

text: use

text: a

text: Mamyshev

text: regenerator

text: as

text: a

text: simultaneous

text: pulse

text: compressor

text: and

text: coherence

text: discriminator,

text: and

text: to

text: subsequently

text: use

text: these

text: properties

text: to

text: enable

text: further

text: nonlinear

text: pulse

text: shaping.

text: In

text: our

text: simulated

text: Mamyshev

text: regenerator,

text: the

text: pulse

text: ﬁrst

text: propagates

text: through

text: meters

text: of

text: passive

text: ﬁber

text: (Nufern

text: Self-phase

text: modulation

text: and

text: optical

text: wavebreaking

text: act

text: on

text: the

text: coherent,

text: high-intensity

text: core

text: to

text: generate

text: a

text: series

text: of

text: new

text: spectral

text: components.

text: Meanwhile,

text: the

text: less-intense

text: pedestal

text: spectrally

text: broad-

text: ens

text: negligibly.

text: Filtering

text: a

text: portion

text: of

text: the

text: newly-created

text: bandwidth

text: therefore

text: isolates

text: part

text: of

text: the

text: coherent

text: component,

text: producing

text: a

text: pulse

text: within

text: of

text: its

text: transform-limited

text: duration

text: (Fig.

text: Im-

text: portantly,

text: the

text: pulse

text: is

text: clean

text: and

text: more

text: coherent,

text: making

text: it

text: a

text: good

text: candidate

text: for

text: ampliﬁcation

text: by

text: parabolic

text: pre-shaping

text: In

text: this

text: technique,

text: an

text: optimized

text: length

text: of

text: normally-dispersive,

text: passive

text: ﬁber

text: is

text: used

text: to

text: parabolically

text: shape

text: the

text: pulse

text: which

text: is

text: then

text: ampliﬁed

text: in

text: the

text: highly

text: nonlinear

text: regime.

text: The

text: parabolic

text: pulse

text: shape

text: converts

text: nonlinear

text: phase

text: into

text: a

text: linear

text: frequency

text: sweep,

text: permitting

text: compression

text: ratios

text: of

text: or

text: more

text: without

text: compromising

text: the

text: pulse

text: quality

text: Here,

text: we

text: simulate

text: shaping

text: the

text: pulse

text: in

text: meters

text: of

text: passive

text: ﬁber

text: (Nufern

text: Fig.

text: before

text: amplifying

text: it

text: ﬁrst

text: in

text: a

text: core-pumped

text: ﬁber

text: ampliﬁer

text: m

text: Nufern

text: PM-YSF-HI)

text: and

text: then

text: in

text: a

text: double-clad

text: ﬁber

text: ampliﬁer.

text: The

text: latter

text: is

text: modeled

text: after

text: chirally

text: coupled

text: core

text: R

text: ﬁber,

text: which

text: uses

text: a

text: large,

text: core

text: diameter

text: to

text: manage

text: high-energy

text: ampliﬁcation

text: while

text: a

text: helical,

text: secondary

text: core

text: maintains

text: single-mode

text: behavior

text: While

text: this

text: is

text: an

text: attractive

text: feature,

text: our

text: system

text: is

text: equally

text: compatible

text: with

text: conventional

text: ﬁber

text: ampliﬁers.

text: The

text: pulse

text: can

text: be

text: ampliﬁed

text: to

text: µJ

text: (Fig.

text: before

text: distortions

text: from

text: gain

text: narrowing

text: and

text: stimulated

text: Raman

text: scattering

text: become

text: noticeable,

text: and

text: dechirps

text: to

text: fs

text: in

text: a

text: realistic

text: grating

text: compressor

text: (Fig.

text: It

text: is

text: worth

text: remarking

text: that

text: if

text: ampliﬁcation

text: by

text: parabolic

text: pre-shaping

text: is

text: applied

text: directly

text: to

text: the

text: GSD

text: pulse,

text: the

text: pedestal

text: will

text: remain

text: incompressible,

text: causing

text: only

text: a

text: fraction

text: of

text: the

text: total

text: energy

text: to

text: contribute

text: to

text: the

text: peak

text: power.

text: Furthermore,

text: studies

text: indicate

text: that

text: Raman

text: scattering

text: will

text: prevent

text: a

text: pulse

text: from

text: being

text: compressed

text: to

text: signiﬁcantly

text: less

text: than

text: fs

text: Thus,

text: the

text: combination

text: of

text: Mamyshev

text: regeneration

text: and

text: ampliﬁcation

text: by

text: parabolic

text: pre-shaping

text: is

text: critical

text: to

text: obtaining

text: such

text: short,

text: clean

text: pulses

text: from

text: a

text: typical

text: GSD.

text: Encouraged

text: by

text: these

text: results,

text: we

text: design

text: an

text: equivalent

text: experimental

text: system

text: along

text: the

text: lines

text: of

text: Figure

text: Our

text: starting

text: point

text: is

text: a

text: commercial

text: GSD

text: (OneFive

text: LP),

text: which

text: produces

text: pulses

text: similar

text: to

text: those

text: numerically

text: modeled.

text: The

text: repetition

text: rate

text: is

text: continuously

text: tunable

text: from

text: kHz

text: to

text: MHz,

text: and

text: is

text: set

text: at

text: MHz

text: for

text: most

text: of

text: what

text: follows.

text: The

text: autocorrelation

text: at

text: the

text: diode

text: output

text: reveals

text: a

text: prominent,

text: peak

text: on

text: top

text: of

text: a

text: broad,

text: complicated

text: background.

text: As

text: in

text: simulations,

text: we

text: use

text: a

text: Mamyshev

text: regenerator

text: with

text: a

text: tunable

text: bandpass

text: ﬁlter

text: to

text: isolate

text: part

text: of

text: the

text: coherent

text: component.

text: The

text: ﬁlter

text: characteristics

text: are

text: experimentally

text: determined,

text: and

text: will

text: be

text: explained

text: later.

text: Figure

text: depicts

text: the

text: resulting

text: eﬀects

text: on

text: the

text: pulse.

text: As

text: expected,

text: the

text: Mamyshev

text: regenerator

text: strips

text: away

text: the

text: incoherent

text: pedestal,

text: and

text: we

text: observe

text: primarily

text: a

text: clean,

text: Gaussian

text: autocorrelation.

text: The

text: ﬁltered

text: pulses

text: are

text: ps

text: long,

text: within

text: of

text: the

text: transform

text: limit.


text: 7 -40 -40 (a) (b) -60 -60 -80 -80 -100 -100 -120 -120 -140 -140 -20 -10 0 10 20 -20 -10 0 10 20 Frequency (kHz) Frequency (kHz) FIG. 6. Measured RF spectra at the system output using (a) a one-photon detector and (b) and two-photon detector. Both spectra are centered at 1 MHz, and have a resolution bandwidth of 200 Hz. Corresponding noise ﬂoors are shown in red. 0.02 0.01 0.00 0 200 400 600 800 RF Frequency (MHz) FIG. 7. Dependence of the RF spectrum background (relative to the comb tooth amplitude) on the RF frequency, measured here at several harmonics of the 1-MHz fundamental. The solid line represents a quadratic ﬁt as described in the text, with the outlier at 448 MHz omitted. ﬁber (Hi1060) is spliced to the end to ﬁlter out higher-order modes. We then directly measure the resulting pulse train with a fast photodetector and a 25-GHz oscilloscope with a long record length. A single sweep of the oscilloscope is used to measure a series of 100 consecutive pulses while preserving the true timing jitter. The pulses are overlaid using the nominal repetition rate in Figure 8, where it is evident that only two of the 100 pulses diﬀer markedly from the average in their spectral shape. These two outliers do not noticeably skew the average spectrum (as measured by an optical spectrum analyzer; red line in Fig. 8a), nor do they correspond to extreme energies in the single-pulse energy distribution (Fig. 8b). Computing the time-integrated photodetector signal and the center-of-mass arrival time for each pulse, we ﬁnd standard deviations of 2% and 30 ps, respectively, in reasonable agreement with the energy jitter and timing jitter derived from RF spectral analysis. It is important to note that this kind of timing jitter derives from a fundamentally diﬀerent cause than the kind typically seen in modelocked oscillators. In the case of the latter, the jitter is correlated from one roundtrip to the next, causing the pulse’s arrival time to drift gradually and continuously over time. Over suﬃciently short observation periods, the accumulated timing jitter is negligible. Over longer observation periods, however, if active stabilization techniques are not used, the timing jitter can reach picosecond scales [33, 34]. Timing jitter in modelocked oscillators therefore depends on the observation period (or, equivalently, on the range of RF frequencies over which the noise is integrated). By contrast, timing jitter in a gain-switched diode is uncorrelated from pulse to pulse. Each new pulse forms from spontaneous emission noise, and so the arrival times of any two pulses are independent of one another. Following from the statistics of the initial noise, the arrival times do nonetheless have a statistical distribution. The measured timing )Bd( rewoP FR dnuorgkcaB FR evitaleR )Bd( rewoP FR ##LTFigure## ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: (a)

text: (b)

text: Frequency

text: (kHz)

text: Frequency

text: (kHz)

text: FIG.

text: Measured

text: RF

text: spectra

text: at

text: the

text: system

text: output

text: using

text: (a)

text: a

text: one-photon

text: detector

text: and

text: (b)

text: and

text: two-photon

text: detector.

text: Both

text: spectra

text: are

text: centered

text: at

text: MHz,

text: and

text: have

text: a

text: resolution

text: bandwidth

text: of

text: Hz.

text: Corresponding

text: noise

text: ﬂoors

text: are

text: shown

text: in

text: red.

text: RF

text: Frequency

text: (MHz)

text: FIG.

text: Dependence

text: of

text: the

text: RF

text: spectrum

text: background

text: (relative

text: to

text: the

text: comb

text: tooth

text: amplitude)

text: on

text: the

text: RF

text: frequency,

text: measured

text: here

text: at

text: several

text: harmonics

text: of

text: the

text: fundamental.

text: The

text: solid

text: line

text: represents

text: a

text: quadratic

text: ﬁt

text: as

text: described

text: in

text: the

text: text,

text: with

text: the

text: outlier

text: at

text: MHz

text: omitted.

text: ﬁber

text: is

text: spliced

text: to

text: the

text: end

text: to

text: ﬁlter

text: out

text: higher-order

text: modes.

text: We

text: then

text: directly

text: measure

text: the

text: resulting

text: pulse

text: train

text: with

text: a

text: fast

text: photodetector

text: and

text: a

text: oscilloscope

text: with

text: a

text: long

text: record

text: length.

text: A

text: single

text: sweep

text: of

text: the

text: oscilloscope

text: is

text: used

text: to

text: measure

text: a

text: series

text: of

text: consecutive

text: pulses

text: while

text: preserving

text: the

text: true

text: timing

text: jitter.

text: The

text: pulses

text: are

text: overlaid

text: using

text: the

text: nominal

text: repetition

text: rate

text: in

text: Figure

text: where

text: it

text: is

text: evident

text: that

text: only

text: two

text: of

text: the

text: pulses

text: diﬀer

text: markedly

text: from

text: the

text: average

text: in

text: their

text: spectral

text: shape.

text: These

text: two

text: outliers

text: do

text: not

text: noticeably

text: skew

text: the

text: average

text: spectrum

text: (as

text: measured

text: by

text: an

text: optical

text: spectrum

text: analyzer;

text: red

text: line

text: in

text: Fig.

text: nor

text: do

text: they

text: correspond

text: to

text: extreme

text: energies

text: in

text: the

text: single-pulse

text: energy

text: distribution

text: (Fig.

text: Computing

text: the

text: time-integrated

text: photodetector

text: signal

text: and

text: the

text: center-of-mass

text: arrival

text: time

text: for

text: each

text: pulse,

text: we

text: ﬁnd

text: standard

text: deviations

text: of

text: and

text: ps,

text: respectively,

text: in

text: reasonable

text: agreement

text: with

text: the

text: energy

text: jitter

text: and

text: timing

text: jitter

text: derived

text: from

text: RF

text: spectral

text: analysis.

text: It

text: is

text: important

text: to

text: note

text: that

text: this

text: kind

text: of

text: timing

text: jitter

text: derives

text: from

text: a

text: fundamentally

text: diﬀerent

text: cause

text: than

text: the

text: kind

text: typically

text: seen

text: in

text: modelocked

text: oscillators.

text: In

text: the

text: case

text: of

text: the

text: latter,

text: the

text: jitter

text: is

text: correlated

text: from

text: one

text: roundtrip

text: to

text: the

text: next,

text: causing

text: the

text: pulse’s

text: arrival

text: time

text: to

text: drift

text: gradually

text: and

text: continuously

text: over

text: time.

text: Over

text: suﬃciently

text: short

text: observation

text: periods,

text: the

text: accumulated

text: timing

text: jitter

text: is

text: negligible.

text: Over

text: longer

text: observation

text: periods,

text: however,

text: if

text: active

text: stabilization

text: techniques

text: are

text: not

text: used,

text: the

text: timing

text: jitter

text: can

text: reach

text: picosecond

text: scales

text: Timing

text: jitter

text: in

text: modelocked

text: oscillators

text: therefore

text: depends

text: on

text: the

text: observation

text: period

text: (or,

text: equivalently,

text: on

text: the

text: range

text: of

text: RF

text: frequencies

text: over

text: which

text: the

text: noise

text: is

text: integrated).

text: By

text: contrast,

text: timing

text: jitter

text: in

text: a

text: gain-switched

text: diode

text: is

text: uncorrelated

text: from

text: pulse

text: to

text: pulse.

text: Each

text: new

text: pulse

text: forms

text: from

text: spontaneous

text: emission

text: noise,

text: and

text: so

text: the

text: arrival

text: times

text: of

text: any

text: two

text: pulses

text: are

text: independent

text: of

text: one

text: another.

text: Following

text: from

text: the

text: statistics

text: of

text: the

text: initial

text: noise,

text: the

text: arrival

text: times

text: do

text: nonetheless

text: have

text: a

text: statistical

text: distribution.

text: The

text: measured

text: timing

text: )Bd(

text: rewoP

text: FR

text: dnuorgkcaB

text: FR

text: evitaleR

text: )Bd(

text: rewoP

text: FR

text: ##LTFigure##

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##