Jérémie Bigot
email: jeremie.bigot@math.univ-toulouse.fr

Sébastien Gadat
email: sebastien.gadat@math.univ-toulouse.fr

Clément Marteau
email: clement.marteau@math.univ-toulouse.fr

Sharp template estimation in a shifted curves model

Keywords: Template estimation, Curve alignment, Stochastic inverse problem, Oracle inequality, Adaptive estimation

This paper considers the problem of adaptive estimation of a template in a randomly shifted curve model. Using the Fourier transform of the data, we show that this problem can be transformed into a stochastic linear inverse problem. Our aim is to approach the estimator that has the smallest risk on the true template over a finite set of linear estimators defined in the Fourier domain. Based on the principle of unbiased empirical risk minimization, we derive a nonasymptotic oracle inequality in the case where the law of the random shifts is known. This inequality can then be used to obtain adaptive results on Sobolev spaces as the number of observed curves tend to infinity. Some numerical experiments are given to illustrate the performances of our approach.

Introduction 1.Model and objectives

The goal of this paper is to study a special class of stochastic inverse problems. We consider the problem of estimating a curve f , called template or shape function, from the observations of n noisy and randomly shifted curves Y 1 , . . . Y n coming from the following Gaussian white noise model: dY j (x) = f (xτ j )dx + ǫdW j (x), x ∈ [0, 1], j = 1, . . . , n

where W j are independent standard Brownian motions on [0, 1], ǫ represents a level of noise common to all curves, the τ j 's are unknown random shifts, f is the unknown template to recover, and n is the number of observed curves that may be let going to infinity to study asymptotic properties. This model is realistic in many situations where it is reasonable to assume that the observed curves represent replications of almost the same process and when a large source of variation in the experiments is due to transformations of the time axis. Such a model is commonly used in many applied areas dealing with functional data such as neuroscience (see e.g. [START_REF] Isserles | Semiparametric density estimation of shifts between curves[END_REF]) or biology (see e.g. [START_REF] Birgitte | Nonparametric maximum likelihood estimation for shifted curves[END_REF]). A well known problem in functional data analysis is the alignment of similar curves that differ by a time transformation to extract their common features, and (1.1) is a simple model where f represents such common features (see [START_REF] Ramsay | Functional Data Analysis[END_REF], [START_REF] Ramsay | Applied Functional Data Analysis[END_REF] for a detailed introduction to curve alignment problems in statistics).

The function f : R → R is assumed to be of period 1 so that the model (1.1) is well defined, and the shifts τ j are supposed to be independent and identically distributed (i.i.d.) random variables with density g : R → R with respect to the Lebesgue measure dx on R. Estimating f can be seen as a stochastic inverse problem as this template is not observed directly, but through n independent realizations of the stochastic operator A τ : L 2 p ([0, 1]) → L 2 p ([0, 1]) defined by

A τ (f )(x) = f (x -τ ), x ∈ [0, 1],
where L 2 p ([0, 1]) denotes the space of squared integrable functions on [0, 1] with period 1, and τ is random variable with density g. The additive Gaussian noise makes this problem ill-posed, and [START_REF] Bigot | A deconvolution approach to estimation of a common shape in a shifted curves model[END_REF] have shown that estimating f in such models is in fact a deconvolution problem where the density g of the random shifts plays the role of the convolution operator. For the L 2 risk on [0, 1], [START_REF] Bigot | A deconvolution approach to estimation of a common shape in a shifted curves model[END_REF] have derived the minimax rate of convergence for the estimation of f over Besov balls as n tends to infinfity. This minimax rate depends both on the smoothness of the template and on the decay of the Fourier coefficients of the density g. This is a well known fact for standard deterministic deconvolution problem in statistics, see e.g. [START_REF] Fan | On the optimal rates of convergence for nonparametric deconvolution problems[END_REF], [START_REF] David | Nonlinear solution of linear inverse problems by wavelet-vaguelette decomposition[END_REF], but the results in [START_REF] Bigot | A deconvolution approach to estimation of a common shape in a shifted curves model[END_REF] represent a novel contribution and a new point of view on template estimation in stochastic inverse problems such as (1.1). However, the approach followed in [START_REF] Bigot | A deconvolution approach to estimation of a common shape in a shifted curves model[END_REF] is only asymptotic, and the main goal of this paper is to derive non-asymptotic results to study the estimation of f by keeping fixed the number n of observed curves.

Deconvolution formulation

Let us first explain how the model (1.1) can be transformed into a deconvolution problem as the one studied in [START_REF] Donoho | Wavelet shrinkage: Asymptopia?[END_REF]. Denote G the following density function defined on [0; 1] as

G(x) = k∈Z g(x + k).
The density G exists as soon as g satisfies the weak condition g(x) ≤ C 1+|x| ν for any ν > 1 and suitable constant C. Note that the Fourier coefficients of G are given by 1 0 G(t)e -i2πlt dt = ∞ -∞ g(t)e -i2πlt dt = γ l Consider now the 1-periodization of f extended to R, one has

1 0 f (x -τ )G(τ )dτ = ∞ -∞ f (x -τ )g(τ )dτ.
The observations Y j can be written as

dY j (x) = f ⋆ G(x)dx + ξ j (x)dx + ǫdW j (x), (1.2)
where ξ j is a second noise term defined as ξ j (x) = f (xτ j )f ⋆ G(x). Hence, our model can be seen as a deconvolution problem with a noisy operator H : f → f ⋆ G + ξ and a more classical independent additive noise W . Note also that the realizations H j : f → f ⋆ G + ξ j are unbiased realizations of the operator H but presents a variance term which depends on the function f we want to estimate. This appears to be a new setting in the field of inverse problem with unknown operators as considered in [START_REF] Cavalier | Adaptive estimation for inverse problems with noisy operators[END_REF], [START_REF] Efromovich | On inverse problems with unknown operators[END_REF], [START_REF] Hoffmann | Nonlinear estimation for linear inverse problems with error in the operator[END_REF], [START_REF] Marteau | Regularization of inverse problems with unknown operator[END_REF] and [START_REF] Cavalier | Wavelet deconvolution with noisy eigenvalues[END_REF]. We will see in the sequel that the additive noise ξ which depends on f slightly modifies the quadratic risk and the way to estimate f when compared to classical procedures used in standard inverse problems with a deterministic operator.

Fourier Analysis and an inverse problem formulation

Supposing that f ∈ L 2 p ([0, 1]), we denote by θ k its k th Fourier coefficient, namely:

θ k = 1 0 e -2ikπx f (x)dx.
In the Fourier domain, the model (1.1) can be rewritten as

c j,k := 1 0 e -2ikπx dY j (x) = θ k e -i2πkτ j + ǫz k,j (1.3)
where z k,j are i.i.d. N C (0, 1) variables, i.e. complex Gaussian variables with zero mean and such that E|z k,j | 2 = 1. This means that the real and imaginary parts of the z k,j 's are Gaussian variables with zero mean and variance 1/2. Thus, we can compute the sample mean of the k th Fourier coefficient over the n curves as

ck := 1 n n j=1 c k,j = θ k γk + ǫ √ n ξ k , (1.4)
where

γk := 1 n n j=1 e -i2πkτ j , (1.5)
and the ξ k 's are i.i.d. complex Gaussian variables with zero mean and variance 1. The Fourier coefficients ck in equation (1.4) can be viewed as observations coming from a statistical inverse problem. Indeed, the standard sequence space model of an ill-posed statistical inverse problem is (see [START_REF] Cavalier | Oracle inequalities for inverse problems[END_REF] and the references therein)

c k = θ k γ k + σz k , (1.6)
where the γ k 's are eigenvalues of a known linear operator, z k are random noise variables and σ is a level of noise which goes to zero for studying asymptotic properties. The issue in such models is to recover the coefficients θ k from the observations c k under various conditions on the decay to zero of the γ k 's as |k| → +∞. A large class of estimators for the problem (1.6) can be written as

θk = λ k c k γ k ,
where λ = (λ k ) k∈Z is a sequence of reals called filter. Various estimators of this form have been studied in a number of papers, and we refer to [START_REF] Cavalier | Oracle inequalities for inverse problems[END_REF] for more details.

In a sense, we can view equation (1.4) as an inverse problem (with σ = ǫ √ n ) where the eigenvalues of the linear operator are the Fourier coefficients of the density g of the shifts i.e.

γ k := E e -i2πkτ = +∞ -∞ e -i2πkx g(x)dx.
Indeed, let us assume that the density g of the random shifts is known. In this case, to estimate the Fourier coefficients of f , one can perform a deconvolution step of the form

θk = λ k ck γ k , (1.7)
where ck is defined in (1.4) and λ = (λ k ) k∈Z is a filter whose choice will be discussed later on. Theoretical properties and optimal choices for the filter λ will be presented in the case where the coefficients γ k are known. Such a framework is commonly used in inverse problems such as (1.6) to obtain consistency results and to study asymptotic rates of convergence, where it is generally supposed that the law of the additive error is Gaussian with zero mean and known variance σ 2 , see e.g [START_REF] Cavalier | Oracle inequalities for inverse problems[END_REF]. In model (1.1), the random shifts may be viewed as a second source of noise and for the theoretical analysis of this problem the law of this other random noise is also supposed to be known.

Recently, some papers have addressed the problem of regularization with partially known operator. For instance, [START_REF] Cavalier | Adaptive estimation for inverse problems with noisy operators[END_REF] consider the case where the eigenvalues are unknown but independently observed. They deal with the model:

c k = γ k θ k + ǫξ k , γk = γ k + ση k , ∀k ∈ N, (1.8)
where (ξ k ) k∈N and (η k ) k∈N denote i.i.d standard gaussian variables. In this case, each coefficient θ k can be estimated by γ-1 k c k . Similar models have been considered in [START_REF] Cavalier | Wavelet deconvolution with noisy eigenvalues[END_REF], [START_REF] Marteau | Regularization of inverse problems with unknown operator[END_REF] or [START_REF] Marteau | On the stability of the risk hull method for projection estimator[END_REF]. In a more general setting, we may refer to [START_REF] Efromovich | On inverse problems with unknown operators[END_REF] and [START_REF] Hoffmann | Nonlinear estimation for linear inverse problems with error in the operator[END_REF].

In this paper, our framework is sligthly different in the sense that the operator is stochastic, but the regularization is operated using deterministic eigenvalues. Hence the approach followed in the previous papers is no directly applicable to model (1.1). We believe that estimating f in model (1.1) without the knowledge of g remains a difficult task, and this paper is a first step to address this issue.

Previous work in template estimation and shift recovery

The problem of estimating the common shape of a set of curves that differ by a time transformation is usually referred to as the curve registration problem, and it has received a lot of attention in the literature over the last two decades. Among the various methods that have been proposed, one can distinguish between landmark-based approaches which aim at aligning common structural points of the curves (typically locations of extrema) see e.g [START_REF] Gasser | Searching for structure in curve samples[END_REF], [START_REF] Gasser | Statistical tools to analyze data representing a sample of curves[END_REF], [START_REF] Bigot | Landmark-based registration of curves via the continuous wavelet transform[END_REF], and nonparametric modeling of the warping functions to align a set of curves see e.g [START_REF] Ramsay | Curve registration[END_REF], [START_REF] Wang | Alignment of curves by dynamic time warping[END_REF], [START_REF] Liu | Functional convex averaging and synchronization for timewarped random curves[END_REF]. However, in these papers, studying consistent estimates of the common shape f as the number of curves n tends to infinity is generally not considered.

In the simplest case of shifted curves, various approaches have been developed. Self-modelling regression methods proposed by [START_REF] Kneip | Convergence and consistency results for self-modelling regression[END_REF] are semiparametric models where each observed curve is a parametric transformation of a common regression function. Such models are usually referred to as shape invariant models and estimation in this setting is usually done by iterating the following two steps: estimation of the parameters of the transformations (here the shifts) given a reference curve, and nonparametric estimation of a template by aligning the observed curves given a set of known transformation parameters. [START_REF] Kneip | Convergence and consistency results for self-modelling regression[END_REF] studied the consistency of such a two steps procedure in an asymptotic framework where both the number of functions n and the number of observed points per curves grows to infinity. Due to the asymptotic equivalence between the white noise model and nonparametric regression with an equi-spaced design (see [START_REF] Brown | Asymptotic equivalence of nonparametric regression and white noise[END_REF]), such an asymptotic framework in our setting would correspond to the case where both n tends to infinity and ǫ is let going to zero. In this paper we prefer to focus only on the case where n may be let going to infinity, and to leave fixed the level of additive noise in each observed curve.

