text: 6 RICCARDA ROSSI ⊂ R × The reference conﬁguration. Let Ω d be a bounded domain, with Lipschitz boundary; we set Q := Ω (0, T). The boundary ∂Ω is given by ∪ ∪ ∂Ω = Γ Γ ∂Γ with Γ , Γ , ∂Γ pairwise disjoint, Dir Neu Dir Neu ΓDir and ΓNeu relatively open in ∂Ω, and ∂Γ their relative boundary in ∂Ω, (2.Ω) − with Hausdorﬀ measure Hd 1(∂Γ) = 0. | | − We will denote by Ω the Lebesgue measure of Ω. On the Dirichlet part Γ , assumed with Hd 1(Γ ) > 0, Dir Dir we shall prescribe the displacement, while on Γ we will impose a Neumann condition on the displacement. Neu The trace of a function v on Γ or Γ shall be still denoted by the symbol v. Dir Neu R Sobolev spaces, the s-Laplacian, Korn’s inequality. In what follows, we will use the notation H1 (Ω; d) := {u ∈ H1(Ω; Rd) : u| (cid:8)= 0}. The symbol W1,p(Ω; Rd), p > 1, sh(cid:9)all denote the analogous W1,p-spDaicre. Further, Dir Dir we will use the notation ∈ ≥ ∈ W1,p(Ω) := ζ W1,p(Ω) : ζ(x) 0 for a.a. x Ω , and analogously for W−1,p(Ω). (2.1) + ∞ Throughout the paper, we shall extensively resort to Korn’s inequality (cf. [GS86]): for every 1 < p < there exists a constant C = C (Ω, p) > 0 such that there holds K K (cid:107)u(cid:107) R ≤ C (cid:107)E(u)(cid:107) M × for all u ∈ W1,p(Ω; Rd) . (2.2) W1,p(Ω; d) K Lp(Ω; dsymd) Dir (cid:0) (cid:1) We will denote by ∈ Hs(Ω) the Sobolev–Slobodeckij space Ws,2(Ω), with s d, 2 . 2 { ∈ ≥ } We will also use the notation Hs (Ω) = z Hs(Ω) : z 0 in Ω and the analogously deﬁned notation H−s (Ω). + We recall that Hs(Ω) is a Hilbert space, with inner product (z , z ) := (z , z ) + a (z , z ), where · · (cid:90)(cid:90) 1 2 Hs(Ω) 1 2 L2(Ω) s 1 2 the bilinear form a ( , ) is deﬁned by s ∇ −∇ ∇ −∇ ( z (x) z (y)) ( z (x) z (y)) as(z1, z2) := × 1 |x1−y|d+2(s−21) 2 dxdy . (2.3) Ω Ω → ∗ We denote by A : Hs(Ω) Hs(Ω) the associated operator s (cid:104) (cid:105) ∈ A (z), v := a (z, v) for all v Hs(Ω) . (2.4) s Hs(Ω) s ∈ R Kinematic admissibility and stress. Given a function w H1(Ω; d), we say that a triple (u, e, p) is kinematically ∈ admissible with boundary datum w, and write (u, e, p) A(w), if ∈ R ∈ M × ∈ M × u H1(Ω; d), e L2(Ω; d d), p L2(Ω; d d), (2.5a) sym D E(u) = e + p a.e. in Ω, (2.5b) u = w on Γ . (2.5c) Dir As for the elasticity and viscosity tensors, we will suppose that (cid:40) C D ∈ × R M × , C0(Ω ; Lin( d d)) , and sym | | ≤ C ≤ | | C D ∃ ∀ ∈ ∀ ∈ R ∀ ∈ M × CC1 A 2 (x, z)A : A CC2 A 2, (2.( , )1) CC1, CC2, CD1, CD2 > 0 x Ω z A dsymd : CD1|A|2 ≤ D(x, z)A : A ≤ CD2|A|2, M × M × M × where Lin( d d) denotes the space of linear operators from d d to d d. Furthermore, we will suppose s∈ym (cid:55)→ C sym Rsym that for every x Ω the map z (x, z) is continuously diﬀerentiable on and fulﬁlls ##LTLine## ##LTLine## ##LTLine##

text: RICCARDA

text: ROSSI

text: R

text: The

text: reference

text: conﬁguration.

text: Let

text: Ω

text: d

text: be

text: a

text: bounded

text: domain,

text: with

text: Lipschitz

text: boundary;

text: we

text: set

text: Q

text: Ω

text: T).

text: The

text: boundary

text: ∂Ω

text: is

text: given

text: by

text: ∂Ω

text: Γ

text: Γ

text: ∂Γ

text: with

text: Γ

text: Γ

text: ∂Γ

text: pairwise

text: disjoint,

text: Dir

text: Neu

text: Dir

text: Neu

text: ΓDir

text: and

text: ΓNeu

text: relatively

text: open

text: in

text: ∂Ω,

text: and

text: ∂Γ

text: their

text: relative

text: boundary

text: in

text: ∂Ω,

text: with

text: Hausdorﬀ

text: measure

text: Hd

text: We

text: will

text: denote

text: by

text: Ω

text: the

text: Lebesgue

text: measure

text: of

text: Ω.

text: On

text: the

text: Dirichlet

text: part

text: Γ

text: assumed

text: with

text: Hd

text: Dir

text: Dir

text: we

text: shall

text: prescribe

text: the

text: displacement,

text: while

text: on

text: Γ

text: we

text: will

text: impose

text: a

text: Neumann

text: condition

text: on

text: the

text: displacement.

text: Neu

text: The

text: trace

text: of

text: a

text: function

text: v

text: on

text: Γ

text: or

text: Γ

text: shall

text: be

text: still

text: denoted

text: by

text: the

text: symbol

text: v.

text: Dir

text: Neu

text: R

text: Sobolev

text: spaces,

text: the

text: s-Laplacian,

text: Korn’s

text: inequality.

text: In

text: what

text: follows,

text: we

text: will

text: use

text: the

text: notation

text: (Ω;

text: d)

text: {u

text: Rd)

text: u|

text: The

text: symbol

text: Rd),

text: p

text: denote

text: the

text: analogous

text: Further,

text: Dir

text: Dir

text: we

text: will

text: use

text: the

text: notation

text: ζ

text: ζ(x)

text: for

text: a.a.

text: x

text: Ω

text: and

text: analogously

text: for

text: Throughout

text: the

text: paper,

text: we

text: shall

text: extensively

text: resort

text: to

text: Korn’s

text: inequality

text: (cf.

text: for

text: every

text: p

text: there

text: exists

text: a

text: constant

text: C

text: C

text: (Ω,

text: p)

text: such

text: that

text: there

text: holds

text: K

text: K

text: R

text: C

text: M

text: for

text: all

text: u

text: Rd)

text: d)

text: K

text: Lp(Ω;

text: dsymd)

text: Dir

text: We

text: will

text: denote

text: by

text: Hs(Ω)

text: the

text: Sobolev–Slobodeckij

text: space

text: with

text: s

text: d,

text: We

text: will

text: also

text: use

text: the

text: notation

text: Hs

text: (Ω)

text: z

text: Hs(Ω)

text: z

text: in

text: Ω

text: and

text: the

text: analogously

text: deﬁned

text: notation

text: H−s

text: (Ω).

text: We

text: recall

text: that

text: Hs(Ω)

text: is

text: a

text: Hilbert

text: space,

text: with

text: inner

text: product

text: (z

text: z

text: (z

text: z

text: a

text: (z

text: z

text: where

text: Hs(Ω)

text: s

text: the

text: bilinear

text: form

text: a

text: is

text: deﬁned

text: by

text: s

text: z

text: (x)

text: z

text: (y))

text: z

text: (x)

text: z

text: (y))

text: dxdy

text: Ω

text: Ω

text: We

text: denote

text: by

text: A

text: Hs(Ω)

text: Hs(Ω)

text: the

text: associated

text: operator

text: s

text: A

text: (z),

text: v

text: a

text: (z,

text: v)

text: for

text: all

text: v

text: Hs(Ω)

text: s

text: Hs(Ω)

text: s

text: R

text: Kinematic

text: admissibility

text: and

text: stress.

text: Given

text: a

text: function

text: w

text: d),

text: we

text: say

text: that

text: a

text: triple

text: (u,

text: e,

text: p)

text: is

text: kinematically

text: admissible

text: with

text: boundary

text: datum

text: w,

text: and

text: write

text: (u,

text: e,

text: p)

text: A(w),

text: if

text: R

text: M

text: M

text: u

text: d),

text: e

text: d

text: d),

text: p

text: d

text: d),

text: sym

text: D

text: E(u)

text: e

text: p

text: a.e.

text: in

text: Ω,

text: u

text: w

text: on

text: Γ

text: Dir

text: As

text: for

text: the

text: elasticity

text: and

text: viscosity

text: tensors,

text: we

text: will

text: suppose

text: that

text: C

text: D

text: R

text: M

text: Lin(

text: d

text: d))

text: and

text: sym

text: C

text: C

text: D

text: R

text: M

text: A

text: (x,

text: z)A

text: A

text: A

text: x

text: Ω

text: z

text: A

text: dsymd

text: D(x,

text: z)A

text: A

text: M

text: M

text: M

text: where

text: Lin(

text: d

text: d)

text: denotes

text: the

text: space

text: of

text: linear

text: operators

text: from

text: d

text: d

text: to

text: d

text: d.

text: Furthermore,

text: we

text: will

text: suppose

text: s∈ym

text: C

text: sym

text: Rsym

text: that

text: for

text: every

text: x

text: Ω

text: the

text: map

text: z

text: (x,

text: z)

text: is

text: continuously

text: diﬀerentiable

text: on

text: and

text: fulﬁlls

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: EgoCap: Egocentric Marker-less Motion Capture (Extended Abstract) 3 head-mounted ﬁsheye views to get 2D body-part annotations. We augment the training frames by replacing the green screen with random background images, and vary the appearance in terms of color and shading by intrinsic recoloring [4]. With this technique, we annotate 100,000 images of egocentric videos of eight people in diﬀerent clothing. We provide the dataset for research purposes [1]. 2 Egocentric Inside-In Motion Capture Our egocentric setup separates human motion capture into two subprob- lems: (1) local skeleton pose estimation with respect to the camera rig, and (2) global rig pose estimation relative to the environment. Global pose is estimated with existing structure-from-motion techniques [5]. We formulate skeletal pose estimation as an analysis-by-synthesis-style optimization problem in the pose parameters pt, that maximizes the alignment of a projected 3D human body I I model in the left t and the right t stereo ﬁsheye views, at each video time left right step t. We use a hybrid alignment energy combining evidence from a generative image-formation model, as well as from a discriminative detection approach: E(pt)=E (pt)+E (pt)+E (pt)+E (pt). (1) color detection pose smooth E is an extension of a generative ray-casting model [7] to the strongly color distorted ﬁsheye views, which provides diﬀerentiable visibility through a volu- metric representation. E constrains pt to 2D joint detections obtained detection from an exiting ConvNet [3], which was ﬁne-tuned on the previously introduced dataset. E penalizes violations of anatomical joint-angle limits as well as pose poses deviating strongly from the rest pose, and E regularizes temporal smooth changes. 3 Evaluation and Applications Dataset Augmentations. We ﬁrst evaluate the learned body-part detectors using the percentage of correct keypoints (PCK) metric [8] on a validation set consisting of 1000 images of two subjects that are not part of the training set. Background augmentation during training brings a clear improvement of 67 PCK points. Cloth recoloring additionally improves signiﬁcantly by 3 PCK points. 3D Body Pose Accuracy. We quantitatively evaluate the 3D body pose ac- curacy of our approach on ground-truth data obtained with the Captury Studio. The average Euclidean 3D distance over all 18 joints, for which detection labels ± are available, is 7 1 cm for a challenging 250-frame walking sequence with occlu- ± sions, and 7 1 cm on a long sequence of 750 frames of gesturing and interaction. It meets the accuracy of outside-in approaches using 2–3 cameras [2]. Large-scale Motion Capture. We successfully tested on a basketball sequence outdoors, which shows quick motion and close interaction, on an outdoor walking sequence, and on a large-scale biking sequence (Figure 1, third column).

