text: 3 scalar ﬁelds [20–23], tachyons [24], Galileons [25], phan- tom and quintom cosmology [26, 27], k-essence [28, 29], where a prime denotes diﬀerentiation with respect to modiﬁed gravity [30], three-form cosmology [31, 32] and dη = Hdt and the variables x and y are functions of dark energy models coupled to dark matter [33–35]. the dimensionless time parameter η = ln a. Note that With the variables (12) the Friedmann constraint (6) the dynamical system (18)-(19) is invariant under the (cid:55)→ − becomes transformation y y, so even if we drop the V > 0 assumption the dynamics on the negative y half-plane would be a copy of the positive y region. Note also that 1 = Ω + Ω = σ2 + x2 + y2 , (13) m φ we are assuming H > 0 in order to describe an expanding universe. However the dynamics of a contracting universe where the relative energy densities are deﬁned as (H < 0) would have the same features of our analysis in the negative y plane switching the direction of time (cid:55)→ − because of the y y symmetry. On the other hand κ2ρ κ2ρ Ω = and Ω = φ . (14) the dynamical system (18)-(19) is also invariant under m 3H2 φ 3H2 the symultaneous transformation Eq. (13) can be used to replace σ2 in favour of x2 and (cid:55)→ − (cid:55)→ − y2. This implies that the only dynamical variables of≥the λ λ and x x , (20) system of equations will be x and y. Also, since σ2 0 ≥ due to the assumption ρ 0, the constraint which shows that opposite values of λ lead to the same ≤ dynamics after a reﬂection over the y-axis. x2 + y2 1 , (15) The acceleration equation (7) gives also (cid:2) (cid:0) (cid:1)(cid:3) will always hold. If in addition one assumes the poten- ≥ H˙ 3 − − tial energy V to be greater than zero, then y 0 and the = (w 1)x2 + (w + 1) y2 1 , (21) phase space of the variables (x, y) reduces to the upper H2 2 half unit disk. At this point it is possible to convert the cosmological which at any ﬁxed point (x∗, y∗) of the phase space can equations into an autonomous system of equations if one be solved for a to give further speciﬁes the potential V . If this is exponential, for example ∝ − − − a (t t )2/[3(w+1)(1 x2∗ y∗2)+2x2∗] , (22) 0 − V (φ) = V e λκφ , (16) 0 where t is a constant of integration. This corresponds 0 to a power law solution, i.e. a solution for which the scale with V > 0 and λ arbitrary parameters, then the 0 factor a evolves as a power of the cosmological time t. If phase space will remain two dimensional. If instead one x = 0 and y = 0 the universe is matter dominated and choses a power-law potential, then the phase space be- its evolution coincides with the standard w-dependent comes three dimensional and the new variable scaling solution. If x = 0 and y = 1 the denominator of (22) vanishes and the universe undergoes a de Sitter − 1 ∂V expansion as can be seen from (21) which forces H to be z = , (17) κV ∂φ constant. An eﬀective EoS parameter w can now be eﬀ deﬁned rewriting (22) as1 needs to be introduced. In this work we will only consider exponential potential of the kind (16). With ∝ − this assumption the acceleration equation (7) and the a (t t0)2/[3(1+weff)] , (23) scalar ﬁeld equation (8) lead to the two dimensional au- tonomous(cid:34)s(cid:114)ystem (cid:35) (cid:0) (cid:1) and corresponds to the EoS parameter of an eﬀective ﬂuid sourcing the gravitational equations, or in other x(cid:48) = 3 2λy2 − (w − 1)x3 − x(w + 1) y2 − 1 , words to an eﬀective matter energy-momentum tensor. 2 (cid:34)3 (cid:114) (cid:35) Comparing with (22) we ﬁnd (cid:0) (cid:1) (18) (cid:48) −3 − − 2 y = y (w 1)x2 + (w + 1) y2 1 + λx , − 2 3 1 If w < 1 then the physical solution for the scale factor in eﬀ ∝ − (19) Eq. (22) should be a (t0 t)2/[3(1+weff)], which implies a Big Rip at t = t0. ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: scalar

text: ﬁelds

text: tachyons

text: Galileons

text: phan-

text: tom

text: and

text: quintom

text: cosmology

text: k-essence

text: where

text: a

text: prime

text: denotes

text: diﬀerentiation

text: with

text: respect

text: to

text: modiﬁed

text: gravity

text: three-form

text: cosmology

text: and

text: dη

text: Hdt

text: and

text: the

text: variables

text: x

text: and

text: y

text: are

text: functions

text: of

text: dark

text: energy

text: models

text: coupled

text: to

text: dark

text: matter

text: the

text: dimensionless

text: time

text: parameter

text: η

text: ln

text: a.

text: Note

text: that

text: With

text: the

text: variables

text: the

text: Friedmann

text: constraint

text: the

text: dynamical

text: system

text: is

text: invariant

text: under

text: the

text: becomes

text: transformation

text: y

text: y,

text: so

text: even

text: if

text: we

text: drop

text: the

text: V

text: assumption

text: the

text: dynamics

text: on

text: the

text: negative

text: y

text: half-plane

text: would

text: be

text: a

text: copy

text: of

text: the

text: positive

text: y

text: region.

text: Note

text: also

text: that

text: Ω

text: Ω

text: σ2

text: m

text: φ

text: we

text: are

text: assuming

text: H

text: in

text: order

text: to

text: describe

text: an

text: expanding

text: universe.

text: However

text: the

text: dynamics

text: of

text: a

text: contracting

text: universe

text: where

text: the

text: relative

text: energy

text: densities

text: are

text: deﬁned

text: as