Based on a model with curves observed at discrete time points, semiparametric estimation of the shifts and the shape function is proposed in [START_REF] Loubes | Semi-parametric estimation of shifts[END_REF] and [START_REF] Vimond | Efficient estimation for homothetic shifted regression models[END_REF] as the number of observations per curve grows, but with a fixed number n of curves. A generalisation of this approach for the estimation of scaling, rotation and translation parameters for two-dimensional images is also proposed in [START_REF] Bigot | Estimation of translation, rotation and scaling between noisy images using the fourier mellin transform[END_REF], but also with a fixed number of observed images. Semiparametric and adaptive estimation of a shift parameter in the case of a single observed curve in a white noise model is also considered by [START_REF] Dalalyan | Penalized maximum likelihood and semiparametric second-order efficiency[END_REF] and [START_REF] Dalalyan | Penalized maximum likelihood and semiparametric second-order efficiency[END_REF]. Estimation of a common shape for randomly shifted curves and asymptotic in n is considered in [START_REF] Birgitte | Nonparametric maximum likelihood estimation for shifted curves[END_REF] from the point of view of semiparametric estimation when the parameter of interest is infinite dimensional.

However, in all the above cited papers rates of convergence or oracle inequalities for the estimation of the template are generally not studied. Moreover, our procedure differs from the approaches classically used in curve registration as our estimator is obtained in only one very simple step, and it is not based on an alternative scheme between estimation of the shifts and averaging of back-transformed curves given estimated values of the shifts parameters.

Finally, note that [START_REF] Castillo | Estimation of the distribution of random shifts deformation[END_REF] and [START_REF] Isserles | Semiparametric density estimation of shifts between curves[END_REF] consider a model similar to (1.1), but they rather focus on the the estimation of the density g of the shifts as n tends to infinity. Using such an approach could be a good start for studying the estimation of the template f without the knowledge of g. However, we believe that this is far beyond the scope of this paper, and we prefer to leave this problem open for future work.

Organization of the paper

In Section 2, we consider an estimator of the shape function f based on spectral cut-off when the eigenvalues γ k are known. Based on the principle of unbiased risk minimization developed by [START_REF] Cavalier | Oracle inequalities for inverse problems[END_REF], we derive an oracle inequality that is then used to derive an adaptive estimator of f on Sobolev spaces. This estimator is based on the Fourier transform of the curves with a data-based choice of the frequency cut-off. In Section 3, we study asymptotic properties of this estimator in terms of minimax rates of converge over Sobolev balls. Finally in Section 4, a short simulation study is proposed to illustrate the numerical properties of the estimator. All proofs are deferred to a technical section at the end of the paper.

Estimation of the common shape

In the following, we assume that the Fourier coefficients γ k are known. In this situation it is possible to choose a data-dependent filter λ ⋆ that mimic the performances of an optimal filter λ 0 called oracle that would be obtained if we knew the true template f . The performances of this filter are related to the performances of the filter λ 0 via an oracle inequality. In this section, most of our results are non-asymptotic and are thus related to the approach proposed in [START_REF] Cavalier | Oracle inequalities for inverse problems[END_REF] to study standard statistical inverse problems via oracle inequalities.

Smoothness assumptions for the density g

In a deconvolution problem, it is well known that the difficulty of estimating f is quantified by the decay to zero of the γ k 's as |k| → +∞. Depending how fast these Fourier coefficients tend to zero as |k| → +∞, the reconstruction of f will be more or less accurate. This phenomenon was systematically studied by [START_REF] Fan | On the optimal rates of convergence for nonparametric deconvolution problems[END_REF] in the context of density deconvolution. In this paper, the following type of assumption on g is considered:

Assumption 2.1 The Fourier coefficients of g have a polynomial decay i.e. for some real β ≥ 0, there exists two constants

C max ≥ C min > 0 such that for all k ∈ Z C min |k| -β ≤ |γ k | ≤ C max |k| -β .
(2.1)

Remark that the knowledge of the constants C max , C min and β will not be necessary for the construction of our estimator.

Risk decomposition

Assuming that γ k = 0 for all k ∈ Z, we recall that an estimator of the θ k 's is given by, see equation

(1.7) θk = λ k ck γ k
where λ = (λ k ) k∈Z is a real sequence. Examples of commonly used filters include projection weights λ k = 1 1 |k|≤N for some integer N , and the Tikhonov weights λ k = 1/(1 + (|k|/ν 2 ) ν 1 ) for some parameters ν 1 > 0 and ν 2 > 0. Based on the θk 's, one can estimate the signal f using the Fourier reconstruction formula. The problem is then to choose the sequence (λ k ) k∈Z in an optimal way with respect to an appropriate risk. For a given filter λ we use the classical ℓ 2 -norm to define the risk of the estimator θ

(λ) = ( θk ) k∈Z R(θ, λ) = E θ(λ) -θ 2 = E k∈Z | θk -θ k | 2 (2.2)
Note that analyzing the above risk (2.2) is equivalent to analyze the mean integrated square risk R( fλ , f

) = E fλ -f 2 = E 1 0 ( fλ (x) -f (x)) 2 dx for the estimator fλ (x) =
k∈Z θk e -2ikπx . The following lemma gives the bias-variance decomposition of R(λ, θ).

Lemma 2.1 For any given nonrandom filter λ, the risk of the estimator θ(λ) can be decomposed as

R(θ, λ) = k∈Z (λ k -1) 2 |θ k | 2 Bias + 1 n k∈Z λ 2 k ǫ 2 |γ k | 2 V 1 + 1 n k∈Z λ 2 k |θ k | 2 1 |γ k | 2 -1 V 2 (2.3)
For a fixed number of curves n and a given shape function f , the problem of choosing an optimal filter in a set of possible candidates is to find the best tradeoff between low bias and low variance in the above expression. However, this decomposition does not correspond exactly to the classical bias-variance decomposition for linear inverse problems. Indeed, the variance term in (2.3) is the sum of two terms and differs from the classical expression of the variance for linear estimator in statistical inverse problems. Using our notations, the classical variance term

is V 1 = ǫ 2 n k∈Z λ 2 k |γ k | 2
and appears in most of linear inverse problems.

However, contrary to standard inverse problems, the variance term of the risk also depends on the Fourier coefficients θ k of the unknown function f to recover. Indeed, our data γ -1 k ck are noisy observations of θ k :

γ -1 k ck = θ k + γk γ k -1 θ k + ǫ √ n γ -1 k ξ k ,
and we invert the problem using the sequence (γ k ) k∈N instead of (γ k ) k∈N , which is involved in the construction of the coefficient c k . It explains the presence of the second term V 2 . In particular, the quadratic risk is expressed in its usual form in the case where γk = γ k .

A similar phenomenon occurs with the model (1.8), although it is more difficult to quantify. Indeed, in this setting:

γ-1 k c k = θ k + γ k γk -1 θ k + ǫγ -1 k ξ k , ∀k ∈ N.
Hence, we also observe an additionnal term depending on θ. This term is controled using a Taylor expension but the quadratic risk cannot be expressed in a simple form. We refer to [START_REF] Marteau | On the stability of the risk hull method for projection estimator[END_REF] for a discussion with some numerical simulation and to [START_REF] Cavalier | Adaptive estimation for inverse problems with noisy operators[END_REF], [START_REF] Efromovich | On inverse problems with unknown operators[END_REF], [START_REF] Hoffmann | Nonlinear estimation for linear inverse problems with error in the operator[END_REF], [START_REF] Marteau | Regularization of inverse problems with unknown operator[END_REF] and [START_REF] Cavalier | Wavelet deconvolution with noisy eigenvalues[END_REF].

An oracle estimator and unbiased estimation of the risk

Suppose that one is given a finite set of possible candidate filters Λ = (λ N ) N ∈ I , with λ N = (λ N k ) k∈Z , N ∈ I ⊂ N which satisfy some general conditions to be discussed later on. In the case of projection filters, Λ can be for example the set of filters λ

N k = 1 1 |k|≤N , k ∈ Z for N = 1, . . . , m 0 .
Given a set of filters Λ, the best estimator corresponds to the filter λ 0 , called oracle, which minimizes the risk R(λ, θ) over Λ i.e.

λ 0 := arg min λ∈Λ R(λ, θ). (2.4)
This filter is called an oracle because it cannot be computed in practice as the sequence of coefficients θ is unknown. However, the oracle λ 0 can be used as a benchmark to evaluate the quality of a data-dependent filter λ ⋆ chosen in the set Λ. This is the main interpretation of the oracle inequality that we will develop in the next section. Now, suppose that it is possible to construct an unbiased estimator Θ2 k of |θ k | 2 . For any nonrandom filter λ, using Θ2 k , one can compute an estimator Ũ (λ, X) of the risk R(λ, θ). Then, for choosing a data-dependent filter, the principle of unbiased risk estimation (see [START_REF] Cavalier | Oracle inequalities for inverse problems[END_REF] for further details) simply suggests to minimize the criterion U (λ, X) over λ ∈ Λ instead of the criterion R(λ, θ). Our data-dependent choice of λ is thus

λ ⋆ := arg min λ∈Λ Ũ (λ, X).
(2.5)

Typically, in practice, all the filters λ ∈ Λ are such that λ k = 0 (or vanishingly small) for all k large enough. Hence, for such choices of filters, numerical computation of the above expression is thus feasible since it only involves the computation of finite sums.

Oracle inequalities for projection filters

Unbiased Risk Estimation (URE)

For the sake of simplicity, we only consider spectral cut-off schemes in the following. In this case, Λ corresponds to the set of filters (11 |k|≤N ) k∈Z for N ∈ N. All the results presented in this paper could be generalized to wider families of estimators (Tikhonov, Landweber, Pinsker,...).

The price to pay is to get longer and more technical proofs. From Lemma 2.1, the quadratic risk R(θ, λ) := R(θ, N ) of a projection filter can be written as:

R(θ, N ) = |k|>N |θ k | 2 + ǫ 2 n |k|≤N |γ k | -2 + 1 n |k|≤N |θ k | 2 1 |γ k | 2 -1 = θ 2 2 - |k|≤N |θ k | 2 + ǫ 2 n |k|≤N |γ k | -2 + 1 n |k|≤N |θ k | 2 1 |γ k | 2 -1 We aim to minimize R with respect to N while θ is unknown. Using Θ2 k = γ -2 k |c k | 2 -ǫ 2 n
as an unbiased estimator of |θ k | 2 , we minimize U defined as

U (Y, N ) = -1 - 1 n |k|≤N |γ k | -2 |c k | 2 - ǫ 2 n + ǫ 2 n |k|≤N |γ k | -2 + 1 n |k|≤N |γ k | -4 | |c k | 2 - ǫ 2 n ,
(2.6) which is an unbiased risk estimator of R(θ, N )θ 2 2 . Unfortunately, such a criterion does not lead to satisfying results. Instead of the approach developed in [START_REF] Cavalier | Adaptive estimation for inverse problems with noisy operators[END_REF], we take into account the error generated by the use of an approximation of the eigenvalues. The estimator related to the criterion (2.6) involves processes that require a specific treatment. In order to contain these processes, we will consider in the following the criterion

Ū (Y, N ) = - |k|≤N |γ k | -2 |c k | 2 - ǫ 2 n + ǫ 2 n |k|≤N |γ k | -2 + log 2 (n) n |k|≤N |γ k | -2 |c k | - ǫ 2 n , (2.7)
Remark that Ū (Y, N ) can be written as U (Y, N )+pen(N ) where (pen(N )) N ∈N denotes a penalty term. It appears from the proofs that this penalty is a natural candidate for the control of the processes involved in the behavior of the estimator constructed below. The associated data-based filter is defined as

N ⋆ = arg min N ≤m 0 Ū (Y, N ), (2.8)
where