text: EgoCap:

label: paragraph

text: Egocentric

text: Marker-less

text: Motion

text: Capture

text: (Extended

text: Abstract)

text: head-mounted

text: ﬁsheye

text: views

text: to

text: get

text: body-part

text: annotations.

text: We

text: augment

text: the

text: training

text: frames

text: by

text: replacing

text: the

text: green

text: screen

text: with

text: random

text: background

text: images,

text: and

text: vary

text: the

text: appearance

text: in

text: terms

text: of

text: color

text: and

text: shading

text: by

text: intrinsic

text: recoloring

text: With

text: this

text: technique,

text: we

text: annotate

text: images

text: of

text: egocentric

text: videos

text: of

text: eight

text: people

text: in

text: diﬀerent

text: clothing.

text: We

text: provide

text: the

text: dataset

text: for

text: research

text: purposes

label: section

text: Egocentric

text: Inside-In

text: Motion

text: Capture

text: Our

text: egocentric

text: setup

text: separates

text: human

text: motion

text: capture

text: into

text: two

text: subprob-

text: lems:

text: local

text: skeleton

text: pose

text: estimation

text: with

text: respect

text: to

text: the

text: camera

text: rig,

text: and

text: global

text: rig

text: pose

text: estimation

text: relative

text: to

text: the

text: environment.

text: Global

text: pose

text: is

text: estimated

text: with

text: existing

text: structure-from-motion

text: techniques

text: We

text: formulate

text: skeletal

text: pose

text: estimation

text: as

text: an

text: analysis-by-synthesis-style

text: optimization

text: problem

text: in

text: the

text: pose

text: parameters

text: pt,

text: that

text: maximizes

text: the

text: alignment

text: of

text: a

text: projected

text: human

text: body

text: I

text: I

text: model

text: in

text: the

text: left

text: t

text: and

text: the

text: right

text: t

text: stereo

text: ﬁsheye

text: views,

text: at

text: each

text: video

text: time

text: left

text: right

text: step

text: t.

text: We

text: use

text: a

text: hybrid

text: alignment

text: energy

text: combining

text: evidence

text: from

text: a

text: generative

text: image-formation

text: model,

text: as

text: well

text: as

text: from

text: a

text: discriminative

text: detection

text: approach:

text: E(pt)=E

text: (pt)+E

text: (pt)+E

text: (pt)+E

text: (pt).

text: color

text: detection

text: pose

text: smooth

text: E

text: is

text: an

text: extension

text: of

text: a

text: generative

text: ray-casting

text: model

text: to

text: the

text: strongly

text: color

text: distorted

text: ﬁsheye

text: views,

text: which

text: provides

text: diﬀerentiable

text: visibility

text: through

text: a

text: volu-

text: metric

text: representation.

text: E

text: constrains

text: pt

text: to

text: joint

text: detections

text: obtained

text: detection

text: from

text: an

text: exiting

text: ConvNet

text: which

text: was

text: ﬁne-tuned

text: on

text: the

text: previously

text: introduced

text: dataset.

text: E

text: penalizes

text: violations

text: of

text: anatomical

text: joint-angle

text: limits

text: as

text: well

text: as

text: pose

text: poses

text: deviating

text: strongly

text: from

text: the

text: rest

text: pose,

text: and

text: E

text: regularizes

text: temporal

text: smooth

text: changes.

text: Evaluation

text: and

text: Applications

text: Dataset

text: Augmentations.

text: We

text: ﬁrst

text: evaluate

text: the

text: learned

text: body-part

text: detectors

text: using

text: the

text: percentage

text: of

text: correct

text: keypoints

text: (PCK)

text: metric

text: on

text: a

text: validation

text: set

text: consisting

text: of

text: images

text: of

text: two

text: subjects

text: that

text: are

text: not

text: part

text: of

text: the

text: training

text: set.

text: Background

text: augmentation

text: during

text: training

text: brings

text: a

text: clear

text: improvement

text: of

text: PCK

text: points.

text: Cloth

text: recoloring

text: additionally

text: improves

text: signiﬁcantly

text: by

text: PCK

text: points.

text: Body

text: Pose

text: Accuracy.

text: We

text: quantitatively

text: evaluate

text: the

text: body

text: pose

text: ac-

text: curacy

text: of

text: our

text: approach

text: on

text: ground-truth

text: data

text: obtained

text: with

text: the

text: Captury

text: Studio.

text: The

text: average

text: Euclidean

text: distance

text: over

text: all

text: joints,

text: for

text: which

text: detection

text: labels

text: are

text: available,

text: is

text: cm

text: for

text: a

text: challenging

text: walking

text: sequence

text: with

text: occlu-

text: sions,

text: and

text: cm

text: on

text: a

text: long

text: sequence

text: of

text: frames

text: of

text: gesturing

text: and

text: interaction.

text: It

text: meets

text: the

text: accuracy

text: of

text: outside-in

text: approaches

text: using

text: cameras

text: Large-scale

text: Motion

text: Capture.

text: We

text: successfully

text: tested

text: on

text: a

text: basketball

text: sequence

text: outdoors,

text: which

text: shows

text: quick

text: motion

text: and

text: close

text: interaction,

text: on

text: an

text: outdoor

text: walking

text: sequence,

text: and

text: on

text: a

text: large-scale

text: biking

text: sequence

text: (Figure

text: third

text: column).


text: english words (anew): Instruction manual and affective rat- Pennington, J.; Socher, R.; and Manning, C. D. 2014. Glove: ings. Technical report, Citeseer. Global vectors for word representation. Proceedings of the Dodds, P. S.; Harris, K. D.; Kloumann, I. M.; Bliss, C. A.; 2014 Empiricial Methods in Natural Language Processing and Danforth, C. M. 2011. Temporal patterns of happiness 12. and information in a global social network: Hedonometrics Plutchik, R. 1980. A general psychoevolutionary theory of and twitter. PloS one 6(12):e26752. emotion. Academic press. 3–33. Esuli, A., and Sebastiani, F. 2006. Sentiwordnet: A publicly Rao, D., and Ravichandran, D. 2009. Semi-supervised po- available lexical resource for opinion mining. In Proceed- larity lexicon induction. In Proceedings of the 12th Confer- ings of LREC, volume 6, 417–422. Citeseer. ence of the European Chapter of the Association for Com- Harris, Z. S. 1954. Distributional structure. Word 10(2- putational Linguistics, 675–682. 3):146–162. Rosenthal, S.; Nakov, P.; Kiritchenko, S.; Mohammad, Hinton, G. E., and Salakhutdinov, R. R. 2006. Reducing S. M.; Ritter, A.; and Stoyanov, V. 2015. Semeval-2015 task the dimensionality of data with neural networks. Science 10: Sentiment analysis in twitter. In Proceedings of the 9th 313(5786):504–507. International Workshop on Semantic Evaluation, SemEval ’2015. Denver, Colorado: Association for Computational Hinton, G. E. 1986. Learning distributed representations of Linguistics. concepts. In Proceedings of the eighth annual conference of the cognitive science society, volume 1, 12. Amherst, MA. Rothe, S.; Ebert, S.; and Schu¨tze, H. 2016. Ultradense word embeddings by orthogonal transformation. arXiv preprint Hu, M., and Liu, B. 2004. Mining and summarizing cus- arXiv:1602.07572. tomer reviews. In Proceedings of the tenth ACM SIGKDD International Conference on Knowledge discovery and data Speriosu, M.; Sudan, N.; Upadhyay, S.; and Baldridge, J. mining, 168–177. 2011. Twitter polarity classiﬁcation with label propagation over lexical links and the follower graph. In Proceedings of Kamps, J.; Marx, M.; Mokken, R. J.; and de Rijke, M. 2004. the First workshop on Unsupervised Learning in NLP, 53– Using wordnet to measure semantic orientations of adjec- 63. Association for Computational Linguistics. tives. In Proceedings of 4th International Conference on Language Resources and Evaluation, Vol IV,, 1115–1118. Tang, D.; Wei, F.; Qin, B.; Zhou, M.; and Liu, T. 2014. Building large-scale twitter-speciﬁc sentiment lexicon : A Kim, S.-M., and Hovy, E. 2006. Identifying and analyz- representation learning approach. In Proceedings of the ing judgment opinions. In Proceedings of the Human Lan- 25th International Conference on Computational Linguis- guage Technology Conference of the NAACL, Main Confer- tics, 172–182. ence, 200–207. Tibshirani, R. 1996. Regression shrinkage and selection via Kiritchenko, S.; Zhu, X.; and Mohammad, S. M. 2014. Sen- the lasso. Journal of the Royal Statistical Society. Series B timent analysis of short informal texts. Journal of Artiﬁcial (Methodological) 267–288. Intelligence Research 723–762. Tumasjan, A.; Sprenger, T. O.; Sandner, P. G.; and Welpe, Labutov, I., and Lipson, H. 2013. Re-embedding words. In I. M. 2010. Predicting elections with twitter: What 140 char- Proceedings of the 51st annual meeting of the ACL, 489– acters reveal about political sentiment. In 4th International 493. AAAI Conference on Weblogs and Social Media. Ling, W.; Dyer, C.; Black, A. W.; Trancoso, I.; Fermandez, Turney, P. D., and Littman, M. L. 2003. Measuring praise R.; Amir, S.; Marujo, L.; and Luis, T. 2015. Finding function and criticism: Inference of semantic orientation from asso- in form: Compositional character models for open vocabu- ciation. ACM Transactions on Information Systems 21(4). lary word representation. In Proceedings of the 2015 Con- ference on Empirical Methods in Natural Language Pro- Vapnik, V. 2000. The nature of statistical learning theory. cessing, 1520–1530. Springer Science & Business Media. Maaten, L. v. d., and Hinton, G. 2008. Visualizing data using Warriner, A. B.; Kuperman, V.; and Brysbaert, M. 2013. t-sne. Journal of Machine Learning Research 9(Nov):2579– Norms of valence, arousal, and dominance for 13,915 en- 2605. glish lemmas. Behavior research methods 45(4):1191–1207. Mitchell, L.; Harris, K. D.; Frank, M. R.; Dodds, P. S.; and Wilson, T.; Wiebe, J.; and Hoffmann, P. 2005. Recogniz- Danforth, C. M. 2013. The geography of happiness: con- ing contextual polarity in phrase-level sentiment analysis. In necting twitter sentiment and expression, demographics, and Proceedings of the conference on human language technol- objective characteristics of place. PLoS ONE 8(5). ogy and empirical methods in natural language processing, Mohammad, S. M., and Turney, P. D. 2013. Crowdsourcing 347–354. Association for Computational Linguistics. a word–emotion association lexicon. Computational Intelli- Yang, Y., and Eisenstein, J. 2015. Putting things in con- gence 29(3). text: Community-speciﬁc embedding projections for senti- O’Connor, B.; Balasubramanyan, R.; Routledge, B. R.; and ment analysis. arXiv preprint arXiv:1511.06052. Smith, N. A. 2010. From tweets to polls: Linking text sen- Yu, L.-C.; Wu, J.-L.; Chang, P.-C.; and Chu, H.-S. 2013. timent to public opinion time series. In Proceedings of the Using a contextual entropy model to expand emotion words 4th International AAAI Conference on Weblogs and Social and their intensity for the sentiment classiﬁcation of stock Media. market news. Knowledge-Based Systems 41(0).