text: (H

text: would

text: have

text: the

text: same

text: features

text: of

text: our

text: analysis

text: in

text: the

text: negative

text: y

text: plane

text: switching

text: the

text: direction

text: of

text: time

text: because

text: of

text: the

text: y

text: y

text: symmetry.

text: On

text: the

text: other

text: hand

text: κ2ρ

text: κ2ρ

text: Ω

text: and

text: Ω

text: φ

text: the

text: dynamical

text: system

text: is

text: also

text: invariant

text: under

text: m

text: φ

text: the

text: symultaneous

text: transformation

text: Eq.

text: can

text: be

text: used

text: to

text: replace

text: σ2

text: in

text: favour

text: of

text: and

text: This

text: implies

text: that

text: the

text: only

text: dynamical

text: variables

text: of≥the

text: λ

text: λ

text: and

text: x

text: x

text: system

text: of

text: equations

text: will

text: be

text: x

text: and

text: y.

text: Also,

text: since

text: σ2

text: due

text: to

text: the

text: assumption

text: ρ

text: the

text: constraint

text: which

text: shows

text: that

text: opposite

text: values

text: of

text: λ

text: lead

text: to

text: the

text: same

text: dynamics

text: after

text: a

text: reﬂection

text: over

text: the

text: y-axis.

text: The

text: acceleration

text: equation

text: gives

text: also

text: will

text: always

text: hold.

text: If

text: in

text: addition

text: one

text: assumes

text: the

text: poten-

text: H˙

text: tial

text: energy

text: V

text: to

text: be

text: greater

text: than

text: zero,

text: then

text: y

text: and

text: the

text: (w

text: (w

text: phase

text: space

text: of

text: the

text: variables

text: (x,

text: y)

text: reduces

text: to

text: the

text: upper

text: half

text: unit

text: disk.

text: At

text: this

text: point

text: it

text: is

text: possible

text: to

text: convert

text: the

text: cosmological

text: which

text: at

text: any

text: ﬁxed

text: point

text: (x∗,

text: y∗)

text: of

text: the

text: phase

text: space

text: can

text: equations

text: into

text: an

text: autonomous

text: system

text: of

text: equations

text: if

text: one

text: be

text: solved

text: for

text: a

text: to

text: give

text: further

text: speciﬁes

text: the

text: potential

text: V

text: If

text: this

text: is

text: exponential,

text: for

text: example

text: a

text: (t

text: t

text: V

text: (φ)

text: V

text: e

text: λκφ

text: where

text: t

text: is

text: a

text: constant

text: of

text: integration.

text: This

text: corresponds

text: to

text: a

text: power

text: law

text: solution,

text: i.e.

text: a

text: solution

text: for

text: which

text: the

text: scale

text: with

text: V

text: and

text: λ

text: arbitrary

text: parameters,

text: then

text: the

text: factor

text: a

text: evolves

text: as

text: a

text: power

text: of

text: the

text: cosmological

text: time

text: t.

text: If

text: phase

text: space

text: will

text: remain

text: two

text: dimensional.

text: If

text: instead

text: one

text: x

text: and

text: y

text: the

text: universe

text: is

text: matter

text: dominated

text: and

text: choses

text: a

text: power-law

text: potential,

text: then

text: the

text: phase

text: space

text: be-

text: its

text: evolution

text: coincides

text: with

text: the

text: standard

text: w-dependent

text: comes

text: three

text: dimensional

text: and

text: the

text: new

text: variable

text: scaling

text: solution.

text: If

text: x

text: and

text: y

text: the

text: denominator

text: of

text: vanishes

text: and

text: the

text: universe

text: undergoes

text: a

text: de

text: Sitter

text: ∂V

text: expansion

text: as

text: can

text: be

text: seen

text: from

text: which

text: forces

text: H

text: to

text: be

text: z

text: κV

text: ∂φ

text: constant.

text: An

text: eﬀective

text: EoS

text: parameter

text: w

text: can

text: now

text: be

text: eﬀ

text: deﬁned

text: rewriting

text: needs

text: to

text: be

text: introduced.

text: In

text: this

text: work

text: we

text: will

text: only

text: consider

text: exponential

text: potential

text: of

text: the

text: kind

text: With

text: this

text: assumption

text: the

text: acceleration

text: equation

text: and

text: the

text: a

text: (t

text: scalar

text: ﬁeld

text: equation

text: lead

text: to

text: the

text: two

text: dimensional

text: au-

text: and

text: corresponds

text: to

text: the

text: EoS

text: parameter

text: of

text: an

text: eﬀective

text: ﬂuid

text: sourcing

text: the

text: gravitational

text: equations,

text: or

text: in

text: other

text: (w

text: x(w

text: words

text: to

text: an

text: eﬀective

text: matter

text: energy-momentum

text: tensor.

text: Comparing

text: with

text: we

text: ﬁnd

text: −3

text: y

text: y

text: (w

text: (w

text: λx

text: If

text: w

text: then

text: the

text: physical

text: solution

text: for

text: the

text: scale

text: factor

text: in

text: eﬀ

text: Eq.

text: should

text: be

text: a

text: which

text: implies

text: a

text: Big

text: Rip

text: at

text: t

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Ho¨lder Regularity of Geometric Subdivision Schemes T. Ewald U. Reif M. Sabin May 26, 2020 Abstract R We present a framework for analyzing non-linear d-valued subdivision schemes R which are geometric in the sense that they commute with similarities in d. It admits to establish C1,α-regularity for arbitrary schemes of this type, and C2,α- regularity for an important subset thereof, which includes all real-valued schemes. Our results are constructive in the sense that they can be veriﬁed explicitly for any scheme and any given set of initial data by a universal procedure. This procedure can be executed automatically and rigorously by a computer when using interval arithmetics. Keywords Non-linear subdivision, geometric subdivision, H¨older regularity, circle- preserving scheme Mathematics Subject Classiﬁcation (2010) 26A16, 68U07 1 Introduction Univariate subdivision schemes deﬁne a function or curve as the limit of a reﬁnement process, starting from a sequence of point positions usually called the ‘control polygon’. Since the ﬁrst introduction of such schemes a question of great interest has been ‘Under what conditions will the limit curve exist, and what H¨older continuity will it have?’. Techniques have been honed since the ﬁrst papers [DGL91, CDM91], and there is now a standard approach which can be applied to any newly proposed subdivision scheme which is linear (the new points are deﬁned by speciﬁc linear combinations of old ones), uniform (the linear combination coeﬃcients are the same at each part of the sequence) and stationary (the coeﬃcients are the same at all steps), see [DL02] for a survey or [Sab10] for a comprehensive exposition. While linear subdivision is meanwhile well understood, non-linear algorithms have gained some interest in recent years. The variety of diﬀerent schemes may be grouped as follows: First, there are manifold-valued schemes where non-linearity comes from adapting a linear scheme to the special structure of the space carrying the data. Today, this class 1

text: Ho¨lder

label: title

text: Regularity

text: of

text: Geometric

text: Subdivision

text: Schemes

text: T.

label: author

text: Ewald

text: U.

label: paragraph

text: Reif

text: M.

text: Sabin

text: May

label: date

text: Abstract

text: R

label: abstract

text: We

text: present

text: a

text: framework

text: for

text: analyzing

text: non-linear

text: d-valued

text: subdivision

text: schemes

text: R

text: which

text: are

text: geometric

text: in

text: the

text: sense

text: that

text: they

text: commute

text: with

text: similarities

text: in

text: d.

text: It

text: admits

text: to

text: establish

text: for

text: arbitrary

text: schemes

text: of

text: this

text: type,

text: and

text: regularity

text: for

text: an

text: important

text: subset

text: thereof,

text: which

text: includes

text: all

text: real-valued

text: schemes.

text: Our

text: results

text: are

text: constructive

text: in

text: the

text: sense

text: that

text: they

text: can

text: be

text: veriﬁed

text: explicitly

text: for

text: any

text: scheme

text: and

text: any

text: given

text: set

text: of

text: initial

text: data

text: by

text: a

text: universal

text: procedure.

text: This

text: procedure

text: can

text: be

text: executed

text: automatically

text: and

text: rigorously

text: by

text: a

text: computer

text: when

text: using

text: interval

text: arithmetics.

text: Keywords

text: Non-linear

text: subdivision,

text: geometric

text: subdivision,

text: H¨older

text: regularity,

text: circle-

text: preserving

text: scheme

text: Mathematics

text: Subject

text: Classiﬁcation

text: Introduction

text: Univariate

text: subdivision

text: schemes

text: deﬁne

text: a

text: function

text: or

text: curve

text: as

text: the

text: limit

text: of

text: a

text: reﬁnement

text: process,

text: starting

text: from

text: a

text: sequence

text: of

text: point

text: positions

text: usually

text: called

text: the

text: ‘control

text: polygon’.

text: Since

text: the

text: ﬁrst

text: introduction

text: of

text: such

text: schemes

text: a

text: question

text: of

text: great

text: interest

text: has

text: been

text: ‘Under

text: what

text: conditions

text: will

text: the

text: limit

text: curve

text: exist,

text: and

text: what

text: H¨older

text: continuity

text: will

text: it

text: have?’.

text: Techniques

text: have

text: been

text: honed

text: since

text: the

text: ﬁrst

text: papers

text: and

text: there

text: is

text: now

text: a

text: standard

text: approach

text: which

text: can

text: be

text: applied

text: to

text: any

text: newly

text: proposed

text: subdivision

text: scheme

text: which

text: is

text: linear

text: (the

text: new

text: points

text: are

text: deﬁned

text: by

text: speciﬁc

text: linear

text: combinations

text: of

text: old

text: ones),

text: uniform

text: (the

text: linear

text: combination

text: coeﬃcients

text: are

text: the

text: same

text: at

text: each

text: part

text: of

text: the

text: sequence)

text: and

text: stationary

text: (the

text: coeﬃcients

text: are

text: the

text: same

text: at

text: all

text: steps),

text: see

text: for

text: a

text: survey

text: or

text: for

text: a

text: comprehensive

text: exposition.

text: While

text: linear

text: subdivision

text: is

text: meanwhile

text: well

text: understood,

text: non-linear

text: algorithms

text: have

text: gained

text: some

text: interest

text: in

text: recent

text: years.

text: The

text: variety

text: of

text: diﬀerent

text: schemes

text: may

text: be

text: grouped

text: as

text: follows:

text: First,

text: there

text: are

text: manifold-valued

text: schemes

text: where

text: non-linearity

text: comes

text: from

text: adapting

text: a

text: linear

text: scheme

text: to

text: the

text: special

text: structure

text: of

text: the

text: space

text: carrying

text: the

text: data.

text: Today,

text: this

text: class


text: | − | ≤ The index j is deﬁned as the integer closest to 2(cid:96)τ, i.e., j 2(cid:96)τ 1/2. Then, with r ⊆ − (cid:88) (cid:0) − ± −(cid:1) | − | such that supp ψ [ r + 3/2, r 3/2], we ﬁnd ψ (2(cid:96)τ i) = 0 whenever i j > r. 2 2 h Hence, − − − − − σ(τ, h) = ψ (2(cid:96)τ+ i) ψ (2(cid:96)τ i) (∆2p(cid:96) ∆2p(cid:96)). 2 h 2 h i j | − |≤ i j r (cid:107) − (cid:107) ≤ | | This expression can be estimated by (17) using the bound ∆2p(cid:96) ∆2p(cid:96) r P(cid:96) and i j 3 (35), (cid:107) (cid:107) ≤ | | ≤ (cid:48) − (cid:48)(cid:48) − σ(τ, h) 2ψ¯ r P(cid:96) 2ψ¯ rC 2 (cid:96)γ¯ = C 2 (cid:96)γ¯. 2 3 2 ≤ (cid:48)(cid:48) − ≤ (cid:48)(cid:48) ≤ (cid:3) Hence, s C 2 (cid:96)γ C hγ, showing that ω (∂2Φ[P], h) Chγ, as requested. 2 z Unfortunately, regularity of A beyond C2,1 is not necessarily inherited by G. As an example, consider the scheme G, given by (cid:107) (cid:107) ∆2p − g (T 3P) = (5p − + 10p + p )/16 + (cid:107) −i 1 (cid:107) ∆2p − 0 i i 1 i i+1 p p − i 1 i+1 i 1 g (T 3P) = (p − + 10p + 5p )/16 1 i i 1 i i+1 Its linear companion is the quartic B-spline scheme A1/2, as discussed in Section , which is C3,1, while numerical experiments suggest that G is not smoother than C2,1. 7 Conclusion We have presented a general framework for the analysis of geometric subdivision schemes. It is related to standard linear C1,α-theory by considering the decay not of second diﬀerences, but of another quantity (relative distortion) measuring the devia- tion from a linear behavior. It is also related to known approaches for the analysis of manifold-valued subdivision as it uses a proximity condition. However, for C1,α- analysis, the linear reference scheme depends only on the shift of the given scheme, and is indiﬀerent otherwise. Unlike any other known analysis of non-linear schemes, our approach admits to establish H¨older regularity by a universal procedure, which can be fully automated. This procedure consists of two steps: First, an upper bound on the maximal relative distortion is determined together with some parameter characterizing the Ho¨lder exponent. This computation can be done once and for all for a given scheme. Second, when a speciﬁc initial chain is given, this chain is checked for compliance with the pre-computed bound. If this bound is met, convergence and regularity of the limit are veriﬁed. Otherwise, a few rounds of subdivision are applied to the initial data, and then the check is repeated. If the check fails even after many subdivision steps, then it is conceivable that the limit does not have the expected regularity for this speciﬁc set of initial data1. In a forthcoming report, we will describe details of an implementation. 1It should be noted that the regularity of the limit curve may indeed depend on the initial data. For instance, this phenomenon can be observed for median-interpolating subdivision [XY05], where non-monotonic data may yield non-diﬀerentiable limits. 29 ##LTLine## ##LTLine##

label: equation

text: The

text: index

text: j

text: is

text: deﬁned

text: as

text: the

text: integer

text: closest

text: to

text: i.e.,

text: j

text: Then,

text: with

text: r

text: such

text: that

text: supp

text: ψ

text: r

text: r

text: we

text: ﬁnd

text: ψ

text: i)

text: whenever

text: i

text: j

text: r.

text: h

text: Hence,

text: σ(τ,

text: h)

text: ψ

text: i)

text: ψ

text: i)

text: h

text: h

text: i

text: j

text: i

text: j

text: r

text: This

text: expression

text: can

text: be

text: estimated

text: by

text: using

text: the

text: bound

text: r

text: and

text: i

text: j

text: σ(τ,

text: h)

text: 2ψ¯

text: r

text: 2ψ¯

text: rC

text: C

text: Hence,

text: s

text: C

text: C

text: hγ,

text: showing

text: that

text: ω

text: h)

text: Chγ,

text: as

text: requested.

text: z

text: Unfortunately,

text: regularity

text: of

text: A

text: beyond

text: is

text: not

text: necessarily

text: inherited

text: by

text: G.

text: As

text: an

text: example,

text: consider

text: the

text: scheme

text: G,

text: given

text: by

text: g

text: (T

text: p

text: −i

text: i

text: i

text: i

text: p

text: p

text: i

text: i

text: g

text: (T

text: (p

text: i

text: i

text: i

text: Its

text: linear

text: companion

text: is

text: the

text: quartic

text: B-spline

text: scheme

text: as

text: discussed

text: in

text: Section

text: which

text: is

text: while

text: numerical

text: experiments

text: suggest

text: that

text: G

text: is

text: not

text: smoother

text: than

text: Conclusion

text: We

text: have

text: presented

text: a

text: general

text: framework

text: for

text: the

text: analysis

text: of

text: geometric

text: subdivision

text: schemes.

text: It

text: is

text: related

text: to

text: standard

text: linear

text: by

text: considering

text: the

text: decay

text: not

text: of

text: second

text: diﬀerences,

text: but

text: of

text: another

text: quantity

text: (relative

text: distortion)

text: measuring

text: the

text: devia-

text: tion

text: from

text: a

text: linear

text: behavior.

text: It

text: is

text: also

text: related

text: to

text: known

text: approaches

text: for

text: the

text: analysis

text: of

text: manifold-valued

text: subdivision

text: as

text: it

text: uses

text: a

text: proximity

text: condition.

text: However,

text: for

text: analysis,

text: the

text: linear

text: reference

text: scheme

text: depends

text: only

text: on

text: the

text: shift

text: of

text: the

text: given

text: scheme,

text: and

text: is

text: indiﬀerent

text: otherwise.

text: Unlike

text: any

text: other

text: known

text: analysis

text: of

text: non-linear

text: schemes,

text: our

text: approach

text: admits

text: to

text: establish

text: H¨older

text: regularity

text: by

text: a

text: universal

text: procedure,

text: which

text: can

text: be

text: fully

text: automated.

text: This

text: procedure

text: consists

text: of

text: two

text: steps:

text: First,

text: an

text: upper

text: bound

text: on

text: the

text: maximal

text: relative

text: distortion

text: is

text: determined

text: together

text: with

text: some

text: parameter

text: characterizing

text: the

text: Ho¨lder

text: exponent.

text: This

text: computation

text: can

text: be

text: done

text: once

text: and

text: for

text: all

text: for

text: a

text: given

text: scheme.

text: Second,

text: when

text: a

text: speciﬁc

text: initial

text: chain

text: is

text: given,

text: this

text: chain

text: is

text: checked

text: for

text: compliance

text: with

text: the

text: pre-computed

text: bound.

text: If

text: this

text: bound

text: is

text: met,

text: convergence

text: and

text: regularity

text: of

text: the

text: limit

text: are

text: veriﬁed.

text: Otherwise,

text: a

text: few

text: rounds

text: of

text: subdivision

text: are

text: applied

text: to

text: the

text: initial

text: data,

text: and

text: then

text: the

text: check

text: is

text: repeated.

text: If

text: the

text: check

text: fails

text: even

text: after

text: many

text: subdivision

text: steps,

text: then

text: it

text: is

text: conceivable

text: that

text: the

text: limit

text: does

text: not

text: have

text: the

text: expected

text: regularity

text: for

text: this

text: speciﬁc

text: set

text: of

text: initial

text: In

text: a

text: forthcoming

text: report,

text: we

text: will

text: describe

text: details

text: of

text: an

text: implementation.

text: should

text: be

text: noted

text: that

text: the

text: regularity

text: of

text: the

text: limit

text: curve

text: may

text: indeed

text: depend

text: on

text: the

text: initial

text: data.

text: For

text: instance,

text: this

text: phenomenon

text: can

text: be

text: observed

text: for

text: median-interpolating

text: subdivision

text: where

text: non-monotonic

text: data

text: may

text: yield

text: non-diﬀerentiable

text: limits.

text: ##LTLine##

text: ##LTLine##


text: There are many obvious directions for future research. For instance, higher order Ho¨lder regularity could be approached by deﬁning appropriate proximity conditions or by considering deviations from a circle instead of a straight line. Further, we conjecture that Theorem 6.1 could be enhanced by showing that regularity is determined only by the normal scheme B, while the tangential scheme A is irrelevant. When trying to further generalize the class of schemes, it would be nice to drop property (E), but this seems to be a real challenge as it is not clear at all how to choose an appropriate parametrization, or to get rid of a speciﬁc parametrization at all and come up with a genuine geometric proof. References [CDM91] A.S. Cavaretta, W. Dahmen, and C.A. Micchelli. Stationary subdivision. Memoires of the AMS, 93(453):1–186, 1991. [CDM03] A. Cohen, N. Dyn, and B. Matei. Quasilinear subdivision schemes with applications to ENO interpolation. Appl. and Comput. Harmonic Analysis, 15(2):89–116, 2003. [Cha74] G.M. Chaikin. An algorithm for high-speed curve generation. Computer Graphics and Image Processing, 3:346 – 349, 1974. [CHR13] T. Cashman, K. Hormann, and U. Reif. Generalized Lane-Riesenfeld algo- rithms. Comp. Aided Geom. Design, 30(4):398–409, 2013. [dB87] C. de Boor. Cutting corners always works. Comp. Aided Geom. Design, 4:125–131, 1987. [DDR+05] D.L. Donoho, I. Drori, I.U. Rahman, P. Schr¨oder, and V.C. Stodden. Mul- tiscale representations for manifold-valued data. Multiscale Modeling and Simulation, 4(4):1201–1232, 2005. [DFH09] N. Dyn, M. S. Floater, and K. Hormann. Four-point curve subdivision based on iterated chordal and centripetal parameterizations. Comp. Aided Geom. Design., 26(3):279–286, 2009. [DGL91] N. Dyn, J.A. Gregory, and D. Levin. Analysis of uniform binary subdivision schemes for curve design. Constr. Approx., 7(1):127–147, 1991. [DH12] N. Dyn and K. Hormann. Geometric conditions for tangent continuity of in- terpolatory planar subdivision curves. Computer Aided Geometric Design, 29(6):332–347, August 2012. [DL02] N. Dyn and D. Levin. Subdivision schemes in geometric modelling. Acta Numerica, 11:73–144, 2002. 30

text: There

text: are

text: many

text: obvious

text: directions

text: for

text: future

text: research.

text: For

text: instance,

text: higher

text: order

text: Ho¨lder

text: regularity

text: could

text: be

text: approached

text: by

text: deﬁning

text: appropriate

text: proximity

text: conditions

text: or

text: by

text: considering

text: deviations

text: from

text: a

text: circle

text: instead

text: of

text: a

text: straight

text: line.

text: Further,

text: we

text: conjecture

text: that

text: Theorem

text: could

text: be

text: enhanced

text: by

text: showing

text: that

text: regularity

text: is

text: determined

text: only

text: by

text: the

text: normal

text: scheme

text: B,

text: while

text: the

text: tangential

text: scheme

text: A

text: is

text: irrelevant.

text: When

text: trying

text: to

text: further

text: generalize

text: the

text: class

text: of

text: schemes,

text: it

text: would

text: be

text: nice

text: to

text: drop

text: property

text: (E),

text: but

text: this

text: seems

text: to

text: be

text: a

text: real

text: challenge

text: as

text: it

text: is

text: not

text: clear

text: at

text: all

text: how

text: to

text: choose

text: an

text: appropriate

text: parametrization,

text: or

text: to

text: get

text: rid

text: of

text: a

text: speciﬁc

text: parametrization

text: at

text: all

text: and

text: come

text: up

text: with

text: a

text: genuine

text: geometric

text: proof.

text: References

text: A.S.

text: Cavaretta,

text: W.

text: Dahmen,

text: and

text: C.A.

text: Micchelli.

text: Stationary

text: subdivision.

text: Memoires

text: of

text: the

text: AMS,

text: A.

text: Cohen,

text: N.

text: Dyn,

text: and

text: B.

text: Matei.

text: Quasilinear

text: subdivision

text: schemes

text: with

text: applications

text: to

text: ENO

text: interpolation.

text: Appl.

text: and

text: Comput.

text: Harmonic

text: Analysis,

text: G.M.

text: Chaikin.

text: An

text: algorithm

text: for

text: high-speed

text: curve

text: generation.

text: Computer

text: Graphics

text: and

text: Image

text: Processing,

text: T.

text: Cashman,

text: K.

text: Hormann,

text: and

text: U.

text: Reif.

text: Generalized

text: Lane-Riesenfeld

text: algo-

text: rithms.

text: Comp.

text: Aided

text: Geom.

text: Design,

text: C.

text: de

text: Boor.

text: Cutting

text: corners

text: always

text: works.

text: Comp.

text: Aided

text: Geom.

text: Design,

text: D.L.

text: Donoho,

text: I.

text: Drori,

text: I.U.

text: Rahman,

text: P.

text: Schr¨oder,

text: and

text: V.C.

text: Stodden.

text: Mul-

text: tiscale

text: representations

text: for

text: manifold-valued

text: data.

text: Multiscale

text: Modeling

text: and

text: Simulation,

text: N.

text: Dyn,

text: M.

text: S.

text: Floater,

text: and

text: K.

text: Hormann.

text: Four-point

text: curve

text: subdivision

text: based

text: on

text: iterated

text: chordal

text: and

text: centripetal

text: parameterizations.

text: Comp.

text: Aided

text: Geom.

text: Design.,

text: N.

text: Dyn,

text: J.A.

text: Gregory,

text: and

text: D.

text: Levin.

text: Analysis

text: of

text: uniform

text: binary

text: subdivision

text: schemes

text: for

text: curve

text: design.

text: Constr.

text: Approx.,

text: N.

text: Dyn

text: and

text: K.

text: Hormann.

text: Geometric

text: conditions

text: for

text: tangent

text: continuity

text: of

text: in-

text: terpolatory

text: planar

text: subdivision

text: curves.

text: Computer

text: Aided

text: Geometric

text: Design,

text: August

text: N.

text: Dyn

text: and

text: D.

text: Levin.

text: Subdivision

text: schemes

text: in

text: geometric

text: modelling.

text: Acta

text: Numerica,


text: S E L First, we note that the action of ( ) on n∗, the space of non-constant linear chains, is transitive. Further, similarities commute with orthogonal projections. Together, these ∈ E ∈ S E facts imply that for any p n∗ there exists S ( ) such that ΠS (p) = S (Πp) = e. p p p The resulting chain q = S (p) is called normalized, and the set of all normalized chains p is denoted by Q { ∈ E } n := q n∗ : Πq = e . Second, we have | | | || | S(p) S p ∈ S E ∈ E κ(S(p)) = | 2| = | || 2| = κ(p), S ( ), p n∗. (2) S(Πp) S Πp 1 1 ∞ ∞ Equally, κ(p) = implies κ(S(p)) = , showing that the relative distortion is invariant with respect to similarities. Combining these two observations, we see that any chain p with non-constant linear part is similar to a normalized chain with equal relative distortion, ∈ E ⇔ ∈ Q { ∈ Q ≤ } p n[δ] S (p) n[δ] := q n : κ(q) δ . p Throughout, the letter q is reserved for normalized chains, and we use the abbreviation − ∈ L d := q e n c for the non-linear part of q without further notice. The relative distortion of a normal- ∈ Q ized chain q n is given by | | | | e + d d | | κ(q) = | 2| = | |2 = d . (3) 2 Π(e + d) e 1 1 Q { ∈ L | | ≤ } | · | So we recognize the set n[δ] = e + d n : d δ as a lower-dimensional -ball c 2 2 centered at the standard linear chain e. Higher order diﬀerences are bounded by lower ones according to the standard estimate | | ≤ | | ∈ E ∈ N p 2j p , p n, i, j . (4) i+j i 0 L | · | | · | Reverse estimates are possible on the subspace n, where not only , but also | · | c ∈ { } 0 1 and are norms and hence equivalent. More precisely, for j 1, 2 , 2 − | | ≤ n j | | ∈ L d − d , d n. j 1 2 j c (cid:40) ∈ R(cid:40) − ∈ R − − To show this, we deﬁne the matrices M1 n,n 1 and M2 n 1,n 2 by − ≤ − − ≤ j+1 1 for i j (j+1)(j+2)(2j−+3 3n) 1 for i j M1 = n , M2 = n(1+n)(1 n)− . i,j j+1 for i > j i,j (j+1)(j+2)(2j−+3 3n) for i > j n n(1+n)(1 n) 7 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: S

text: E

text: L

text: First,

text: we

text: note

text: that

text: the

text: action

text: of

text: on

text: n∗,

text: the

text: space

text: of

text: non-constant

text: linear

text: chains,

text: is

text: transitive.

text: Further,

text: similarities

text: commute

text: with

text: orthogonal

text: projections.

text: Together,

text: these

text: E

text: S

text: E

text: facts

text: imply

text: that

text: for

text: any

text: p

text: n∗

text: there

text: exists

text: S

text: such

text: that

text: ΠS

text: (p)

text: S

text: (Πp)

text: e.

text: p

text: p

text: p

text: The

text: resulting

text: chain

text: q

text: S

text: (p)

text: is

text: called

text: normalized,

text: and

text: the

text: set

text: of

text: all

text: normalized

text: chains

text: p

text: is

text: denoted

text: by

text: Q

text: E

text: n

text: q

text: n∗

text: Πq

text: e

text: Second,

text: we

text: have

text: S(p)

text: S

text: p

text: S

text: E

text: E

text: κ(S(p))

text: κ(p),

text: S

text: p

text: n∗.

text: S(Πp)

text: S

text: Πp

text: Equally,

text: κ(p)

text: implies

text: κ(S(p))

text: showing

text: that

text: the

text: relative

text: distortion

text: is

text: invariant

text: with

text: respect

text: to

text: similarities.

text: Combining

text: these

text: two

text: observations,

text: we

text: see

text: that

text: any

text: chain

text: p

text: with

text: non-constant

text: linear

text: part

text: is

text: similar

text: to

text: a

text: normalized

text: chain

text: with

text: equal

text: relative

text: distortion,

text: E

text: Q

text: Q

text: p

text: n[δ]

text: S

text: (p)

text: n[δ]

text: q

text: n

text: κ(q)

text: δ

text: p

text: Throughout,

text: the

text: letter

text: q

text: is

text: reserved

text: for

text: normalized

text: chains,

text: and

text: we

text: use

text: the

text: abbreviation

text: L

text: d

text: q

text: e

text: n

text: c

text: for

text: the

text: non-linear

text: part

text: of

text: q

text: without

text: further

text: notice.

text: The

text: relative

text: distortion

text: of

text: a

text: normal-

text: Q

text: ized

text: chain

text: q

text: n

text: is

text: given

text: by

text: e

text: d

text: d

text: κ(q)

text: d

text: Π(e

text: d)

text: e

text: Q

text: L

text: So

text: we

text: recognize

text: the

text: set

text: n[δ]

text: e

text: d

text: n

text: d

text: δ

text: as

text: a

text: lower-dimensional

text: -ball

text: c

text: centered

text: at

text: the

text: standard

text: linear

text: chain

text: e.

text: Higher

text: order

text: diﬀerences

text: are

text: bounded

text: by

text: lower

text: ones

text: according

text: to

text: the

text: standard

text: estimate

text: E

text: N

text: p

text: p

text: p

text: n,

text: i,

text: j

text: i+j

text: i

text: L

text: Reverse

text: estimates

text: are

text: possible

text: on

text: the

text: subspace

text: n,

text: where

text: not

text: only

text: but

text: also

text: c

text: and

text: are

text: norms

text: and

text: hence

text: equivalent.

text: More

text: precisely,

text: for

text: j

text: n

text: j

text: L

text: d

text: d

text: d

text: n.

text: j

text: j

text: c

text: R

text: To

text: show

text: this,

text: we

text: deﬁne

text: the

text: matrices

text: n,n

text: and

text: n

text: by

text: for

text: i

text: j

text: for

text: i

text: j

text: n

text: n)−

text: i,j

text: for

text: i

text: j

text: i,j

text: for

text: i

text: j

text: n

text: n)

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: of children xz and yz, at least one connects two diﬀerent parts; this child necessarily belongs to M. Thus, | ∩ | ≥ 1 | | F M F + o(n2). i i 2 | | (Recall that parent edges th(cid:88)at intersect X produce at most 2n X = o(n2) children.) Therefore, | | ≥ 1 s | | ≥ m M F + o(n2) + o(n2) = Ω(n2), i 2 2 i=1 contradicting (2.6). This contradiction proves Lemma 2.5. We are now able to prove Theorem 1.6. Proof of the upper bound in Theorem 1.6. Let C be the constant returned by Theo- rem 2.2 for r = R. Let n = n (r , . . . , r ) be suﬃciently large to satisfy all the 0 0 1 k ≥ inequalities we will encounter. Let G be a k-edge-coloured graph on n n vertices. C ≤ 0 We will show that φ (G, ) t − (n) with equality if and only if G = T − (n), and k R 1 ≤R 1≤ G does not contain a monochromatic copy of K in colour i for every 1 i k. ri Let e(G) = t − (n) + m, where m is an integer. If m < 0, we can decompose G R 1 into single edges and there is nothing to prove. (cid:0) (cid:1) Suppose m = 0. If G contains a monochromatic copy of K in colour i for ≤ ≤ C ri some 1 i k, then G admits a monochromatic -decomposition with at most − t − (n) ri + 1 < t − (n) parts and we are done. Otherwise, the deﬁnition of R R 1 2 R 1 implies that G does not contain a copy of K . Therefore, G(cid:0) =(cid:1) T − (n) by Tura´n’s C R R 1 theorem and φ (G, ) = t − (n) as required. k R 1 Now suppose m > 0. We can also assume that m < n /C for otherwise we C 2 are done: φ (G, ) < t − (n) by Lemma 2.5. Thus, by Theorem 2.2, the graph G k − R 1 (cid:80) (cid:80) (cid:0) (cid:1) (cid:80) contains at least m Cm2/n2 > m edge-disjoint copies of K . Since each K contains 2 R ≤ ≤ R a monochromatic copy of K in the colour-i graph G , for some 1 i k, we conclude ri (cid:18) (cid:19) − i ≥ that k ν (G ) > m, so that (cid:88)k ( ri 1)ν (G(cid:88)) k 2ν (G ) > m. We have i=1 ri i 2 i=1 2 ri i i=1 ri i C − k r k φ (G, ) = e(G) i ν (G ) + ν (G ) < t − (n), k 2 ri i ri i R 1 i=1 i=1 giving the required. Remark. By analysing the above argument, one can also derive the following stability C → ∞ property for every ﬁxed family of cliques as n : every graph G on n vertices C with φ (G, ) = t − (n) + o(n2) is o(n2)-close to the Tur´an graph T − (n) in the edit k R 1 R 1 distance. 12 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: of

text: children

text: xz

text: and

text: yz,

text: at

text: least

text: one

text: connects

text: two

text: diﬀerent

text: parts;

text: this

text: child

text: necessarily

text: belongs

text: to

text: M.

text: Thus,

text: F

text: M

text: F

text: i

text: i

text: (Recall

text: that

text: parent

text: edges

text: intersect

text: X

text: produce

text: at

text: most

text: X

text: children.)

text: Therefore,

text: s

text: m

text: M

text: F

text: i

text: contradicting

text: This

text: contradiction

text: proves

text: Lemma

text: We

text: are

text: now

text: able

text: to

text: prove

text: Theorem

text: Proof

text: of

text: the

text: upper

text: bound

text: in

text: Theorem

text: Let

text: C

text: be

text: the

text: constant

text: returned

text: by

text: Theo-

text: rem

text: for

text: r

text: R.

text: Let

text: n

text: n

text: (r

text: r

text: be

text: suﬃciently

text: large

text: to

text: satisfy

text: all

text: the

text: k

text: inequalities

text: we

text: will

text: encounter.

text: Let

text: G

text: be

text: a

text: k-edge-coloured

text: graph

text: on

text: n

text: n

text: vertices.

text: C

text: We

text: will

text: show

text: that

text: φ

text: (G,

text: t

text: (n)

text: with

text: equality

text: if

text: and

text: only

text: if

text: G

text: T

text: (n),

text: and

text: k

text: R

text: ≤R

text: 1≤

text: G

text: does

text: not

text: contain

text: a

text: monochromatic

text: copy

text: of

text: K

text: in

text: colour

text: i

text: for

text: every

text: i

text: k.

text: ri

text: Let

text: e(G)

text: t

text: (n)

text: m,

text: where

text: m

text: is

text: an

text: integer.

text: If

text: m

text: we

text: can

text: decompose

text: G

text: R

text: into

text: single

text: edges

text: and

text: there

text: is

text: nothing

text: to

text: prove.

text: Suppose

text: m

text: If

text: G

text: contains

text: a

text: monochromatic

text: copy

text: of

text: K

text: in

text: colour

text: i

text: for

text: C

text: ri

text: some

text: i

text: k,

text: then

text: G

text: admits

text: a

text: monochromatic

text: -decomposition

text: with

text: at

text: most

text: t

text: (n)

text: ri

text: t

text: (n)

text: parts

text: and

text: we

text: are

text: done.

text: Otherwise,

text: the

text: deﬁnition

text: of

text: R

text: R

text: R

text: implies

text: that

text: G

text: does

text: not

text: contain

text: a

text: copy

text: of

text: K

text: Therefore,

text: T

text: (n)

text: by

text: Tura´n’s

text: C

text: R

text: R

text: theorem

text: and

text: φ

text: (G,

text: t

text: (n)

text: as

text: required.

text: k

text: R

text: Now

text: suppose

text: m

text: We

text: can

text: also

text: assume

text: that

text: m

text: n

text: /C

text: for

text: otherwise

text: we

text: C

text: are

text: done:

text: φ

text: (G,

text: t

text: (n)

text: by

text: Lemma

text: Thus,

text: by

text: Theorem

text: the

text: graph

text: G

text: k

text: R

text: contains

text: at

text: least

text: m

text: m

text: edge-disjoint

text: copies

text: of

text: K

text: Since

text: each

text: K

text: contains

text: R

text: R

text: a

text: monochromatic

text: copy

text: of

text: K

text: in

text: the

text: colour-i

text: graph

text: G

text: for

text: some

text: i

text: k,

text: we

text: conclude

text: ri

text: i

text: that

text: k

text: ν

text: (G

text: m,

text: so

text: that

text: ri

text: k

text: 2ν

text: (G

text: m.

text: We

text: have

text: ri

text: i

text: ri

text: i

text: ri

text: i

text: C

text: k

text: r

text: k

text: φ

text: (G,

text: e(G)

text: i

text: ν

text: (G

text: ν

text: (G

text: t

text: (n),

text: k

text: ri

text: i

text: ri

text: i

text: R

text: giving

text: the

text: required.

text: Remark.

text: By

text: analysing

text: the

text: above

text: argument,

text: one

text: can

text: also

text: derive

text: the

text: following

text: stability

text: C

text: property

text: for

text: every

text: ﬁxed

text: family

text: of

text: cliques

text: as

text: n

text: every

text: graph

text: G

text: on

text: n

text: vertices

text: C

text: with

text: φ

text: (G,

text: t

text: (n)

text: is

text: to

text: the

text: Tur´an

text: graph

text: T

text: (n)

text: in

text: the

text: edit

text: k

text: R

text: R

text: distance.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: ∗ ∗ τ (H) = ν (H). (2.7) r r By the result of Haxell and Ro¨dl [9] we have that ∗ ν (H) = ν (H) + o(n2). (2.8) r r Krivelevich [10] showed that ≤ ∗ τ (H) 2τ (H). (2.9) 3 3 ≤ Thus, τ (H) 2ν (H) + o(n2) giving (2.1) for r = 3. 3 3 The proof of Krivelevich [10] of (2.9) is based on the following result. → R Lemma 2.6. Let H be an arbitrary graph and f : E(H) be a minimum ≤ ∗ ∈ + fractional K -cover. Then τ (H) 3 τ (H) or there is xy E(H) with f(xy) = 0 3 3 2 3 that belongs to at least one triangle of H. ∈ Proof. If there is an edge xy E(H) that does not belong to a triangle, then neces- sarily f(xy) = 0 and xy does not belong to any optimal fractional or integer K -cover. 3 We can remove xy from E(H) without changing the validity of the lemma. Thus, we can assume that every edge of H belongs to a triangle. Suppose that f(xy) > 0 for every edge xy of H, for otherwise we are done. Take a maximum fractional K -packing p. Recall that it is a function that assigns a weight ∈ R 3 p(xyz) to each triangle xyz of H such that for every edge xy the sum of weights + over all K ’s of H containing xy is(cid:88)at most 1, that is, 3 ≤ p(xyz) 1, (2.10) ∈ ∩ z Γ(x) Γ(y) where Γ(v) denotes the set of neighbours of the vertex v in H. This is the dual LP to the minimum fractional K -cover problem. By the comple- 3 mentary slackness condition (since f and p are optimal solutions), we have equality (cid:88) (cid:88) (cid:88) ∈ in (2.10) for every xy E(H). This and the LP duality imply that ∗ ∗ 1 1 τ (H) = ν (H) = p(xyz) = p(xyz) = e(H). 3 3 3 3 ∈ ∈ ∩ triangle xyz xy E(H) z Γ(x) Γ(y) 9 ##LTLine## ##LTLine## ##LTLine##

text: τ

text: (H)

text: ν

text: (H).

text: r

text: r

text: By

text: the

text: result

text: of

text: Haxell

text: and

text: Ro¨dl

text: we

text: have

text: that

text: ν

text: (H)

text: ν

text: (H)

text: r

text: r

text: Krivelevich

text: showed

text: that

text: τ

text: (H)

text: 2τ

text: (H).

text: Thus,

text: τ

text: (H)

text: 2ν

text: (H)

text: giving

text: for

text: r

text: The

text: proof

text: of

text: Krivelevich

text: of

text: is

text: based

text: on

text: the

text: following

text: result.

text: R

text: Lemma

text: Let

text: H

text: be

text: an

text: arbitrary

text: graph

text: and

text: f

text: E(H)

text: be

text: a

text: minimum

text: fractional

text: K

text: -cover.

text: Then

text: τ

text: (H)

text: τ

text: (H)

text: or

text: there

text: is

text: xy

text: E(H)

text: with

text: f(xy)

text: that

text: belongs

text: to

text: at

text: least

text: one

text: triangle

text: of

text: H.

text: Proof.

text: If

text: there

text: is

text: an

text: edge

text: xy

text: E(H)

text: that

text: does

text: not

text: belong

text: to

text: a

text: triangle,

text: then

text: neces-

text: sarily

text: f(xy)

text: and

text: xy

text: does

text: not

text: belong

text: to

text: any

text: optimal

text: fractional

text: or

text: integer

text: K

text: -cover.

text: We

text: can

text: remove

text: xy

text: from

text: E(H)

text: without

text: changing

text: the

text: validity

text: of

text: the

text: lemma.

text: Thus,

text: we

text: can

text: assume

text: that

text: every

text: edge

text: of

text: H

text: belongs

text: to

text: a

text: triangle.

text: Suppose

text: that

text: f(xy)

text: for

text: every

text: edge

text: xy

text: of

text: H,

text: for

text: otherwise

text: we

text: are

text: done.

text: Take

text: a

text: maximum

text: fractional

text: K

text: -packing

text: p.

text: Recall

text: that

text: it

text: is

text: a

text: function

text: that

text: assigns

text: a

text: weight

text: R

text: p(xyz)

text: to

text: each

text: triangle

text: xyz

text: of

text: H

text: such

text: that

text: for

text: every

text: edge

text: xy

text: the

text: sum

text: of

text: weights

text: over

text: all

text: K

text: ’s

text: of

text: H

text: containing

text: xy

text: most

text: that

text: is,

text: p(xyz)

text: z

text: Γ(x)

text: Γ(y)

text: where

text: Γ(v)

text: denotes

text: the

text: set

text: of

text: neighbours

text: of

text: the

text: vertex

text: v

text: in

text: H.

text: This

text: is

text: the

text: dual

text: LP

text: to

text: the

text: minimum

text: fractional

text: K

text: -cover

text: problem.

text: By

text: the

text: comple-

text: mentary

text: slackness

text: condition

text: (since

text: f

text: and

text: p

text: are

text: optimal

text: solutions),

text: we

text: have

text: equality

text: in

text: for

text: every

text: xy

text: E(H).

text: This

text: and

text: the

text: LP

text: duality

text: imply

text: that

text: τ

text: (H)

text: ν

text: (H)

text: p(xyz)

text: p(xyz)

text: e(H).

text: triangle

text: xyz

text: xy

text: E(H)

text: z

text: Γ(x)

text: Γ(y)

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 11 forms. Solving this problem would lead immediately to an improvement for indexed binary jumbled pattern matching. The observation that our language is a bubble language has opened up completely new roads. An eﬃcient implementation of the generating algorithm led to new experimental results which were not available with our previous approach. The obtained data led to new conjectures and results. We are conﬁdent that the connection to bubble languages will also help in establishing theoretical results about the number and structure of preﬁx normal words, and could hopefully lead to a strongly subquadratic testing algorithm. References 1. A. Amir, A. Apostolico, G. M. Landau, and G. Satta. Eﬃcient text ﬁngerprinting via Parikh mapping. J. Discrete Algorithms, 1(5-6):409–421, 2003. 2. G. Badkobeh, G. Fici, S. Kroon, and Zs. Lipt´ak. Binary jumbled string matching for highly run-length compressible texts. Inf. Process. Lett., 113(17):604–608, 2013. 3. G. Benson. Composition alignment. In Proc. of the 3rd International Workshop on Algorithms in Bioinformatics (WABI’03), pages 447–461, 2003. 4. S. Bo¨cker. Simulating multiplexed SNP discovery rates using base-speciﬁc cleavage and mass spec- trometry. Bioinformatics, 23(2):5–12, 2007. 5. S. Bo¨cker, K. Jahn, J. Mixtacki, and J. Stoye. Computation of median gene clusters. In Proc. of the Twelfth Annual International Conference on Computational Molecular Biology (RECOMB 2008), pages 331–345, 2008. LNBI 4955. 6. P. Burcsi, F. Cicalese, G. Fici, and Zs. Lipta´k. On Table Arrangements, Scrabble Freaks, and Jumbled Pattern Matching. In Proc. of the 5th International Conference on Fun with Algorithms (FUN 2010), volume 6099 of LNCS, pages 89–101, 2010. 7. P. Burcsi, F. Cicalese, G. Fici, and Zs. Lipta´k. On approximate jumbled pattern matching in strings. Theory Comput. Syst., 50(1):35–51, 2012. 8. A. Butman, R. Eres, and G. M. Landau. Scaled and permuted string matching. Inf. Process. Lett., 92(6):293–297, 2004. 9. F. Cicalese, G. Fici, and Zs. Lipta´k. Searching for jumbled patterns in strings. In Proc. of the Prague Stringology Conference 2009 (PSC 2009), pages 105–117. Czech Technical University in Prague, 2009. 10. F. Cicalese, T. Gagie, E. Giaquinta, E. S. Laber, Zs. Lipta´k, R. Rizzi, and A. I. Tomescu. Indexes for jumbled pattern matching in strings, trees and graphs. In Proc. of the 20th String Processing and Information Retrieval Symposium (SPIRE 2013), volume 8214 of LNCS, pages 56–63, 2013. 11. F. Cicalese, E. S. Laber, O. Weimann, and R. Yuster. Near linear time construction of an approximate index for all maximum consecutive sub-sums of a sequence. In Proc. 23rd Annual Symposium on Combinatorial Pattern Matching (CPM 2012), volume 7354 of LNCS, pages 149–158, 2012. 12. K. Du¨hrkop, M. Ludwig, M. Meusel, and S. Bo¨cker. Faster mass decomposition. In WABI, pages 45–58, 2013. 13. G. Fici and Zs. Lipta´k. On preﬁx normal words. In Proc. of the 15th Intern. Conf. on Developments in Language Theory (DLT 2011), volume 6795 of LNCS, pages 228–238. Springer, 2011. 14. T. Gagie, D. Hermelin, G. M. Landau, and O. Weimann. Binary jumbled pattern matching on trees and tree-like structures. In Proc. of the 21st Annual European Symposium on Algorithm (ESA 2013), pages 517–528, 2013. 15. E. Giaquinta and Sz. Grabowski. New algorithms for binary jumbled pattern matching. Inf. Process. Lett., 113(14-16):538–542, 2013. 16. L. J. Guibas and A. Odlyzko. Long repetitive patterns in random sequences. Zeitschrift fu¨r Wahrscheinlichkeitstheorie und verwandte Gebeite, 53:241–262, 1980. 17. T. Kociumaka, J. Radoszewski, and W. Rytter. Eﬃcient indexes for jumbled pattern matching with constant-sized alphabet. In Proc. of the 21st Annual European Symposium on Algorithm (ESA 2013), pages 625–636, 2013. 18. L.-K. Lee, M. Lewenstein, and Q. Zhang. Parikh matching in the streaming model. In Proc. of 19th International Symposium on String Processing and Information Retrieval, SPIRE 2012, volume 7608 of Lecture Notes in Computer Science, pages 336–341. Springer, 2012. 19. T. M. Moosa and M. S. Rahman. Indexing permutations for binary strings. Inf. Process. Lett., 110:795–798, 2010. 20. T. M. Moosa and M. S. Rahman. Sub-quadratic time and linear space data structures for permutation matching in binary strings. J. Discrete Algorithms, 10:5–9, 2012.

text: forms.

text: Solving

text: this

text: problem

text: would

text: lead

text: immediately

text: to

text: an

text: improvement

text: for

text: indexed

text: binary

text: jumbled

text: pattern

text: matching.

text: The

text: observation

text: that

text: our

text: language

text: is

text: a

text: bubble

text: language

text: has

text: opened

text: up

text: completely

text: new

text: roads.

text: An

text: eﬃcient

text: implementation

text: of

text: the

text: generating

text: algorithm

text: led

text: to

text: new

text: experimental

text: results

text: which

text: were

text: not

text: available

text: with

text: our

text: previous

text: approach.

text: The

text: obtained

text: data

text: led

text: to

text: new

text: conjectures

text: and

text: results.

text: We

text: are

text: conﬁdent

text: that

text: the

text: connection

text: to

text: bubble

text: languages

text: will

text: also

text: help

text: in

text: establishing

text: theoretical

text: results

text: about

text: the

text: number

text: and

text: structure

text: of

text: preﬁx

text: normal

text: words,

text: and

text: could

text: hopefully

text: lead

text: to

text: a

text: strongly

text: subquadratic

text: testing

text: algorithm.

text: References

label: reference

text: A.

text: Amir,

text: A.

text: Apostolico,

text: G.

text: M.

text: Landau,

text: and

text: G.

text: Satta.

text: Eﬃcient

text: text

text: ﬁngerprinting

text: via

text: Parikh

text: mapping.

text: J.

text: Discrete

text: Algorithms,

text: G.

text: Badkobeh,

text: G.

text: Fici,

text: S.

text: Kroon,

text: and

text: Zs.

text: Lipt´ak.

text: Binary

text: jumbled

text: string

text: matching

text: for

text: highly

text: run-length

text: compressible

text: texts.

text: Inf.

text: Process.

text: Lett.,

text: G.

text: Benson.

text: Composition

text: alignment.

text: In

text: Proc.

text: of

text: the

text: International

text: Workshop

text: on

text: Algorithms

text: in

text: Bioinformatics

text: pages

text: S.

text: Bo¨cker.

text: Simulating

text: multiplexed

text: SNP

text: discovery

text: rates

text: using

text: base-speciﬁc

text: cleavage

text: and

text: mass

text: spec-

text: trometry.

text: Bioinformatics,

text: S.

text: Bo¨cker,

text: K.

text: Jahn,

text: J.

text: Mixtacki,

text: and

text: J.

text: Stoye.

text: Computation

text: of

text: median

text: gene

text: clusters.

text: In

text: Proc.

text: of

text: the

text: Twelfth

text: Annual

text: International

text: Conference

text: on

text: Computational

text: Molecular

text: Biology

text: (RECOMB

text: pages

text: LNBI

text: P.

text: Burcsi,

text: F.

text: Cicalese,

text: G.

text: Fici,

text: and

text: Zs.

text: Lipta´k.

text: On

text: Table

text: Arrangements,

text: Scrabble

text: Freaks,

text: and

text: Jumbled

text: Pattern

text: Matching.

text: In

text: Proc.

text: of

text: the

text: International

text: Conference

text: on

text: Fun

text: with

text: Algorithms

text: (FUN

text: volume

text: of

text: LNCS,

text: pages

text: P.

text: Burcsi,

text: F.

text: Cicalese,

text: G.

text: Fici,

text: and

text: Zs.

text: Lipta´k.

text: On

text: approximate

text: jumbled

text: pattern

text: matching

text: in

text: strings.

text: Theory

text: Comput.

text: Syst.,

text: A.

text: Butman,

text: R.

text: Eres,

text: and

text: G.

text: M.

text: Landau.

text: Scaled

text: and

text: permuted

text: string

text: matching.

text: Inf.

text: Process.

text: Lett.,

text: F.

text: Cicalese,

text: G.

text: Fici,

text: and

text: Zs.

text: Lipta´k.

text: Searching

text: for

text: jumbled

text: patterns

text: in

text: strings.

text: In

text: Proc.

text: of

text: the

text: Prague

text: Stringology

text: Conference

text: (PSC

text: pages

text: Czech

text: Technical

text: University

text: in

text: Prague,

text: F.

text: Cicalese,

text: T.

text: Gagie,

text: E.

text: Giaquinta,

text: E.

text: S.

text: Laber,

text: Zs.

text: Lipta´k,

text: R.

text: Rizzi,

text: and

text: A.

text: I.

text: Tomescu.

text: Indexes

text: for

text: jumbled

text: pattern

text: matching

text: in

text: strings,

text: trees

text: and

text: graphs.

text: In

text: Proc.

text: of

text: the

text: String

text: Processing

text: and

text: Information

text: Retrieval

text: Symposium

text: (SPIRE

text: volume

text: of

text: LNCS,

text: pages

text: F.

text: Cicalese,

text: E.

text: S.

text: Laber,

text: O.

text: Weimann,

text: and

text: R.

text: Yuster.

text: Near

text: linear

text: time

text: construction

text: of

text: an

text: approximate

text: index

text: for

text: all

text: maximum

text: consecutive

text: sub-sums

text: of

text: a

text: sequence.

text: In

text: Proc.

text: Annual

text: Symposium

text: on

text: Combinatorial

text: Pattern

text: Matching

text: (CPM

text: volume

text: of

text: LNCS,

text: pages

text: K.

text: Du¨hrkop,

text: M.

text: Ludwig,

text: M.

text: Meusel,

text: and

text: S.

text: Bo¨cker.

text: Faster

text: mass

text: decomposition.

text: In

text: WABI,

text: pages

text: G.

text: Fici

text: and

text: Zs.

text: Lipta´k.

text: On

text: preﬁx

text: normal

text: words.

text: In

text: Proc.

text: of

text: the

text: Intern.

text: Conf.

text: on

text: Developments

text: in

text: Language

text: Theory

text: (DLT

text: volume

text: of

text: LNCS,

text: pages

text: Springer,

text: T.

text: Gagie,

text: D.

text: Hermelin,

text: G.

text: M.

text: Landau,

text: and

text: O.

text: Weimann.

text: Binary

text: jumbled

text: pattern

text: matching

text: on

text: trees

text: and

text: tree-like

text: structures.

text: In

text: Proc.

text: of

text: the

text: Annual

text: European

text: Symposium

text: on

text: Algorithm

text: (ESA

text: pages

text: E.

text: Giaquinta

text: and

text: Sz.

text: Grabowski.

text: New

text: algorithms

text: for

text: binary

text: jumbled

text: pattern

text: matching.

text: Inf.

text: Process.

text: Lett.,

text: L.

text: J.

text: Guibas

text: and

text: A.

text: Odlyzko.

text: Long

text: repetitive

text: patterns

text: in

text: random

text: sequences.

text: Zeitschrift

text: fu¨r

text: Wahrscheinlichkeitstheorie

text: und

text: verwandte

text: Gebeite,

text: T.

text: Kociumaka,

text: J.

text: Radoszewski,

text: and

text: W.

text: Rytter.

text: Eﬃcient

text: indexes

text: for

text: jumbled

text: pattern

text: matching

text: with

text: constant-sized

text: alphabet.

text: In

text: Proc.

text: of

text: the

text: Annual

text: European

text: Symposium

text: on

text: Algorithm

text: (ESA

text: pages

text: L.-K.

text: Lee,

text: M.

text: Lewenstein,

text: and

text: Q.

text: Zhang.

text: Parikh

text: matching

text: in

text: the

text: streaming

text: model.

text: In

text: Proc.

text: of

text: International

text: Symposium

text: on

text: String

text: Processing

text: and

text: Information

text: Retrieval,

text: SPIRE

text: volume

text: of

text: Lecture

text: Notes

text: in

text: Computer

text: Science,

text: pages

text: Springer,

text: T.

text: M.

text: Moosa

text: and

text: M.

text: S.

text: Rahman.

text: Indexing

text: permutations

text: for

text: binary

text: strings.

text: Inf.

text: Process.

text: Lett.,

text: T.

text: M.

text: Moosa

text: and

text: M.

text: S.

text: Rahman.

text: Sub-quadratic

text: time

text: and

text: linear

text: space

text: data

text: structures

text: for

text: permutation

text: matching

text: in

text: binary

text: strings.

text: J.

text: Discrete

text: Algorithms,


text: Journal of Machine Learning Research vol (year) pages Submitted 1/14; Revised 7/14; Published pub Local Identiﬁcation of Overcomplete Dictionaries Karin Schnass karin.schnass@uibk.ac.at Department of Mathematics University of Innsbruck Technikerstraße 19a 6020 Innsbruck, Austria Editor: Shie Mannor Abstract This paper presents the ﬁrst theoretical results showing that stable identiﬁcation of over- complete µ-coherent dictionaries Φ ∈ Rd×K is locally possible from train√ing signals with − sparsity levels S up to the order O(µ 2) and signal to noise ratios up to O( d). In particu- lar the dictionary is recoverable as the local maximum of a new maximisation criterion that generalises the K-means criterion. For this maximisation criterion results for asymptotic exact recovery for sparsity levels up to O(µ−1) and √stable recovery for sparsity levels up − to O(µ 2) as well as signal to noise ratios up to O( d) are provided. These asymptotic results translate to ﬁnite sample size recovery results with high probability as long as the − sample size N scales as O(K3dSε˜ 2), where the recovery precision ε˜ can go down to the asymptotically achievable precision. Further, to actually ﬁnd the local maxima of the new criterion, a very simple Iterative Thresholding and K (signed) Means algorithm (ITKM), which has complexity O(dKN) in each iteration, is presented and its local eﬃciency is demonstrated in several experiments. Keywords: dictionary learning, dictionary identiﬁcation, sparse coding, sparse compo- nent analysis, vector quantisation, K-means, ﬁnite sample size, sample complexity, max- imisation criterion, sparse representation 1. Introduction Be it the 300 million photos uploaded to Facebook per day, the 800GB the large Hadron collider records per second or the 320.000GB per second it cannot record, it is clear that we have reached the age of big data. Indeed, in 2012, the amount of data existing worldwide is estimated to have reached 2.8 ZB = 2.800 billion GB and while 23 % of these data are expected to be useful if analysed, only 1% actually are. So how do we deal with this big data challenge? The key concept, that has driven data processing and data analysis in the past decade, is that even high-dimensional data has intrinsically low complexity, meaning that every data point y can be represented as linear combination of a sparse (small) number ∈ R (cid:107) (cid:107) (cid:88) of elements or atoms φ d, φ = 1 of an overcomplete dictionary Φ = (φ , . . . φ ), that i 2 1 K is, ≈ y Φ x = x(i)ϕ , I I i ∈ i I | | (cid:28) ≤ for a set I of size S, I = S, which is small compared to the ambient dimension, S d K. These sparse components do not only describe the data but the representations can also be (cid:13) c year Karin Schnass. ##LTLine## ##LTLine##

text: Journal

text: of

text: Machine

text: Learning

text: Research

text: vol

text: (year)

text: pages

text: Submitted

text: Revised

text: Published

text: pub

text: Local

text: Identiﬁcation

text: of

text: Overcomplete

text: Dictionaries

text: Karin

text: Schnass

text: karin.schnass@uibk.ac.at

text: Department

text: of

text: Mathematics

text: University

text: of

text: Innsbruck

text: Technikerstraße

text: Innsbruck,

text: Austria

text: Editor:

text: Shie

text: Mannor

text: Abstract

text: This

text: paper

text: presents

text: the

text: ﬁrst

text: theoretical

text: results

text: showing

text: that

text: stable

text: identiﬁcation

text: of

text: over-

text: complete

text: µ-coherent

text: dictionaries

text: Φ

text: Rd×K

text: is

text: locally

text: possible

text: from

text: train√ing

text: signals

text: with

text: sparsity

text: levels

text: S

text: up

text: to

text: the

text: order

text: O(µ

text: and

text: signal

text: to

text: noise

text: ratios

text: up

text: to

text: O(

text: d).

text: In

text: particu-

text: lar

text: the

text: dictionary

text: is

text: recoverable

text: as

text: the

text: local

text: maximum

text: of

text: a

text: new

text: maximisation

text: criterion

text: that

text: generalises

text: the

text: K-means

text: criterion.

text: For

text: this

text: maximisation

text: criterion

text: results

text: for

text: asymptotic

text: exact

text: recovery

text: for

text: sparsity

text: levels

text: up

text: to

text: and

text: √stable

text: recovery

text: for

text: sparsity

text: levels

text: up

text: to

text: O(µ

text: as

text: well

text: as

text: signal

text: to

text: noise

text: ratios

text: up

text: to

text: O(

text: d)

text: are

text: provided.

text: These

text: asymptotic

text: results

text: translate

text: to

text: ﬁnite

text: sample

text: size

text: recovery

text: results

text: with

text: high

text: probability

text: as

text: long

text: as

text: the

text: sample

text: size

text: N

text: scales

text: as

text: where

text: the

text: recovery

text: precision

text: ε˜

text: can

text: go

text: down

text: to

text: the

text: asymptotically

text: achievable

text: precision.

text: Further,

text: to

text: actually

text: ﬁnd

text: the

text: local

text: maxima

text: of

text: the

text: new

text: criterion,

text: a

text: very

text: simple

text: Iterative

text: Thresholding

text: and

text: K

text: (signed)

text: Means

text: algorithm

text: (ITKM),

text: which

text: has

text: complexity

text: O(dKN)

text: in

text: each

text: iteration,

text: is

text: presented

text: and

text: its

text: local

text: eﬃciency

text: is

text: demonstrated

text: in

text: several

text: experiments.

text: Keywords:

text: dictionary

text: learning,

text: dictionary

text: identiﬁcation,

text: sparse

text: coding,

text: sparse

text: compo-

text: nent

text: analysis,

text: vector

text: quantisation,

text: K-means,

text: ﬁnite

text: sample

text: size,

text: sample

text: complexity,

text: max-

text: imisation

text: criterion,

text: sparse

text: representation

text: Introduction

text: Be

text: it

text: the

text: million

text: photos

text: uploaded

text: to

text: Facebook

text: per

text: day,

text: the

text: the

text: large

text: Hadron

text: collider

text: records

text: per

text: second

text: or

text: the

text: per

text: second

text: it

text: cannot

text: record,

text: it

text: is

text: clear

text: that

text: we

text: have

text: reached

text: the

text: age

text: of

text: big

text: data.

text: Indeed,

text: in

text: the

text: amount

text: of

text: data

text: existing

text: worldwide

text: is

text: estimated

text: to

text: have

text: reached

text: ZB

text: billion

text: GB

text: and

text: while

text: of

text: these

text: data

text: are

text: expected

text: to

text: be

text: useful

text: if

text: analysed,

text: only

text: actually

text: are.

text: So

text: how

text: do

text: we

text: deal

text: with

text: this

text: big

text: data

text: challenge?

text: The

text: key

text: concept,

text: that

text: has

text: driven

text: data

text: processing

text: and

text: data

text: analysis

text: in

text: the

text: past

text: decade,

text: is

text: that

text: even

text: high-dimensional

text: data

text: has

text: intrinsically

text: low

text: complexity,

text: meaning

text: that

text: every

text: data

text: point

text: y

text: can

text: be

text: represented

text: as

text: linear

text: combination

text: of

text: a

text: sparse

text: (small)

text: number

text: R

text: of

text: elements

text: or

text: atoms

text: φ

text: d,

text: φ

text: of

text: an

text: overcomplete

text: dictionary

text: Φ

text: (φ

text: φ

text: that

text: i

text: K

text: is,

text: y

text: Φ

text: x

text: x(i)ϕ

text: I

text: I

text: i

text: i

text: I

text: for

text: a

text: set

text: I

text: of

text: size

text: S,

text: I

text: S,

text: which

text: is

text: small

text: compared

text: to

text: the

text: ambient

text: dimension,

text: S

text: d

text: K.

text: These

text: sparse

text: components

text: do

text: not

text: only

text: describe

text: the

text: data

text: but

text: the

text: representations

text: can

text: also

text: be

text: c

text: year

text: Karin

text: Schnass.

text: ##LTLine##

text: ##LTLine##


text: Karin Schnass ψnew = 0. For example we can choose the zero-updated atom uniformly at random from k the unit sphere or from the input signals. Note that ﬁnding the sets I(Ψold, y ) corresponds to N thresholding operations while up- n dating according to (14) corresponds to K signed means. Altogether this means that each iteration of ITKM has computational complexity determined by the matrix multiplication Ψ(cid:63)Y , meaning O(dKN). This is light in comparison to K-SVD, which even when using thresholding instead of OMP as sparse approximation procedure still requires the calculation × of the maximal singular vector of K on average d N matrices. It is also more compu- K tationally eﬃcient than the algorithm for local dictionary reﬁnement, proposed in Arora et al. (2014), which is also based on averaging. Furthermore it is straightforward to derive online or parallelised versions of ITKM. In an online version for each newly arriving signal (cid:104) (cid:105) y we calculate I(Ψold, y ) using thresholding and update ψnew = ψnew + sign( ψold, y )y n ∈ n k k k n n for k I(Ψold, y ). After N signals have been processed we renormalise the atoms ψnew n (cid:80) k to have unit norm and set Ψold = Ψnew. Similarly, to parallelise we divide the training samples into m sets of size N . Then on each node m we learn a dictionary Ψnew according m m to (14) with λ = 1. We then calculate the sum of these dictionaries Ψnew = Ψnew and k 0 m m renormalise the atoms in Ψnew to have unit norm. 0 Armed with this very simple algorithm we will now conduct four experiments to illustrate our theoretical ﬁndings1. Signal Model Given the generating dictionary Φ our signal model further depends on four coeﬃcient parameters, S - the eﬀective sparsity or number of comparatively large coeﬃcients, b - deciding the decay factor of these sparse coeﬃcients, ≥ T - the total number of non-zero coeﬃcients (T S) and ρ - the noise level. √ Given these parameters we choose a decay factor c uniformly at random in the interval − ≤ ≤ b ≤ [1 b, 1]. We set c = ci/ S for 1 i S and c = 0 for T < i K. If T = S i b i we renormalise the sequence to have unit norm, while if T > S we choose the vector (cid:112) (c , . . . , c ) uniformly at random on the sphere of radius R, where R is chosen such that S+1 T the resulting sequence c has unit norm. We then choose a permutation p and a sign sequence (cid:107) (cid:107) σ uniformly at random and set y = Φc , respectively y = (Φc + r)/ 1 + r where r p,σ p,σ 2 is a Gaussian noise-vector with variance ρ2 if ρ > 0. Table 1: Signal Model 6.1 ITKM vs. K-SVD In our ﬁrst experiment we compare the local recovery error of ITKM and K-SVD for 3-dimensional bases with increasing condition numbers. The bases are perturbations of the canonical basis Φ = (e , e , e ) with the vector v = 1 2 3 1. A Matlab penknife (mini-toolbox) for playing around with ITKM and reproducing the experiments can be found at http://homepage.uibk.ac.at/~c7021041/ITKM.zip 14 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Karin

text: Schnass

text: ψnew

text: For

text: example

text: we

text: can

text: choose

text: the

text: zero-updated

text: atom

text: uniformly

text: at

text: random

text: from

text: k

text: the

text: unit

text: sphere

text: or

text: from

text: the

text: input

text: signals.

text: Note

text: that

text: ﬁnding

text: the

text: sets

text: I(Ψold,

text: y

text: corresponds

text: to

text: N

text: thresholding

text: operations

text: while

text: up-

text: n

text: dating

text: according

text: to

text: corresponds

text: to

text: K

text: signed

text: means.

text: Altogether

text: this

text: means

text: that

text: each

text: iteration

text: of

text: ITKM

text: has

text: computational

text: complexity

text: determined

text: by

text: the

text: matrix

text: multiplication

text: meaning

text: O(dKN).

text: This

text: is

text: light

text: in

text: comparison

text: to

text: K-SVD,

text: which

text: even

text: when

text: using

text: thresholding

text: instead

text: of

text: OMP

text: as

text: sparse

text: approximation

text: procedure

text: still

text: requires

text: the

text: calculation

text: of

text: the

text: maximal

text: singular

text: vector

text: of

text: K

text: on

text: average

text: d

text: N

text: matrices.

text: It

text: is

text: also

text: more

text: compu-

text: K

text: tationally

text: eﬃcient

text: than

text: the

text: algorithm

text: for

text: local

text: dictionary

text: reﬁnement,

text: proposed

text: in

text: Arora

text: et

text: al.

text: which

text: is

text: also

text: based

text: on

text: averaging.

text: Furthermore

text: it

text: is

text: straightforward

text: to

text: derive

text: online

text: or

text: parallelised

text: versions

text: of

text: ITKM.

text: In

text: an

text: online

text: version

text: for

text: each

text: newly

text: arriving

text: signal

text: y

text: we

text: calculate

text: I(Ψold,

text: y

text: using

text: thresholding

text: and

text: update

text: ψnew

text: ψnew

text: sign(

text: ψold,

text: y

text: )y

text: n

text: n

text: k

text: k

text: k

text: n

text: n

text: for

text: k

text: I(Ψold,

text: y

text: After

text: N

text: signals

text: have

text: been

text: processed

text: we

text: renormalise

text: the

text: atoms

text: ψnew

text: n

text: k

text: to

text: have

text: unit

text: norm

text: and

text: set

text: Ψold

text: Ψnew.

text: Similarly,

text: to

text: parallelise

text: we

text: divide

text: the

text: training

text: samples

text: into

text: m

text: sets

text: of

text: size

text: N

text: Then

text: on

text: each

text: node

text: m

text: we

text: learn

text: a

text: dictionary

text: Ψnew

text: according

text: m

text: m

text: to

text: with

text: λ

text: We

text: then

text: calculate

text: the

text: sum

text: of

text: these

text: dictionaries

text: Ψnew

text: Ψnew

text: and

text: k

text: m

text: m

text: renormalise

text: the

text: atoms

text: in

text: Ψnew

text: to

text: have

text: unit

text: norm.

text: Armed

text: with

text: this

text: very

text: simple

text: algorithm

text: we

text: will

text: now

text: conduct

text: four

text: experiments

text: to

text: illustrate

text: our

text: theoretical

text: Signal

text: Model

text: Given

text: the

text: generating

text: dictionary

text: Φ

text: our

text: signal

text: model

text: further

text: depends

text: on

text: four

text: coeﬃcient

text: parameters,

text: S

text: the

text: eﬀective

text: sparsity

text: or

text: number

text: of

text: comparatively

text: large

text: coeﬃcients,

text: b

text: deciding

text: the

text: decay

text: factor

text: of

text: these

text: sparse

text: coeﬃcients,

text: T

text: the

text: total

text: number

text: of

text: non-zero

text: coeﬃcients

text: (T

text: S)

text: and

text: ρ

text: the

text: noise

text: level.

text: Given

text: these

text: parameters

text: we

text: choose

text: a

text: decay

text: factor

text: c

text: uniformly

text: at

text: random

text: in

text: the

text: interval

text: b

text: b,

text: We

text: set

text: c

text: ci/

text: S

text: for

text: i

text: S

text: and

text: c

text: for

text: T

text: i

text: K.

text: If

text: T

text: S

text: i

text: b

text: i

text: we

text: renormalise

text: the

text: sequence

text: to

text: have

text: unit

text: norm,

text: while

text: if

text: T

text: S

text: we

text: choose

text: the

text: vector

text: (c

text: c

text: uniformly

text: at

text: random

text: on

text: the

text: sphere

text: of

text: radius

text: R,

text: where

text: R

text: is

text: chosen

text: such

text: that

text: T

text: the

text: resulting

text: sequence

text: c

text: has

text: unit

text: norm.

text: We

text: then

text: choose

text: a

text: permutation

text: p

text: and

text: a

text: sign

text: sequence

text: σ

text: uniformly

text: at

text: random

text: and

text: set

text: y

text: Φc

text: respectively

text: y

text: (Φc

text: r)/

text: r

text: where

text: r

text: p,σ

text: p,σ

text: is

text: a

text: Gaussian

text: noise-vector

text: with

text: variance

text: ρ2

text: if

text: ρ

text: Table

text: Signal

text: Model

text: ITKM

text: vs.

text: K-SVD

text: In

text: our

text: ﬁrst

text: experiment

text: we

text: compare

text: the

text: local

text: recovery

text: error

text: of

text: ITKM

text: and

text: K-SVD

text: for

text: bases

text: with

text: increasing

text: condition

text: numbers.

text: The

text: bases

text: are

text: perturbations

text: of

text: the

text: canonical

text: basis

text: Φ

text: (e

text: e

text: e

text: with

text: the

text: vector

text: v

text: A

text: Matlab

text: penknife

text: (mini-toolbox)

text: for

text: playing

text: around

text: with

text: ITKM

text: and

text: reproducing

text: the

text: experiments

text: can

text: be

text: found

text: at

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Karin Schnass maximisers that have not all, but only most atoms in common with what seems to be the global maximiser near the generating dictionary. This behaviour is in strong contrast to the algorithms presented in Arora et al. (2014); Agarwal et al. (2014b), that have global success guarantees at a computational cost of the order O(dN2), and leads to several very √ important research directions. First we want to conﬁrm that ITKM has a convergence radius of the order O(1/ S). This is suggested by the derived radius of the area on which the generating dictionary is the opti- mal maximiser as well as preliminary experiments. Alternatively, we could investigate how the results for the local iterative algorithms in Arora et al. (2014); Agarwal et al. (2014a) could be extended to larger sparsity levels and convergence radii using our techniques. The associated important question is how to extend the results for the algorithms presented in − Arora et al. (2014); Agarwal et al. (2014b) to sparsity levels O(µ 2), if possible at lower cost than O(dN2). Given the conjectured size of the convergence radius for ITKM it would √ even be suﬃcient for the output of the algorithm to arrive at a dictionary within distance O(1/ S) to the generating dictionary, since the output could then be used as initialisation for ITKM. − A parallel approach for getting global identiﬁcation results for sparsity levels O(µ 2), that we are currently pursuing, is to analyse a version of ITKM using residual instead of pure signal means, which in preliminary experiments exhibits global convergence properties. The last research directions we want to point out are concerned with the realism of the − signal model. The fact that for an input sparsity S a gap of order O(µ 2) between the S and S + 1 largest coeﬃcient is suﬃcient can be interpreted as a relaxed dependence of the − algorithm on the sparsity parameter, since a gap of order µ 2 can occur quite frequently. To further decrease this sensitivity to the sparsity parameter in the criterion and the algorithm we would therefore like to extend our results to the case where we can only guarantee a gap − of order O(µ 2) between the S largest and the S + T largest coeﬃcient for some T > 1. Last but not least we would like to exactly reﬂect the practical situation, where we would normalise our training signals to equally weight their importance and analyse the unit norm (cid:107) (cid:107) signal model where y = Φx + r/ Φx + r . 2 Acknowledgments This work was supported by the Austrian Science Fund (FWF) under Grant no. J3335 and improved thanks to the reviewers’ comments and suggestions. Thanks also go to the Computer Vision Laboratory of the University of Sassari, Italy, which provided the sur- roundings, where almost all of the presented work was done, and to Michael Dymond, who looked over the ﬁnal manuscript with a native speaker’s eye. Appendix A. Proofs A.1 Proof of Theorem 2 We ﬁrst reformulate and prove the theorem for the simple case of a symmetric coeﬃcient distribution based on one sequence and then use an integration argument to extend it to the general case. 18 ##LTLine## ##LTLine##

text: Karin

text: Schnass

text: maximisers

text: that

text: have

text: not

text: all,

text: but

text: only

text: most

text: atoms

text: in

text: common

text: with

text: what

text: seems

text: to

text: be

text: the

text: global

text: maximiser

text: near

text: the

text: generating

text: dictionary.

text: This

text: behaviour

text: is

text: in

text: strong

text: contrast

text: to

text: the

text: algorithms

text: presented

text: in

text: Arora

text: et

text: al.

text: Agarwal

text: et

text: al.

text: that

text: have

text: global

text: success

text: guarantees

text: at

text: a

text: computational

text: cost

text: of

text: the

text: order

text: and

text: leads

text: to

text: several

text: very

text: important

text: research

text: directions.

text: First

text: we

text: want

text: to

text: conﬁrm

text: that

text: ITKM

text: has

text: a

text: convergence

text: radius

text: of

text: the

text: order

text: S).

text: This

text: is

text: suggested

text: by

text: the

text: derived

text: radius

text: of

text: the

text: area

text: on

text: which

text: the

text: generating

text: dictionary

text: is

text: the

text: opti-

text: mal

text: maximiser

text: as

text: well

text: as

text: preliminary

text: experiments.

text: Alternatively,

text: we

text: could

text: investigate

text: how

text: the

text: results

text: for

text: the

text: local

text: iterative

text: algorithms

text: in

text: Arora

text: et

text: al.

text: Agarwal

text: et

text: al.

text: could

text: be

text: extended

text: to

text: larger

text: sparsity

text: levels

text: and

text: convergence

text: radii

text: using

text: our

text: techniques.

text: The

text: associated

text: important

text: question

text: is

text: how

text: to

text: extend

text: the

text: results

text: for

text: the

text: algorithms

text: presented

text: in

text: Arora

text: et

text: al.

text: Agarwal

text: et

text: al.

text: to

text: sparsity

text: levels

text: O(µ

text: if

text: possible

text: at

text: lower

text: cost

text: than

text: Given

text: the

text: conjectured

text: size

text: of

text: the

text: convergence

text: radius

text: for

text: ITKM

text: it

text: would

text: even

text: be

text: suﬃcient

text: for

text: the

text: output

text: of

text: the

text: algorithm

text: to

text: arrive

text: at

text: a

text: dictionary

text: within

text: distance

text: S)

text: to

text: the

text: generating

text: dictionary,

text: since

text: the

text: output

text: could

text: then

text: be

text: used

text: as

text: initialisation

text: for

text: ITKM.

text: A

text: parallel

text: approach

text: for

text: getting

text: global

text: identiﬁcation

text: results

text: for

text: sparsity

text: levels

text: O(µ

text: that

text: we

text: are

text: currently

text: pursuing,

text: is

text: to

text: analyse

text: a

text: version

text: of

text: ITKM

text: using

text: residual

text: instead

text: of

text: pure

text: signal

text: means,

text: which

text: in

text: preliminary

text: experiments

text: exhibits

text: global

text: convergence

text: properties.

text: The

text: last

text: research

text: directions

text: we

text: want

text: to

text: point

text: out

text: are

text: concerned

text: with

text: the

text: realism

text: of

text: the

text: signal

text: model.

text: The

text: fact

text: that

text: for

text: an

text: input

text: sparsity

text: S

text: a

text: gap

text: of

text: order

text: O(µ

text: between

text: the

text: S

text: and

text: S

text: largest

text: coeﬃcient

text: is

text: suﬃcient

text: can

text: be

text: interpreted

text: as

text: a

text: relaxed

text: dependence

text: of

text: the

text: algorithm

text: on

text: the

text: sparsity

text: parameter,

text: since

text: a

text: gap

text: of

text: order

text: µ

text: can

text: occur

text: quite

text: frequently.

text: To

text: further

text: decrease

text: this

text: sensitivity

text: to

text: the

text: sparsity

text: parameter

text: in

text: the

text: criterion

text: and

text: the

text: algorithm

text: we

text: would

text: therefore

text: like

text: to

text: extend

text: our

text: results

text: to

text: the

text: case

text: where

text: we

text: can

text: only

text: guarantee

text: a

text: gap

text: of

text: order

text: O(µ

text: between

text: the

text: S

text: largest

text: and

text: the

text: S

text: T

text: largest

text: coeﬃcient

text: for

text: some

text: T

text: Last

text: but

text: not

text: least

text: we

text: would

text: like

text: to

text: exactly

text: reﬂect

text: the

text: practical

text: situation,

text: where

text: we

text: would

text: normalise

text: our

text: training

text: signals

text: to

text: equally

text: weight

text: their

text: importance

text: and

text: analyse

text: the

text: unit

text: norm

text: signal

text: model

text: where

text: y

text: Φx

text: r/

text: Φx

text: r

text: Acknowledgments

text: This

text: work

text: was

text: supported

text: by

text: the

text: Austrian

text: Science

text: Fund

text: (FWF)

text: under

text: Grant

text: no.

text: and

text: improved

text: thanks

text: to

text: the

text: reviewers’

text: comments

text: and

text: suggestions.

text: Thanks

text: also

text: go

text: to

text: the

text: Computer

text: Vision

text: Laboratory

text: of

text: the

text: University

text: of

text: Sassari,

text: Italy,

text: which

text: provided

text: the

text: sur-

text: roundings,

text: where

text: almost

text: all

text: of

text: the

text: presented

text: work

text: was

text: done,

text: and

text: to

text: Michael

text: Dymond,

text: who

text: looked

text: over

text: the

text: ﬁnal

text: manuscript

text: with

text: a

text: native

text: speaker’s

text: eye.

text: Appendix

text: A.

text: Proofs

text: Proof

text: of

text: Theorem

text: We

text: ﬁrst

text: reformulate

text: and

text: prove

text: the

text: theorem

text: for

text: the

text: simple

text: case

text: of

text: a

text: symmetric

text: coeﬃcient

text: distribution

text: based

text: on

text: one

text: sequence

text: and

text: then

text: use

text: an

text: integration

text: argument

text: to

text: extend

text: it

text: to

text: the

text: general

text: case.

text: ##LTLine##

text: ##LTLine##


text: Local Identification of Overcomplete Dictionaries iterative algorithm, based on thresholding and K signed means, is locally successful. The paper is organised as follows. After introducing all necessary notation in Section we present a new optimisation criterion, motivated by the analysis of the K-SVD principle, (Schnass, 2014), in Section . In Section we give asymptotic identiﬁcation results both for exact and stable recovery, which in Section 5 are extended to results to ﬁnite sample sizes. Section 6 provides an algorithm for actually ﬁnding a local optimum and some experiments conﬁrming the theoretical results. Finally in the last section we compare the results for the new criterion to existing identiﬁcation results, discuss the implications of these local results for global dictionary identiﬁcation algorithms and point out directions for future research. 2. Notations and Conventions Before we jump into the fray, we collect some deﬁnitions and lose a few words on notations; usually subscripted letters will denote vectors with the exception of c and ε ∈ R × ∈ R where they are numbers, eg. (x , . . . , x ) = X d K vs. c = (c , . . . , c ) K, however, 1 K 1 K it should always be clear from the context what we are dealing with. ∈ R (cid:107) (cid:107) We consider a dictionary Φ a collection of K unit norm vectors φ d, φ = 1. By × i i 2 abuse of notation we will also refer to the d K matrix collecting the atoms as its columns as the dictionary, that is Φ = (φ , . . . φ ). The maximal absolute inner product between two i K |(cid:104) (cid:105)| diﬀerent atoms is called the coherence µ of the dictionary, µ = max (cid:54) φ , φ . By Φ we i=j i j I denote the restriction of the dictionary to the atoms indexed by I, that is Φ = (φ . . . φ ), ∈ I i1 iS i I. We indicate the conjugate transpose of a matrix with a (cid:63), for example Φ(cid:63) would be j the transpose of Φ. × D The set of all dictionaries of a given size (d K) is denoted by . For two dictionaries ∈ D Φ, Ψ we deﬁne the distance between each other as the maximal distance between two corresponding atoms, (cid:107) − (cid:107) d(Φ, Ψ) := max φ ψ . i i 2 i ≥ ∈ R We consider a frame F a collection of K d vectors f d for which there exist two ∈ R i positive frame constants A, B such that for all v d we have (cid:88) K (cid:107) (cid:107) ≤ |(cid:104) (cid:105)| ≤ (cid:107) (cid:107) A v 2 f , v 2 B v 2. (1) 2 i 2 i=1 × √ √ From (1) it follows that F , interpreted as d K matrix, has rank d and that its non-zero singular values are in the interval [ A, B]. If B can be chosen equal to A, that is B = A, the frame is called tight. If all frame elements f have unit norm, we call F a unit norm i frame. For more details on frames, see e.g. Christensen (2003). Finally we introduce the Landau symbols O, o to characterise the growth of a function. We write 3 ##LTLine## ##LTLine##

text: Local

text: Identification

text: of

text: Overcomplete

text: Dictionaries

text: iterative

text: algorithm,

text: based

text: on

text: thresholding

text: and

text: K

text: signed

text: means,

text: is

text: locally

text: successful.

text: The

text: paper

text: is

text: organised

text: as

text: follows.

text: After

text: introducing

text: all

text: necessary

text: notation

text: in

text: Section

text: we

text: present

text: a

text: new

text: optimisation

text: criterion,

text: motivated

text: by

text: the

text: analysis

text: of

text: the

text: K-SVD

text: principle,

text: (Schnass,

text: in

text: Section

text: In

text: Section

text: we

text: give

text: asymptotic

text: identiﬁcation

text: results

text: both

text: for

text: exact

text: and

text: stable

text: recovery,

text: which

text: in

text: Section

text: are

text: extended

text: to

text: results

text: to

text: ﬁnite

text: sample

text: sizes.

text: Section

text: provides

text: an

text: algorithm

text: for

text: actually

text: ﬁnding

text: a

text: local

text: optimum

text: and

text: some

text: experiments

text: conﬁrming

text: the

text: theoretical

text: results.

text: Finally

text: in

text: the

text: last

text: section

text: we

text: compare

text: the

text: results

text: for

text: the

text: new

text: criterion

text: to

text: existing

text: identiﬁcation

text: results,

text: discuss

text: the

text: implications

text: of

text: these

text: local

text: results

text: for

text: global

text: dictionary

text: identiﬁcation

text: algorithms

text: and

text: point

text: out

text: directions

text: for

text: future

text: research.

text: Notations

text: and

text: Conventions

text: Before

text: we

text: jump

text: into

text: the

text: fray,

text: we

text: collect

text: some

text: deﬁnitions

text: and

text: lose

text: a

text: few

text: words

text: on

text: notations;

text: usually

text: subscripted

text: letters

text: will

text: denote

text: vectors

text: with

text: the

text: exception

text: of

text: c

text: and

text: ε

text: R

text: R

text: where

text: they

text: are

text: numbers,

text: eg.

text: (x

text: x

text: X

text: d

text: K

text: vs.

text: c

text: (c

text: c

text: K,

text: however,

text: K

text: K

text: it

text: should

text: always

text: be

text: clear

text: from

text: the

text: context

text: what

text: we

text: are

text: dealing

text: with.

text: R

text: We

text: consider

text: a

text: dictionary

text: Φ

text: a

text: collection

text: of

text: K

text: unit

text: norm

text: vectors

text: φ

text: d,

text: φ

text: By

text: i

text: i

text: abuse

text: of

text: notation

text: we

text: will

text: also

text: refer

text: to

text: the

text: d

text: K

text: matrix

text: collecting

text: the

text: atoms

text: as

text: its

text: columns

text: as

text: the

text: dictionary,

text: that

text: is

text: Φ

text: (φ

text: φ

text: The

text: maximal

text: absolute

text: inner

text: product

text: between

text: two

text: i

text: K

text: diﬀerent

text: atoms

text: is

text: called

text: the

text: coherence

text: µ

text: of

text: the

text: dictionary,

text: µ

text: max

text: φ

text: φ

text: By

text: Φ

text: we

text: i=j

text: i

text: j

text: I

text: denote

text: the

text: restriction

text: of

text: the

text: dictionary

text: to

text: the

text: atoms

text: indexed

text: by

text: I,

text: that

text: is

text: Φ

text: (φ

text: φ

text: I

text: iS

text: i

text: I.

text: We

text: indicate

text: the

text: conjugate

text: transpose

text: of

text: a

text: matrix

text: with

text: a

text: for

text: example

text: would

text: be

text: j

text: the

text: transpose

text: of

text: Φ.

text: D

text: The

text: set

text: of

text: all

text: dictionaries

text: of

text: a

text: given

text: size

text: (d

text: K)

text: is

text: denoted

text: by

text: For

text: two

text: dictionaries

text: D

text: Φ,

text: Ψ

text: we

text: deﬁne

text: the

text: distance

text: between

text: each

text: other

text: as

text: the

text: maximal

text: distance

text: between

text: two

text: corresponding

text: atoms,

text: d(Φ,

text: Ψ)

text: max

text: φ

text: ψ

text: i

text: i

text: i

text: R

text: We

text: consider

text: a

text: frame

text: F

text: a

text: collection

text: of

text: K

text: d

text: vectors

text: f

text: d

text: for

text: which

text: there

text: exist

text: two

text: R

text: i

text: positive

text: frame

text: constants

text: A,

text: B

text: such

text: that

text: for

text: all

text: v

text: d

text: we

text: have

text: K

text: A

text: v

text: f

text: v

text: B

text: v

text: i

text: From

text: it

text: follows

text: that

text: F

text: interpreted

text: as

text: d

text: K

text: matrix,

text: has

text: rank

text: d

text: and

text: that

text: its

text: non-zero

text: singular

text: values

text: are

text: in

text: the

text: interval

text: A,

text: B].

text: If

text: B

text: can

text: be

text: chosen

text: equal

text: to

text: A,

text: that

text: is

text: B

text: A,

text: the

text: frame

text: is

text: called

text: tight.

text: If

text: all

text: frame

text: elements

text: f

text: have

text: unit

text: norm,

text: we

text: call

text: F

text: a

text: unit

text: norm

text: i

text: frame.

text: For

text: more

text: details

text: on

text: frames,

text: see

text: e.g.

text: Christensen

text: Finally

text: we

text: introduce

text: the

text: Landau

text: symbols

text: O,

text: o

text: to

text: characterise

text: the

text: growth

text: of

text: a

text: function.

text: We

text: write

text: ##LTLine##

text: ##LTLine##