m 0 = inf k : |γ k | 2 ≤ log 2 n n -1.
(2.9)

Remark that we do not minimize our criterion Ū (Y, N ) over N but rather for N ≤ m 0 . Indeed, each coefficient θ k is estimated by γ -1 k ck where

γ k = E[γ k ].
Hence, the ratio γ -1 k γk should be as close as possible to 1. Since γ k → 0 as k → +∞ and the variance of γk is constant in k, it seems clear that large k should be avoided.

Similar bounds on the resolution level are used in papers related to partially known operator: see for instance [START_REF] Cavalier | Adaptive estimation for inverse problems with noisy operators[END_REF] or [START_REF] Efromovich | On inverse problems with unknown operators[END_REF]. This bounds have to be carefully chosen but are not of first importance. In general, estimating the operator is easier than estimating the function f .

Sharp estimator of the risk

We are now able to propose a first adaptive estimator. In the following, we denote by θ ⋆ the estimator related to the bandwidth N ⋆ namely

θ ⋆ k = ck γ k 1 1 {k≤N ⋆ } .
(2.10)

The next theorem summarizes the performances of θ ⋆ through a simple oracle inequality. The proof is postponed to the Section 5.

Theorem 2.1 Let θ ⋆ defined by (2.10) and assume that the density g satisfies Assumption 2.1. Then, there exists 0 < γ 1 < 1 such that, for all 0 < γ < γ 1 ,

E θ θ ⋆ -θ 2 ≤ (1 + h 1 (γ)) inf N ≤m 0 R(θ, N ) + C 1 ǫ 2 n 1 γ 4β+1 + C 1 nγ , (2.11) where R(θ, N ) = |k|>N |θ k | 2 + ǫ 2 n |k|≤N |γ k | -2 + log 2 (n) n |k|≤N |γ k | -2 |θ k | 2 ,
(2.12) h 1 (γ) → 0 as γ → 0 and C 1 denotes a positive constant independent of ǫ and n.

From Theorem 2.1, our estimator θ ⋆ presents a behavior similar to the minimizer of R(θ, N ). This term only differs from the quadratic risk by a log term. This result can be explained by the choice of the criterion (2.7). The two last terms in the right hand side of (2.11) are at least of order 1/n and may be thus considered as negligible in most cases.

In the next section, we prove that our estimator attains the minimax of convergence on many functional spaces. In particular, the log term and the bandwidth m 0 have no influence on the performances of our estimator from a minimax point of view.

Rough estimator

In the procedure described above, we have decided to take into account the error generated by the use of a the sequence (γ k ) k∈N instead of (γ k ) k∈N . Although their setting is slightly different from ours, papers dealing with regularization with unknown operator consider implicitly this error as negligible for the regularization. The goal is then to prove that the related estimator are not affected by the noise in the operator, i.e. this error is avoided in the oracle.

It is thus also possible to apply a similar scheme in our setting and consider the bias enlightened in Lemma 2.1 as negligible. We introduce

R(θ, N ) = |k|>N |θ k | 2 + ǫ 2 n |k|≤N |γ k | -2 , (2.13)
that corresponds to the usual quadratic risk in an inverse problems setting. From now on, our aim is to mimic the oracle for R(θ, N ), i.e Ñ0 = arg min

N ∈N R(θ, N ).
To this end, we use exactly the same scheme than for the construction of

θ ⋆ starting from R(θ, N ) instead of R(θ, N ). Define Ũ (Y, N ) = - |k|≤N |γ k | -2 |c k | 2 - ǫ 2 n + ǫ 2 n |k|≤N |γ k | -2 .
(2.14)

Then, we introduce Ñ = arg min

N ≤m 0 Ũ (Y, N ) and θk = ck γ k 1 1 {k≤ Ñ} , (2.15)
where m 0 has been introduced in (2.9). Hence, this estimator only differs from the previous one by the choice of the regularization parameter Ñ . The performances of θ are detailed bellow.

Theorem 2.2 Let θ defined by (2.15) and assume that the density g satisfies Assumption 2.1. Then, there exists 0 < γ 2 < 1 such that, for all 0 < γ < γ 2 ,

E θ θ -θ 2 ≤ (1 + h 2 (γ)) inf N ≤m 0 R(θ, N ) + C 2 ǫ 2 n θ 2 log 2 (n) γ 2 2β + C 2 ǫ 2 n 1 γ 4β+1 + C 2 n , (2.16)
where h 2 (γ) → 0 as γ → 0 and C 2 denote a positive constant independent of ǫ and n.

We will see in Section 3 that the performances of θ ⋆ and θ are essentially the same from a minimax point of view. The existing differences may be revealed by the comparison of the oracle inequalities obtained in Theorems 2.1 and 2.2, although this is always a difficult task. Since R(θ, N ) only differs from R(θ, N ) by a log term, we may be interested in the residual of order θ 2 . For fixed ǫ and n, this term may have importance compared to R(θ, N ), in particular for large θ 2 . Hence, the second estimator may be incongruous when estimating function with large norm.

More carefully, θ is a pertinent choice as soon as R(θ, N ) is close to R(θ, N ). This can be strengthened by the study of the quadratic risk defined in Lemma 2.1. For instance, with a fixed ǫ, this will be the case for function with 'small' Fourier coefficients (in particular small norms). On the other hand, as soon as ǫ becomes 'small', the behaviour of R(θ, N ) and R(θ, N ) may strongly differs. This may produce significant differences on the performances of both θ ⋆ and θ.

Minimax rates of convergence for Sobolev balls

We provide in this section a short discussion about the performances of our estimator from the asymptotic minimax point of view. For this, let 1 ≤ p, q ≤ ∞ and A > 0, and suppose that f belongs to a Besov ball B s p,q (A) of radius A (see e.g. [START_REF] Donoho | Wavelet shrinkage: Asymptopia?[END_REF] for a precise definition of Besov spaces). [START_REF] Bigot | A deconvolution approach to estimation of a common shape in a shifted curves model[END_REF] have derived the following asymptotic minimax lower bound for the quadratic risk over a large class of Besov balls.

Theorem 3.1 Let 1 ≤ p, q ≤ ∞ and A > 0, let p ′ = p ∧ 2 and assume that:

• (Regularity condition on f ) f ∈ B s p,q (A) and s ≥ p ′ , • (Regularity condition on g) g satisfies the polynomial decay condition (2.1) at rate β for its Fourier coefficients,

• (Dense case) s ≥ (2β + 1)(1/p -1/2) and s ≥ 2β + 1.

Then, there exists a universal constant M 1 depending on A, s, p, q such that inf fn sup f ∈B s p,q (A)

E fn -f 2 ≥ M 1 n -2s 2s+2β+1 , as n → ∞,
where fn ∈ L 2 p ([0, 1]) denotes any estimator of the common shape f , i.e a measurable function of the random processes Y j , j = 1, . . . , n Therefore, Theorem 3.1 extends the lower bound n -2s 2s+2β+1 usually obtained in a classical deconvolution model to the more complicated model of deconvolution with a random operator derived from equation (1.2). Then, let us introduce the following smoothness class of functions which can be identified with a periodic Sobolev ball:

H s (A) = f ∈ L 2 p ([0, 1]) ; k∈Z (1 + |k| 2s )|θ k | 2 ≤ A ,
for some constant A > 0 and some smoothness parameter s > 0, where θ k = 1 0 e -2ikπx f (x)dx. It is known (see e.g. [START_REF] Donoho | Wavelet shrinkage: Asymptopia?[END_REF]) that if s is not an integer then H s (A) can be identified with a Besov ball B s 2,2 (A ′ ). Assuming f ∈ H s (A) with s > 0, then the classical choice

N ⋆ ∼ n 1 2s+2β+1 yields that R(θ, N ⋆ ) ∼ inf N ≤m 0 R(θ, N ) ∼ n -2s 2s+2β+1 .
provided N ⋆ ≤ m 0 . It can be checked that the choice (2.9) implies that m 0 ∼ n 1 2β and thus for a sufficiently large n, we have that N ⋆ < m 0 . Similarly the choice

N ⋆ ∼ n 1 2s+2β+1 yields that R(θ, N ⋆ ) ∼ inf N ≤m 0 R(θ, N ⋆ ) ∼ log 2 (n)n -2s 2s+2β+1 ,
Now, remark that for the two estimators θ ⋆ and θ, both Theorems 2.1 and 2.2 yield that

E θ θ ⋆ -θ 2 = O inf N ≤m 0 R(θ, N ) and E θ θ -θ 2 = O (inf N ≤m 0 R(θ, N
)) as n → +∞, since additional terms in bounds (2.11) and (2.16) are of the order O( 1 n 1-ζ ) for a sufficiently small positive ζ. Hence, combining the above arguments one finally obtains the following result:

Corollary 1 Suppose that the density g satisfies the polynomial decay condition (2.1) at rate β for its Fourier coefficients. Then, as n → +∞ sup

f ∈Hs(A) E θ θ ⋆ -θ 2 ∼ log 2 (n)n -2s 2s+2β+1 and sup f ∈Hs(A) E θ θ -θ 2 ∼ n -2s 2s+2β+1 .
From the lower bound obtained in Theorem 3.1 we conclude that, for s ≥ 2β + 1, the performances of the estimator θ are asymptotically optimal from the minimax point of view, while the estimator θ ⋆ is near-optimal up to a log 2 (n) factor. This near-optimal rate of convergence of θ ⋆ is due to the use of the penalised criterion Ū (Y, N ), see (2.7), with a penalty term involving a log 2 (n) n factor used to eliminate the term

1 n |k|≤N |γ k | -4 | |c k | 2 -ǫ 2 n in the unbiased risk U (Y, N ), see (2.6
). This shows that the performances of θ ⋆ and θ are essentially the same from a minimax point of view.

Numerical experiments

For the mean pattern f to recover, we consider the smooth function shown in Figure 1(a). Then, we simulate n = 100 randomly shifted curves with shifts following a Laplace distribution g

(x) = 1 √ 2σ exp - √ 2 |x|
σ with σ = 0.1. Gaussian noise with a moderate variance (different to that used in the Laplace distribution) is then added to each curve. A subsample of 10 curves is shown in Figure 1(b). The Fourier coefficients of the density g are given by γ k = 1 1+2σ 2 π 2 k 2 which corresponds to a degree of ill-posedness β = 2.

The condition (2.9) thus leads to the choice m 0 = 32. Minimisation of the criterions (2.8) and (2.15) leads respectively to the choices N ⋆ = 13 and Ñ = 30. An example of estimation by spectral cut-off using either the value of N ⋆ or Ñ is displayed in Figure 1(c) and Figure 1(d). The estimator obtained with the frequency cut-off N ⋆ = 13 is very satisfactory, while the choice Ñ = 30 seems to be too large as the resulting estimator in Figure 1(d) is not as smooth as the estimator with N ⋆ = 13. This result tends to suggest that minimising Ū (Y, N ) leads to a smaller choice for the frequency cut-off than the one obtained by the minimisation of the criterion Ũ (Y, N ). This is confirmed by the results displayed in Figure 2 which gives the histogram of the selected values for N ⋆ and Ñ over M = 100 independent replications of the above described simulations. Clearly the value of N ⋆ is generally much smaller than Ñ , and thus minimising (2.15) may lead to undersmoothing which illustrates numerically our discussion in Section 2 on the differences between θ ⋆ and θ.

Proofs

Proof of Theorem 2.1. The proof uses the following scheme. In a first time, we compute the quadratic risk of θ ⋆ and we prove that it is close to R(θ, N ⋆ ). The aim of the second part is to prove that Ū (Y, N ⋆ ) is close to R(θ, N ⋆ ), even for a random bandwidth N ⋆ . Then, we use the fact that N ⋆ minimizes the criterion Ū (Y, N ⋆ ) over the integer smaller than m 0 and we compute the expectation of U (Y, N ) for all deterministic N in order to obtain an oracle inequality.

In a first time,