text: english

label: reference

text: words

text: (anew):

text: Instruction

text: manual

text: and

text: affective

text: rat-

text: Pennington,

text: J.;

text: Socher,

text: R.;

text: and

text: Manning,

text: C.

text: D.

text: Glove:

text: ings.

text: Technical

text: report,

text: Citeseer.

text: Global

text: vectors

text: for

text: word

text: representation.

text: Proceedings

text: of

text: the

text: Dodds,

text: P.

text: S.;

text: Harris,

text: K.

text: D.;

text: Kloumann,

text: I.

text: M.;

text: Bliss,

text: C.

text: A.;

text: Empiricial

text: Methods

text: in

text: Natural

text: Language

text: Processing

text: and

text: Danforth,

text: C.

text: M.

text: Temporal

text: patterns

text: of

text: happiness

text: and

text: information

text: in

text: a

text: global

text: social

text: network:

text: Hedonometrics

text: Plutchik,

text: R.

text: A

text: general

text: psychoevolutionary

text: theory

text: of

text: and

text: twitter.

text: PloS

text: one

text: emotion.

text: Academic

text: press.

text: Esuli,

text: A.,

text: and

text: Sebastiani,

text: F.

text: Sentiwordnet:

text: A

text: publicly

text: Rao,

text: D.,

text: and

text: Ravichandran,

text: D.

text: Semi-supervised

text: po-

text: available

text: lexical

text: resource

text: for

text: opinion

text: mining.

text: In

text: Proceed-

text: larity

text: lexicon

text: induction.

text: In

text: Proceedings

text: of

text: the

text: Confer-

text: ings

text: of

text: LREC,

text: volume

text: Citeseer.

text: ence

text: of

text: the

text: European

text: Chapter

text: of

text: the

text: Association

text: for

text: Com-

text: Harris,

text: Z.

text: S.

text: Distributional

text: structure.

text: Word

text: putational

text: Linguistics,

text: Rosenthal,

text: S.;

text: Nakov,

text: P.;

text: Kiritchenko,

text: S.;

text: Mohammad,

text: Hinton,

text: G.

text: E.,

text: and

text: Salakhutdinov,

text: R.

text: R.

text: Reducing

text: S.

text: M.;

text: Ritter,

text: A.;

text: and

text: Stoyanov,

text: V.

text: task

text: the

text: dimensionality

text: of

text: data

text: with

text: neural

text: networks.

text: Science

text: Sentiment

text: analysis

text: in

text: twitter.

text: In

text: Proceedings

text: of

text: the

text: International

text: Workshop

text: on

text: Semantic

text: Evaluation,

text: SemEval

text: Denver,

text: Colorado:

text: Association

text: for

text: Computational

text: Hinton,

text: G.

text: E.

text: Learning

text: distributed

text: representations

text: of

text: Linguistics.

text: concepts.

text: In

text: Proceedings

text: of

text: the

text: eighth

text: annual

text: conference

text: of

text: the

text: cognitive

text: science

text: society,

text: volume

text: Amherst,

text: MA.

text: Rothe,

text: S.;

text: Ebert,

text: S.;

text: and

text: Schu¨tze,

text: H.

text: Ultradense

text: word

text: embeddings

text: by

text: orthogonal

text: transformation.

text: arXiv

text: preprint

text: Hu,

text: M.,

text: and

text: Liu,

text: B.

text: Mining

text: and

text: summarizing

text: cus-

text: tomer

text: reviews.

text: In

text: Proceedings

text: of

text: the

text: tenth

text: ACM

text: SIGKDD

text: International

text: Conference

text: on

text: Knowledge

text: discovery

text: and

text: data

text: Speriosu,

text: M.;

text: Sudan,

text: N.;

text: Upadhyay,

text: S.;

text: and

text: Baldridge,

text: J.

text: mining,

text: Twitter

text: polarity

text: classiﬁcation

text: with

text: label

text: propagation

text: over

text: lexical

text: links

text: and

text: the

text: follower

text: graph.

text: In

text: Proceedings

text: of

text: Kamps,

text: J.;

text: Marx,

text: M.;

text: Mokken,

text: R.

text: J.;

text: and

text: de

text: Rijke,

text: M.

text: the

text: First

text: workshop

text: on

text: Unsupervised

text: Learning

text: in

text: NLP,

text: Using

text: wordnet

text: to

text: measure

text: semantic

text: orientations

text: of

text: adjec-

text: Association

text: for

text: Computational

text: Linguistics.

text: tives.

text: In

text: Proceedings

text: of

text: International

text: Conference

text: on

text: Language

text: Resources

text: and

text: Evaluation,

text: Vol

text: IV,,

text: Tang,

text: D.;

text: Wei,

text: F.;

text: Qin,

text: B.;

text: Zhou,

text: M.;

text: and

text: Liu,

text: T.

text: Building

text: large-scale

text: twitter-speciﬁc

text: sentiment

text: lexicon

text: A

text: Kim,

text: S.-M.,

text: and

text: Hovy,

text: E.

text: Identifying

text: and

text: analyz-

text: representation

text: learning

text: approach.

text: In

text: Proceedings

text: of

text: the

text: ing

text: judgment

text: opinions.

text: In

text: Proceedings

text: of

text: the

text: Human

text: Lan-

text: International

text: Conference

text: on

text: Computational

text: Linguis-

text: guage

text: Technology

text: Conference

text: of

text: the

text: NAACL,

text: Main

text: Confer-

text: tics,

text: ence,

text: Tibshirani,

text: R.

text: Regression

text: shrinkage

text: and

text: selection

text: via

text: Kiritchenko,

text: S.;

text: Zhu,

text: X.;

text: and

text: Mohammad,

text: S.

text: M.

text: Sen-

text: the

text: lasso.

text: Journal

text: of

text: the

text: Royal

text: Statistical

text: Society.

text: Series

text: B

text: timent

text: analysis

text: of

text: short

text: informal

text: texts.

text: Journal

text: of

text: Artiﬁcial

text: (Methodological)

text: Intelligence

text: Research

text: Tumasjan,

text: A.;

text: Sprenger,

text: T.

text: O.;

text: Sandner,

text: P.

text: G.;

text: and

text: Welpe,

text: Labutov,

text: I.,

text: and

text: Lipson,

text: H.

text: Re-embedding

text: words.

text: In

text: I.

text: M.

text: Predicting

text: elections

text: with

text: twitter:

text: What

text: char-

text: Proceedings

text: of

text: the

text: annual

text: meeting

text: of

text: the

text: ACL,

text: acters

text: reveal

text: about

text: political

text: sentiment.

text: In

text: International

text: AAAI

text: Conference

text: on

text: Weblogs

text: and

text: Social

text: Media.

text: Ling,

text: W.;

text: Dyer,

text: C.;

text: Black,

text: A.

text: W.;

text: Trancoso,

text: I.;

text: Fermandez,

text: Turney,

text: P.

text: D.,

text: and

text: Littman,

text: M.

text: L.

text: Measuring

text: praise

text: R.;

text: Amir,

text: S.;

text: Marujo,

text: L.;

text: and

text: Luis,

text: T.

text: Finding

text: function

text: and

text: criticism:

text: Inference

text: of

text: semantic

text: orientation

text: from

text: asso-

text: in

text: form:

text: Compositional

text: character

text: models

text: for

text: open

text: vocabu-

text: ciation.

text: ACM

text: Transactions

text: on

text: Information

text: Systems

text: lary

text: word

text: representation.

text: In

text: Proceedings

text: of

text: the

text: Con-

text: ference

text: on

text: Empirical

text: Methods

text: in

text: Natural

text: Language

text: Pro-

text: Vapnik,

text: V.

text: The

text: nature

text: of

text: statistical

text: learning

text: theory.

text: cessing,

text: Springer

text: Science

text: Business

text: Media.

text: Maaten,

text: L.

text: v.

text: d.,

text: and

text: Hinton,

text: G.

text: Visualizing

text: data

text: using

text: Warriner,

text: A.

text: B.;

text: Kuperman,

text: V.;

text: and

text: Brysbaert,

text: M.

text: t-sne.

text: Journal

text: of

text: Machine

text: Learning

text: Research

text: Norms

text: of

text: valence,

text: arousal,

text: and

text: dominance

text: for

text: en-

text: glish

text: lemmas.

text: Behavior

text: research

text: methods

text: Mitchell,

text: L.;

text: Harris,

text: K.

text: D.;

text: Frank,

text: M.

text: R.;

text: Dodds,

text: P.

text: S.;

text: and

text: Wilson,

text: T.;

text: Wiebe,

text: J.;

text: and

text: Hoffmann,

text: P.

text: Recogniz-

text: Danforth,

text: C.

text: M.

text: The

text: geography

text: of

text: happiness:

text: con-

text: ing

text: contextual

text: polarity

text: in

text: phrase-level

text: sentiment

text: analysis.

text: In

text: necting

text: twitter

text: sentiment

text: and

text: expression,

text: demographics,

text: and

text: Proceedings

text: of

text: the

text: conference

text: on

text: human

text: language

text: technol-

text: objective

text: characteristics

text: of

text: place.

text: PLoS

text: ONE

text: ogy

text: and

text: empirical

text: methods

text: in

text: natural

text: language

text: processing,

text: Mohammad,

text: S.

text: M.,

text: and

text: Turney,

text: P.

text: D.

text: Crowdsourcing

text: Association

text: for

text: Computational

text: Linguistics.

text: a

text: word–emotion

text: association

text: lexicon.

text: Computational

text: Intelli-

text: Yang,

text: Y.,

text: and

text: Eisenstein,

text: J.

text: Putting

text: things

text: in

text: con-

text: gence

text: text:

text: Community-speciﬁc

text: embedding

text: projections

text: for

text: senti-

text: O’Connor,

text: B.;

text: Balasubramanyan,

text: R.;

text: Routledge,

text: B.

text: R.;

text: and

text: ment

text: analysis.

text: arXiv

text: preprint

text: Smith,

text: N.

text: A.

text: From

text: tweets

text: to

text: polls:

text: Linking

text: text

text: sen-

text: Yu,

text: L.-C.;

text: Wu,

text: J.-L.;

text: Chang,

text: P.-C.;

text: and

text: Chu,

text: H.-S.

text: timent

text: to

text: public

text: opinion

text: time

text: series.

text: In

text: Proceedings

text: of

text: the

text: Using

text: a

text: contextual

text: entropy

text: model

text: to

text: expand

text: emotion

text: words

text: International

text: AAAI

text: Conference

text: on

text: Weblogs

text: and

text: Social

text: and

text: their

text: intensity

text: for

text: the

text: sentiment

text: classiﬁcation

text: of

text: stock

text: Media.

text: market

text: news.

text: Knowledge-Based

text: Systems


