text: FIG. 3: Quality of the single exchange approximation for the high-spin ﬁrst-order · · · · · · · · · exchange energy in the Li Li, Li N, and N N systems measured as the ratio E(10)(S2)/E(10). Color-coded vertical dashed lines correspond to the positions of minima exch exch for the high-spin complexes. N-Li 1.4 Li-Li 1.2 N-N 1 0.8 0.6 0.4 0.2 0 4 5 6 7 8 9 10 11 12 R [bohr] 36 )01(E /)2S( )01(E (cid:9) hcxe hcxe ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: FIG.

text: Quality

text: of

text: the

text: single

text: exchange

text: approximation

text: for

text: the

text: high-spin

text: ﬁrst-order

text: exchange

text: energy

text: in

text: the

text: Li

text: Li,

text: Li

text: N,

text: and

text: N

text: N

text: systems

text: measured

text: as

text: the

text: ratio

text: Color-coded

text: vertical

text: dashed

text: lines

text: correspond

text: to

text: the

text: positions

text: of

text: minima

text: exch

text: exch

text: for

text: the

text: high-spin

text: complexes.

text: N-Li

text: Li-Li

text: N-N

text: R

text: [bohr]

text: hcxe

text: hcxe

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: FIG. 5: Diagonal and spin-ﬂip parts of the ﬁrst-order exchange energy for the dimer of − ground-state oxygen molecules (3Σ ) for four basic geometric conﬁgurations. For the g X-shape conﬁgurations, the absolute value of the spin-ﬂip term is shown, hence the dip around 7a corresponding to a change of sign from positive (for small R) to negative. 0 1000 1000 E(10) exch,diag 100 100 E(10) exch,1flip 10 10 1 1 0.1 0.1 H 0.01 0.001 X 0.01 0.0001 0.001 1e−05 5 6 7 8 9 5 6 7 8 9 10000 100000 1000 10000 1000 100 100 10 10 1 1 L 0.1 T 0.1 0.01 0.01 0.001 0.001 5 6 7 8 9 5 6 7 8 9 R [a.u.] 38 ]Vem[ ygrenE ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: FIG.

label: paragraph

text: Diagonal

label: caption

text: and

text: spin-ﬂip

text: parts

text: of

text: the

text: ﬁrst-order

text: exchange

text: energy

text: for

text: the

text: dimer

text: of

text: ground-state

text: oxygen

text: molecules

text: for

text: four

text: basic

text: geometric

text: conﬁgurations.

text: For

text: the

text: g

text: X-shape

text: conﬁgurations,

text: the

text: absolute

text: value

text: of

text: the

text: spin-ﬂip

text: term

text: is

text: shown,

text: hence

text: the

text: dip

text: around

text: corresponding

text: to

text: a

text: change

text: of

text: sign

text: from

text: positive

text: (for

text: small

text: R)

text: to

text: negative.

font: default

text: exch,diag

text: H

text: X

text: L

text: T

text: R

text: [a.u.]

text: ]Vem[

text: ygrenE

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: · · · FIG. 7: First-order exchange energy for the Mn Mn complex: (a) diagonal and spin-ﬂip contributions to the exchange energies compared with the high-spin exchange energy; the extremely small contribution of spin-ﬂip exchange is evident; (b) the quality of the S2 · · · approximation for the high-spin (undecaplet) Mn Mn state; (c) comparison of the Heisenberg J parameters derived from SF-SAPT with existing theoretical and AB experimental data; note that only in the study of Buchachenko et al. [72] the J AB parameter is available as a function of R, whereas other data are provided for the respective equilibrium distances. For the experimental value, the distance at which J is AB marked corresponds to the CCSD(T) 1Σ+ minimum obtained in Ref. [72]. g 100000 E(10) E(10)exch,diag exch,1flip 10000 1000 100 (a) 1.1 1 (b) 0.9 0.8 0.7 5 0 −5 MCQDPT2 [65] ACPF [67] −10 experiment [70] −15 (c) −20 CASPT2 [66] SF−SAPT MRCI [69] −25 5 6 7 8 9 10 R [bohr] 40 ]1−mc[ ygrenE hcxe)01(E /)2S(hcxe)01(E ]1−mc[ J ##LTFigure## ##LTLine## ##LTLine##

text: FIG.

text: First-order

text: exchange

text: energy

text: for

text: the

text: Mn

text: Mn

text: complex:

text: (a)

text: diagonal

text: and

text: spin-ﬂip

text: contributions

text: to

text: the

text: exchange

text: energies

text: compared

text: with

text: the

text: high-spin

text: exchange

text: energy;

text: the

text: extremely

text: small

text: contribution

text: of

text: spin-ﬂip

text: exchange

text: is

text: evident;

text: (b)

text: the

text: quality

text: of

text: the

text: approximation

text: for

text: the

text: high-spin

text: (undecaplet)

text: Mn

text: Mn

text: state;

text: (c)

text: comparison

text: of

text: the

text: Heisenberg

text: J

text: parameters

text: derived

text: from

text: SF-SAPT

text: with

text: existing

text: theoretical

text: and

text: AB

text: experimental

text: data;

text: note

text: that

text: only

text: in

text: the

text: study

text: of

text: Buchachenko

text: et

text: al.

text: the

text: J

text: AB

text: parameter

text: is

text: available

text: as

text: a

text: function

text: of

text: R,

text: whereas

text: other

text: data

text: are

text: provided

text: for

text: the

text: respective

text: equilibrium

text: distances.

text: For

text: the

text: experimental

text: value,

text: the

text: distance

text: at

text: which

text: J

text: is

text: AB

text: marked

text: corresponds

text: to

text: the

text: CCSD(T)

text: minimum

text: obtained

text: in

text: Ref.

text: g

text: (a)

text: (b)

text: −5

text: ACPF

text: experiment

text: (c)

text: SF−SAPT

text: MRCI

text: R

text: [bohr]

text: ygrenE

text: J

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##


text: of two spins. In Section III we give the most important details regarding the implementation of the theory, and in Section IV we report the test calculations for several important open- · · · shell open-shell systems. In the last section of the paper, we summarize our results and discuss prospects for the future. II. THEORY Similar to the existing closed-shell and high-spin open-shell SAPT approaches, the per- mutational symmetry adaptation, leading to the exchange corrections, is performed in the simplest manner, within the symmetrized Rayleigh-Schr¨odinger (SRS) formalism [24, 43]. Speciﬁcally, the SRS wavefunction corrections are computed from the standard Rayleigh- Schro¨dinger (RS) perturbation expansion without any symmetry adaptation: only later, the energy corrections are computed from a formula that involves a symmetry projector. In the spin-free formalism used, for example, in Ref. [38], this symmetry operator projects onto a particular irreducible representation of the permutation group S (N is the NA+NB X number of electrons of molecule X): the choice of this representation is determined by the spin multiplicity. In the more conventional, spin formalism employed here (and used in the high-spin case so far), this operator has to be replaced by the (N + N )-electron antisym- A B metrizer and an appropriate spin projection. In the already existing high-spin open-shell SAPT theories the monomer wavefunctions Ψ and Ψ as well as the zeroth-order dimer A B wavefunction Ψ = Ψ Ψ are pure spin functions so the spin projection is not needed. This 0 A B is only the case if all unpaired electrons on both monomers have the same spin, that is, when ± M = (S + S ) so that no contamination by lower-spin states is possible. Indeed, the S A B restricted open-shell Hartree-Fock and Kohn-Sham (ROHF/ROKS) SAPT exchange correc- tions have been developed [26] under the assumption that all unpaired spins point the same way. A For the low-spin case, it is known [12, 39] that the antisymmetrizer in the SRS energy expression has to be accompanied by an operator P that projects a dimer function onto SMS a subspace corresponding to a particular value of the total spin S (with an appropriate M ). S In this way, the exchange corrections, diﬀerent for diﬀerent dimer spin states, are obtained by expanding the energy expression (cid:104) | A | (cid:105) Ψ Ψ V P Φ E = (cid:104) A B |A SMS| AB(cid:105) , (1) int Ψ Ψ P Φ A B SMS AB 6 ##LTLine##

text: of

text: two

text: spins.

text: In

text: Section

text: III

text: we

text: give

text: the

text: most

text: important

text: details

text: regarding

text: the

text: implementation

text: of

text: the

text: theory,

text: and

text: in

text: Section

text: IV

text: we

text: report

text: the

text: test

text: calculations

text: for

text: several

text: important

text: open-

text: shell

text: open-shell

text: systems.

text: In

text: the

text: last

text: section

text: of

text: the

text: paper,

text: we

text: summarize

text: our

text: results

text: and

text: discuss

text: prospects

text: for

text: the

text: future.

text: II.

label: section

text: THEORY

text: Similar

text: to

text: the

text: existing

text: closed-shell

text: and

text: high-spin

text: open-shell

text: SAPT

text: approaches,

text: the

text: per-

text: mutational

text: symmetry

text: adaptation,

text: leading

text: to

text: the

text: exchange

text: corrections,

text: is

text: performed

text: in

text: the

text: simplest

text: manner,

text: within

text: the

text: symmetrized

text: Rayleigh-Schr¨odinger

text: (SRS)

text: formalism

text: Speciﬁcally,

text: the

text: SRS

text: wavefunction

text: corrections

text: are

text: computed

text: from

text: the

text: standard

text: Rayleigh-

text: Schro¨dinger

text: (RS)

text: perturbation

text: expansion

text: without

text: any

text: symmetry

text: adaptation:

text: only

text: later,

text: the

text: energy

text: corrections

text: are

text: computed

text: from

text: a

text: formula

text: that

text: involves

text: a

text: symmetry

text: projector.

text: In

text: the

text: spin-free

text: formalism

text: used,

text: for

text: example,

text: in

text: Ref.

text: this

text: symmetry

text: operator

text: projects

text: onto

text: a

text: particular

text: irreducible

text: representation

text: of

text: the

text: permutation

text: group

text: S

text: (N

text: is

text: the

text: NA+NB

text: X

text: number

text: of

text: electrons

text: of

text: molecule

text: X):

text: the

text: choice

text: of

text: this

text: representation

text: is

text: determined

text: by

text: the

text: spin

text: multiplicity.

text: In

text: the

text: more

text: conventional,

text: spin

text: formalism

text: employed

text: here

text: (and

text: used

text: in

text: the

text: high-spin

text: case

text: so

text: far),

text: this

text: operator

text: has

text: to

text: be

text: replaced

text: by

text: the

text: (N

text: N

text: )-electron

text: antisym-

text: A

text: B

text: metrizer

text: and

text: an

text: appropriate

text: spin

text: projection.

text: In

text: the

text: already

text: existing

text: high-spin

text: open-shell

text: SAPT

text: theories

text: the

text: monomer

text: wavefunctions

text: Ψ

text: and

text: Ψ

text: as

text: well

text: as

text: the

text: zeroth-order

text: dimer

text: A

text: B

text: wavefunction

text: Ψ

text: Ψ

text: Ψ

text: are

text: pure

text: spin

text: functions

text: so

text: the

text: spin

text: projection

text: is

text: not

text: needed.

text: This

text: A

text: B

text: is

text: only

text: the

text: case

text: if

text: all

text: unpaired

text: electrons

text: on

text: both

text: monomers

text: have

text: the

text: same

text: spin,

text: that

text: is,

text: when

text: M

text: (S

text: S

text: so

text: that

text: no

text: contamination

text: by

text: lower-spin

text: states

text: is

text: possible.

text: Indeed,

text: the

text: S

text: A

text: B

text: restricted

text: open-shell

text: Hartree-Fock

text: and

text: Kohn-Sham

text: (ROHF/ROKS)

text: SAPT

text: exchange

text: correc-

text: tions

text: have

text: been

text: developed

text: under

text: the

text: assumption

text: that

text: all

text: unpaired

text: spins

text: point

text: the

text: same

text: way.

text: A

text: For

text: the

text: low-spin

text: case,

text: it

text: is

text: known

text: that

text: the

text: antisymmetrizer

text: in

text: the

text: SRS

text: energy

text: expression

text: has

text: to

text: be

text: accompanied

text: by

text: an

text: operator

text: P

text: that

text: projects

text: a

text: dimer

text: function

text: onto

text: SMS

text: a

text: subspace

text: corresponding

text: to

text: a

text: particular

text: value

text: of

text: the

text: total

text: spin

text: S

text: (with

text: an

text: appropriate

text: M

text: S

text: In

text: this

text: way,

text: the

text: exchange

text: corrections,

text: diﬀerent

text: for

text: diﬀerent

text: dimer

text: spin

text: states,

text: are

text: obtained

text: by

text: expanding

text: the

text: energy

text: expression

text: A

text: Ψ

text: Ψ

text: V

text: P

text: Φ

text: E

text: A

text: B

text: |A

text: SMS|

text: int

text: Ψ

text: Ψ

text: P

text: Φ

text: A

text: B

text: SMS

text: AB

text: ##LTLine##


text: in powers of the intermolecular interaction operator V and separating the polarization and A exchange eﬀects in each order. In Eq. (1), is the (N + N )-electron antisymmetrizer and A B Φ is the polarization (RS) expansion of the wave function for the complex [24]. We will AB assume that Ψ and Ψ are ground-state high-spin open-shell determinants. The occupied A B orbitals in Ψ are χ , χ , . . . , χ (inactive, doubly occupied) and χ , χ , . . . , χ A i1 i2 ikA a1 a2 a2SA (active, occupied by α electrons only). The occupied orbitals in Ψ are χ , χ , . . . , χ B j1 j2 jkB (inactive, doubly occupied) and χ , χ , . . . , χ (active, occupied by β electrons only). b1 b2 b2SB The spin projector P commutes with V and the zeroth-order Hamiltonian H = SMS 0 H + H as the latter operators are spin-independent. Moreover, the operator Sˆ2, and thus A B also P , is independent of the ordering of electrons and hence commutes with any electron SMS A permutations or their linear combinations including . As a result, we can rewrite Eq. (1) in an alternative form where the spin projection acts in the bra instead of the ket: (cid:104) | A| (cid:48) (cid:105) P Ψ Ψ V Φ E = (cid:104) SMS A B |A| (cid:48) AB(cid:105) . (2) int P Ψ Ψ Φ SMS A B AB While Eqs. (1) and (2) are fully equivalent, they have quite diﬀerent interpretations. Eq. (1) corresponds to a standard RS treatment where the wavefunction corrections in the expansion of Φ are the same for all asymptotically degenerate multiplets: the spin pro- AB jection enters later, at the calculation of SRS energy corrections. Eq. (2) corresponds to a perturbation expansion initiated from a spin-adapted zeroth-order function P Ψ Ψ , SMS A B (cid:48) with all resulting perturbation corrections (in the expansion of Φ ) also being of pure AB spin. Importantly, both approaches allow the use of standard nondegenerate perturbation theory (unless degeneracy arises from the orbital part of the monomer wavefunctions, which is outside the scope of this work), albeit for quite diﬀerent reasons. For Eq. (2), the projec- tor P reduces the zeroth-order space of (2S + 1)(2S + 1) asymptotically degenerate SMS A B product functions corresponding to a pair of interacting multiplets to a single spin-adapted combination with the requested (S, M ). For Eq. (1), any of the (2S + 1)(2S + 1) product S A B functions, including Ψ Ψ , is a valid zeroth-order state for nondegenerate RS perturbation A B theory as neither V nor H mix states with diﬀerent M or M . We choose Eq. (1) as the 0 SA SB starting point for the derivation below. We now introduce the single exchange approximation (often called the S2 approximation 7 ##LTLine##

text: in

text: powers

text: of

text: the

text: intermolecular

text: interaction

text: operator

text: V

text: and

text: separating

text: the

text: polarization

text: and

text: A

text: exchange

text: eﬀects

text: in

text: each

text: order.

text: In

text: Eq.

text: is

text: the

text: (N

text: N

text: )-electron

text: antisymmetrizer

text: and

text: A

text: B

text: Φ

text: is

text: the

text: polarization

text: (RS)

text: expansion

text: of

text: the

text: wave

text: function

text: for

text: the

text: complex

text: We

text: will

text: AB

text: assume

text: that

text: Ψ

text: and

text: Ψ

text: are

text: ground-state

text: high-spin

text: open-shell

text: determinants.

text: The

text: occupied

text: A

text: B

text: orbitals

text: in

text: Ψ

text: are

text: χ

text: χ

text: χ

text: (inactive,

text: doubly

text: occupied)

text: and

text: χ

text: χ

text: χ

text: A

text: ikA

text: (active,

text: occupied

text: by

text: α

text: electrons

text: only).

text: The

text: occupied

text: orbitals

text: in

text: Ψ

text: are

text: χ

text: χ

text: χ

text: B

text: jkB

text: (inactive,

text: doubly

text: occupied)

text: and

text: χ

text: χ

text: χ

text: (active,

text: occupied

text: by

text: β

text: electrons

text: only).

text: The

text: spin

text: projector

text: P

text: commutes

text: with

text: V

text: and

text: the

text: zeroth-order

text: Hamiltonian

text: H

text: SMS

text: H

text: H

text: as

text: the

text: latter

text: operators

text: are

text: spin-independent.

text: Moreover,

text: the

text: operator

text: and

text: thus

text: A

text: B

text: also

text: P

text: is

text: independent

text: of

text: the

text: ordering

text: of

text: electrons

text: and

text: hence

text: commutes

text: with

text: any

text: electron

text: SMS

text: A

text: permutations

text: or

text: their

text: linear

text: combinations

text: including

text: As

text: a

text: result,

text: we

text: can

text: rewrite

text: Eq.

text: in

text: an

text: alternative

text: form

text: where

text: the

text: spin

text: projection

text: acts

text: in

text: the

text: bra

text: instead

text: of

text: the

text: ket:

text: A|

text: P

text: Ψ

text: Ψ

text: V

text: Φ

text: E

text: SMS

text: A

text: B

text: |A|

text: int

text: P

text: Ψ

text: Ψ

text: Φ

text: SMS

text: A

text: B

text: AB

text: While

text: Eqs.

text: and

text: are

text: fully

text: equivalent,

text: they

text: have

text: quite

text: diﬀerent

text: interpretations.

text: Eq.

text: corresponds

text: to

text: a

text: standard

text: RS

text: treatment

text: where

text: the

text: wavefunction

text: corrections

text: in

text: the

text: expansion

text: of

text: Φ

text: are

text: the

text: same

text: for

text: all

text: asymptotically

text: degenerate

text: multiplets:

text: the

text: spin

text: pro-

text: AB

text: jection

text: enters

text: later,

text: at

text: the

text: calculation

text: of

text: SRS

text: energy

text: corrections.

text: Eq.

text: corresponds

text: to

text: a

text: perturbation

text: expansion

text: initiated

text: from

text: a

text: spin-adapted

text: zeroth-order

text: function

text: P

text: Ψ

text: Ψ

text: SMS

text: A

text: B

text: with

text: all

text: resulting

text: perturbation

text: corrections

text: (in

text: the

text: expansion

text: of

text: Φ

text: also

text: being

text: of

text: pure

text: AB

text: spin.

text: Importantly,

text: both

text: approaches

text: allow

text: the

text: use

text: of

text: standard

text: nondegenerate

text: perturbation

text: theory

text: (unless

text: degeneracy

text: arises

text: from

text: the

text: orbital

text: part

text: of

text: the

text: monomer

text: wavefunctions,

text: which

text: is

text: outside

text: the

text: scope

text: of

text: this

text: work),

text: albeit

text: for

text: quite

text: diﬀerent

text: reasons.

text: For

text: Eq.

text: the

text: projec-

text: tor

text: P

text: reduces

text: the

text: zeroth-order

text: space

text: of

text: asymptotically

text: degenerate

text: SMS

text: A

text: B

text: product

text: functions

text: corresponding

text: to

text: a

text: pair

text: of

text: interacting

text: multiplets

text: to

text: a

text: single

text: spin-adapted

text: combination

text: with

text: the

text: requested

text: (S,

text: M

text: For

text: Eq.

text: any

text: of

text: the

text: product

text: S

text: A

text: B

text: functions,

text: including

text: Ψ

text: Ψ

text: is

text: a

text: valid

text: zeroth-order

text: state

text: for

text: nondegenerate

text: RS

text: perturbation

text: A

text: B

text: theory

text: as

text: neither

text: V

text: nor

text: H

text: mix

text: states

text: with

text: diﬀerent

text: M

text: or

text: M

text: We

text: choose

text: Eq.

text: as

text: the

text: SA

text: SB

text: starting

text: point

text: for

text: the

text: derivation

text: below.

text: We

text: now

text: introduce

text: the

text: single

text: exchange

text: approximation

text: (often

text: called

text: the

text: approximation

text: ##LTLine##


text: References C. E. Bannier, E. Feess, and N. Packham. Incentive schemes, private information and the double-edged role of competition for agents. Working Paper, June 2016. R. B´enabou and J. Tirole. Bonus culture: Competitive pay, screening, and multitasking. Journal of Political Economy, 124(2):305–370, 2016. W. H. Fleming and R. W. Rishel. Deterministic and Stochastic Optimal Control. Springer, 1975. B. Holmstrom and P. Milgrom. Aggregation and linearity in the provision of intertemporal incentives. Econometrica, 55:303–328, 1987. B. Jullien. Participation constraints in adverse selection models. Journal of Economic Theory, 93(1):1–47, 2000. B. Salani´e. The Economics of Contracts. MIT Press, 2nd edition, 2005. H. Schaettler and J. Sung. The ﬁrst-order approach to the continuous-time principal–agent problem with exponential utility. Journal of Economic Theory, 61(2):331–371, 1993. J. Sung. Optimal contracts under adverse selection and moral hazard: a continuous-time ap- proach. Review of Financial Studies, 18(3):1021–1073, 2005. 8

text: References

label: reference

text: C.

text: E.

text: Bannier,

text: E.

text: Feess,

text: and

text: N.

text: Packham.

text: Incentive

text: schemes,

text: private

text: information

text: and

text: the

text: double-edged

text: role

text: of

text: competition

text: for

text: agents.

text: Working

text: Paper,

text: June

text: R.

text: B´enabou

text: and

text: J.

text: Tirole.

text: Bonus

text: culture:

text: Competitive

text: pay,

text: screening,

text: and

text: multitasking.

text: Journal

text: of

text: Political

text: Economy,

text: W.

text: H.

text: Fleming

text: and

text: R.

text: W.

text: Rishel.

text: Deterministic

text: and

text: Stochastic

text: Optimal

text: Control.

text: Springer,

text: B.

text: Holmstrom

text: and

text: P.

text: Milgrom.

text: Aggregation

text: and

text: linearity

text: in

text: the

text: provision

text: of

text: intertemporal

text: incentives.

text: Econometrica,

text: B.

text: Jullien.

text: Participation

text: constraints

text: in

text: adverse

text: selection

text: models.

text: Journal

text: of

text: Economic

text: Theory,

text: B.

text: Salani´e.

text: The

text: Economics

text: of

text: Contracts.

text: MIT

text: Press,

text: edition,

text: H.

text: Schaettler

text: and

text: J.

text: Sung.

text: The

text: ﬁrst-order

text: approach

text: to

text: the

text: continuous-time

text: principal–agent

text: problem

text: with

text: exponential

text: utility.

text: Journal

text: of

text: Economic

text: Theory,

text: J.

text: Sung.

text: Optimal

text: contracts

text: under

text: adverse

text: selection

text: and

text: moral

text: hazard:

text: a

text: continuous-time

text: ap-

text: proach.

text: Review

text: of

text: Financial

text: Studies,


text: 2 blind approach was intensively investigated [44], where no ad- envelopes using band-pass ﬁlter banks. Ozerov et al. developed ditional information about the target source exists. These blind ﬂexible audio source separation toolbox (FASST), in which source separation (BSS) studies often assume that the target spectra are also split into excitations and ﬁlter parts [29], [36]. sound has certain statistical features such as non-Gaussianity In this paper, we present a novel approach to the single- and independence [5] or sparsity [44]. BSS techniques are channel instrument sound separation problem. In the ﬁrst part useful in some cases; however, such statistical assumptions of this paper, we assume that the instruments are known in cannot be guaranteed in many practical situations, which advance and that their spectral envelopes can be obtained. For eventually causes performance degradation. instance, when audio segments of the instruments are given, To overcome this low performance, informed source sep- we can extract the spectral envelopes from them. The spectral aration (ISS) was widely studied [42]. These studies assume bases of the NMF to approximate the mixture spectrogram situations where side-information about the target sources is are partitioned ahead of the iteration and then constrained to available. Such information includes spectro-temporal charac- resemble the extracted envelopes. The constraint imposition is teristics such as music score [13], [12], [15], partial infor- achieved with the use of generalized Dirichlet prior which has mation such as onset [30], and direct information such as been used in the source separation tasks. In the second part of manually provided annotations [11], [24], [3] and user-guided this paper, we extend the informed approach to the case where audio signal [38]. no additional information is available. In the blind approach, Especially, recent approaches have examined the effect of the spectral envelopes of each basis are calculated through artiﬁcial neural network-based methods on the source sep- LPC, and all envelopes belong to the same group are averaged. aration tasks. While some of the research efforts directly This is because the spectral envelope is determined for each applied the deep learning-based techniques like autoencoder instrument whereas the excitations can differ from other bases as Lim and Lee’s work [26], Osako et al.’s work [27], and that belong to the same group. As the iteration proceeds, the Grais and Plumbley’s work [17], others attempted to enhance average spectral envelopes of each group converge to the true conventional approaches like matrix decomposition [21] and spectral envelopes of the instruments. These two methods are time-frequency mask [20]. based on the source-ﬁlter model with linear predictive coding However, it is still a big issue to reduce the amount of infor- (LPC), but they obtain the envelopes of the spectra (or spectral mation needed for successful separation of the target sound, bases of the NMF) without converting them to the time-domain as the situation where side-information can be provided is signal. The comparative evaluation reveals that the proposed highly limited. Especially in deep learning-based approaches, method outperforms the other conventional methods. a signiﬁcant amount of training data is required for each sound The rest of the paper is organized as follows. Section 2 source. Hence, we focus on reducing the amount of required describes our informed approach method. In Section 3, we information. extend the informed approach to blind approach. Section 4 C. Instrument sound separation shows the experimental results with real recordings. Conclu- Musical instruments are known to show static spectro- sions are presented in Section 5. temporal characteristics and timbre. These characteristics can II. PROPOSED INFORMED APPROACH also be used for the source separation. Especially in cases In this section, we present a detailed description of the where harmonic instruments and drums coexist, their attributes proposed informed source separation method. This section is that appear in the time-frequency representation are easily composed of three subsections that present excitation-ﬁlter distinguishable. Our previous work focused on the spectral model, linear predictive coding, and the proposed NMF-based features of harmonic and percussive sounds [31], and it spectrogram decomposition procedure. was also extended to simultaneously consider the time and A. Excitation-ﬁlter model frequency domain aspects of the instruments [32]. The time domain mixture signal is generated by summing The separation of harmonic instrument sounds is a more individual sources as (cid:88) challenging problem as the differences in the spectral and temporal characteristics are less obvious compared to the I harmonic-percussive source separation. Spiertz and Gnann x = x (1) i presented the basis clustering algorithm as a post-processing i=1 of non-negative matrix factorization (NMF) [39]. Fitzgerald et al. used shift-invariant non-negative tensor factorization [14]. where x denotes the mixture sound, x denotes the sound of i Ozerov and Fevotte focused on the mixing procedure [28]. the i-th instrument, and I denotes the number of instruments. Other studies on harmonic instrument sound separation When this time domain signal is converted into a spectrogram, adopt source-ﬁlter model. Heittola et al. trained bases for it can be similarly represe(cid:88)nted as instruments and used them for separation [18]. Rodriguez- I Serrano et al. also made instrument-dependent models and used them for separation [35]. Klapuri et al.’s work extended X = (cid:88) X(cid:88)i Heittola et al.’s method to separately estimate approximated i=1 (2) spectral envelopes and their corresponding excitations without ≈ I w h k k the pre-training process [22]. But their work fails to precisely ∈ assess spectral envelopes since it roughly approximates the i=1 k Φi

text: blind

text: approach

text: was

text: intensively

text: investigated

text: where

text: no

text: ad-

text: envelopes

text: using

text: band-pass

text: ﬁlter

text: banks.

text: Ozerov

text: et

text: al.

text: developed

text: ditional

text: information

text: about

text: the

text: target

text: source

text: exists.

text: These

text: blind

text: ﬂexible

text: audio

text: source

text: separation

text: toolbox

text: (FASST),

text: in

text: which

text: source

text: separation

text: (BSS)

text: studies

text: often

text: assume

text: that

text: the

text: target

text: spectra

text: are

text: also

text: split

text: into

text: excitations

text: and

text: ﬁlter

text: parts

text: sound

text: has

text: certain

text: statistical

text: features

text: such

text: as

text: non-Gaussianity

text: In

text: this

text: paper,

text: we

text: present

text: a

text: novel

text: approach

text: to

text: the

text: single-

text: and

text: independence

text: or

text: sparsity

text: BSS

text: techniques

text: are

text: channel

text: instrument

text: sound

text: separation

text: problem.

text: In

text: the

text: ﬁrst

text: part

text: useful

text: in

text: some

text: cases;

text: however,

text: such

text: statistical

text: assumptions

text: of

text: this

text: paper,

text: we

text: assume

text: that

text: the

text: instruments

text: are

text: known

text: in

text: cannot

text: be

text: guaranteed

text: in

text: many

text: practical

text: situations,

text: which

text: advance

text: and

text: that

text: their

text: spectral

text: envelopes

text: can

text: be

text: obtained.

text: For

text: eventually

text: causes

text: performance

text: degradation.

text: instance,

text: when

text: audio

text: segments

text: of

text: the

text: instruments

text: are

text: given,

text: To

text: overcome

text: this

text: low

text: performance,

text: informed

text: source

text: sep-

text: we

text: can

text: extract

text: the

text: spectral

text: envelopes

text: from

text: them.

text: The

text: spectral

text: aration

text: (ISS)

text: was

text: widely

text: studied

text: These

text: studies

text: assume

text: bases

text: of

text: the

text: NMF

text: to

text: approximate

text: the

text: mixture

text: spectrogram

text: situations

text: where

text: side-information

text: about

text: the

text: target

text: sources

text: is

text: are

text: partitioned

text: ahead

text: of

text: the

text: iteration

text: and

text: then

text: constrained

text: to

text: available.

text: Such

text: information

text: includes

text: spectro-temporal

text: charac-

text: resemble

text: the

text: extracted

text: envelopes.

text: The

text: constraint

text: imposition

text: is

text: teristics

text: such

text: as

text: music

text: score

text: partial

text: infor-

text: achieved

text: with

text: the

text: use

text: of

text: generalized

text: Dirichlet

text: prior

text: which

text: has

text: mation

text: such

text: as

text: onset

text: and

text: direct

text: information

text: such

text: as

text: been

text: used

text: in

text: the

text: source

text: separation

text: tasks.

text: In

text: the

text: second

text: part

text: of

text: manually

text: provided

text: annotations

text: and

text: user-guided

text: this

text: paper,

text: we

text: extend

text: the

text: informed

text: approach

text: to

text: the

text: case

text: where

text: audio

text: signal

text: no

text: additional

text: information

text: is

text: available.

text: In

text: the

text: blind

text: approach,

text: Especially,

text: recent

text: approaches

text: have

text: examined

text: the

text: effect

text: of

text: the

text: spectral

text: envelopes

text: of

text: each

text: basis

text: are

text: calculated

text: through

text: artiﬁcial

text: neural

text: network-based

text: methods

text: on

text: the

text: source

text: sep-

text: LPC,

text: and

text: all

text: envelopes

text: belong

text: to

text: the

text: same

text: group

text: are

text: averaged.

text: aration

text: tasks.

text: While

text: some

text: of

text: the

text: research

text: efforts

text: directly

text: This

text: is

text: because

text: the

text: spectral

text: envelope

text: is

text: determined

text: for

text: each

text: applied

text: the

text: deep

text: learning-based

text: techniques

text: like

text: autoencoder

text: instrument

text: whereas

text: the

text: excitations

text: can

text: differ

text: from

text: other

text: bases

text: as

text: Lim

text: and

text: Lee’s

text: work

text: Osako

text: et

text: al.’s

text: work

text: and

text: that

text: belong

text: to

text: the

text: same

text: group.

text: As

text: the

text: iteration

text: proceeds,

text: the

text: Grais

text: and

text: Plumbley’s

text: work

text: others

text: attempted

text: to

text: enhance

text: average

text: spectral

text: envelopes

text: of

text: each

text: group

text: converge

text: to

text: the

text: true

text: conventional

text: approaches

text: like

text: matrix

text: decomposition

text: and

text: spectral

text: envelopes

text: of

text: the

text: instruments.

text: These

text: two

text: methods

text: are

text: time-frequency

text: mask

text: based

text: on

text: the

text: source-ﬁlter

text: model

text: with

text: linear

text: predictive

text: coding

text: However,

text: it

text: is

text: still

text: a

text: big

text: issue

text: to

text: reduce

text: the

text: amount

text: of

text: infor-

text: (LPC),

text: but

text: they

text: obtain

text: the

text: envelopes

text: of

text: the

text: spectra

text: (or

text: spectral

text: mation

text: needed

text: for

text: successful

text: separation

text: of

text: the

text: target

text: sound,

text: bases

text: of

text: the

text: NMF)

text: without

text: converting

text: them

text: to

text: the

text: time-domain

text: as

text: the

text: situation

text: where

text: side-information

text: can

text: be

text: provided

text: is

text: signal.

text: The

text: comparative

text: evaluation

text: reveals

text: that

text: the

text: proposed

text: highly

text: limited.

text: Especially

text: in

text: deep

text: learning-based

text: approaches,

text: method

text: outperforms

text: the

text: other

text: conventional

text: methods.

text: a

text: signiﬁcant

text: amount

text: of

text: training

text: data

text: is

text: required

text: for

text: each

text: sound

text: The

text: rest

text: of

text: the

text: paper

text: is

text: organized

text: as

text: follows.

text: Section

text: source.

text: Hence,

text: we

text: focus

text: on

text: reducing

text: the

text: amount

text: of

text: required

text: describes

text: our

text: informed

text: approach

text: method.

text: In

text: Section

text: we

text: information.

text: extend

text: the

text: informed

text: approach

text: to

text: blind

text: approach.

text: Section

text: C.

text: Instrument

text: sound

text: separation

text: shows

text: the

text: experimental

text: results

text: with

text: real

text: recordings.

text: Conclu-

text: Musical

text: instruments

text: are

text: known

text: to

text: show

text: static

text: spectro-

text: sions

text: are

text: presented

text: in

text: Section

text: temporal

text: characteristics

text: and

text: timbre.

text: These

text: characteristics

text: can

text: II.

text: PROPOSED

text: INFORMED

text: APPROACH

text: also

text: be

text: used

text: for

text: the

text: source

text: separation.

text: Especially

text: in

text: cases

text: In

text: this

text: section,

text: we

text: present

text: a

text: detailed

text: description

text: of

text: the

text: where

text: harmonic

text: instruments

text: and

text: drums

text: coexist,

text: their

text: attributes

text: proposed

text: informed

text: source

text: separation

text: method.

text: This

text: section

text: is

text: that

text: appear

text: in

text: the

text: time-frequency

text: representation

text: are

text: easily

text: composed

text: of

text: three

text: subsections

text: that

text: present

text: excitation-ﬁlter

text: distinguishable.

text: Our

text: previous

text: work

text: focused

text: on

text: the

text: spectral

text: model,

text: linear

text: predictive

text: coding,

text: and

text: the

text: proposed

text: NMF-based

text: features

text: of

text: harmonic

text: and

text: percussive

text: sounds

text: and

text: it

text: spectrogram

text: decomposition

text: procedure.

text: was

text: also

text: extended

text: to

text: simultaneously

text: consider

text: the

text: time

text: and

text: A.

text: Excitation-ﬁlter

text: model

text: frequency

text: domain

text: aspects

text: of

text: the

text: instruments

text: The

text: time

text: domain

text: mixture

text: signal

text: is

text: generated

text: by

text: summing

text: The

text: separation

text: of

text: harmonic

text: instrument

text: sounds

text: is

text: a

text: more

text: individual

text: sources

text: as

text: challenging

text: problem

text: as

text: the

text: differences

text: in

text: the

text: spectral

text: and

text: temporal

text: characteristics

text: are

text: less

text: obvious

text: compared

text: to

text: the

text: I

text: harmonic-percussive

text: source

text: separation.

text: Spiertz

text: and

text: Gnann

text: x

text: x

text: i

text: presented

text: the

text: basis

text: clustering

text: algorithm

text: as

text: a

text: post-processing

text: of

text: non-negative

text: matrix

text: factorization

text: (NMF)

text: Fitzgerald

text: et

text: al.

text: used

text: shift-invariant

text: non-negative

text: tensor

text: factorization

text: where

text: x

text: denotes

text: the

text: mixture

text: sound,

text: x

text: denotes

text: the

text: sound

text: of

text: i

text: Ozerov

text: and

text: Fevotte

text: focused

text: on

text: the

text: mixing

text: procedure

text: the

text: i-th

text: instrument,

text: and

text: I

text: denotes

text: the

text: number

text: of

text: instruments.

text: Other

text: studies

text: on

text: harmonic

text: instrument

text: sound

text: separation

text: When

text: this

text: time

text: domain

text: signal

text: is

text: converted

text: into

text: a

text: spectrogram,

text: adopt

text: source-ﬁlter

text: model.

text: Heittola

text: et

text: al.

text: trained

text: bases

text: for

text: it

text: can

text: be

text: similarly

text: as

text: instruments

text: and

text: used

text: them

text: for

text: separation

text: Rodriguez-

text: I

text: Serrano

text: et

text: al.

text: also

text: made

text: instrument-dependent

text: models

text: and

text: used

text: them

text: for

text: separation

text: Klapuri

text: et

text: al.’s

text: work

text: extended

text: X

text: Heittola

text: et

text: al.’s

text: method

text: to

text: separately

text: estimate

text: approximated

text: spectral

text: envelopes

text: and

text: their

text: corresponding

text: excitations

text: without

text: I

text: w

text: h

text: k

text: k

text: the

text: pre-training

text: process

text: But

text: their

text: work

text: fails

text: to

text: precisely

text: assess

text: spectral

text: envelopes

text: since

text: it

text: roughly

text: approximates

text: the

text: k

text: Φi


text: 3 where X denotes the magnitude spectrogram of instrument i ia,ndΦihdedneonteostethteheinkd-etxh sseptecotfrablabseassisthaantdexitpslatiinmeXai,ctaivnadtiwonk, 200 SSppeeccttrruaml envelope k respectively. The spectrogram conversion error is assumed to -20 be small and negligible. For the convenience of description, -40 || || we assume that w = 1 for all k. w and h can be -60 k 1 estimated with the matrix decomposition algorithms such as -80 probabilistic latent semantic analysis (PLSA), probabilistic -100 latent component analysis (PLCA) [37], and NMF [23]. -120 0 500 1000 1500 2000 2500 3000 3500 4000 We also assume that the instrument sounds can be repre- Frequency [Hz] sented using the source-ﬁlter model, which we alternatively (a) address as excitation-ﬁlter model to avoid term collision. 20 The excitation-ﬁlter model has been widely used to analyze Spectrum 0 Spectral envelope the speech production mechanism [34]. According to the -20 excitation-ﬁlter model, the timbre of an instrument is deter- mined by its ﬁlter, whereas the pitch is determined by the -40 excitation signal. Figure 1 (a) and (b) illustrate the spectrum -60 and the corresponding LPC spectral envelope of violin and -80 clarinet, respectively, plotted on a log-scale. Even though the -100 excitation-ﬁlter model is to describe the generation of the -120 0 500 1000 1500 2000 2500 3000 3500 4000 harmonic instrument sound, we similarly extend it to the Frequency [Hz] (b) percussive instruments since they also present difference in the energy distribution of the spectra as shown in Figure 1 -10 (c), (d), and (e). -20 SSppeeccttrruaml envelope As the excitation signal is ﬁltered by the instrument’s -30 resonant structure, a spectral basis (or a spectrum of an -40 instrument, equivalently) w has to be represented as -50 k -60 (cid:12) -70 wk = vi ek (3) -80 -90 0 500 1000 1500 2000 2500 3000 3500 4000 Frequency [Hz] (c) where v is the ﬁlter’s frequency response of instrument i i that can be alternatively referred to as spectral envelope, e -10 is the spectrum of the k-th excitation signal, the operator (cid:12)k -20 SSppeeccttrruaml envelope ∈ denotes the element-wise multiplication, and k Φ . -30 i Note that the above Eq. 3 can be satisﬁed only if a -40 proper source separation is applied. During the ongoing matrix -50 decomposition iteration, the spectral envelopes vary for each k. -60 However, the proposed method focuses on the reverse direction -70 of this theory: Can a group of bases successfully reconstruct -80 the sound of an instrument, if we can make the basis envelopes -900 500 1000 1500 2000 2500 3000 3500 4000 Frequency [Hz] equal to the true envelope of the instrument? Since the (d) proposed method requires the estimation of the true spectral envelopes of the instruments and the basis envelopes, the -10 Spectrum representative spectral envelope extraction method is presented -20 Spectral envelope in the next subsection. -30 -40 B. Linear predictive coding -50 The spectral envelope can be obtained using LPC, which -60 assumes that the ﬁlter can be approximated by a ﬁnite number -70 of poles. In this subsection, we describe how we can obtain -80 LPC coefﬁcients and how they can be extensively applied to -900 500 1000 1500 2000 2500 3000 3500 4000 Frequency [Hz] the spectral bases of the NMF algorithm. (e) LPC aims to calculate the all-pole inﬁnite impulse response Fig. 1: Spectrum and corresponding spectral envelope com- (IIR) ﬁlter coefﬁcients a = (a , a , ... , a )T that best predict 1 2 M puted via linear prediction of (a) violin, (b) clarinet (c) hi-hat the signal value minimizing the energy of the error signal, drum, (d) snare drum, and (e) bass drum. represented as ]elacs Bd[ edutingaM ]elacs Bd[ edutingaM ]elacs Bd[ edutingaM ]elacs Bd[ edutingaM ]elacs Bd[ edutingaM ##LTFigure## ##LTFigure## ##LTFigure## ##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## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##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: where

text: X

text: denotes

text: the

text: magnitude

text: spectrogram

text: of

text: instrument

text: i

text: ia,ndΦihdedneonteostethteheinkd-etxh

text: SSppeeccttrruaml

text: envelope

text: k

text: respectively.

text: The

text: spectrogram

text: conversion

text: error

text: is

text: assumed

text: to

text: be

text: small

text: and

text: negligible.

text: For

text: the

text: convenience

text: of

text: description,

text: we

text: assume

text: that

text: w

text: for

text: all

text: k.

text: w

text: and

text: h

text: can

text: be

text: k

text: estimated

text: with

text: the

text: matrix

text: decomposition

text: algorithms

text: such

text: as

text: probabilistic

text: latent

text: semantic

text: analysis

text: (PLSA),

text: probabilistic

text: latent

text: component

text: analysis

text: (PLCA)

text: and

text: NMF

text: We

text: also

text: assume

text: that

text: the

text: instrument

text: sounds

text: can

text: be

text: repre-

text: Frequency

text: [Hz]

text: sented

text: using

text: the

text: source-ﬁlter

text: model,

text: which

text: we

text: alternatively

text: (a)

text: address

text: as

text: excitation-ﬁlter

text: model

text: to

text: avoid

text: term

text: collision.

text: The

text: excitation-ﬁlter

text: model

text: has

text: been

text: widely

text: used

text: to

text: analyze

text: Spectrum

text: Spectral

text: envelope

text: the

text: speech

text: production

text: mechanism

text: According

text: to

text: the

text: excitation-ﬁlter

text: model,

text: the

text: timbre

text: of

text: an

text: instrument

text: is

text: deter-

text: mined

text: by

text: its

text: ﬁlter,

text: whereas

text: the

text: pitch

text: is

text: determined

text: by

text: the

text: excitation

text: signal.

text: Figure

text: (a)

text: and

text: (b)

text: illustrate

text: the

text: spectrum

text: and

text: the

text: corresponding

text: LPC

text: spectral

text: envelope

text: of

text: violin

text: and

text: clarinet,

text: respectively,

text: plotted

text: on

text: a

text: log-scale.

text: Even

text: though

text: the

text: excitation-ﬁlter

text: model

text: is

text: to

text: describe

text: the

text: generation

text: of

text: the

text: harmonic

text: instrument

text: sound,

text: we

text: similarly

text: extend

text: it

text: to

text: the

text: Frequency

text: [Hz]

text: (b)

text: percussive

text: instruments

text: since

text: they

text: also

text: present

text: difference

text: in

text: the

text: energy

text: distribution

text: of

text: the

text: spectra

text: as

text: shown

text: in

text: Figure

text: (c),

text: (d),

text: and

text: (e).

text: SSppeeccttrruaml

text: envelope

text: As

text: the

text: excitation

text: signal

text: is

text: ﬁltered

text: by

text: the

text: instrument’s

text: resonant

text: structure,

text: a

text: spectral

text: basis

text: (or

text: a

text: spectrum

text: of

text: an

text: instrument,

text: equivalently)

text: w

text: has

text: to

text: be

text: represented

text: as

text: k

text: wk

text: vi

text: ek

text: Frequency

text: [Hz]

text: (c)

text: where

text: v

text: is

text: the

text: ﬁlter’s

text: frequency

text: response

text: of

text: instrument

text: i

text: i

text: that

text: can

text: be

text: alternatively

text: referred

text: to

text: as

text: spectral

text: envelope,

text: e

text: is

text: the

text: spectrum

text: of

text: the

text: k-th

text: excitation

text: signal,

text: the

text: operator

text: SSppeeccttrruaml

text: envelope

text: denotes

text: the

text: element-wise

text: multiplication,

text: and

text: k

text: Φ

text: i

text: Note

text: that

text: the

text: above

text: Eq.

text: can

text: be

text: satisﬁed

text: only

text: if

text: a

text: proper

text: source

text: separation

text: is

text: applied.

text: During

text: the

text: ongoing

text: matrix

text: decomposition

text: iteration,

text: the

text: spectral

text: envelopes

text: vary

text: for

text: each

text: k.

text: However,

text: the

text: proposed

text: method

text: focuses

text: on

text: the

text: reverse

text: direction

text: of

text: this

text: theory:

text: Can

text: a

text: group

text: of

text: bases

text: successfully

text: reconstruct

text: the

text: sound

text: of

text: an

text: instrument,

text: if

text: we

text: can

text: make

text: the

text: basis

text: envelopes

text: Frequency

text: [Hz]

text: equal

text: to

text: the

text: true

text: envelope

text: of

text: the

text: instrument?

text: Since

text: the

text: (d)

text: proposed

text: method

text: requires

text: the

text: estimation

text: of

text: the

text: true

text: spectral

text: envelopes

text: of

text: the

text: instruments

text: and

text: the

text: basis

text: envelopes,

text: the

text: Spectrum

text: representative

text: spectral

text: envelope

text: extraction

text: method

text: is

text: presented

text: Spectral

text: envelope

text: in

text: the

text: next

text: subsection.

text: B.

text: Linear

text: predictive

text: coding

text: The

text: spectral

text: envelope

text: can

text: be

text: obtained

text: using

text: LPC,

text: which

text: assumes

text: that

text: the

text: ﬁlter

text: can

text: be

text: approximated

text: by

text: a

text: ﬁnite

text: number

text: of

text: poles.

text: In

text: this

text: subsection,

text: we

text: describe

text: how

text: we

text: can

text: obtain

text: LPC

text: coefﬁcients

text: and

text: how

text: they

text: can

text: be

text: extensively

text: applied

text: to

text: Frequency

text: [Hz]

text: the

text: spectral

text: bases

text: of

text: the

text: NMF

text: algorithm.

text: (e)

text: LPC

text: aims

text: to

text: calculate

text: the

text: all-pole

text: inﬁnite

text: impulse

text: response

text: Fig.

text: Spectrum

text: and

text: corresponding

text: spectral

text: envelope

text: com-

text: (IIR)

text: ﬁlter

text: coefﬁcients

text: a

text: (a

text: a

text: a

text: )T

text: that

text: best

text: predict

text: M

text: puted

text: via

text: linear

text: prediction

text: of

text: (a)

text: violin,

text: (b)

text: clarinet

text: (c)

text: hi-hat

text: the

text: signal

text: value

text: minimizing

text: the

text: energy

text: of

text: the

text: error

text: signal,

text: drum,

text: (d)

text: snare

text: drum,

text: and

text: (e)

text: bass

text: drum.

text: represented

text: as

text: ]elacs

text: Bd[

text: edutingaM

text: ]elacs

text: Bd[

text: edutingaM

text: ]elacs

text: Bd[

text: edutingaM

text: ]elacs

text: Bd[

text: edutingaM

text: ]elacs

text: Bd[

text: edutingaM

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

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##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 14 Vaˆn Anh Huynh-Thu and Guido Sanguinetti another gene (or, indeed, itself) at a later time point (see Figure 4 for an example). In this way, the DAG condition is automatically satisﬁed, while at the same time biologically plausible features such as feedback mechanisms can be easily incorpo- rated. In most cases, the dynamic structure of a DBN is chosen such that edges are only present between nodes at consecutive time points, with time-independent tran- sition probabilities: this assumption of a homogeneous, ﬁrst order Markov process is a plausible approximation in many cases, and, particularly when the conditional distributions are chosen to be Gaussian, it allows the modeller to leverage a rich literature on signal processing in autoregressive models. dynamic_bayesian_network-eps-converted-to.pdf Fig. 4 Example of a Dynamic Bayesian Network with four nodes: static representation (with cy- cles) on the left, and unrolled dynamic representation on the right. DBNs are extremely popular in the GRN context, and are implemented in sev- eral software tools (see [37] for a recent review). Structure learning within DBNs is easier than in standard Bayesian Networks, since the DAG condition is automati- cally satisﬁed, however it still remains computationally demanding, particularly in a Bayesian setting. From the modelling point of view, most implementations assume a linear dynamic model, which is clearly a limitation. Extensions exist which include nonlinear mappings between time points [38, 39] or that relax the time-homogeneity assumption [40], however these incur generally higher computational costs and/or place strong restrictions on the class of nonlinear functions allowed. Most often, ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Vaˆn

label: author

text: Anh

text: Huynh-Thu

text: and

text: Guido

text: Sanguinetti

text: another

text: gene

text: (or,

text: indeed,

text: itself)

text: at

text: a

text: later

text: time

text: point

text: (see

text: Figure

text: for

text: an

text: example).

text: In

text: this

text: way,

text: the

text: DAG

text: condition

text: is

text: automatically

text: satisﬁed,

text: while

text: at

text: the

text: same

text: time

text: biologically

text: plausible

text: features

text: such

text: as

text: feedback

text: mechanisms

text: can

text: be

text: easily

text: incorpo-

text: rated.

text: In

text: most

text: cases,

text: the

text: dynamic

text: structure

text: of

text: a

text: DBN

text: is

text: chosen

text: such

text: that

text: edges

text: are

text: only

text: present

text: between

text: nodes

text: at

text: consecutive

text: time

text: points,

text: with

text: time-independent

text: tran-

text: sition

text: probabilities:

text: this

text: assumption

text: of

text: a

text: homogeneous,

text: ﬁrst

text: order

text: Markov

text: process

text: is

text: a

text: plausible

text: approximation

text: in

text: many

text: cases,

text: and,

text: particularly

text: when

text: the

text: conditional

text: distributions

text: are

text: chosen

text: to

text: be

text: Gaussian,

text: it

text: allows

text: the

text: modeller

text: to

text: leverage

text: a

text: rich

text: literature

text: on

text: signal

text: processing

text: in

text: autoregressive

text: models.

text: Fig.

text: Example

text: of

text: a

text: Dynamic

text: Bayesian

text: Network

text: with

text: four

text: nodes:

text: static

text: representation

text: (with

text: cy-

text: cles)

text: on

text: the

text: left,

text: and

text: unrolled

text: dynamic

text: representation

text: on

text: the

text: right.

text: DBNs

text: are

text: extremely

text: popular

text: in

text: the

text: GRN

text: context,

text: and

text: are

text: implemented

text: in

text: sev-

text: eral

text: software

text: tools

text: (see

text: for

text: a

text: recent

text: review).

text: Structure

text: learning

text: within

text: DBNs

text: is

text: easier

text: than

text: in

text: standard

text: Bayesian

text: Networks,

text: since

text: the

text: DAG

text: condition

text: is

text: automati-

text: cally

text: satisﬁed,

text: however

text: it

text: still

text: remains

text: computationally

text: demanding,

text: particularly

text: in

text: a

text: Bayesian

text: setting.

text: From

text: the

text: modelling

text: point

text: of

text: view,

text: most

text: implementations

text: assume

text: a

text: linear

text: dynamic

text: model,

text: which

text: is

text: clearly

text: a

text: limitation.

text: Extensions

text: exist

text: which

text: include

text: nonlinear

text: mappings

text: between

text: time

text: points

text: or

text: that

text: relax

text: the

text: time-homogeneity

text: assumption

text: however

text: these

text: incur

text: generally

text: higher

text: computational

text: costs

text: and/or

text: place

text: strong

text: restrictions

text: on

text: the

text: class

text: of

text: nonlinear

text: functions

text: allowed.

text: Most

text: often,

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Gene regulatory network inference: an introductory survey 17 running challenge on GRN inference, providing both a stimulus and a benchmark for methodological development. Another direction has been the use of synthetic gene circuits as a benchmark for network reconstruction algorithms. The most well known example of this is probably the IRMA network [57], a synthetic network of 5 genes engineered within living yeast cells. While this synthetic biology approach is appealingly close to biological reality, so far technological limitations mean that such an approach has been limited to small networks containing a handful of genes. Having decided on a benchmark data generation procedure, the next step in eval- uating a GRN inference algorithm is the choice of a suitable metric. Naively, one may consider thresholding the algorithm’s outputs and reporting an average accu- racy in detecting presence or absence of edges. This strategy is however ﬂawed since GRNs are typically very sparse, so that an algorithm constantly predicting the absence of edges would potentially achieve high accuracy. A better strategy is to consider the fraction of true positive calls relative to all positives (sensitivity or recall) and the fraction of true positive calls out of all positive calls (precision or positive predictive value). Naturally, precision and recall depend on the threshold chosen: with a very lax cutoff, we will likely recall many true positives (high recall), at the cost of many false positives (low precision). To elucidate the effectiveness of an algorithm in handling the precision/recall trade-off, a visually appealing strategy is the use of precision-recall curves. These are constructed as follows: given the output of a GRN inference algorithm as a weighted network, one starts by thresholding at a very strict (high) threshold, where precision is expected to be high and recall will be low. Decreasing the threshold, one will progressively lower precision by introducing some false positives, but also increase recall, until at zero threshold (fully connected network) recall is 1 and precision is the fraction of actual edges over possible edges (positives fraction). This procedure results in a curve in precision-recall space (see Figure 5, right panel, for an illustration) indicative of the overall performance of the inference algorithm: a random predictor will always have an expected precision equal to the positives fraction, while an ideal algorithm will have precision 1 for any recall between 0 and 1. These observations justify the use of the area under the curve as a global metric of performance for an algorithm, a choice almost universally adopted in evaluating GRN inference methods. Alternatively, a receiver operating characteristic (ROC) curve may be used to evaluate a weighted network against a gold standard. A ROC curve plots the re- call versus the false positive rate (the fraction of false positive calls relative to all negatives) for different thresholds on the weights, again progressively lowering the threshold. Precision-recall curves are however more suited than ROC curves for problems where the number of negatives is much higher than the number of posi- tives, which is typically the case of GRNs [58]. 8 Software tools Most of the methods described above have been implemented in software tools which have been made freely available to the community. As it is perhaps to be ex-

text: Gene

label: title

text: regulatory

text: network

text: inference:

text: an

text: introductory

text: survey

text: running

text: challenge

text: on

text: GRN

text: inference,

text: providing

text: both

text: a

text: stimulus

text: and

text: a

text: benchmark

text: for

text: methodological

text: development.

text: Another

text: direction

text: has

text: been

text: the

text: use

text: of

text: synthetic

text: gene

text: circuits

text: as

text: a

text: benchmark

text: for

text: network

text: reconstruction

text: algorithms.

text: The

text: most

text: well

text: known

text: example

text: of

text: this

text: is

text: probably

text: the

text: IRMA

text: network

text: a

text: synthetic

text: network

text: of

text: genes

text: engineered

text: within

text: living

text: yeast

text: cells.

text: While

text: this

text: synthetic

text: biology

text: approach

text: is

text: appealingly

text: close

text: to

text: biological

text: reality,

text: so

text: far

text: technological

text: limitations

text: mean

text: that

text: such

text: an

text: approach

text: has

text: been

text: limited

text: to

text: small

text: networks

text: containing

text: a

text: handful

text: of

text: genes.

text: Having

text: decided

text: on

text: a

text: benchmark

text: data

text: generation

text: procedure,

text: the

text: next

text: step

text: in

text: eval-

text: uating

text: a

text: GRN

text: inference

text: algorithm

text: is

text: the

text: choice

text: of

text: a

text: suitable

text: metric.

text: Naively,

text: one

text: may

text: consider

text: thresholding

text: the

text: algorithm’s

text: outputs

text: and

text: reporting

text: an

text: average

text: accu-

text: racy

text: in

text: detecting

text: presence

text: or

text: absence

text: of

text: edges.

text: This

text: strategy

text: is

text: however

text: ﬂawed

text: since

text: GRNs

text: are

text: typically

text: very

text: sparse,

text: so

text: that

text: an

text: algorithm

text: constantly

text: predicting

text: the

text: absence

text: of

text: edges

text: would

text: potentially

text: achieve

text: high

text: accuracy.

text: A

text: better

text: strategy

text: is

text: to

text: consider

text: the

text: fraction

text: of

text: true

text: positive

text: calls

text: relative

text: to

text: all

text: positives

text: (sensitivity

text: or

text: recall)

text: and

text: the

text: fraction

text: of

text: true

text: positive

text: calls

text: out

text: of

text: all

text: positive

text: calls

text: (precision

text: or

text: positive

text: predictive

text: value).

text: Naturally,

text: precision

text: and

text: recall

text: depend

text: on

text: the

text: threshold

text: chosen:

text: with

text: a

text: very

text: lax

text: cutoff,

text: we

text: will

text: likely

text: recall

text: many

text: true

text: positives

text: (high

text: recall),

text: at

text: the

text: cost

text: of

text: many

text: false

text: positives

text: (low

text: precision).

text: To

text: elucidate

text: the

text: effectiveness

text: of

text: an

text: algorithm

text: in

text: handling

text: the

text: precision/recall

text: trade-off,

text: a

text: visually

text: appealing

text: strategy

text: is

text: the

text: use

text: of

text: precision-recall

text: curves.

text: These

text: are

text: constructed

text: as

text: follows:

text: given

text: the

text: output

text: of

text: a

text: GRN

text: inference

text: algorithm

text: as

text: a

text: weighted

text: network,

text: one

text: starts

text: by

text: thresholding

text: at

text: a

text: very

text: strict

text: (high)

text: threshold,

text: where

text: precision

text: is

text: expected

text: to

text: be

text: high

text: and

text: recall

text: will

text: be

text: low.

text: Decreasing

text: the

text: threshold,

text: one

text: will

text: progressively

text: lower

text: precision

text: by

text: introducing

text: some

text: false

text: positives,

text: but

text: also

text: increase

text: recall,

text: until

text: at

text: zero

text: threshold

text: (fully

text: connected

text: network)

text: recall

text: is

text: and

text: precision

text: is

text: the

text: fraction

text: of

text: actual

text: edges

text: over

text: possible

text: edges

text: (positives

text: fraction).

text: This

text: procedure

text: results

text: in

text: a

text: curve

text: in

text: precision-recall

text: space

text: (see

text: Figure

text: right

text: panel,

text: for

text: an

text: illustration)

text: indicative

text: of

text: the

text: overall

text: performance

text: of

text: the

text: inference

text: algorithm:

text: a

text: random

text: predictor

text: will

text: always

text: have

text: an

text: expected

text: precision

text: equal

text: to

text: the

text: positives

text: fraction,

text: while

text: an

text: ideal

text: algorithm

text: will

text: have

text: precision

text: for

text: any

text: recall

text: between

text: and

text: These

text: observations

text: justify

text: the

text: use

text: of

text: the

text: area

text: under

text: the

text: curve

text: as

text: a

text: global

text: metric

text: of

text: performance

text: for

text: an

text: algorithm,

text: a

text: choice

text: almost

text: universally

text: adopted

text: in

text: evaluating

text: GRN

text: inference

text: methods.

text: Alternatively,

text: a

text: receiver

text: operating

text: characteristic

text: (ROC)

text: curve

text: may

text: be

text: used

text: to

text: evaluate

text: a

text: weighted

text: network

text: against

text: a

text: gold

text: standard.

text: A

text: ROC

text: curve

text: plots

text: the

text: re-

text: call

text: versus

text: the

text: false

text: positive

text: rate

text: (the

text: fraction

text: of

text: false

text: positive

text: calls

text: relative

text: to

text: all

text: negatives)

text: for

text: different

text: thresholds

text: on

text: the

text: weights,

text: again

text: progressively

text: lowering

text: the

text: threshold.

text: Precision-recall

text: curves

text: are

text: however

text: more

text: suited

text: than

text: ROC

text: curves

text: for

text: problems

text: where

text: the

text: number

text: of

text: negatives

text: is

text: much

text: higher

text: than

text: the

text: number

text: of

text: posi-

text: tives,

text: which

text: is

text: typically

text: the

text: case

text: of

text: GRNs

text: Software

text: tools

text: Most

text: of

text: the

text: methods

text: described

text: above

text: have

text: been

text: implemented

text: in

text: software

text: tools

text: which

text: have

text: been

text: made

text: freely

text: available

text: to

text: the

text: community.

text: As

text: it

text: is

text: perhaps

text: to

text: be

text: ex-


text: Gene regulatory network inference: an introductory survey 5 followed by sequencing (ChIP-seq), has been instrumental in obtaining in vivo map- pings of possible regulatory relationships [18]. 2 Introduction: the mathematical formulation In the previous section, we have given a condensed tour of the fundamental bio- logical problem addressed in this book. We have seen that interactions between gene products are the fundamental processes underpinning the cell’s ability to modulate gene expression. High-throughput measuring techniques paved the way to the use of computational statistics techniques to reconstruct statistically such interactions, a process sometimes called reverse engineering. In this section we introduce some of the fundamental mathematical concepts common to all methods for reverse engi- neering GRNs, see e.g. [19] for a more comprehensive review of these concepts. Deﬁnition 1 (Network). A (directed) network or graph is a pair (V,E) where V is a ﬁnite set of vertices (or nodes) and E is a set of edges (or arcs) connecting the vertices. If I is a set indexing the nodes, the set of edges is a subset of the ⊂ × Cartesian product E I I , with element (ij) indicating the presence of an edge between node i and node j. An undirected network is a network where the edge set is symmetric under swapping the indices of the nodes, i.e. whenever edge (ij) exists also edge (ji) exists. Within the GRN context, network nodes universally represent the expression level of genes. Edges are intuitively linked to associations between genes, but the precise meaning of an edge depends on the mathematical model of the system. Networks are abstract representations of systems, and per se do not have a semantic interpre- tation that could link the network to node behaviours, e.g. their collective dynamics. Nevertheless, the structure of a network (the topology) can provide an intuitively appealing visualisation of the system, and often be informative in itself. Informally, the aim of a network abstraction is to condense in a simple representation the com- plexity of interactions underpinning gene expression, see Figure 1 for a cartoon representation. One of the most important quantities in this regard is the degree of a node, i.e. the number of edges that are attached to the node, and the degree distri- bution of the network, i.e. the empirical distribution of degrees across all nodes in the network. Degree distributions often encode intuitively interpretable properties of networks such as the presence of hubs or the ability to reach rapidly any node from any starting node, and in many cases they can be related to distinct stochastic mechanisms by which the network may arise. In the case of directed networks, one may further distinguish between in-degree (also called fan-in), the number of edges terminating at a node, and out-degree (also called fan-out), the number of edges starting at a node. Finally, in many cases the bare topological description is insufﬁcient in capturing aspects of interest, such as the different importances of different edges. To obviate this problem, one can consider weighted networks, where each edge is associated with a real number, its weight. We will see that in most cases reconstructed net- works, the topic of this book, arise naturally as weighted networks, where the weight is intuitively associated with the support that the data offers for the existence of an

text: Gene

text: regulatory

text: network

text: inference:

text: an

text: introductory

text: survey

text: followed

text: by

text: sequencing

text: (ChIP-seq),

text: has

text: been

text: instrumental

text: in

text: obtaining

text: in

text: vivo

text: map-

text: pings

text: of

text: possible

text: regulatory

text: relationships

text: Introduction:

text: the

text: mathematical

text: formulation

text: In

text: the

text: previous

text: section,

text: we

text: have

text: given

text: a

text: condensed

text: tour

text: of

text: the

text: fundamental

text: bio-

text: logical

text: problem

text: addressed

text: in

text: this

text: book.

text: We

text: have

text: seen

text: that

text: interactions

text: between

text: gene

text: products

text: are

text: the

text: fundamental

text: processes

text: underpinning

text: the

text: cell’s

text: ability

text: to

text: modulate

text: gene

text: expression.

text: High-throughput

text: measuring

text: techniques

text: paved

text: the

text: way

text: to

text: the

text: use

text: of

text: computational

text: statistics

text: techniques

text: to

text: reconstruct

text: statistically

text: such

text: interactions,

text: a

text: process

text: sometimes

text: called

text: reverse

text: engineering.

text: In

text: this

text: section

text: we

text: introduce

text: some

text: of

text: the

text: fundamental

text: mathematical

text: concepts

text: common

text: to

text: all

text: methods

text: for

text: reverse

text: engi-

text: neering

text: GRNs,

text: see

text: e.g.

text: for

text: a

text: more

text: comprehensive

text: review

text: of

text: these

text: concepts.

text: Deﬁnition

text: (Network).

text: A

text: (directed)

text: network

text: or

text: graph

text: is

text: a

text: pair

text: (V,E)

text: where

text: V

text: is

text: a

text: ﬁnite

text: set

text: of

text: vertices

text: (or

text: nodes)

text: and

text: E

text: is

text: a

text: set

text: of

text: edges

text: (or

text: arcs)

text: connecting

text: the

text: vertices.

text: If

text: I

text: is

text: a

text: set

text: indexing

text: the

text: nodes,

text: the

text: set

text: of

text: edges

text: is

text: a

text: subset

text: of

text: the

text: Cartesian

text: product

text: E

text: I

text: I

text: with

text: element

text: (ij)

text: indicating

text: the

text: presence

text: of

text: an

text: edge

text: between

text: node

text: i

text: and

text: node

text: j.

text: An

text: undirected

text: network

text: is

text: a

text: network

text: where

text: the

text: edge

text: set

text: is

text: symmetric

text: under

text: swapping

text: the

text: indices

text: of

text: the

text: nodes,

text: i.e.

text: whenever

text: edge

text: (ij)

text: exists

text: also

text: edge

text: (ji)

text: exists.

text: Within

text: the

text: GRN

text: context,

text: network

text: nodes

text: universally

text: represent

text: the

text: expression

text: level

text: of

text: genes.

text: Edges

text: are

text: intuitively

text: linked

text: to

text: associations

text: between

text: genes,

text: but

text: the

text: precise

text: meaning

text: of

text: an

text: edge

text: depends

text: on

text: the

text: mathematical

text: model

text: of

text: the

text: system.

text: Networks

text: are

text: abstract

text: representations

text: of

text: systems,

text: and

text: per

text: se

text: do

text: not

text: have

text: a

text: semantic

text: interpre-

text: tation

text: that

text: could

text: link

text: the

text: network

text: to

text: node

text: behaviours,

text: e.g.

text: their

text: collective

text: dynamics.

text: Nevertheless,

text: the

text: structure

text: of

text: a

text: network

text: (the

text: topology)

text: can

text: provide

text: an

text: intuitively

text: appealing

text: visualisation

text: of

text: the

text: system,

text: and

text: often

text: be

text: informative

text: in

text: itself.

text: Informally,

text: the

text: aim

text: of

text: a

text: network

text: abstraction

text: is

text: to

text: condense

text: in

text: a

text: simple

text: representation

text: the

text: com-

text: plexity

text: of

text: interactions

text: underpinning

text: gene

text: expression,

text: see

text: Figure

text: for

text: a

text: cartoon

text: representation.

text: One

text: of

text: the

text: most

text: important

text: quantities

text: in

text: this

text: regard

text: is

text: the

text: degree

text: of

text: a

text: node,

text: i.e.

text: the

text: number

text: of

text: edges

text: that

text: are

text: attached

text: to

text: the

text: node,

text: and

text: the

text: degree

text: distri-

text: bution

text: of

text: the

text: network,

text: i.e.

text: the

text: empirical

text: distribution

text: of

text: degrees

text: across

text: all

text: nodes

text: in

text: the

text: network.

text: Degree

text: distributions

text: often

text: encode

text: intuitively

text: interpretable

text: properties

text: of

text: networks

text: such

text: as

text: the

text: presence

text: of

text: hubs

text: or

text: the

text: ability

text: to

text: reach

text: rapidly

text: any

text: node

text: from

text: any

text: starting

text: node,

text: and

text: in

text: many

text: cases

text: they

text: can

text: be

text: related

text: to

text: distinct

text: stochastic

text: mechanisms

text: by

text: which

text: the

text: network

text: may

text: arise.

text: In

text: the

text: case

text: of

text: directed

text: networks,

text: one

text: may

text: further

text: distinguish

text: between

text: in-degree

text: (also

text: called

text: fan-in),

text: the

text: number

text: of

text: edges

text: terminating

text: at

text: a

text: node,

text: and

text: out-degree

text: (also

text: called

text: fan-out),

text: the

text: number

text: of

text: edges

text: starting

text: at

text: a

text: node.

text: Finally,

text: in

text: many

text: cases

text: the

text: bare

text: topological

text: description

text: is

text: insufﬁcient

text: in

text: capturing

text: aspects

text: of

text: interest,

text: such

text: as

text: the

text: different

text: importances

text: of

text: different

text: edges.

text: To

text: obviate

text: this

text: problem,

text: one

text: can

text: consider

text: weighted

text: networks,

text: where

text: each

text: edge

text: is

text: associated

text: with

text: a

text: real

text: number,

text: its

text: weight.

text: We

text: will

text: see

text: that

text: in

text: most

text: cases

text: reconstructed

text: net-

text: works,

text: the

text: topic

text: of

text: this

text: book,

text: arise

text: naturally

text: as

text: weighted

text: networks,

text: where

text: the

text: weight

text: is

text: intuitively

text: associated

text: with

text: the

text: support

text: that

text: the

text: data

text: offers

text: for

text: the

text: existence

text: of

text: an


text: (cid:104) (cid:105) TABLE II: The maximal values δφ¯2 , the oscillation amplitude of the inﬂaton ﬁeld φ˜ (x ), and f 0 f (cid:104) (cid:105) the ratio of them ( δφ¯2 /φ˜2(x )) in the metric and Palatini formalisms for diﬀerent ξ. f 0 f (cid:104) (cid:105) (cid:104) (cid:105) δφ¯2 /M2 φ˜ (x )/M δφ¯2 /φ˜2(x ) f PL 0 f PL f 0 f ξ Palatini Metric Palatini Metric Palatini Metric × − × − × − × − 0 1.460 10 7 1.460 10 7 1.35 10 3 1.35 10 3 0.08 0.08 × − × − × − × − -1 1.454 10 7 1.451 10 7 1.30 10 3 1.25 10 3 0.09 0.09 × − × − × − × − -50 1.403 10 7 7.642 10 8 1.04 10 3 3.67 10 4 0.13 0.56 × − × − × − × − -200 1.414 10 7 1.709 10 6 8.56 10 4 9.50 10 4 0.19 1.88 in the metric formalism and R − 1 R (cid:39) − R ω = ξa2 ˆ a2 ξαa2 (47) 2 6 in the Palatini formalism. Thus, in the metric formalism the perturbation term 1 d2a is a dx2 | | magniﬁed 6 ξ times, suggesting that the decrease of ω is lower than ω with the increase 2 1 | | R | | of ξ . In the Palatini formalism, the ξa2 ˆ term is also ampliﬁed with the increase of ξ but it is much less than that in the metric formalism. In Figs. 2, 3, and 4, the evolutions of ω and ω with x are plotted with three diﬀerent 1 2 − − − values of ξ: ξ = 1, 50 and 200. We ﬁnd that the oscillating period of the scalar ﬁeld | | increases with the increase of ξ , and for a given ξ , it is shorter in the Palatini formalism than in the metric formalism, which is a result of the fact, as is shown in Tab. (I), that the | | values of φ (t ) at the beginning of the preheating decrease with the increasing of ξ and this 0 i decrease is faster in metric formalism than in the Palatini one. Furthermore, one can see that in the Palatini formalism the amplitude of ω is always larger than that of ω although 1 2 | | the decrease of ω is slightly lower than that of ω with the increase of ξ . While in the 2 1 | | metric formalism with the increase of ξ the amplitude of ω will become larger than that 2 of ω at the initial stage of preheating since the signiﬁcant magniﬁcation on ω arises from 1 2 the non-minimal coupling, and the domination duration of the ω term becomes longer with 2 14 ##LTLine## ##LTLine## ##LTLine## ##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: TABLE

text: II:

text: The

text: maximal

text: values

text: δφ¯2

text: the

text: oscillation

text: amplitude

text: of

text: the

text: inﬂaton

text: ﬁeld

text: φ˜

text: (x

text: and

text: f

text: f

text: the

text: ratio

text: of

text: them

text: δφ¯2

text: in

text: the

text: metric

text: and

text: Palatini

text: formalisms

text: for

text: diﬀerent

text: ξ.

text: f

text: f

label: table

text: δφ¯2

text: φ˜

text: (x

text: )/M

text: δφ¯2

text: f

text: PL

text: f

text: PL

text: f

text: f

text: ξ

text: Palatini

text: Metric

text: Palatini

text: Metric

text: Palatini

text: Metric

text: in

text: the

text: metric

text: formalism

text: and

text: R

text: R

text: R

text: ω

text: ˆ

text: ξαa2

text: in

text: the

text: Palatini

text: formalism.

text: Thus,

text: in

text: the

text: metric

text: formalism

text: the

text: perturbation

text: term

text: is

text: a

text: magniﬁed

text: ξ

text: times,

text: suggesting

text: that

text: the

text: decrease

text: of

text: ω

text: is

text: lower

text: than

text: ω

text: with

text: the

text: increase

text: R

text: of

text: ξ

text: In

text: the

text: Palatini

text: formalism,

text: the

text: ˆ

text: term

text: is

text: also

text: ampliﬁed

text: with

text: the

text: increase

text: of

text: ξ

text: but

text: it

text: is

text: much

text: less

text: than

text: that

text: in

text: the

text: metric

text: formalism.

text: In

text: Figs.

text: and

text: the

text: evolutions

text: of

text: ω

text: and

text: ω

text: with

text: x

text: are

text: plotted

text: with

text: three

text: diﬀerent

text: values

text: of

text: ξ:

text: ξ

text: and

text: We

text: ﬁnd

text: that

text: the

text: oscillating

text: period

text: of

text: the

text: scalar

text: ﬁeld

text: increases

text: with

text: the

text: increase

text: of

text: ξ

text: and

text: for

text: a

text: given

text: ξ

text: it

text: is

text: shorter

text: in

text: the

text: Palatini

text: formalism

text: than

text: in

text: the

text: metric

text: formalism,

text: which

text: is

text: a

text: result

text: of

text: the

text: fact,

text: as

text: is

text: shown

text: in

text: Tab.

text: (I),

text: that

text: the

text: values

text: of

text: φ

text: (t

text: at

text: the

text: beginning

text: of

text: the

text: preheating

text: decrease

text: with

text: the

text: increasing

text: of

text: ξ

text: and

text: this

text: i

text: decrease

text: is

text: faster

text: in

text: metric

text: formalism

text: than

text: in

text: the

text: Palatini

text: one.

text: Furthermore,

text: one

text: can

text: see

text: that

text: in

text: the

text: Palatini

text: formalism

text: the

text: amplitude

text: of

text: ω

text: is

text: always

text: larger

text: than

text: that

text: of

text: ω

text: although

text: the

text: decrease

text: of

text: ω

text: is

text: slightly

text: lower

text: than

text: that

text: of

text: ω

text: with

text: the

text: increase

text: of

text: ξ

text: While

text: in

text: the

text: metric

text: formalism

text: with

text: the

text: increase

text: of

text: ξ

text: the

text: amplitude

text: of

text: ω

text: will

text: become

text: larger

text: than

text: that

text: of

text: ω

text: at

text: the

text: initial

text: stage

text: of

text: preheating

text: since

text: the

text: signiﬁcant

text: magniﬁcation

text: on

text: ω

text: arises

text: from

text: the

text: non-minimal

text: coupling,

text: and

text: the

text: domination

text: duration

text: of

text: the

text: ω

text: term

text: becomes

text: longer

text: with

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##