E θ θ ⋆ -θ 2 = E θ k∈Z |θ ⋆ k -θ k | 2 , = E θ |k|≤N ⋆ |γ -1 k ck -θ k | 2 + E θ |k|>N ⋆ |θ k | 2 , = E θ |k|≤N ⋆ γk γ k θ k -θ k + γ -1 k ǫ √ n ξ k 2 + E θ |k|>N ⋆ |θ k | 2 , = E θ |k|≤N ⋆ γk γ k -1 2 |θ k | 2 + ǫ 2 n E θ |k|≤N ⋆ |ξ k | 2 |γ k | -2 +E θ |k|>N ⋆ |θ k | 2 + 2E θ |k|≤N ⋆ ǫ √ n Re (γ -1 k γk -1)θ k × γ-1 k ξk ,
where for a given z ∈ C, Re(z) denotes the real part of z and z the conjuguate. The last equality can be rewritten as

E θ θ ⋆ -θ 2 = E θ R(θ, N ⋆ ) + E θ |k|≤N ⋆ γk γ k -1 2 |θ k | 2 + ǫ 2 n E θ |k|≤N ⋆ |γ k | -2 (|ξ k | 2 -1) +2E θ |k|≤N ⋆ ǫ √ n Re (γ -1 k γk -1)θ k × γ-1 k ξk , = E θ R(θ, N ⋆ ) + A 1 + A 2 + A 3 , (5.1)
where R(θ, N ) is defined in (2.13). Thanks to Lemma 5.1, setting K = 1,