text: edges. Consequently, none of the vertex tiles may be placed; all of them must appear on the left side of the bridge tile. Now consider the tiles on the left side of the bridge tile. Observe that, to be compatible with the − T T color O to the right, we may only place the vertex tile oriented as (+I , +U , +O , +U ). vj vj vj vj vj Tvj Similarly, to be compatible with the color +I to the right, we may only place some edge tile T − − − vj eij oriented as ( O , +X, I , X). Therefore, these tiles may only be placed if they correspond vi vj to a path on G ending at t. Since all vertex tiles appear to the left of the bridge tile, we have a path visiting all vertices ending at t. Moreover, as our starting vertex s is a source, the color +I T s cannot be matched by any tile. Thus must be the left-most tile on the grid. That is, the tiles s to the left of the bridge tile encode a Hamiltonian path of G, as desired. × 5 Inapproximability of 1 n Edge-Matching Puzzles In this section, we generalize the approach from Section in order to prove Theorem 1, NP- × hardness of approximation of 1 n Max-Placement Edge-Matching Puzzle. To this end, we use the optimization variant of Hamiltonian Path called Max Vertex-Disjoint Path Cover deﬁned earlier, and provide a gap-preserving reduction from Max Vertex-Disjoint Path Cover × to 1 n Max-Placement Edge-Matching Puzzle. We largely focus on the unsigned variant because it is the more complicated case. Speciﬁcally, by removing the signs in the reduction of Section , it becomes possible to place two edge tiles next to each other without using the garbage color since they share an additional color if they have the same starting vertex or ending vertex. We circumvent this problem by restricting to graphs of in-degrees and out-degrees at most two. This requries us to later show the hardness of approximation for Max Vertex-Disjoint Path Cover(2) in this more restricted family of graphs. × We describe our reduction from Max Vertex-Disjoint Path Cover(2) to 1 n Max- Placement Edge-Matching Puzzle in Section . We then prove in Section that the reduction satisﬁes the properties stated in the lemma below: Lemma 3. For any nonnegative constants α and α < α /48, the following properties MPC| | EMP MPC hold for the reduction described in Section when V is suﬃciently large: • | |− if the optimum of the Max Vertex-Disjoint Path Cover(2) instance is V 1 (the graph × contains a Hamiltonian path), then the optimum of the resulting 1 n Max-Placement Edge-Matching Puzzle instance is at least n, i.e., every tile can be placed compatibly on the board, and, • − if the optimum of the Max Vertex-Disjoint Path Cover(2) instance is at most (1 | |− × α )( V 1), then the optimum of the resulting 1 n Max-Placement Edge-Matching MPC − Puzzle is at most (1 α )n. EMP We will later show NP-hardness of approximation of Max Vertex-Disjoint Path Cover(2), namely Theorem 2, in Section . The above lemma and Theorem 2 immediately imply Theorem 1. Then, we describe how to modify the reduction to arrive at a similar inapproximability result × for 1 n Max-Placement Signed Edge-Matching Puzzle (Corollary 1) in Section . Lastly, × we provide another reduction to obtain the inapproximability result for 1 n Max-Matched Edge-Matching Puzzle (Corollary 2) in Section . 11

text: edges.

text: Consequently,

text: of

text: the

text: vertex

text: tiles

text: may

text: be

text: placed;

text: all

text: of

text: them

text: must

text: appear

text: on

text: the

text: left

text: side

text: of

text: the

text: bridge

text: tile.

text: Now

text: consider

text: the

text: tiles

text: on

text: the

text: left

text: side

text: of

text: the

text: bridge

text: tile.

text: Observe

text: that,

text: to

text: be

text: compatible

text: with

text: the

text: T

text: T

text: color

text: O

text: to

text: the

text: right,

text: we

text: may

text: only

text: place

text: the

text: vertex

text: tile

text: oriented

text: as

text: (+I

text: +U

text: +O

text: +U

text: vj

text: vj

text: vj

text: vj

text: vj

text: Tvj

text: Similarly,

text: to

text: be

text: compatible

text: with

text: the

text: color

text: +I

text: to

text: the

text: right,

text: we

text: may

text: only

text: place

text: some

text: edge

text: tile

text: T

text: vj

text: eij

text: oriented

text: as

text: O

text: +X,

text: I

text: X).

text: Therefore,

text: these

text: tiles

text: may

text: only

text: be

text: placed

text: if

text: they

text: correspond

text: vi

text: vj

text: to

text: a

text: path

text: on

text: G

text: ending

text: at

text: t.

text: Since

text: all

text: vertex

text: tiles

text: appear

text: to

text: the

text: left

text: of

text: the

text: bridge

text: tile,

text: we

text: have

text: a

text: path

text: visiting

text: all

text: vertices

text: ending

text: at

text: t.

text: Moreover,

text: as

text: our

text: starting

text: vertex

text: s

text: is

text: a

text: source,

text: the

text: color

text: +I

text: T

text: s

text: cannot

text: be

text: matched

text: by

text: any

text: tile.

text: Thus

text: must

text: be

text: the

text: left-most

text: tile

text: on

text: the

text: grid.

text: That

text: is,

text: the

text: tiles

text: s

text: to

text: the

text: left

text: of

text: the

text: bridge

text: tile

text: encode

text: a

text: Hamiltonian

text: path

text: of

text: G,

text: as

text: desired.

text: Inapproximability

text: of

text: n

text: Edge-Matching

text: Puzzles

text: In

text: this

text: section,

text: we

text: generalize

text: the

text: approach

text: from

text: Section

text: in

text: order

text: to

text: prove

text: Theorem

text: NP-

text: hardness

text: of

text: approximation

text: of

text: n

text: Max-Placement

text: Edge-Matching

text: Puzzle.

text: To

text: this

text: end,

text: we

text: use

text: the

text: optimization

text: variant

text: of

text: Hamiltonian

text: Path

text: called

text: Max

text: Vertex-Disjoint

text: Path

text: Cover

text: deﬁned

text: earlier,

text: and

text: provide

text: a

text: gap-preserving

text: reduction

text: from

text: Max

text: Vertex-Disjoint

text: Path

text: Cover

text: to

text: n

text: Max-Placement

text: Edge-Matching

text: Puzzle.

text: We

text: largely

text: focus

text: on

text: the

text: unsigned

text: variant

text: because

text: it

text: is

text: the

text: more

text: complicated

text: case.

text: Speciﬁcally,

text: by

text: removing

text: the

text: signs

text: in

text: the

text: reduction

text: of

text: Section

text: it

text: becomes

text: possible

text: to

text: place

text: two

text: edge

text: tiles

text: next

text: to

text: each

text: other

text: without

text: using

text: the

text: garbage

text: color

text: since

text: they

text: share

text: an

text: additional

text: color

text: if

text: they

text: have

text: the

text: same

text: starting

text: vertex

text: or

text: ending

text: vertex.

text: We

text: circumvent

text: this

text: problem

text: by

text: restricting

text: to

text: graphs

text: of

text: in-degrees

text: and

text: out-degrees

text: at

text: most

text: two.

text: This

text: requries

text: us

text: to

text: later

text: show

text: the

text: hardness

text: of

text: approximation

text: for

text: Max

text: Vertex-Disjoint

text: Path

text: in

text: this

text: more

text: restricted

text: family

text: of

text: graphs.

text: We

text: describe

text: our

text: reduction

text: from

text: Max

text: Vertex-Disjoint

text: Path

text: to

text: n

text: Max-

text: Placement

text: Edge-Matching

text: Puzzle

text: in

text: Section

text: We

text: then

text: prove

text: in

text: Section

text: that

text: the

text: reduction

text: satisﬁes

text: the

text: properties

text: stated

text: in

text: the

text: lemma

text: below:

text: Lemma

text: For

text: any

text: nonnegative

text: constants

text: α

text: and

text: α

text: α

text: the

text: following

text: properties

text: MPC|

text: EMP

text: MPC

text: hold

text: for

text: the

text: reduction

text: described

text: in

text: Section

text: when

text: V

text: is

text: suﬃciently

text: large:

text: if

text: the

text: optimum

text: of

text: the

text: Max

text: Vertex-Disjoint

text: Path

text: instance

text: is

text: V

text: (the

text: graph

text: contains

text: a

text: Hamiltonian

text: path),

text: then

text: the

text: optimum

text: of

text: the

text: resulting

text: n

text: Max-Placement

text: Edge-Matching

text: Puzzle

text: instance

text: is

text: at

text: least

text: n,

text: i.e.,

text: every

text: tile

text: can

text: be

text: placed

text: compatibly

text: on

text: the

text: board,

text: and,

text: if

text: the

text: optimum

text: of

text: the

text: Max

text: Vertex-Disjoint

text: Path

text: instance

text: is

text: at

text: most

text: α

text: V

text: then

text: the

text: optimum

text: of

text: the

text: resulting

text: n

text: Max-Placement

text: Edge-Matching

text: MPC

text: Puzzle

text: is

text: at

text: most

text: α

text: )n.

text: EMP

text: We

text: will

text: later

text: show

text: NP-hardness

text: of

text: approximation

text: of

text: Max

text: Vertex-Disjoint

text: Path

text: namely

text: Theorem

text: in

text: Section

text: The

text: above

text: lemma

text: and

text: Theorem

text: immediately

text: imply

text: Theorem

text: Then,

text: we

text: describe

text: how

text: to

text: modify

text: the

text: reduction

text: to

text: arrive

text: at

text: a

text: similar

text: inapproximability

text: result

text: for

text: n

text: Max-Placement

text: Signed

text: Edge-Matching

text: Puzzle