A 1 = E θ |k|≤N ⋆ γk γ k -1 2 |θ k | 2 ≤ log 2 (n) n E θ |k|≤N ⋆ |γ k | -2 |θ k | 2 + C n . (5.2)
Now, consider a bound for A 2 . For all N ∈ N set Σ N = |k|≤N |γ k | -4 . Then, for all p ∈]1, 2[ and 1 > γ > 0:

A 2 = ǫ 2 n E θ |k|≤N ⋆ |γ k | -2 (|ξ k | 2 -1), = ǫ 2 n E θ   |k|≤N ⋆ |γ k | -2 (|ξ k | 2 -1) -γ Σ ⋆ N p   + γ ǫ 2 n E θ Σ ⋆ N p , ≤ ǫ 2 n E θ sup N   |k|≤N |γ k | -2 (|ξ k | 2 -1) -γ Σ ⋆ N p   + γ ǫ 2 n E θ Σ ⋆ N p , ≤ γ ǫ 2 n E θ Σ ⋆ N p + C γ 1/(1-p) ǫ 2 n .
The last step can be derived from a Doob inequality: see for instance [START_REF] Cavalier | Risk hull method and regularization by projections of ill-posed inverse problems[END_REF]. Thanks to the polynomial Assumption 2.1 on the sequence (γ k ) k and setting p = 2 × (2β + 1)/(4β + 1), we obtain

A 2 = ǫ 2 n E θ |k|≤N ⋆ |γ k | -2 (|ξ k | 2 -1) ≤ γ ǫ 2 n E θ |k|≤N ⋆ |γ k | -2 + C γ 4β+1 ǫ 2 n . (5.3)
Then, for all 1 > B > 0, using the Cauchy-Schwarz and Young inequalities with the bounds (5.2) and (5.3)

A 3 = 2E θ |k|≤N ⋆ ǫ √ n Re (γ -1 k γk -1)θ k × γ-1 k ξk , ≤ B ǫ 2 n E θ |k|≤N ⋆ |γ k | -2 |ξ k | 2 + B -1 E θ |k|≤N ⋆ |θ k | 2 γk γ k -1 2 ,
Thus, for any K > 0,

A 3 ≤ (B + Bγ) ǫ 2 n E θ |k|≤N ⋆ |γ k | -2 + B -1 K log 2 (n) n E θ |k|≤N ⋆ |γ k | -2 |θ k | 2 + Cǫ 2 nγ 4β+1 + C nK . (5.4) With B = √ K = √ γ
, we obtain from (5.1)-(5.4)

E θ θ ⋆ -θ 2 ≤ (1 + γ + 2 √ γ)E θ R(θ, N ⋆ ) + Cǫ 2 nγ 4β+1 + C n , (5.5)
where R(θ, N ) is defined in (2.12). This concludes the first step of our proof. Now, we write Ū (Y, N ⋆ ) in terms of R(θ, N ⋆ ). In the following, we define x n = (1n -1 ). We have

Ū (Y, N ⋆ ) = -x n |k|≤N ⋆ |γ k | -2 |c k | 2 - ǫ 2 n + ǫ 2 n |k|≤N ⋆ |γ k | -2 + log 2 (n) n |k|≤N |γ k | -4 |c k | - ǫ 2 n , = R(θ, N ⋆ ) -1 - 1 n |k|≤N ⋆ |γ k | -2 |c k | 2 - ǫ 2 n - |k|≥N ⋆ |θ k | 2 + log 2 (n) n |k|≤N ⋆ |γ k | -4 |c k | - ǫ 2 n -|γ k | -2 |θ k | 2
This equality can be rewritten as

R(θ, N ⋆ ) = Ū (Y, N ⋆ ) + θ 2 + x n |k|≤N ⋆ |γ k | -2 |c k | 2 - ǫ 2 n |γ k | -2 - |k|≤N ⋆ |θ k | 2 + log 2 (n) n |k|≤N ⋆ |γ k | -2 |θ k | 2 -|γ k | -4 |c k | 2 - ǫ 2 n . (5.6) For all k ∈ N |c k | 2 = |θ k γk | 2 + ǫ 2 n |ξ k | 2 + 2ǫn -1/2 Re(θ k γk ξk ),
and

|γ k | -2 |c k | 2 = |θ k | 2 γk γ k 2 + ǫ 2 n |γ k | -2 |ξ k | 2 + 2 ǫ √ n |γ k | -2 Re(θ k γk ξk ). Since x n < 1 x n E θ |k|≤N ⋆ |γ k | -2 |c k | 2 - ǫ 2 n |γ k | -2 - |k|≤N ⋆ |θ k | 2 ≤ E θ |k|≤N ⋆ |θ k | 2 γk γ k 2 -1 + ǫ 2 n x n |k|≤N ⋆ |γ k | -2 (|ξ k | 2 -1) + 2 ǫ √ n x n |k|≤N ⋆ |γ k | -2 Re(θ k γk ξk ), = E 1 + E 2 + E 3 .
(5.7)

First consider the bound of E 1 . Thanks to Lemma 5.2 and some simple algebra

E 1 = E θ |k|≤N ⋆ |θ k | 2 γk γ k 2 -1 , ≤ 2γ log 2 (n) n E θ |k|≤N ⋆ |θ k | 2 |γ k | -2 + γE θ |k|>N ⋆ |θ k | 2 +γ |k|>N 0 |θ k | 2 + γ -1 |k|≤N 0 |θ k | 2 |γ k | -2 (1 -|γ k | 2 ) + C nγ 2 , ≤ 2γE θ R(θ, N ⋆ ) + γ + γ -1 log 2 (n) R(θ, N 0 ) + C nγ 2 ,
where N 0 = arg min

N ≤m 0 R(θ, N ).
The terms E 2 and E 3 are bounded using respectively (5.3) and Lemma 5.3. We get

E θ |k|≤N ⋆ |γ k | -2 |c k | 2 - ǫ 2 n |γ k | -2 -|θ k | 2 ≤ DγE θ R(θ, N ⋆ ) + Dγ R(θ, N 0 ) + ǫ 2 n C γ 4β+1 + C nγ 2 .
(5.8)

We are now interested in the second residual term of (5.6). Thanks to the definition of ck :

log 2 n n E θ |k|≤N ⋆ |γ k | -2 -|γ k | -2 |c k | 2 + ǫ 2 n |γ k | -2 + |θ k | 2 = E θ |k|≤N ⋆ |γ k | -2 |θ k | 2 1 - γk γ k 2 + ǫ 2 n |k|≤N ⋆ |γ k | -4 (1 -|ξ k | 2 ) -2 ǫ √ n |k|≤N ⋆ |γ k | -4 Re(θ k γk ξk ), ≤ DγE θ R(θ, N ⋆ ) + Dγ R(θ, N 0 ) + ǫ 2 n C γ 4β+1 + C nγ 2 ,
(5.9)

for some D > 0 independent of ǫ and n.Indeed, we can use essentialy the same algebra as for the bound of the terms E 1 , E 2 and E 3 and the inequality

|γ k | -2 ≤ n log 2 n , ∀k ≤ m 0 .
Hence, using (5.8) and (5.9)

(1 -Dγ)E θ R(θ, N ⋆ ) ≤ E θ U (Y, N ⋆ ) + θ 2 + Dγ R(θ, N 0 ) + C nγ 2 + Cǫ 2 n 1 γ 4β+1 .
(5.10) ¿From the definition of N ⋆ , we immediatly get

(1 -Dγ)E θ R(θ, N ⋆ ) ≤ E θ U (Y, N 0 ) + θ 2 + Dγ R(θ, N 0 ) + C nγ 2 + Cǫ 2 n 1 γ 4β+1 ,
where N 0 denotes the oracle bandwidth. Since

E θ U (Y, N 0 ) = R(θ, N 0 ) -θ 2 , we obtain (1 -Dγ)E θ R(θ, N ) ≤ (1 + Dγ) R(θ, N 0 ) + C nγ 2 + Cǫ 2 n 1 γ 4β+1 .
(5.11) Using (5.5) and (5.11), we get:

E θ θ ⋆ -θ 2 ≤ (1 + D √ γ)E θ R(θ, N ⋆ ) + Cǫ 2 n 1 γ 4β+1 + C nγ , ≤ 1 + D √ γ 1 -Dγ R(θ, N 0 ) + Cǫ 2 n 1 γ 4β+1 + C nγ .
This concludes the proof of Theorem 2.1.

Proof of Theorem 2.2. The proof follows the same main lines as for Theorem 2.1. Inequality (5.1) provides:

E θ θ ⋆ -θ 2 = E θ R(θ, N ⋆ ) + E θ |k|≤N ⋆ γk γ k -1 2 |θ k | 2 + ǫ 2 n E θ |k|≤N ⋆ |γ k | -2 (|ξ k | 2 -1) +2E θ |k|≤N ⋆ ǫ √ n Re (γ -1 k γk -1)θ k × γ-1 k ξk , = E θ R(θ, N ⋆ ) + A 1 + A 2 + A 3 .
Thanks to Lemma 5.1 and an inequality of [START_REF] Cavalier | Oracle inequalities for inverse problems[END_REF], we obtain for all 0 < γ < 1:

A 1 ≤ log 2 (n) ǫ 2 n E θ sup |k|≤N ⋆ |γ k | -2 |θ k | 2 + C n , ≤ γ ǫ 2 n E θ |k|≤N ⋆ |γ k | -2 + Cǫ 2 n θ 2 log 2 (n) γ 2β + C n .
(5.12)

Then, for all B > 0, using the Cauchy-Schwarz and Young inequalities with the bounds (5.2),(5.3):

A 3 = 2E θ |k|≤N ⋆ ǫ √ n Re (γ -1 k γk -1)θ k × γ-1 k ξk , ≤ (B + Bγ + B -1 γ) ǫ 2 n E θ |k|≤N ⋆ |γ k | -2 + Cǫ 2 n θ 2 log 2 (n) γ 2β + Cǫ 2 nγ 4β+1 + C n .
(5.13)

With the choice B = √ γ, we obtain from (5.1)-(5.4):

E θ θ ⋆ -θ 2 ≤ (1 + 3γ + 2 √ γ)E θ R(θ, N ⋆ ) + Cǫ 2 n θ 2 log 2 (n) γ 2β + Cǫ 2 nγ 4β+1 + C n . (5.14) Then, U (Y, N ⋆ ) = - |k|≤N ⋆ |γ k | -2 |c k | 2 - ǫ 2 n |γ k | -2 + ǫ 2 n |k|≤N ⋆ |γ k | -2 , = - |k|≤N ⋆ |γ k | -2 |c k | 2 - ǫ 2 n |γ k | -2 - |k|≥N ⋆ |θ k | 2 + |k|≥N ⋆ |θ k | 2 + ǫ 2 n |k|≤N ⋆ |γ k | -2 , = R(θ, N ⋆ ) - |k|≤N ⋆ |γ k | -2 |c k | 2 - ǫ 2 n |γ k | -2 - |k|≥N ⋆ |θ k | 2 .
This equality can be rewritten as

R(θ, N ⋆ ) = U (Y, N ⋆ ) + θ 2 + |k|≤N ⋆ |γ k | -2 |c k | 2 - ǫ 2 n |γ k | -2 -|θ k | 2 .
Hence,

E θ R(θ, N ) = E θ U (Y, N ⋆ ) + θ 2 + E θ |k|≤N ⋆ |θ k | 2 γk γ k 2 -1 + ǫ 2 n |k|≤N ⋆ |γ k | -2 (|ξ k | 2 -1) + 2 ǫ √ n |k|≤N ⋆ |γ k | -2 Re(θ k γk ξk ), = E θ U (Y, N ⋆ ) + θ 2 + E 1 + E 2 + E 3 .
(5.15)

Using previous results:

E 1 = E θ |k|≤N ⋆ |θ k | 2 γk γ k 2 -1 , ≤ 2γE θ R(θ, N ⋆ ) + γ R(θ, N 0 ) + C n + Cǫ 2 n θ 2 log 2 (n) γ 2 2β .
(5.16)

The terms E 2 and E 3 are bounded using respectively (5.3) and Lemma 5.3. We get:

E θ R(θ, N ⋆ ) ≤ E θ U (Y, N ⋆ ) + θ 2 + DγE θ R(θ, N ⋆ ) + Dγ R(θ, N 0 ) + C nγ 2β + Cǫ 2 n θ 2 log 2 (n) γ 2 2β . Hence, (1-Dγ)E θ R(θ, N ⋆ ) ≤ E θ U (Y, N ⋆ )+ θ 2 +Dγ R(θ, N 0 )+ C nγ 2β + Cǫ 2 n θ 2 log 2 (n) γ 2 2β
.

(5.17) ¿From the definition of N ⋆ , we immediatly get:

(

1-Dγ)E θ R(θ, N ⋆ ) ≤ E θ U (Y, N 0 )+ θ 2 +Dγ R(θ, N 0 )+ C nγ 2β + Cǫ 2 n θ 2 log 2 (n) γ 2 2β . (5.18)
In order to conclude the proof, we prove that E θ U (Y, N 0 ) is close to R(θ, N 0 ). First remark that:

E θ U (Y, N 0 ) = E θ - N 0 k=1 |γ k | -2 |c k | 2 - ǫ 2 n + ǫ 2 n N 0 k=1 |γ k | -2 , = E θ - N 0 k=1 |γ k | -2 |c k | 2 -|γ k | -2 ǫ 2 n -|θ k | 2 - N 0 k=1 |θ k | 2 + ǫ 2 n N 0 k=1 |γ k | -2 .
Since for all k ∈ N:

E θ |c k | 2 = |θ k | 2 E θ |γ k | 2 + ǫ 2 n = |θ k | 2 |γ k | 2 + 1 n + ǫ 2 n ,
we obtain,

E θ U (Y, N 0 ) = - N 0 k=1 |θ k | 2 |γ k | -2 n + |k|>N 0 |θ k | 2 + ǫ 2 n N 0 k=1 |γ k | -2 -θ 2 .
Therefore,

E θ U (Y, N 0 ) = - N 0 k=1 |θ k | 2 |γ k | -2 n + R(θ, N 0 ) -θ 2 ≤ R(θ, N 0 ) -θ 2 ,
and

(1 -Dγ)E θ R(θ, N ) ≤ (1 + Dγ) R(θ, N 0 ) + C nγ 2β + Cǫ 2 n θ 2 log 2 (n) γ 2 2β .
(5.19) Using (5.5) and (5.19), we get:

E θ θ ⋆ -θ 2 ≤ (1 + D √ γ)E θ R(θ, N ⋆ ) + Cǫ 2 n θ 2 log 2 (n) γ 2 2β + Cǫ 2 n 1 γ 4β+1 + 1 n , ≤ 1 + D √ γ 1 -Dγ R(θ, N 0 ) + Cǫ 2 n θ 2 log 2 (n) γ 2 2β + Cǫ 2 n 1 γ 4β+1 + 1 n .
Since R(θ, N ) ≤ R(θ, N ), we eventually get:

E θ θ ⋆ -θ 2 ≤ 1 + D √ γ 1 -Dγ inf N R(θ, N ) + Cǫ 2 n θ 2 log 2 (n) γ 2 2β + Cǫ 2 n 1 γ 4β+1 + 1 n .
This concludes the proof of Theorem 2.2.

Appendix

Lemma 5.1 For all K > 0, we have

E θ |k|≤N ⋆ γk γ k -1 2 |θ k | 2 ≤ K log 2 (n) n E θ |k|≤N ⋆ |γ k | -2 |θ k | 2 + C nK ,
where C denote a positive constant independent of ǫ and n.

PROOF. Let Q > 0 a deterministic term which will be chosen later.

E θ |k|≤N ⋆ γk γ k -1 2 |θ k | 2 = E θ |k|≤N ⋆ |θ k | 2 |γ k | -2 |γ k -γ k | 2 , ≤ QE θ |k|≤N ⋆ |θ k | 2 |γ k | -2 + E θ |k|≤N ⋆ |θ k | 2 |γ k | -2 |γ k -γ k | 2 -Q 1 1 {|γ k -γ k | 2 >Q} .
Thanks to (2.8) and (2.9)

E θ |k|≤N ⋆ |θ k | 2 |γ k | -2 |γ k -γ k | 2 -Q 1 1 {|γ k -γ k | 2 >Q} ≤ C n log 2 (n) |k|≤m 0 |θ k | 2 E θ |γ k -γ k | 2 -Q 1 1 {|γ k -γ k | 2 >Q} .
For all |k| ≤ m 0 , using an integration by part

E θ |γ k -γ k | 2 -Q 1 1 {|γ k -γ k | 2 >Q} = +∞ Q P (|γ k -γ k | 2 ≥ x)dx. Let x ≥ Q. A Bernstein type inequality provides P (|γ k -γ k | 2 ≥ x) = P 1 n n l=1 e -2iπkτ l -E[e -2iπkτ l ] ≥ √ x , ≤ 2 exp - (n √ x) 2 2 n l=1 Var(e -2iπkτ l ) + n √ x/3 , ≤ 2 exp - (n √ x) 2 2n + n √ x/3 .
Hence, for all |k| ≤ m 0 ,

E θ |γ k -γ k | 2 -Q 1 1 {|γ k -γ k | 2 >Q} ≤ +∞ Q exp - nx 2 + √ x/3 dx, ≤ 36 Q exp - nx 4 dx + +∞ 36 exp -Cn √ x dx ≤ C n e -Qn/4 ,
where C denotes a positive constant independent of Q. Let K > 0. Choosing for instance

Q = n -1 K log 2 (n), we obtain E θ |k|≤N ⋆ γk γ k -1 2 |θ k | 2 ≤ K log 2 (n) n E θ |k|≤N ⋆ |γ k | -2 |θ k | 2 + Cnm 0 log 2 (n) e -K log 2 (n)/4 , ≤ K log 2 (n) n E θ |k|≤N ⋆ |γ k | -2 |θ k | 2 + C nK ,
where C denotes a positive constant independent of ǫ and n. This concludes the proof of Lemma 5.1.

Lemma 5.2 Let N ⋆ defined in (2.8). For all deterministic bandwidth N and 0 < γ < 1, we have

E θ |k|≤N ⋆ |θ k | 2 γk γ k 2 -1 ≤ 2γ log 2 (n) n E θ |k|≤N ⋆ |θ k | 2 |γ k | -2 + γE θ |k|>N ⋆ |θ k | 2 +γ |k|>N |θ k | 2 + γ -1 n |k|≤N |θ k | 2 |γ k | -2 (1 -|γ k | 2 ) + C nγ 2 .
where C denotes a positive constant independent of ǫ and n.

PROOF. In a first time, remark that

E θ |k|≤N ⋆ |θ k | 2 γk γ k 2 -1 = E θ |k|≤N ⋆ |θ k | 2 |γ k | -2 (|γ k -γ k + γ k | 2 -|γ k | 2 ), = E θ |k|≤N ⋆ |θ k | 2 |γ k | -2 |γ k -γ k | 2 + 2Re((γ k -γ k )γ k ) .
(5.20)

Let N ∈ N be a deterministic bandwidth. Since E θ γk = γ k for all k ∈ N, we can write that

E θ |k|≤N ⋆ |θ k | 2 |γ k | -2 Re((γ k -γ k )γ k ) = E θ |k|∈{N ...N ⋆ } |θ k | 2 |γ k | -2 Re((γ k -γ k )γ k ), ≤ E θ |k|∈{N ...N ⋆ } |θ k | 2 |γ k | -2 Re((γ k -γ k )γ k ) , ≤ E θ k∈Z (11 {|k|≤N ⋆ } -1 1 {|k|≤N } )|θ k | 2 |γ k | -2 Re((γ k -γ k )γ k ) .
Using simple algebra

1 1 {|k|≤N ⋆ } -1 1 {|k|≤N } = (1 1 {|k|≤N ⋆ } + 1 1 {|k|≤N } )(11 {|k|≤N ⋆ } -1 1 {|k|≤N } ) , = (11 {|k|≤N ⋆ } + 1 1 {|k|≤N } ) 1 1 {|k|>N ⋆ } -1 1 {|k|>N } , ≤ 1 1 {|k|>N ⋆ } 1 1 {|k|≤N } + 1 1 {|k|≤N ⋆ } 1 1 {|k|>N } .
For all γ > 0, using the Cauchy-Schwartz and Young inequalities, we obtain

E θ |k|≤N ⋆ |θ k | 2 |γ k | -2 Re((γ k -γ k )γ k ) ≤ E θ k∈Z 1 1 {|k|>N ⋆ } 1 1 {|k|≤N } |θ k | 2 |γ k | -2 Re((γ k -γ k )γ k ) +E θ k∈Z 1 1 {|k|≤N ⋆ } 1 1 {|k|>N } |θ k | 2 |γ k | -2 Re((γ k -γ k )γ k ) ≤ γE θ |k|>N ⋆ |θ k | 2 + γ |k|>N |θ k | 2 + γ -1 E θ |k|≤N |θ k | 2 |γ k | -2 |γ k -γ k | 2 +γ -1 E θ |k|≤N ⋆ |θ k | 2 |γ k | -2 |γ k -γ k | 2 .
(5.21) Hence, from (5.20) and (5.21)

E θ |k|≤N ⋆ |θ k | 2 γk γ k 2 -1 ≤ (1 + γ -1 )E θ |k|≤N ⋆ |θ k | 2 |γ k | -2 |γ k -γ k | 2 + γE θ |k|>N ⋆ |θ k | 2 +γ |k|>N |θ k | 2 + γ -1 E θ |k|≤N |θ k | 2 |γ k | -2 |γ k -γ k | 2 .
A direct application of Lemma 5.1 provides, for all K > 0

E θ |k|≤N ⋆ |θ k | 2 γk γ k 2 -1 ≤ (1 + γ -1 )K log 2 (n) n E θ |k|≤N ⋆ |θ k | 2 |γ k | -2 + γE θ |k|>N ⋆ |θ k | 2 +γ |k|>N |θ k | 2 + γ -1 n |k|≤N |θ k | 2 |γ k | -2 (1 -|γ k | 2 ) + C nK .
Just set K = γ 2 in order to conclude the proof of Lemma 5.2.

Lemma 5.3 Let N ⋆ the bandwidth defined in (2.8). For all deterministic bandwidth N and 0 < γ < 1, we have

2ǫ √ n E θ |k|≤N ⋆ |γ k | -2 Re(θ k γk ξk ) ≤ 3γ    |k|>N 0 |θ k | 2 + ǫ 2 n |k|≤N 0 |γ k | -2    +3γ log 2 (n)E θ    |k|>N ⋆ |θ k | 2 + ǫ 2 n |k|≤N ⋆ |γ k | -2    + C n + Cǫ 2 γ 4β+1 .
PROOF. In the following, we will use the inequality:

P m 0 k=1 1 2 ≤ γk γ k ≤ 2 ≤ exp(-log 1+τ n),
for some τ > 0, wich can be proved using a Bernstein type inequality. Then, for all γ > 0, using the above result and inequality (4.31) of [START_REF] Cavalier | Risk hull method and regularization by projections of ill-posed inverse problems[END_REF], we obtain

2ǫ √ n E θ |k|≤N ⋆ |γ k | -2 Re(θ k γk ξk ) ≤ γ    |k|>N 0 |θ k | 2 + ǫ 2 n E θ |k|≤N 0 |γ k | -4 |γ k | 2    +γE θ    |k|>N ⋆ |θ k | 2 + ǫ 2 n |k|≤N ⋆ |γ k | -4 |γ k | 2    + Cǫ 2 n 1 γ 4β+1 .
In order to prove the above inequality, we use the inequality (4.31) of [START_REF] Cavalier | Risk hull method and regularization by projections of ill-posed inverse problems[END_REF] and Since E θ γk = γ k ,

ǫ 2 n E θ |k|≤N |γ k | -4 |γ k | 2 = ǫ 2 n |k|≤N |γ k | -4 E θ |γ k | 2 -|γ k | 2 + |γ k | 2 , = ǫ 2 n |k|≤N |γ k | -4 |γ k | 2 + Var(γ k ) , = ǫ 2 n |k|≤N |γ k | -4 |γ k | 2 + 1 n ≤ 2 ǫ 2 n |k|≤N 0 |γ k | -2 .
The same kind of inequality can be obtained with the random bandwidth N ⋆ . Indeed,

ǫ 2 n E θ |k|≤N ⋆ |γ k | -4 |γ k | 2 = ǫ 2 n E θ |k|≤N ⋆ |γ k | -4 |γ k -γ k + γ k | 2 , ≤ ǫ 2 n E θ |k|≤N ⋆ |γ k | -4 2|γ k -γ k | 2 + 2|γ k | 2 , ≤ 2ǫ 2 n E θ |k|≤N ⋆ |γ k | -2 + 2ǫ 2 n E θ |k|≤N ⋆ |γ k | -4 |γ k -γ k | 2 .
Using the same algebra as in the proof of Lemma 5.1, we obtain, for all Q > 0:

ǫ 2 n E θ |k|≤N ⋆ |γ -4 k ||γ k -γ k | 2 = Q ǫ 2 n E θ |k|≤N ⋆ |γ k | -4 + ǫ 2 n E θ |k|≤N ⋆ |γ k | -4 |γ k -γ k | 2 -Q 1 1 {|γ k -γ k | 2 >Q} , ≤ Q ǫ 2 n E θ |k|≤N ⋆ |γ k | -4 + Cǫ 2 n log 2 (n) E θ |k|≤N ⋆ |γ k -γ k | 2 1 1 {|γ k -γ k | 2 >Q} , ≤ Q ǫ 2 n E θ |k|≤N ⋆ |γ k | -4 + Cǫ 2 log 4 (n)
e -Qn/4 .

Setting Q = n -1 log 2 (n), we obtain,

ǫ 2 n E θ |k|≤N ⋆ |γ -4 k ||γ k -γ k | 2 ≤ ǫ 2 n E θ |k|≤N ⋆ |γ k | -2 |γ k | -2 log 2 (n) n + Cǫ 2 n , ≤ ǫ 2 n E θ |k|≤N ⋆ |γ k | -2 + Cǫ 2 n .
This concludes the proof.

Figure 1 :

 1 Figure 1: Wave function. (a) Mean pattern f , (b) Sample of 10 curves out of n = 100, (c) Estimation by spectral cut-off with N ⋆ = 13, (d) Estimation by spectral cut-off with Ñ = 30. The dotted curve corresponds to the true mean pattern f .

Figure 2 :

 2 Figure 2: Selection of the frequency cut-off over M = 100 replications of the simulations (with m 0 = 32): (a) Histogram of the selected value for N ⋆ , (b) Histogram of the selected value for Ñ .


Sergio Peignier
email: sergio.peignier@insa-lyon.fr

Patricia Zapata
email: pzapata@umsa.bo

Frequent Itemsets and Clustering Unravel the Evolution of Evo Morales Discursive Strategies

Introduction

Evo Morales, is a Bolivian politician, leader of the Movement for Socialism party, and former president of Bolivia from 2006 to 2019. His administration has been part of the latin-american Socialism of the 21st century. The leaders belonging to this movement are characterized by their ability to use their rhetorical skills to seduce people. Indeed, Morales has been described as a "charismatic populist" [START_REF] Linda | Evo's Bolivia: Continuity and change[END_REF], who aimed at identifying himself with his audience [START_REF] Zapata | Análisis del Discurso Socialista Lati-noamericano Basado en Inteligencia Artificial[END_REF], by means of a populist discourse [START_REF] Philip | The triumph of politics[END_REF]. Indeed, his speeches are organized as a Triadic Scenario where people, guided by Morales himself, fight against a common enemy (e.g., political class, elite), which is responsible for a disastrous social situation [START_REF] Philip | The triumph of politics[END_REF][START_REF] Zapata | Análisis del Discurso Socialista Lati-noamericano Basado en Inteligencia Artificial[END_REF]. Moreover, he often refers to social welfare and economic progress as a powerful recruitment process strategy [START_REF] Zapata | Análisis del Discurso Socialista Lati-noamericano Basado en Inteligencia Artificial[END_REF], in order to stir positive feelings in the audience, as a rhetoric of effects. And thus, studying Morales' rhetoric skills is a crucial step towards understanding his political success. Interestingly, discursive strategies change according to external events (e.g., during crisis [START_REF] De | Discourse and crisis: Critical perspectives[END_REF][START_REF] Candón | El discurso político y su reflejo en los medios: la credibilidad en tiempos de crisis (2008-2011)/political discourse and its reflection in the media: credibility in times of crisis (2008-2011)[END_REF]) and evolve along time, as shown for instance in [START_REF] Sousa | À l'épreuve des temps[END_REF]. Here, we studied the evolution of Morale's discursive strategies combining frequent itemsets mining and clustering, with the linguistic speech analysis methodology of P. Charaudeau. In this work, we studied 477 tweets from Evo Morales, posted between the 1st of November and the 2nd of December 2019, i.e., during the particularly turbulent period, that characterized the end of his administration. Dates Events 10/20 General Elections (first results suggest the need of a 2nd tour).

Dataset

Context During October and November 2019, Bolivia experienced a dramatic socio-political crisis, and underwent major political changes, as summarised in the timeline 1. This period can be separated in three major intervals:

1) Between the 1st and the 20th of October, Bolivia underwent a political campaign towards general elections.

2) Between the 21st of October to the 10th of November, Bolivia experienced a socio-political post-electoral crisis.

3) Between the 11th and the end of November, Bolivia went though an administration change and an important socio-political crisis.

Therefore characterizing Morale's discursive strategies during this period is an important step towards interesting the mechanisms driving the evolution of discourse under political crisis.

Dataset description This paper studies the evolution of Evo Morales' discursive strategies on Twitter, by focusing on the tweets he posted between the 1st of October 2019 and the 2 of December 2019. In practice, the tweepy python library [7] was used to download 477 Morales' tweets, containing 12871 words in total, and representing a vocabulary of 3678 distinct words.

Methodology

Pre-processing As in many Natural Language Processing applications, a first step consisted in filtering stop-words and rare-words. Stop-words filtering aims at removing too common words conveying little semantic information, whereas rare-words filtering aims at removing "noisy words" that are not used often. Here, we selected a curated set of 34 stop-words 1 , and words that were only used once in the dataset were considered rare, and were removed accordingly. This step was ensured using custom Python scripts based on the nltk library [START_REF] Bird | Natural language processing with Python: analyzing text with the natural language toolkit[END_REF]. The pre-processed dataset contains 10693 words in total, and a vocabulary with 1500 distinct words.

Frequent itemsets extraction In order to detect sets of words that are frequently used together, we used a frequent itemset mining procedure.

More formally, let a tweet s be an ordered list of words from vocabulary V = {w 1 , w 2 , ...}, and let a tweets dataset be S = (s 1 , s 2 , . . . ) an ordered list of tweets s i received at time i. The dataset vocabulary V , denotes the set of possible items, the transactions dataset is simply T = (t 1 , t 2 , . . . ), with t i = {w ∈ s i } for each tweet s i ∈ S, and let m ⊆ V denote an itemset. The support supp(m, T ) of an itemset m in T , is simply the frequency of transactions in T containing m, i.e., supp(m, T

) = |{t∈T | m⊆t}| |T | .
In practice, we used the popular FP-growth algorithm [START_REF] Han | Mining frequent patterns without candidate generation: A frequent-pattern tree approach[END_REF], to extract 2552 frequent itemsets M = {m 1 , m 2 , . . . } such that, ∀m ∈ M , supp(m, T ) ≥ 0.015.

Frequent itemsets selection

The frequency (i.e., number of occurrences) of word w in the dataset T is denoted f req(w, T ), and thus the total number of words in T is N = w∈V f req(w, T ). The coverage of a set of words m in T is coverage(m, T ) = w∈m f req(w,T ) N .

In order to select an informative subset of itemsets M * ⊆ M with size |M * | = M , we select iteratively the itemsets leading to the highest gain in coverage, using the greedy strategy described in Algorithm 1.

In practice, selecting a subset M * with size M = 200 and vocabulary V * , leaded to a overall coverage(V * , T ) = 0.613. The cumulative gain in coverage using Algorithm 1, is represented Figures 1.

Algorithm 1 Itemsets selection

1: procedure GreedyItemsetsSelection(T , M, M ) 2: M * ← ∅ Initialize M * 3: for i ← 1 to M do 4: V * ← M * Vocabulary in M * 5: m * ← arg max m∈M (coverage(m \ V * )) Highest coverage itemset 6: M * ← M * ∪ {m * } Update M * 7:
return M * , V * Then we used the well-known K-means algorithm [START_REF] Macqueen | Some methods for classification and analysis of multivariate observations[END_REF], to partition itemsets into k clusters, according to their respective activity vectors {X m , ∀m ∈ M * }, so clusters group itemsets that tend to be active simultaneously.

In order to choose the number of clusters, we have computed the Sum of Squared Distance (SSE), between vectors X m and their respective centroids, for different number of clusters from K = 1 to K = 50. Then, we applied the Kneedle algorithm [START_REF] Satopaa | Finding a" kneedle" in a haystack: Detecting knee points in system behavior[END_REF], to determine the elbow point in the SSE curve (i.e., a classical indicator for choosing the number of clusters), that suggests to take K = 9 clusters, as shown Figure 2. Finally the k-means algorithm was executed 1000 times, the clustering leading to the best SSE was selected. Thus, itemsets M were clustered in K = 9 groups , Finally, for each cluster C k = {m ∈ M}, we computed its activity vector X C k = m∈C k X m , as the element-wise sum of activity vectors X m of each itemset m belonging to cluster C k .

Discourse Analysis Methodology

The clusters' itemsets were studied using Patrick Charaudeau's well-known discourse analysis methodology [START_REF] Charaudeau | Réflexions pour l'analyse du discours populiste[END_REF]. This • Ethos strategies allow the politician to define his discursive identity, and identify himself with the audience, to increase its credibility and charisma.

• Pathos strategies aim at using rhetoric of effects to bringing out feelings and passions, and also recruitment processes to lead the audience to accept the politician's project willingly.

• Logos strategies rely on rational arguments, mainly based on simplified causal reasoning, and discursive formulas analogous to slogans.

Results