text: (Corollary

text: in

text: Section

text: Lastly,

text: we

text: provide

text: another

text: reduction

text: to

text: obtain

text: the

text: inapproximability

text: result

text: for

text: n

text: Max-Matched

text: Edge-Matching

text: Puzzle

text: (Corollary

text: in

text: Section


text: (a) (b) Figure 9: (a) Possible constructions of path covers when the clause is satisﬁed (symmetric cases are omitted). (b) The shaded region must contain an endpoint if the path cover includes all thick edges. our assignment as follows. If there are no endpoints in x ’s variable territory, we assign the truth i value according to the literal in the path cover. Otherwise, assign an arbitrary one. We now show that our assignment fails to satisfy strictly less than α m clauses. 3SAT First, we prove the following lemma. Lemma 7. If a clause c is not satisﬁed by our assignment, then c ’s clause territory contains an j j endpoint. Proof. Suppose that there are no endpoints in any of the variable territories of any variable occurring in c . Then for c to be unsatisﬁed, all literal edges in c must be False and not included in the j j j path cover. Observation 1 implies that we must traverse all three edges on the right of c ’s clause j gadget; these are shown in Figure 9b as the curved thick edges. Notice that our path leaves the shaded vertices disconnected from the remaining part of the graph, which requires at least one additional path to cover. That is, there must still be an endpoint in the clause territory of c . j Lemma 7 implies that an endpoint must be present for a clause to be unsatisﬁed. Next, we show that each endpoint cannot be contained in very many clause territories. Lemma 8. Each endpoint is in at most 29 clause territories. Proof. If the endpoint is not in any variable territory, then it is in at most one clause territory because clause gadgets do not overlap. Otherwise, notice that the endpoint can be only in one variable territory as variable territories also do not overlap. One variable may occur at most 29 times, so a variable territory can be in at most 29 clause territories. Therefore, any endpoint can be in at most 29 clause territories. 19 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: (a)

text: (b)

text: Figure

text: (a)

label: caption

text: Possible

text: constructions

text: of

text: path

text: covers

text: when

text: the

text: clause

text: is

text: satisﬁed

text: (symmetric

text: cases

text: are

text: omitted).

text: (b)

text: The

text: shaded

text: region

text: must

text: contain

text: an

text: endpoint

text: if

text: the

text: path

text: cover

text: includes

text: all

text: thick

text: edges.

text: our

text: assignment

text: as

text: follows.

text: If

text: there

text: are

text: no

text: endpoints

text: in

text: x

text: ’s

text: variable

text: territory,

text: we

text: assign

text: the

text: truth

text: i

text: value

text: according

text: to

text: the

text: literal

text: in

text: the

text: path

text: cover.

text: Otherwise,

text: assign

text: an

text: arbitrary

text: one.

text: We

text: now

text: show

text: that

text: our

text: assignment

text: fails

text: to

text: satisfy

text: strictly

text: less

text: than

text: α

text: m

text: clauses.

text: First,

text: we

text: prove

text: the

text: following

text: lemma.

text: Lemma

text: If

text: a

text: clause

text: c

text: is

text: not

text: satisﬁed

text: by

text: our

text: assignment,

text: then

text: c

text: ’s

text: clause

text: territory

text: contains

text: an

text: j

text: j

text: endpoint.

text: Proof.

text: Suppose

text: that

text: there

text: are

text: no

text: endpoints

text: in

text: any

text: of

text: the

text: variable

text: territories

text: of

text: any

text: variable

text: occurring

text: in

text: c

text: Then

text: for

text: c

text: to

text: be

text: unsatisﬁed,

text: all

text: literal

text: edges

text: in

text: c

text: must

text: be

text: False

text: and

text: not

text: included

text: in

text: the

text: j

text: j

text: j

text: path

text: cover.

text: Observation

text: implies

text: that

text: we

text: must

text: traverse

text: all

text: three

text: edges

text: on

text: the

text: right

text: of

text: c

text: ’s

text: clause

text: j

text: gadget;

text: these

text: are

text: shown

text: in

text: Figure

text: as

text: the

text: curved

text: thick

text: edges.

text: Notice

text: that

text: our

text: path

text: leaves

text: the

text: shaded

text: vertices

text: disconnected

text: from

text: the

text: remaining

text: part

text: of

text: the

text: graph,

text: which

text: requires

text: at

text: least

text: one

text: additional

text: path

text: to

text: cover.

text: That

text: is,

text: there

text: must

text: still

text: be

text: an

text: endpoint

text: in

text: the

text: clause

text: territory

text: of

text: c

text: j

text: Lemma

text: implies

text: that

text: an

text: endpoint

text: must

text: be

text: present

text: for

text: a

text: clause

text: to

text: be

text: unsatisﬁed.

text: Next,

text: we

text: show

text: that

text: each

text: endpoint

text: cannot

text: be

text: contained

text: in

text: very

text: many

text: clause

text: territories.

text: Lemma

text: Each

text: endpoint

text: is

text: in

text: at

text: most

text: clause

text: territories.

text: Proof.

text: If

text: the

text: endpoint

text: is

text: not

text: in

text: any

text: variable

text: territory,

text: then

text: it

text: is

text: in

text: at

text: most

text: one

text: clause

text: territory

text: because

text: clause

text: gadgets

text: do

text: not

text: overlap.

text: Otherwise,

text: notice

text: that

text: the

text: endpoint

text: can

text: be

text: only

text: in

text: one

text: variable

text: territory

text: as

text: variable

text: territories

text: also

text: do

text: not

text: overlap.

text: One

text: variable

text: may

text: occur

text: at

text: most

text: times,

text: so

text: a

text: variable

text: territory

text: can

text: be

text: in

text: at

text: most

text: clause

text: territories.

text: Therefore,

text: any

text: endpoint

text: can

text: be

text: in

text: at

text: most

text: clause

text: territories.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: [ALM+98] Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof veriﬁcation and the hardness of approximation problems. Journal of the ACM, 45(3):501–555, May 1998. [AS98] Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: A new characteriza- tion of np. Journal of the ACM, 45(1):70–122, January 1998. [Coo71] Stephen A. Cook. The complexity of theorem-proving procedures. In Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, STOC ’71, pages 151–158, New York, NY, USA, 1971. ACM. [DD07] Erik D. Demaine and Martin L. Demaine. Jigsaw puzzles, edge matching, and polyomino packing: Connections and complexity. Graphs and Combinatorics, 23 (Supplement):195–208, June 2007. [EFW11] Martin Ebbesen, Paul Fischer, and Carsten Witt. Edge-matching problems with rota- tions. In Proceedings of the 18th International Symposium on Fundamentals of Com- putation Theory, volume 6914 of Lecture Notes in Computer Science, pages 114–125, Oslo, Norway, August 2011. [Eng03] Lars Engebretsen. An explicit lower bound for TSP with distances one and two. Algo- rithmica, 35(4):301–319, 2003. [Fei98] Uriel Feige. A threshold of ln N for approximating set cover. Journal of the ACM, 45(4):634–652, July 1998. [GJ79] Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA, 1979. [GJT76] Michael R. Garey, David S. Johnson, and Robert E. Tarjan. The planar Hamiltonian circuit problem is NP-complete. SIAM Journal on Computing, 5(4):704–714, 1976. [Hau95] Jacques Haubrich. Compendium of Card Matching Puzzles. Self-published, May 1995. Three volumes. [Kar72] Richard M. Karp. Reducibility among combinatorial problems. In Raymond E. Miller, James W. Thatcher, and Jean D. Bohlinger, editors, Complexity of Computer Compu- tations, The IBM Research Symposia Series, pages 85–103. Springer US, 1972. [Ple79] J´an Plesn´ık. The NP-completeness of the Hamiltonian cycle problem in planar diagraphs with degree bound two. Information Processing Letters, 8(4):199–201, April 1979. [PY88] Christos Papadimitriou and Mihalis Yannakakis. Optimization, approximation, and complexity classes. In Proceedings of the 20th Annual ACM Symposium on Theory of Computing, pages 229–234, New York, NY, USA, 1988. ACM. [Thu09] Christel Thunell. Lundafamilj b¨ast i v¨arlden p˚a sv˚arkn¨ackt pussel. Sydsven- skan, January 21 2009. http://www.sydsvenskan.se/lund/lundafamilj-bast-i-varlden- pa-svarknackt-pussel/. 21

text: Sanjeev

text: Arora,

text: Carsten

text: Lund,

text: Rajeev

text: Motwani,

text: Madhu

text: Sudan,

text: and

text: Mario

text: Szegedy.

text: Proof

text: veriﬁcation

text: and

text: the

text: hardness

text: of

text: approximation

text: problems.

text: Journal

text: of

text: the

text: ACM,

text: May

text: Sanjeev

text: Arora

text: and

text: Shmuel

text: Safra.

text: Probabilistic

text: checking

text: of

text: proofs:

text: A

text: new

text: characteriza-

text: tion

text: of

text: np.

text: Journal

text: of

text: the

text: ACM,

text: January

text: Stephen

text: A.

text: Cook.

text: The

text: complexity

text: of

text: theorem-proving

text: procedures.

text: In

text: Proceedings

text: of

text: the

text: Annual

text: ACM

text: Symposium

text: on

text: Theory

text: of

text: Computing,

text: STOC

text: pages

text: New

text: York,

text: NY,

text: USA,

text: ACM.

text: Erik

text: D.

text: Demaine

text: and

text: Martin

text: L.

text: Demaine.

text: Jigsaw

text: puzzles,

text: edge

text: matching,

text: and

text: polyomino

text: packing:

text: Connections

text: and

text: complexity.

text: Graphs

text: and

text: Combinatorics,

text: June

text: Martin

text: Ebbesen,

text: Paul

text: Fischer,

text: and

text: Carsten

text: Witt.

text: Edge-matching

text: problems

text: with

text: rota-

text: tions.

text: In

text: Proceedings

text: of

text: the

text: International

text: Symposium

text: on

text: Fundamentals

text: of

text: Com-

text: putation

text: Theory,

text: volume

text: of

text: Lecture

text: Notes

text: in

text: Computer

text: Science,

text: pages

text: Oslo,

text: Norway,

text: August

text: Lars

text: Engebretsen.

text: An

text: explicit

text: lower

text: bound

text: for

text: TSP

text: with

text: distances

text: one

text: and

text: two.

text: Algo-

text: rithmica,

text: Uriel

text: Feige.

text: A

text: threshold

text: of

text: ln

text: N

text: for

text: approximating

text: set

text: cover.

text: Journal

text: of

text: the

text: ACM,

text: July

text: Michael

text: R.

text: Garey

text: and

text: David

text: S.

text: Johnson.

text: Computers

text: and

text: Intractability:

text: A

text: Guide

text: to

text: the

text: Theory

text: of

text: NP-Completeness.

text: W.

text: H.

text: Freeman

text: Co.,

text: New

text: York,

text: NY,

text: USA,

text: Michael

text: R.

text: Garey,

text: David

text: S.

text: Johnson,

text: and

text: Robert

text: E.

text: Tarjan.

text: The

text: planar

text: Hamiltonian

text: circuit

text: problem

text: is

text: NP-complete.

text: SIAM

text: Journal

text: on

text: Computing,

text: Jacques

text: Haubrich.

text: Compendium

text: of

text: Card

text: Matching

text: Puzzles.

text: Self-published,

text: May

text: Three

text: volumes.

text: Richard

text: M.

text: Karp.

text: Reducibility

text: among

text: combinatorial

text: problems.

text: In

text: Raymond

text: E.

text: Miller,

text: James

text: W.

text: Thatcher,

text: and

text: Jean

text: D.

text: Bohlinger,

text: editors,

text: Complexity

text: of

text: Computer

text: Compu-

text: tations,

text: The

text: IBM

text: Research

text: Symposia

text: Series,

text: pages

text: Springer

text: US,

text: J´an

text: Plesn´ık.

text: The

text: NP-completeness

text: of

text: the

text: Hamiltonian

text: cycle

text: problem

text: in

text: planar

text: diagraphs

text: with

text: degree

text: bound

text: two.

text: Information

text: Processing

text: Letters,

text: April

text: Christos

text: Papadimitriou

text: and

text: Mihalis

text: Yannakakis.

text: Optimization,

text: approximation,

text: and

text: complexity

text: classes.

text: In

text: Proceedings

text: of

text: the

text: Annual

text: ACM

text: Symposium

text: on

text: Theory

text: of

text: Computing,

text: pages

text: New

text: York,

text: NY,

text: USA,

text: ACM.

text: Christel

text: Thunell.

text: Lundafamilj

text: b¨ast

text: i

text: v¨arlden

text: p˚a

text: sv˚arkn¨ackt

text: pussel.

text: Sydsven-

text: skan,

text: January

text: pa-svarknackt-pussel/.


text: Step 6. For q = 0, i.e., φ = X−, the harmonicity equation (6.3.1) becomes − · (6.3.2) ∂¯∂ log λ R2 λ2 = 0, which can be solved explicitly. We obtain 1 · i (6.3.3) λ = − . 0 R z z¯ Let us denote by i 1 (6.3.4) λ = − = · , (cid:92) z z¯ 2 y where z = x + iy. The corresponding hermitian metric is then · dz dz¯ g = · , (cid:92) 4 y2 whose Gaussian curvature is − 4 · − (6.3.5) K := ∂∂¯log λ = 4. λ2 (cid:92) (cid:92) H Indeed, g is the globally deﬁned constant curvature metric on the upper half plane , which is (cid:92) R H invariant u≥nder the action of P SL2( )H= Aut( ). Since we are dealing with a Rieman∼n sHurface C of genus g 2, its universal covering is , and we have a non-canonical isomorphism C = /π (C), H −→ R 1 where π (C) acts on through a representation ρ : π (C) SL ( ). By inducing a metric by 1 H −→ 1 2 the push-forward of the covering map C, we conclude that the harmonicity equation (6.3.2) − can be solved globally on C with(cid:20)the h(cid:21)yperbolic metric(cid:20)on C of(cid:21)constant(cid:20)curvat(cid:21)ure 4R2. (cid:126) Since ζ = , we obtain R 1 · 0 0 · − · 1 0 (cid:126) · 0 λ2 D(ζ, R) = d + (cid:126) 1 0 dz ∂ log λ(cid:92) 0 −1 dz + 0 0(cid:92) dz¯ (6.3.6) 1 · · − · · (cid:126) · · · = d + (cid:126) dz X1 ∂ log λ(cid:92) dz H + λ2(cid:92) dz¯ X+, which does not depend on R. (cid:54) Step 7. The case when q = 0 in general. We remark that any hermitian metric compatible with the complex structure of C is conformal to the constant curvature metric g . Therefore, we can (cid:92) write · λ · λ = λ ef(R) = (cid:92) ef(R) 0 R with a conformal factor ef(R) depending on a real valued function f(R) on C. We plug this expression into (6.3.1) and apply the implicit function theorem to yield that f is real analytic, and · more signiﬁcantly, that f(R) = f R4+ higher order terms. This implies 4 − R2 · − R2 O λ O O λ 2 = e 2f(R) = + (R6), λ = (cid:92) + (R3), ∂ log λ = ∂ log λ + (R4). λ2 λ2 R (cid:92) (cid:92) (cid:92) 26 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Step

text: For

text: q

text: i.e.,

text: φ

text: X−,

text: the

text: harmonicity

text: equation

text: becomes

text: log

text: λ

text: λ2

text: which

text: can

text: be

text: solved

text: explicitly.

text: We

text: obtain

text: i

text: λ

text: R

text: z

text: z¯

text: Let

text: us

text: denote

text: by

text: i

text: λ

text: z

text: z¯

text: y

text: where

text: z

text: x

text: iy.

text: The

text: corresponding

text: hermitian

text: metric

text: is

text: then

text: dz

text: dz¯

text: g

text: whose

text: Gaussian

text: curvature

text: is

text: K

text: ∂∂¯log

text: λ

text: λ2

text: H

text: Indeed,

text: g

text: is

text: the

text: globally

text: deﬁned

text: constant

text: curvature

text: metric

text: on

text: the

text: upper

text: half

text: plane

text: which

text: is

text: R

text: H

text: invariant

text: u≥nder

text: the

text: action

text: of

text: P

text: )H=

text: Aut(

text: Since

text: we

text: are

text: dealing

text: with

text: a

text: Rieman∼n

text: sHurface

text: C

text: of

text: genus

text: g

text: its

text: universal

text: covering

text: is

text: and

text: we

text: have

text: a

text: non-canonical

text: isomorphism

text: C

text: /π

text: (C),

text: H

text: R

text: where

text: π

text: (C)

text: acts

text: on

text: through

text: a

text: representation

text: ρ

text: π

text: (C)

text: SL

text: By

text: inducing

text: a

text: metric

text: by

text: H

text: the

text: push-forward

text: of

text: the

text: covering

text: map

text: C,

text: we

text: conclude

text: that

text: the

text: harmonicity

text: equation

text: can

text: be

text: solved

text: globally

text: on

text: C

text: C

text: Since

text: ζ

text: we

text: obtain

text: R

text: λ2

text: D(ζ,

text: R)

text: d

text: dz

text: log

text: −1

text: dz

text: dz¯

text: d

text: dz

text: log

text: dz

text: H

text: dz¯

text: X+,

text: which

text: does

text: not

text: depend

text: on

text: R.

text: Step

text: The

text: case

text: when

text: q

text: in

text: general.

text: We

text: remark

text: that

text: any

text: hermitian

text: metric

text: compatible

text: with

text: the

text: complex

text: structure

text: of

text: C

text: is

text: conformal

text: to

text: the

text: constant

text: curvature

text: metric

text: g

text: Therefore,

text: we

text: can

text: write

text: λ

text: λ

text: λ

text: ef(R)

text: ef(R)

text: R

text: with

text: a

text: conformal

text: factor

text: ef(R)

text: depending

text: on

text: a

text: real

text: valued

text: function

text: f(R)

text: on

text: C.

text: We

text: plug

text: this

text: expression

text: into

text: and

text: apply

text: the

text: implicit

text: function

text: theorem

text: to

text: yield

text: that

text: f

text: is

text: real

text: analytic,

text: and

text: more

text: signiﬁcantly,

text: that

text: f(R)

text: f

text: higher

text: order

text: terms.

text: This

text: implies

text: O

text: λ

text: O

text: O

text: λ

text: e

text: λ

text: log

text: λ

text: log

text: λ

text: λ2

text: λ2

text: R

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: C Here, we only indicate the oper we obtain through Gaiotto’s scaling limit for the case of SL ( )- r Higgs bundles. We will give a geometric deﬁnition of oper that generalizes Gunning’s Deﬁnition encaptured by Theorem 5.7 from rank two to arbitrary rank r. Deﬁnition 7.2 (Beilinson-Drinfeld, 1993). Let V be a holomorphic vector bundle of rank r and C ∇ ∈ M degree 0. An SL ( )-oper is a pair (V, ) satisfying the following conditions: r deR → → → (1) There is a global ﬁltration 0 = F (cid:44) F − (cid:44) . . . (cid:44) F = V in V . r r∇1 0 ∇| → ⊗ (2) Griﬃths transversality. The connection induces a map : F F K for every − Fi+1 i+1 i C i = 0, . . . , r 1. ∼ ∇| O ⊗ (3) induces an -linear isomorphism F /F = F /F K for every i. Fi+1 C i+1 i+2 i i+1 C Let (E , φ(q)) be a point on the Hitchin section of Section 3.2. Then Gaiotto’s scaling limit 0 (cid:126) ∇(cid:126) produces an -family of opers (V(cid:126), ) deﬁned as follows. First, we choose once and for all the M¨obius coordinate system associated with the uniformization mentioned above. (cid:18) (cid:19) • { (cid:126) } V(cid:126) is given by the transition function f , where αβ (cid:126) · · (cid:126) · d log ξαβ · f = exp(H log ξ ) exp X . αβ αβ dz + β • The connection is deﬁned by ∇(cid:126) 1 · := d + (cid:126) φ(q). Note that this deﬁnition is globally valid with respect to a M¨obius coordinate system. • r−1 ⊕ ⊕ −r−1 (cid:126) · V = K 2 . . . K 2 = E , since f =0 = exp(H log ξ ) = ξH . 0 C C 0 αβ αβ αβ • r−1 There is a unique ﬁltration in the vector bundle V(cid:126) with F − = K 2 that satisﬁes the r 1 C conditions of Deﬁnition 7.2. • (cid:126) (cid:54) The vector bundles V(cid:126) are isomorphic for all = 0. We refer to [14, 15] for more detail. 8. Conclusion We emphasize again that the nonabelian Hodge correspondence is a diﬀeomorphism between M M and . ([8, 26, 38]). Conjecture 6.2 of Gaiotto realizes a holomorphic point by Dol deR M point correspondence between two holomorphic Lagrangians, the Hitchin section in and M Dol the moduli space of opers in . Since the quantum curve should depend holomorphically on deR the spectral curve, we consider the Gaiotto correspondence as the desired construction of quantum curves. • Donaldson, Hitchin, Simpson Nonabelian-Hodge correspondence M −→ M diﬀeomorphism Dol deR • Gaiotto’s conjecture gives a holomorphic correspondence between Lagrangians −→ holomorphic Hitchin Section moduli space of opers 29 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: C

text: Here,

text: we

text: only

text: indicate

text: the

text: oper

text: we

text: obtain

text: through

text: Gaiotto’s

text: scaling

text: limit

text: for

text: the

text: case

text: of

text: SL

text: r

text: Higgs

text: bundles.

text: We

text: will

text: give

text: a

text: geometric

text: deﬁnition

text: of

text: oper

text: that

text: generalizes

text: Gunning’s

text: Deﬁnition

text: encaptured

text: by

text: Theorem

text: from

text: rank

text: two

text: to

text: arbitrary

text: rank

text: r.

text: Deﬁnition

text: (Beilinson-Drinfeld,

text: Let

text: V

text: be

text: a

text: holomorphic

text: vector

text: bundle

text: of

text: rank

text: r

text: and

text: C

text: M

text: degree

text: An

text: SL

text: )-oper

text: is

text: a

text: pair

text: (V,

text: satisfying

text: the

text: following

text: conditions:

text: r

text: deR

label: list

text: There

text: is

text: a

text: global

text: ﬁltration

text: F

text: F

text: F

text: V

text: in

text: V

text: r

text: Griﬃths

text: transversality.

text: The

text: connection

text: induces

text: a

text: map

text: F

text: F

text: K

text: for

text: every

text: i

text: C

text: i

text: r

text: O

text: induces

text: an

text: -linear

text: isomorphism

text: F

text: /F

text: F

text: /F

text: K

text: for

text: every

text: i.

text: C

text: i

text: C

text: Let

text: (E

text: φ(q))

text: be

text: a

text: point

text: on

text: the

text: Hitchin

text: section

text: of

text: Section

text: Then

text: Gaiotto’s

text: scaling

text: limit

text: produces

text: an

text: -family

text: of

text: opers

text: deﬁned

text: as

text: follows.

text: First,

text: we

text: choose

text: once

text: and

text: for

text: all

text: the

text: M¨obius

text: coordinate

text: system

text: associated

text: with

text: the

text: uniformization

text: mentioned

text: above.

text: is

text: given

text: by

text: the

text: transition

text: function

text: f

text: where

text: αβ

text: d

text: log

text: ξαβ

text: f

text: exp(H

text: log

text: ξ

text: exp

text: X

text: αβ

text: αβ

text: dz

text: β

text: The

text: connection

text: is

text: deﬁned

text: by

text: d

text: φ(q).

text: Note

text: that

text: this

text: deﬁnition

text: is

text: globally

text: valid

text: with

text: respect

text: to

text: a

text: M¨obius

text: coordinate

text: system.

text: −r−1

text: V

text: K

text: K

text: E

text: since

text: f

text: exp(H

text: log

text: ξ

text: ξH

text: C

text: C

text: αβ

text: αβ

text: αβ

text: There

text: is

text: a

text: unique

text: ﬁltration

text: in

text: the

text: vector

text: bundle

text: with

text: F

text: K

text: that

text: satisﬁes

text: the

text: r

text: C

text: conditions

text: of

text: Deﬁnition

text: The

text: vector

text: bundles

text: are

text: isomorphic

text: for

text: all

text: We

text: refer

text: to

text: for

text: more

text: detail.

text: Conclusion

text: We

text: emphasize

text: again

text: that

text: the

text: nonabelian

text: Hodge

text: correspondence

text: is

text: a

text: diﬀeomorphism

text: between

text: M

text: M

text: and

text: Conjecture

text: of

text: Gaiotto

text: realizes

text: a

text: holomorphic

text: point

text: by

text: Dol

text: deR

text: M

text: point

text: correspondence

text: between

text: two

text: holomorphic

text: Lagrangians,

text: the

text: Hitchin

text: section

text: in

text: and

text: M

text: Dol

text: the

text: moduli

text: space

text: of

text: opers

text: in

text: Since

text: the

text: quantum

text: curve

text: should

text: depend

text: holomorphically

text: on

text: deR

text: the

text: spectral

text: curve,

text: we

text: consider

text: the

text: Gaiotto

text: correspondence

text: as

text: the

text: desired

text: construction

text: of

text: quantum

text: curves.

text: Donaldson,

text: Hitchin,

text: Simpson

text: Nonabelian-Hodge

text: correspondence

text: M

text: M

text: diﬀeomorphism

text: Dol

text: deR

text: Gaiotto’s

text: conjecture

text: gives

text: a

text: holomorphic

text: correspondence

text: between

text: Lagrangians

text: holomorphic

text: Hitchin

text: Section

text: moduli

text: space

text: of

text: opers

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Nonlinear Flows for Displacement Correction and Applications in Tomography Guozhi Dong1 and Otmar Scherzer1,2 1 Computational Science Center, University of Vienna, Oskar-Morgenstern-Platz 1, 1090 Wien, Austria {guozhi.dong,otmar.scherzer}@univie.ac.at 2 Johann Radon Institute for Computational and Applied Mathematics (RICAM), Austrian Academy of Sciences, Altenbergerstrasse 69, A-4040 Linz, Austria Abstract. In this paper we derive nonlinear evolution equations asso- ciated with a class of non-convex energy functionals which can be used for correcting displacement errors in imaging data. We study properties of these ﬁltering ﬂows and provide experiments for correcting angular perturbations in tomographical data. Keywords: Non-convex regularization, nonlinear ﬂow, displacement correction, Radon transform, angular perturbation 1 Introduction In this paper, we are investigating variational methods and partial diﬀeren- tial equations for ﬁltering displacement errors in imaging data. Such types of errors appear when measurement data are sampled erroneously. In this work we consider measurement data uδ, which are considered perturbations of an ideal function u at random sampling locations (x + d (x ), x ): That is, 1 i i 2 ∈ uδ(x) = u(x1 + di(xi), x2), for x = (x1, x2) R2. (1) → A particular case of a displacement error x d (x ) appears in Comput- 1 1 1 erized Tomography (here the x -component denotes the X-ray beam direction 1 (θ below)) when the angular sampling is considered erroneous. In this case the recorded data are yδ(θ, l) = R[f](θ + d (θ), l). (2) 1 Here R[f] denotes the Radon transform or X-ray transform of the function f, and θ and l denote the beam direction and beam distance, respectively.

text: Nonlinear

label: title

text: Flows

text: for

text: Displacement

text: Correction

text: and

text: Applications

text: in

text: Tomography

text: Guozhi

label: author

text: and

text: Otmar

text: Computational

text: Science

text: Center,

text: University

text: of

text: Vienna,

text: Oskar-Morgenstern-Platz

text: Wien,

text: Austria

text: Johann

text: Radon

text: Institute

text: for

text: Computational

text: and

text: Applied

text: Mathematics

text: (RICAM),

text: Austrian

text: Academy

text: of

text: Sciences,

text: Altenbergerstrasse

text: Linz,

text: Austria

text: Abstract.

text: In

label: abstract

text: this

text: paper

text: we

text: derive

text: nonlinear

text: evolution

text: equations

text: asso-

text: ciated

text: with

text: a

text: class

text: of

text: non-convex

text: energy

text: functionals

text: which

text: can

text: be

text: used

text: for

text: correcting

text: displacement

text: errors

text: in

text: imaging

text: data.

text: We

text: study

text: properties

text: of

text: these

text: ﬁltering

text: ﬂows

text: and

text: provide

text: experiments

text: for

text: correcting

text: angular

text: perturbations

text: in

text: tomographical

text: data.

text: Keywords:

text: Non-convex

text: regularization,

text: nonlinear

text: ﬂow,

text: displacement

text: correction,

text: Radon

text: transform,

text: angular

text: perturbation

text: Introduction

text: In

text: this

text: paper,

text: we

text: are

text: investigating

text: variational

text: methods

text: and

text: partial

text: diﬀeren-

text: tial

text: equations

text: for

text: ﬁltering

text: displacement

text: errors

text: in

text: imaging

text: data.

text: Such

text: types

text: of

text: errors

text: appear

text: when

text: measurement

text: data

text: are

text: sampled

text: erroneously.

text: In

text: this

text: work

text: we

text: consider

text: measurement

text: data

text: uδ,

text: which

text: are

text: considered

text: perturbations

text: of

text: an

text: ideal

text: function

text: u

text: at

text: random

text: sampling

text: locations

text: (x

text: d

text: (x

text: x

text: That

text: is,

text: i

text: i

text: uδ(x)

text: di(xi),

text: for

text: x

text: A

text: particular

text: case

text: of

text: a

text: displacement

text: error

text: x

text: d

text: (x

text: appears

text: in

text: Comput-

text: erized

text: Tomography

text: (here

text: the

text: x

text: -component

text: denotes

text: the

text: X-ray

text: beam

text: direction

text: (θ

text: below))

text: when

text: the

text: angular

text: sampling

text: is

text: considered

text: erroneous.

text: In

text: this

text: case

text: the

text: recorded

text: data

text: are

text: yδ(θ,

text: l)

text: R[f](θ

text: d

text: (θ),

text: l).

text: Here

text: R[f]

text: denotes

text: the

text: Radon

text: transform

text: or

text: X-ray

text: transform

text: of

text: the

text: function

text: f,

text: and

text: θ

text: and

text: l

text: denote

text: the

text: beam

text: direction

text: and

text: beam

text: distance,

text: respectively.


text: 12 G. Dong, and O. Scherzer The work of OS has been supported by the Austrian Science Fund (FWF): Geometry and Simulation, project S11704 (Variational methods for imaging on manifolds), and Interdisciplinary Coupled Physics Imaging, project P26687-N25. References 1. R. Burkard, M. Dellamico, and S. Martello. Assignment Problems, revised reprint. Other titles in applied mathematics, SIAM Philadelphia, 2009. Revised edition. 2. T. Chan and P. Mulet. On the convergence of the lagged diﬀusivity ﬁxed point method in total variation image restoration. SIAM J. Numer. Anal., 36(2):354– 367, 1999. 3. G. Dong, A.R. Patrone, O. Scherzer, and O. O¨ktem. Inﬁnite dimensional opti- mization models and pdes for dejittering. In Scale Space and Variational Methods in Computer Vision 5th International Conference, SSVM 2015, L`ege-Cap Ferret, France, May 31 - June 4, 2015, Proceedings, pages 678–689. Springer. 4. L. C. Evans and J. Spruck. Motion of level sets by mean curvature. I. J. Diﬀerential Geom., 33:635–681, 1991. 5. L. C. Evans and J. Spruck. Motion of level sets by mean curvature. II. Trans. Amer. Math. Soc., 330:321–332, 1992. 6. S. H. Kang and J. Shen. Video dejittering by bake and shake. Image Vision Comput., 24(2):143–152, 2006. 7. F. Lenzen and O. Scherzer. A geometric pde for interpolation of m-channel data. In SSVM ’09: Proceedings of the Second International Conference on Scale Space and Variational Methods in Computer Vision, pages 413–425, Berlin, Heidelberg, 2009. Springer-Verlag. 8. F. Lenzen and O. Scherzer. Partial diﬀerential equations for zooming, deinterlacing and dejittering. Int. J. Comput. Vision, 92(2):162–176, April 2011. 9. J. Munkres. Algorithms for assignment and transportation problems. J. Soc. Indu. Appl. Math., 5(1):32–38, Mar 1957. 10. F. Natterer and F. Wu¨bbeling. Mathematical Methods in Image Reconstruc- tion. SIAM Monographs on Mathematical Modelling and Computation, SIAM Philadelphia, 2001. 11. M. Nikolova. Fast dejittering for digital video frames. In X.C. Tai, M. Knut, L. Mar- ius, and L. Knut-Andreas, editors, SSVM’09, LNCS, pages 439–451. Springer Berlin Heidelberg, 2009. 12. M. Nikolova. One-iteration dejittering of digital video images. J. Vis. Commun. Image Represent., 20:254–274, 2009. 13. O. O¨ktem. Mathematics of Electron Tomography. In O. Scherzer, editors, Handbook of Mathematical Methods in Imaging, pages 937–1031, 2015. Springer New York. 14. S. Voss. Heuristics for nonlinear assignment problems. In P. M. Pardalos, and L. Pitsoulis, editors, Nonlinear Assignment Problems, algorithms and applications, Volume 7 of the series Combinatorial Optimization, pages 175–215, 2000. Kluwer Academic Publishers. 15. J. Shen. Bayesian video dejittering by bv image model. SIAM J. Appl. Math., 64(5):1691–1708, 2004. 16. K. Uhlenbeck. Regularity for a class of non-linear elliptic systems. Acta Math., 138(1):219–240, 1977.

text: G.

text: Dong,

text: and

text: O.

text: Scherzer

text: The

text: work

text: of

text: OS

text: has

text: been

text: supported

text: by

text: the

text: Austrian

text: Science

text: Fund

text: (FWF):

text: Geometry

text: and

text: Simulation,

text: project

text: (Variational

text: methods

text: for

text: imaging

text: on

text: manifolds),

text: and

text: Interdisciplinary

text: Coupled

text: Physics

text: Imaging,

text: project

text: References

text: R.

text: Burkard,

text: M.

text: Dellamico,

text: and

text: S.

text: Martello.

text: Assignment

text: Problems,

text: revised

text: reprint.

text: Other

text: titles

text: in

text: applied

text: mathematics,

text: SIAM

text: Philadelphia,

text: Revised

text: edition.

text: T.

text: Chan

text: and

text: P.

text: Mulet.

text: On

text: the

text: convergence

text: of

text: the

text: lagged

text: diﬀusivity

text: ﬁxed

text: point

text: method

text: in

text: total

text: variation

text: image

text: restoration.

text: SIAM

text: J.

text: Numer.

text: Anal.,

text: G.

text: Dong,

text: A.R.

text: Patrone,

text: O.

text: Scherzer,

text: and

text: O.

text: O¨ktem.

text: Inﬁnite

text: dimensional

text: opti-

text: mization

text: models

text: and

text: pdes

text: for

text: dejittering.

text: In

text: Scale

text: Space

text: and

text: Variational

text: Methods

text: in

text: Computer

text: Vision

text: International

text: Conference,

text: SSVM

text: L`ege-Cap

text: Ferret,

text: France,

text: May

text: June

text: Proceedings,

text: pages

text: Springer.

text: L.

text: C.

text: Evans

text: and

text: J.

text: Spruck.

text: Motion

text: of

text: level

text: sets

text: by

text: mean

text: curvature.

text: I.

text: J.

text: Diﬀerential

text: Geom.,

text: L.

text: C.

text: Evans

text: and

text: J.

text: Spruck.

text: Motion

text: of

text: level

text: sets

text: by

text: mean

text: curvature.

text: II.

text: Trans.

text: Amer.

text: Math.

text: Soc.,

text: S.

text: H.

text: Kang

text: and

text: J.

text: Shen.

text: Video

text: dejittering

text: by

text: bake

text: and

text: shake.

text: Image

text: Vision

text: Comput.,

text: F.

text: Lenzen

text: and

text: O.

text: Scherzer.

text: A

text: geometric

text: pde

text: for

text: interpolation

text: of

text: m-channel

text: data.

text: In

text: SSVM

text: Proceedings

text: of

text: the

text: Second

text: International

text: Conference

text: on

text: Scale

text: Space

text: and

text: Variational

text: Methods

text: in

text: Computer

text: Vision,

text: pages

text: Berlin,

text: Heidelberg,

text: Springer-Verlag.

text: F.

text: Lenzen

text: and

text: O.

text: Scherzer.

text: Partial

text: diﬀerential

text: equations

text: for

text: zooming,

text: deinterlacing

text: and

text: dejittering.

text: Int.

text: J.

text: Comput.

text: Vision,

text: April

text: J.

text: Munkres.

text: Algorithms

text: for

text: assignment

text: and

text: transportation

text: problems.

text: J.

text: Soc.

text: Indu.

text: Appl.

text: Math.,

text: Mar

text: F.

text: Natterer

text: and

text: F.

text: Wu¨bbeling.

text: Mathematical

text: Methods

text: in

text: Image

text: Reconstruc-

text: tion.

text: SIAM

text: Monographs

text: on

text: Mathematical

text: Modelling

text: and

text: Computation,

text: SIAM

text: Philadelphia,

text: M.

text: Nikolova.

text: Fast

text: dejittering

text: for

text: digital

text: video

text: frames.

text: In

text: X.C.

text: Tai,

text: M.

text: Knut,

text: L.

text: Mar-

text: ius,

text: and

text: L.

text: Knut-Andreas,

text: editors,

text: LNCS,

text: pages

text: Springer

text: Berlin

text: Heidelberg,

text: M.

text: Nikolova.

text: One-iteration

text: dejittering

text: of

text: digital

text: video

text: images.

text: J.

text: Vis.

text: Commun.

text: Image

text: Represent.,

text: O.

text: O¨ktem.

text: Mathematics

text: of

text: Electron

text: Tomography.

text: In

text: O.

text: Scherzer,

text: editors,

text: Handbook

text: of

text: Mathematical

text: Methods

text: in

text: Imaging,

text: pages

text: Springer

text: New

text: York.

text: S.

text: Voss.

text: Heuristics

text: for

text: nonlinear

text: assignment

text: problems.

text: In

text: P.

text: M.

text: Pardalos,

text: and

text: L.

text: Pitsoulis,

text: editors,

text: Nonlinear

text: Assignment

text: Problems,

text: algorithms

text: and

text: applications,

text: Volume

text: of

text: the

text: series

text: Combinatorial

text: Optimization,

text: pages

text: Kluwer

text: Academic

text: Publishers.

text: J.

text: Shen.

text: Bayesian

text: video

text: dejittering

text: by

text: bv

text: image

text: model.

text: SIAM

text: J.

text: Appl.

text: Math.,

text: K.

text: Uhlenbeck.

text: Regularity

text: for

text: a

text: class

text: of

text: non-linear

text: elliptic

text: systems.

text: Acta

text: Math.,


text: Then, following the strategy proposed by [4], we remove samples that are currently misclassiﬁed so as to reach the desired size (if possible) based on how far on the wrong side of the margin they are (lines 10 to 15). The intuition is that such samples are likely to be noise and are deforming the boundary in a very convoluted way. Not only they require a coeﬃcient for themselves only, but they also provide no generalization which is a hint of overﬁtting. Lastly, if the SV set is still over the budget, we remove samples with minimal absolute value weights (lines 16 to 19). The idea is that these samples are the least contributing to the decision function and thus can be removed as a last resort. A better choice would be to balance the weight of the samples by the norm of the corresponding columns in the kernel matrix to take into account the inﬂuence the sample has on its neighborhood. However, we didn’t found it to be signiﬁcantly better in practice while being much more costly. Algorithm 2 SV Set pruning A { } 1: funSct←ion∅ pBru←ne∅( = (xi, αi) , n) 2: , |A| 3: for i = 0 to do A (cid:80) 4: updat(cid:54) e( , xi, yi) 5: if αi =←0 then 6: zBi ← Byi∪ n αnk(xi, xn) 7: (xi, zi) 8: end if 9: end for |B| 10: if > n then B 11: so←rt by decreasing zi 12: θB ←mBi\n({0, zn) | } 13: (xi, zi) zi < θ 14: end if S ← { ∈ A | ∈ B} 15: |S| (xi, αi) (xi, zi) 16: if > n then S | | 17: sSor←t S b\y{decreasi|ng αi } 18: (xi, αi) i > n 19: end if S 20: return 21: end function 4 Divide and Conquer approach Limiting the number of support vectors has the advantage of speeding up the decision function, which has a positive impact on both the training and testing phases, since the online training scheme also uses the evaluation of the decision function to update the weights. However, it also comes at the price of a simpler boundary which can lead reduced accuracy. To overcome this problem, we propose to use a divide and conquer approach inspired from [5] where S the input space is partitioned into K clusters µ and a budget constrained SV set is learned inside k k each part. The algorithm has now two parameters, namely the number of clusters K and the budget of each SV set n, which make the total storage cost of the model of size Kn support vectors. However, O the evaluation cost is only (K + n) since the decision function is only computed in the corresponding cluster. The full algorithm is detailed in Algorithm 3. To provide a fully online learning scheme, we propose to learn the partition also online using LVQ [6]. While we have not reach this number, we recruit a new cluster centered on the current sample, and associate with it a SV set consisting of the sample and it label as weight (lines 3 to 5). If k clusters are already present, we assign the current sample to its closest center k (line 7). We S then update the corresponding center using standard LVQ (line 8) and update the SV set using the S k update online procedure. We use the pruning procedure to keep the size of under the constraint if needed. Although the algorithm is simply to program, our version is publicly available1. 1download full project at https://github.com/davidpicard/dc-bsdca 3 ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Then,

text: following

text: the

text: strategy

text: proposed

text: by

text: we

text: remove

text: samples

text: that

text: are

text: currently

text: misclassiﬁed

text: so

text: as

text: to

text: reach

text: the

text: desired

text: size

text: (if

text: possible)

text: based

text: on

text: how

text: far

text: on

text: the

text: wrong

text: side

text: of

text: the

text: margin

text: they

text: are

text: (lines

text: to

text: The

text: intuition

text: is

text: that

text: such

text: samples

text: are

text: likely

text: to

text: be

text: noise

text: and

text: are

text: deforming

text: the

text: boundary

text: in

text: a

text: very

text: convoluted

text: way.

text: Not

text: only

text: they

text: require

text: a

text: coeﬃcient

text: for

text: themselves

text: only,

text: but

text: they

text: also

text: provide

text: no

text: generalization

text: which

text: is

text: a

text: hint

text: of

text: overﬁtting.

text: Lastly,

text: if

text: the

text: SV

text: set

text: is

text: still

text: over

text: the

text: budget,

text: we

text: remove

text: samples

text: with

text: minimal

text: absolute

text: value

text: weights

text: (lines

text: to

text: The

text: idea

text: is

text: that

text: these

text: samples

text: are

text: the

text: least

text: contributing

text: to

text: the

text: decision

text: function

text: and

text: thus

text: can

text: be

text: removed

text: as

text: a

text: last

text: resort.

text: A

text: better

text: choice

text: would

text: be

text: to

text: balance

text: the

text: weight

text: of

text: the

text: samples

text: by

text: the

text: norm

text: of

text: the

text: corresponding

text: columns

text: in

text: the

text: kernel

text: matrix

text: to

text: take

text: into

text: account

text: the

text: inﬂuence

text: the

text: sample

text: has

text: on

text: its

text: neighborhood.

text: However,

text: we

text: didn’t

text: found

text: it

text: to

text: be

text: signiﬁcantly

text: better

text: in

text: practice

text: while

text: being

text: much

text: more

text: costly.

text: Algorithm

text: SV

text: Set

text: pruning

text: A

text: funSct←ion∅

text: pBru←ne∅(

text: (xi,

text: αi)

text: n)

text: |A|

text: for

text: i

text: to

text: do

text: A

text: e(

text: xi,

text: yi)

text: if

text: αi

text: then

text: zBi

text: Byi∪

text: n

text: αnk(xi,

text: xn)

text: (xi,

text: zi)

text: end

text: if

text: end

text: for

text: |B|

text: if

text: n

text: then

text: B

text: so←rt

text: by

text: decreasing

text: zi

text: θB

text: zn)

text: (xi,

text: zi)

text: zi

text: θ

text: end

text: if

text: S

text: A

text: B}

text: |S|

text: (xi,

text: αi)

text: (xi,

text: zi)

text: if

text: n

text: then

text: S

text: sSor←t

text: S

text: b\y{decreasi|ng

text: αi

text: (xi,

text: αi)

text: i

text: n

text: end

text: if

text: S

text: return

text: end

text: function

text: Divide

text: and

text: Conquer

text: approach

text: Limiting

text: the

text: number

text: of

text: support

text: vectors

text: has

text: the

text: advantage

text: of

text: speeding

text: up

text: the

text: decision

text: function,

text: which

text: has

text: a

text: positive

text: impact

text: on

text: both

text: the

text: training

text: and

text: testing

text: phases,

text: since

text: the

text: online

text: training

text: scheme

text: also

text: uses

text: the

text: evaluation

text: of

text: the

text: decision

text: function

text: to

text: update

text: the

text: weights.

text: However,

text: it

text: also

text: comes

text: at

text: the

text: price

text: of

text: a

text: simpler

text: boundary

text: which

text: can

text: lead

text: reduced

text: accuracy.

text: To

text: overcome

text: this

text: problem,

text: we

text: propose

text: to

text: use

text: a

text: divide

text: and

text: conquer

text: approach

text: inspired

text: from

text: where

text: S

text: the

text: input

text: space

text: is

text: partitioned

text: into

text: K

text: clusters

text: µ

text: and

text: a

text: budget

text: constrained

text: SV

text: set

text: is

text: learned

text: inside

text: k

text: k

text: each

text: part.

text: The

text: algorithm

text: has

text: now

text: two

text: parameters,

text: namely

text: the

text: number

text: of

text: clusters

text: K

text: and

text: the

text: budget

text: of

text: each

text: SV

text: set

text: n,

text: which

text: make

text: the

text: total

text: storage

text: cost

text: of

text: the

text: model

text: of

text: size

text: Kn

text: support

text: vectors.

text: However,

text: O

text: the

text: evaluation

text: cost

text: is

text: only

text: (K

text: n)

text: since

text: the

text: decision

text: function

text: is

text: only

text: computed

text: in

text: the

text: corresponding

text: cluster.

text: The

text: full

text: algorithm

text: is

text: detailed

text: in

text: Algorithm

text: To

text: provide

text: a

text: fully

text: online

text: learning

text: scheme,

text: we

text: propose

text: to

text: learn

text: the

text: partition

text: also

text: online

text: using

text: LVQ

text: While

text: we

text: have

text: not

text: reach

text: this

text: number,

text: we

text: recruit

text: a

text: new

text: cluster

text: centered

text: on

text: the

text: current

text: sample,

text: and

text: associate

text: with

text: it

text: a

text: SV

text: set

text: consisting

text: of

text: the

text: sample

text: and

text: it

text: label

text: as

text: weight

text: (lines

text: to

text: If

text: k

text: clusters

text: are

text: already

text: present,

text: we

text: assign

text: the

text: current

text: sample

text: to

text: its

text: closest

text: center

text: k

text: (line

text: We

text: S

text: then

text: update

text: the

text: corresponding

text: center

text: using

text: standard

text: LVQ

text: (line

text: and

text: update

text: the

text: SV

text: set

text: using

text: the

text: S

text: k

text: update

text: online

text: procedure.

text: We

text: use

text: the

text: pruning

text: procedure

text: to

text: keep

text: the

text: size

text: of

text: under

text: the

text: constraint

text: if

text: needed.

text: Although

text: the

text: algorithm

text: is

text: simply

text: to

text: program,

text: our

text: version

text: is

text: publicly

text: full

text: project

text: at

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##