Clusters of itemsets are represented in Table 2, and their temporal activities are depicted in Figure 3 as a row-wise z-scored heat-map. According to these results, during his electoral campaign, Morales mainly relies on recruitment processes based on economical progress and social welfare, which often arise feelings of hope and pride (clusters 7, 2 and 1). Furthermore, Morales also used a triadic scenario to oppose neoliberalism and people, and to delegitimize his main opponent Carlos Mesa, by linking him to the former president Gonzalo Sánchez de Lozada, how was overthrown in 2003 by a social revolt, during the so-called "Bolivian gas war". Interestingly, at first Morales seems to minimize the social conflicts that arose soon after the elections. Indeed, he keeps developing recruitment processes as before, and claiming his electoral victory (cluster 4). Then, he seems to develop a recruitment process based on nationalism, unity and moral values, in order to support the request he made to the OAE, to audit the electoral process. We can also perceive that Morales employs the word racism, possibly to delegitimize the opposition (cluster 6). Finally in cluster 6, Morales keeps on developing similar recruitment processes, and he also employs many terms related to peace. And thus, he aims a coping with the social crisis by showing himself as a peacemaker. Nevertheless, he simulteaously use verbs in infinitive, with an imperative value, that suggest he calls upon his supporters and people to defend his government. Finally, after being overthrown, Morales almost completely drops the previous recruitment process strategies, in order to devote almost entirely to the description of a new triadic scenario. On the one hand, he denounces his enemies, (i.e., the army, the police, opponents leaders such as Luis Fernando Camacho and the new president Jeanine Añez), as a member of a dictatorship, and he also denounces their actions as a violent coup. On the other hand, he describes his allies, which would also correspond to the victims, i.e., indigenous and poor people. This description aims at evoking strong feelings in the audience, such as injustice, empathy, piety, fear, sadness and hatred. Moreover it aims at delegitimizing his opponents, by depicting them as a violent and racist group, and it aims at recruiting new allies based on their ethnic and ideological belonging.

Conclusion and Discussion

In this work we have studied 477 tweets from Evo Morales during turbulent period that characterized the end of his administration, using a technique combining clustering and frequent item-sets mining. This technique has shown to be effective in revealing the temporal discursive strategy of Evo Morales: 1) Before the elections, Morales used both economical and social welfare recruitment

1Figure 1 :

 1 Figure 1: Model Coverage gain vs. number of itemsets

Figure 2 :

 2 Figure 2: SSE vs. number of clusters, knee point for 9 clusters

Figure 3 :

 3 Figure 3: Standardize average use of each cluster along time

k Itemsets 7

 7 familias trabajadores jóvenes nuevas•generaciones neoliberales liberación educación proyectos salud autoridades informó entregamos garantizamos garantiza saludamos gracias•unidad prensa oruro años cada 2 pobreza octubre masacre sánchez•carlos•mesa•lozada cómplices eeuu•gas industrialización•nacionalización muy•futuroseguro estabilidad económica plan seguridad garantizar fortaleza historia mejor gran muchas trabajamos política junto juntos nuestras cariño reunimos sucre homenaje agradecido•apoyo mientras fue así día 1 más•ahora económico•crecimiento trabajo procesodecambio rrnn construcción obras ley inversiones conciencia será grande grandes estamos cierre•campaña unidos vamos concentración santacruz lapaz potosí reportó desde hasta 4 como•es•hoy•bolivia soberanía agua integración desarrollo beneficio solidaridad•hermano nueva tenemos triunfo voto cochabamba argentina países entregar nunca porque todas 6 pueblo•por•para•que familia entre•bolivianos racismo nuestra•querida•su hermanos•sus agradecemos•nos somos auditoría compromiso país político pero solo está primera ni era 0 sectores•sociales profesionales humildes campo ciudad social•paz patria boliviana economía pacíficamente proceso libre hermana hermanas hemos casa nuestro•no defender cuidar trabajar escuchar todo ante manera medio 3 pobres golpe•estado•democracia violencia•mi grupos boliviano derecho políticas pacífica elecciones democrática constitucional cpe rt•evoespueblo mundo llamado evo pido me presidente todos han ha o si nuevo 5 indígenas alto contra•vida represión muertos ffaa•policía áñez•camacho facto golpistas golpista dictadura militares agradezco mis respeto diálogo libertad denuncio comunidad•internacional después tienen 8 pueblos•identidad movimiento•indígena movimientos fuerza derecha dignidad•lucha derechos nacional gobierno•nuestros saludo defensa son sin ser tiene sobre quieren Table 2: Clusters itemsets coloured by discursive strategy: blue: commitment, authority (Ethos), Yellow: ally (Pathos), Red: enemy (Pathos), Orange: people as victim (Pathos), Green: Recruitment process based on development, welfare, moral values (Pathos), Violet: Identification with people, charisma (Pathos) processes, as well as a triadic scenario to oppose neoliberalism and people. 2) During the political conflicts, Morales first tends to underestimate the conflicts, then he relies on a recruitment process based on nationalism, unity, peace and moral values. 3) After being overthrown, Morales completely changes his strategy and entirely relies on a new triadic scenario opposing the new government (characterized by Morales as a violent dictatorship), and the people.

  10/21 Live vote count interruption, opposition denounces electoral fraud. 10/22 General strike proclaimed, demonstrations/riots until 11/10. Clashes between opponents vs. police and Morales supporters. 10/23 Morales' government asks the OAE to audit the elections. 10/25 Morales is re-elected without needing a 2nd tour. 10/31 OAE electoral audit begins. 11/08 Police mutiny. 11/09 Government call to convene a dialogue, but the opposition refused. 11/10 Preliminary OAE report confirms intentional electoral manipulation. Workers union, police and army call Morales to resign. Morales and senior members of the government resign. Pro-Morales riots until 11/22, clashes with police and army. 11/11 Morales leaves Bolivia. 11/12 Senator J. Añez assumes the presidential office.

Table 1 :

 1 Timeline of main events since Bolivian general election

	2 Materials and Methods


Cyrille Bertelle

Antoine Dutot

Michel Nabaa

Damien Olivier Litis

Damien Olivier

Pascal Mallet
email: pascal.mallet@agglo-havraise.fr

DETECTION OF ORGANIZATIONS IN LARGE GRAPHS : APPLICATION ON RISK MANAGEMENT

Recent events have shown that our agglomerations are vulnerable in front of emergency situations. There are a lot of factors to consider and one of them is the structure of towns generated by road networks. One way to study these structures is to modelize the networks by graphs and to use the theory developed on them. Recently, some works have studied the detection of communities in large graphs. A community in a graph is a set of connected nodes strongly connected to each other and less connected to nodes from other communities. The aim of detection is to identify communities according to a predefined criteria but without specifying the number of communities and the size of communites. The known algorithms find communities but without taking into account the time. We propose a dynamic algorithm of communities detection and we explain how it can be applied on Le Havre agglomeration, for example, to estimate the vulnerability related to the road network use by vehicles.

Introduction

Modeling the population flow aims to provide a simplified representation of the population displacement, which is a complex phenomena. It must take into ac-count the displacement of individuals in their normal daily activities or under exceptional activities requiring an evacuation in a danger case. Models must eventually allow a better understanding of the parameters influencing the flow evolution and provide decision making tools to know the spatial and temporal distribution of people in a given urban zone. The objective is therefore to realize a simulation that can be used to define a strategy for evacuation planning and crisis management. Different types of models exist and may be used depending on the level of accuracy and representation of the flow we search for. But we can identify three main families of flow modelling : microscopic, macroscopic and hybrid models. In Le Havre Agglomeration (CODAH), we are faced to different types of natural and industrial hazards; 33 establishments are classified SEVESO2 . In this context, the Major Risk Management Direction team (DIRM) of CODAH has developed a model which estimates the nocturnal and diurnal exposed population allocation PRET-RESSE (Bourcier and Mallet, 2006). So, we have ventilated the day / night population inside buildings. The model was able to locate people during the day both in their workplace and their residence (the unemployed and retirees). Although the model is able to locate the diurnal and nocturnal population, it remains static because it does not take into account the daily movement of people and the road network utilization. The using of road network by vehicles with diffrent behaviors can generate a danger especially in case of evacuation situations. So, it is important to us to detect congested areas that may be more vulnerable than others. In the literature, many clustering algorithms have been applied on a graph to detect organisations according to a predefined criteria as the connectivity, the distance or capacity of edges between adjacent nodes. Most of these models are static and do not meet the dynamic due to graph evolution. Since CODAH can be seen as a graph on which we have vehicles flow that evolve during time, we develop a dynamic algorithm which dynamically detects organizations according to the traffic state. The algorithm belongs to collective intelligence algorithms and can be referred to as an ant algorithm. the result of this algorithm must be visualized, as a dynamic map, in the Geographical Information System (GIS) of CODAH to help decision makers in assessing the danger related to road network use by vehicles.

CODAH as a complex system

We are intersted in detecting vulnerability related to the road network use in CO-DAH and we are working with DIRM team to setup a decision making tool assessing this vulnerability. In this context, it is very important to understand the dynamic related to the road network use by vehicles. In fact, a vehicle tends to follow the same path taken by other vehicles to evacuate a dangerous area. In this case, any perturbation (accident...) may cause traffic jams causing serious problem to evacuees. So, we can see CODAH as a system in which the environemnt may influence on evacuation to reduce or not the flow fluidity(existence or not of safe refuge and emergency exits, routes traffic direction) and vice versa (a fire or an accident may cause damages and change the environment). For us, CODAH can be seen as a complex system in perpetual evolution, in which vehicles interact between them and with environment (vehicles acts on environment which in turn influences vehicles).

Complex system

CODAH A big number of entities interacting with some others (dispersed interactions)

Vehicles on the same route interact but not necessarily with vehicles on other routes Absence of global control

We have some local rules (traffic lights, priorities on intersections) but no global control There are cross-hierarchical organizations with many interactions An organization of rescue service interacts with vehicles in a dangerous area Continual adaptation, learning and thus evolution Vehicles learn about congestions in some zones at peak hours in the journey and try to avoid them Perpetual evolution with appearing and disappearing of organizations Traffic jams can appear and disappear in time and at different places The system is far from equilibrium dynamics (no equilibrium or transition from an equilibrium to another one.

Passing from a normal situation to a traffic jam and vice versa Table 1: CODAH meets complex system properties defined by Arthur et al.

A complex system is characterized by numerous entities of the same or different nature that interact in a non-trivial way (non-linear, feedback loop ...); the global emergence of new properties not seen in these entities : Properties or evo-lution cannot be predicted by simple calculations. According to Arthur, Durlauf and Lane (?), a complex system has six properties. Table ?? shows these properties and shows that CODAH can be seen as complex system with a big number of vehicles interacting on the road network.

Traffic approaches

Traffic modelling becomes a point of interest for different researchers coming from different fields. It may help decision makers to resolve congestion problems by introducing a set of rules related to environment and different behaviours in entities (vehicles, pedestrians...). In risk context, it helps decision makers to have a better idea about vehicles distribution in space and time to assess vulnerability and to prepare evacuation plans. It can be seen as a complex system in which we have an environement (graph, grid...) and entities in interaction. We can identify three big families of traffic modelling:

• Macroscopic models : The macroscopic model is based on the analogy between vehicular traffic and the fluid flow within a canal.

• Microscopic models : The microscopic model details the behavior of each individual vehicle by representing interactions with other vehicles and in general by using a spatialization. Interactions are generally modeled by car following rules. We can also refine the model by adding passing lanes rules, priority rules on roads intersection, traffic lights, accidents... So, vehicles with different behaviors interact between them and organizations (traffic jams) may appear. With a top down approach, we can examine the global behavior of the system and try to locally modify the environment, when necessary, to ameliorate the system. Recently, some researchers worked on a traffic model in which we have to simulate an urban zone with vehicles and pedestrians. In (?), a model is adopted combining cellular automata and Agent Based Model (ABM). For the vehicles, two-way traffic with turning movements are adopted with simples rules of acceleration and deceleration (due to other vehicles, intersections, or pedestrians). For the pedestrians, they have destination points, influenced by marked crosswalk, walk on sidewalk or street, cross if they feel safe (no near vehicles). Accidents may occur if a vehicle hasn't sufficient time to stop when pedestrian crosses the street (signalized crossing or not) and the severity of an accident depends on vehicle speed. It was difficult to compare results with any verified model because, according to the authors, there was no previous study which has been done on such interactions.

• Hybrid models : The hybrid model allows coupling the two types of dynamics flow models within the same simulation. Several works have already borrowed this direction (???), however, this approach is relatively new and very few have adopted it to our knowledge (?). In risk context, the use of a hybrid model is very important especially when dealing with large volume of data : changing the scale from micro to macro in a region where we haven't a crisis situation (everything is normal) allows to economize the computation and the change from macro to micro in a critical situation allows to zoom and detect the behaviors and interactions between entities in danger.

Risk modelling

Traditional methods evaluating the risk for population do not generally treat evacuees behavior (e.g. initial response to an evacuation, travel speed, family interactions / group, and so on.); they describe prescriptive rules as the travel distance.

The computerized models offer the potential to evaluate the evacuation of a neighborhood in emergency situations and overcome these limitations (?), even than in panic situation, the human behaviour can not be easily predictable and modeled.

In this context, Provitolo (?) studied the spread of the panic of a group of individuals in danger situation to non panicked people. For the author, panic generally results from the lack of coordination and dialogue between individuals. She used a dynamic system (differential equations) and STELLA software to simulate the behavior of individuals. Several simulation scenarios were presented and showed that the emergence of panic has not occurred in all scenarios when changing some parameters. The emergence depends on the rate of transmission from a population susceptible to panic to a panicked population , the time taken to return to a normal behavior (the population is more panicked after the disaster) and the number of initially panicked people. The principle of resilience was also discussed and represents the time that the system makes to return to its initial state after a period of instability due to a disaster. Cova and Church (?) opened the way on the study based on geographic information systems to evacuate people. Their study identified the communities that may face transport difficulties during an evacuation. Research has modelled the population by lane occupation during an evacuation emergency using the city of Santa Barbara. An optimization based model (graph partitioning problem) was realized to find the neighborhood that causes the highest vulnerability around each node in the graph and a vulnerability map around nodes in the city was constructed. A constructive heuristic has been used to calculate the best cluster around each node.

This heuristic was developed in C and the result was displayed on a map (with ArcInfo). Nevertheless, in this approach, we predefine the maximum number of nodes in a neighborhood (or a community), which may not always be realistic and does not take into account the traffic evolution during the calculation of critical neighborhoods. So, the vulnerable neighborhoods don't evolve according to traffic state.

Communities detection

Our aim is to identify communities in graphs according to a predefined criteria and without any fixing of number of communities and the number of nodes per community.

Some definitions

For Newman et al, a community is a set of nodes strongly linked to each other and more weakly linked to the outside world, according to a predefined criteria, but without any fixing of the nodes number in each community (?). Radicchi (?) proposes two possible definitions to quantify Newman definition:

• Community C in a Strong Sense :

d out C (i) > d out C (i), ∀i ∈ C.
A node belongs to a strong community if it has more connections within the community than outside.

• Community C in a Weak Sense :

i∈C d out C (i) > i∈C d out C (i), ∀i ∈ C.
A community is qualified as weak if sum of all degrees inside is more important than sum of degrees towards the rest of the graph.

d out C (i)
is the exiting edges number from a node i belonging to the community C towards the nodes of the same community. d out C (i) is the exiting edges number from a node i belonging to the community C towards the nodes of other communities. Finding organizations is a new field of research (??). Recent works identify two big families in organization detection in large graphs.

• Graph partitioning : a NP-complete problem (?)which consists in grouping nodes in fixed number of partitions with a fixed size, while minimizing the number of inter-partitions connections.

• Data partitioning or hierarchical clustering : based on statistical methods to analyse data and regroup similar data by using some similarity distance. Many of works used this type of models (??).

Stochastic approaches and collective explorations are generally based on random walk in graphs (?). A random walk is a simple stochastic process. It is a formalization of the intuitive idea that we can explore a graph if we walk from an initial node and choose a next adjacent node randomly. To detect organizations, the main idea lays on the fact that small random walks tend to be trapped into them (??).

A dissimilarity index (?) between two nearest neighboring vertices of the graph is measured by a random walk. It is used to determine if nearest-neighboring vertices must be in the same organization. It integrates both the local and the global structural information of the given graph and bias can be introduced, injecting numerical pheromones is an example.

Proposed algorithm

Our aim is to identify communities in graphs, i.e. dense areas strongly linked to each other and more weakly linked to the outside world. If the concept of communities in a graph is difficult to define formally, it can be seen as a set of nodes whose internal connections density is higher than the outside density without defining formal threshold (?). Thus the goal is to find a partition of nodes in communities according to a certain predefined criteria without fixing the number of such communities or the number of nodes in a community. Interesting works were developed in the literature on the detection of structure in large communities in graphs (????).

In our problem, we look for a self-organization in networks with an algorithm close to the detection of communities in large graphs and belonging to collective intelligence algorithms. Organizations connect elements, events or individuals by interrelations so that they become components of a whole. They assume the solidarity and robustness of these links, and ensure that the system will eventually be long lasting despite random perturbations. The organizations, therefore : transform, produce, tie and maintain. Time is present generating the dynamic and we will try to fight against these organizations, in the case of risk management, to avoid bottlenecks which do not facilitate the evacuations. Thus we will considered the graph at time t, G(t) = (V (t), E(t)) where the edges are weighted, this weight being noted |e| for the edge e and represents the needed time to cross this arc, depending on the current load of the traffic and we try to define a colored dynamic graph

G(t) = (E(t), V (t), C(t)).
The algorithm used can be referred to as an ant algorithm (?). Our ant algorithm use several colonies of ants, each of a distinct color. Ants travel inside the graph an lay down pheromones, information that can be detected by other ants. Pheromones are also colored. Ants tend to be repulsed by pheromones of other colors. Furthermore, ants tend to favor edges with important weights. The colored dynamic graph previously mentionned is defined such that:

• V (t) is the set of vertices at time t. Each vertex v is characterized by: a color c ∈ C(t),

• E(t) is the set of edges at time t. Each edge e is characterized by: a weight |e| ∈ N + that corresponds to interaction importance between the elements at each end of edge e.

a quantity of pheromones of each color.

• C(t) is a set of colors representing the ant colonies at time t.

The algorithm principle is to color the graph using pheromones. Each colony will collaborate to colonize zones, whereas colonies compete to maintain their own colored zone (see figure ??). Solutions will therefore emerge and be maintained by the ant behavior. The solutions will be the color of each vertex in the graph. Indeed, colored pheromones are deposited by ants on edges. The color of a vertex is obtained from the color having the largest proportion of pheromones on all incident edges (see algorithm ??). Choose an edge to cross in a weighted random fashion, using edges weight (if available) Lay down a small amount of pheromone of the ant color on this edge n ← vertex at the other end of the chosen edge

In our problem, we have an interaction between each two local adjacent nodes according to the attraction force that exists between them. At each time step, this force depends in our case on the report of the actual number of vehicles on the arc between 2 nodes neighbors / vehicles capacity of the arc. This report was chosen because, in every community, we will have a large number of vehicles which all decide to exit through a single road in the case of a potential danger; this responds well to one of the purposes listed in beginning to have a pessimistic approach in the calculation of vulnerability. The algorithm has the advantage of not allowing the breaking of a link between 2 adjacent nodes to maintain the structure of the road network. When the traffic evolves, the algorithm detects that and communities can change or disappear as a result of local forces that change between the nodes locally. In previous work, we applied this algorithm on the Amazon website. Most of the time, when we are on a page that describes some product, several other items are recommended by the site. We see something like "customers that bought item A also bought B, C, D...". The algorithm has detected and separated items in communities depending on their similarity. Currently, we work on the application of the algorithm on a graph with a dynamic flow model (see figure ??).

6 Dynamic model • The communities detection component : Its input is the extracted graph and the current flow. It returns the communities that are formed according to the current state of road traffic.

Visualization module

Recently, some interesting applications have been developed by including the population dynamics, the models of urban growth patterns and land use. In (?), the authors emphasize the importance of the collaboration between geographers and multi agents system community to model spatial urban systems. They also underline some conceptual and practical difficulties to such coupling. For computer modelers, this integration provides the ability to have computing entities as agents that are linked to real geographical locations. For GIS users, it provides the ability to model the emergence of phenomena by various interactions of agents in time and space by using a GIS (?). So, combining several layers as houses, road network, population... allows us to model different types of agents into a GIS environment. Many researchers have emphasized the need to create vector based Multi Agents System (MAS), which may require the topological data structure provided by using a GIS (?). In geography, the representation of a MAS coexists n levels of organizations and use several classes of agents (e.g. Level 1: individuals or companies, Level 2 and three: economic, urban communities).There will be rules at every level and the approach is not necessarily a bottom up one (as in the models of self-organization). . .) (?).

In this paper, the visualization module consists of the road network layer integrated into the GIS. This layer represents CODAH network layer. This module communicates with the simulation module: the graph is constructed from this module, which in turn get the simulation result and visualize it as a dynamic vulnerability map.

Environment modeling

The road network is integrated as a layer in the Geographic Information System (GIS). From this layer, we extract the data by using the open source java GIS toolkit Geotools. This toolkit provides several methods to manipulate geospatial data and implements Open Geospatial Consortium (OGC) specifications, so we can read and write to ESRI shapefile format. Once data road network are extracted, we use the GraphStream tool (?) developed within LITIS laboratory of Le Havre to construct a graph corresponding to the GIS network layer. This tool is designed for modeling; processing and visualizing graphs. The data extracted from network layer contains the roads circulation direction, roads id, roads type, their lengths and geometry. The extracted multigraph G (t) = (V (t), E (t)) represents the road network at time t where V (t) is the set of nodes at t and E (t) the set of arcs at t. We deal with a multigraph because we have sometimes more than one oriented arc in the same direction between two adjacent nodes due to multiple routes between two points in CODAH road network. GraphStream facilitates this task because it is adapted to model and visualize multigraphs. In the constructed multigraph:

• The nodes represent roads intersections,

• The arcs represent the roads taken by vehicles,

• The weight on each arc represents the needed time to cross this arc, depending on the current load of the traffic

• Dynamic aspect relates to the weights of the arcs, which can evolve in time, according to the evolution of the fluidity of circulation.

We have also constructed a Voronoi tessellation (Thiessen polygon) around nodes and projected the population in buildings on these nodes. The population in buildings is extracted from PRET-RESS model.

Vehicles flow

We have adopted a macroscopic model in which flows circulate normally (without accidents) in order to establish a dynamic pessimistic vulnerability map. In evacuation situations (when an accident occurs), this macroscopic model is not relevant to the reality because most of people panic and take the same road to exit the dangerous area. Hence, it is important to develop a micro approach with multiscale description (from micro to macro and vice versa during the simulation) to simulate scenarios of danger in real time (accidents, behavior of drivers, vehicles interactions. . . ).

Conclusion

The proposed method allowed us to dynamically detect organization in large graphs.

We will apply this algorithm on the graph extracted from CODAH road network layer. It will serve decision makers to estimate the risk due to the use of the road network by vehicles and categorize CODAH areas by their vulnerability. We will complete our work by using real traffic data retrieved from a displacements survey with CODAH population which will help us to better locate people during the day and therefore having a more realistic vulnerability dynamic map.

Figure 1 :

 1 Figure 1: Communities detection in a graph extracted from Amazon website

Figure 2 :

 2 Figure 2: Example of a dynamic evolution and communities detection.

  Our system consists of two modules as shown in the figure ??.

Figure 3 :

 3 Figure 3: System architecture

  Sum of all weights on each incident edge to n τ ← Sum of all pheromones of all colors on each incident edge to n τ c ← Sum of pheromones of the ant color on each incident edge to n

	Algorithm 1: Ant behavior
	n: current node
	t: current time
	A: fear of hostile environment threshold
	T : resting time
	∆t: time counter
	if degree(n)=0 then
	Jump randomly on another node
	else
	w ← a ← τc τ
	if ∆t < T then
	Choose an edge to cross in a weighted random fashion, using edges
	weight (if available)
	Lay down a small amount of pheromone of the ant color on this
	edge
	n ← vertex at the other end of the chosen edge
	∆t ← ∆t + 1
	else
	if a < A then
	Jump randomly on another node
	∆t ← 0
	else

Corresponding author. Authors are alphabetically ordered. Michel Nabaa research is supported by Haute-Normandie Region.

Directive SEVESO is an European directive, it lays down to the states to identify potential dangerous site. It intends to prevent major accidents involving dangerous substances and limit their consequences for man and the environment, with a view to ensuring high levels of protection throughout the Community.