Jean-Baptiste Monnier
email: monnier@math.jussieu.fr

Minimax optimality of the local multi-resolution projection estimator over Besov spaces

Keywords: AMS 2000 subject classifications: Primary 62G05, 62G08 Nonparametric regression, Random design, Multi-resolution analysis

.

1 Introduction

The regression problem

Let us assume we dispose of a set D n = {(X i , Y i ), i = 1, . . . , n} of n independent and identically distributed random vectors. They are constituted of a co-variable X ∈ E ⊂ R d and an associated observation Y ∈ R and are generated by the model,

Y = f (X) + σξ, (1)
where f is an unknown map from E into R, ξ is a standard normal random variable independent from X, which we write ξ ∼ Φ(0, 1), and the law P X of X admits an unknown density µ on E.

In the regression setting, our aim is to best recover f from the data D n under the assumption that f belongs to a smoothness class F. To be more precise, our aim is to build a map f n from E into R upon the data D n so as to minimize the loss E f n -f p Lp(E,µ) uniformly over f . In other terms, we aim at constructing f n such that, sup

f ∈F E f -f n p Lp(E,µ) (log n) δ inf θn sup f ∈F E f -θ n p Lp(E,µ) , δ ≥ 0, n ≥ 0,
where means inferior or equal modulo a constant independent of n and the inf θn is taken over all the estimators θ n of f , that is all measurable maps from E into R. When δ = 0 (δ > 0), f n will be said to be (near-) minimax optimal over the smoothness class F. Throughout the paper, we will work under the following assumption. (CS1) There exist two universal constants 0 < µ min ≤ µ max < ∞ such that µ min ≤ µ(x) ≤ µ max for all x ∈ E and E = [0, 1] d . This is a strong but classical assumption which can be found in previous works such as [START_REF] Baraud | Model selection for regression on a random design[END_REF][START_REF] Audibert | Fast learning rates for plug-in classifiers[END_REF][START_REF] Monnier | Classification via local multi-resolution projections[END_REF], for example.

Construction of the LMPE

We recall the construction of the LMPE, which was introduced in [START_REF] Monnier | Classification via local multi-resolution projections[END_REF]. Assume we dispose of a multiresolution analysis (MRA) of L 2 (R d ) constituted of nested approximation spaces V j ⊂ V j+1 , j ≥ 0, which reproduce polynomials of degree r-1 (meaning that P j p = p, where P j stands for the orthogonal projector from L 2 (R d ) into V j and p is any polynomial of degree r -1). We assume that it is generated by the Daubechies' scaling function ϕ, meaning that (ϕ j,k ) k∈Z d stands for an orthonormal basis of V j , where we have written ϕ j,k (.) = 2 j d 2 ϕ(2 j . -k). In the sequel, we will refer to such a MRA as a r-MRA. As described in [START_REF] Monnier | Classification via local multi-resolution projections[END_REF], [0, 1] d can be partitioned into hypercubes of the form O j,k = 2 -j (k + [0, 1] d ) for ks that belong to a well chosen subset Z d j of Z d . In addition, Suppϕ = [1 -r, r] d so that there are only m = (2r -1) d scaling functions which intercept a cell O j,k . It is crucial here to notice that m is a constant independent from both j and k. The LMPE of f at resolution level j is then obtained by performing 2 jd local regressions, that is one on each cell O j,k . Under the assumption that f belongs to a Besov ball, the remainder f -P j f can be naturally controlled so that it remains to estimate P j f by localized projections onto the O j,k . As detailed above, we denote by ϕ j,k 1 , . . . , ϕ j,km the scaling functions whose supports intercept the cell O j,k . For any x ∈ O j,k , we can write

P j f (x) = α j,k 1 ϕ j,k 1 (x) + . . . + α j,km ϕ j,km (x),
so that we must estimate the m coefficients α j,k i to obtain an estimator of P j f on O j,k . This is done by standard regression on O j,k . More precisely, we consider the least-squares problem,

LS(O j,k ) = arg min (a 1 ,...,at)∈R m n i=1 Y i - m t=1 a t ϕ j,kt (X i ) 2 1 O j,k (X i ).
Solving the above least-squares problem boils down to the inversion of the local regression matrix

G ∈ R m × R m whose coefficients are the, G ℓ,ℓ ′ = 1 n n i=1 ϕ j,k ℓ (X i )ϕ j,k ℓ ′ (X i )1 O j,k (X i ). (2)
Obviously, if G is invertible then LS(O j,k ) holds one single element. Finally, we define the LMPE f @ j by spectral thresholding of the smallest eigenvalue of the local regression matrix λ min (G) at level π -1 n , where we can take π n = log n. We set indeed f @ j = 0 if λ min (G) < π -1 n and f @ j (x) = m t=1 a @ t ϕ j,kt (x) for all x ∈ O j,k otherwise, where a @ is the unique element of LS(O j,k ).

2 Results τ,∞ (E). Assume that the regression loss is measured in L p -norm. Generalized Lipschitz spaces Lip s (E) are defined to be the Besov spaces B s ∞,∞ (E) and thus correspond to the vertical coordinate axis 1/τ = 0 (see [START_REF] Monnier | Quelques contributions en classification, régression et étude d'un problème inverse en finance[END_REF]). Besov spaces B s τ,∞ (E) get larger and larger along the arrows drawn on the figure. In [7, Corollary 7.1] the LMPE was proved to be near minimax optimal over generalized Lipschitz spaces (thick vertical red line). Here we show that these results can be extended to the whole domain {(1/τ, s) :

1 τ s 1 p s = d( 1 τ -1 p ) + ( N L ) (L) 1 τ 1 1 τ 2 1 τ 3 B γ τ 1 ,∞ B γ τ 2 ,∞ B γ τ 3 ,∞ B γ p,∞ γ B γ-d( 1 τ 2 -1 p ) p,∞ Lip s 1 2 B s τ,∞ L p
1/τ ≤ 1/p}.
In what follows, we prove that the LMPE is minimax optimal in the regression setting over Besov spaces. This is a generalization of the results described in [START_REF] Monnier | Classification via local multi-resolution projections[END_REF]Corollary 7.1], where the LMPE was proved to be minimax optimal over generalized Lipschitz spaces Lip s (E), which are slightly larger than Hölder spaces. To be more precise, we prove in what follows that the LMPE is near minimax optimal over Besov spaces B s τ,q (E), s > 0, τ ≥ p, q > 0, when the loss is measured in L p -norm, p ∈ [2, ∞) (see Theorem 2.1), and over Besov spaces B s τ,q (E), s > d/τ , τ, q > 0, when the loss is measured in L ∞ -norm (see Theorem 2.2). As described in Figure 1, these smoothness classes are much larger than the Lipschitz spaces. In addition, it is well-known that, outside this domain, linear estimators such as the LMPE are necessarily sub-optimal (see [START_REF] Donoho | Density estimation by wavelet thresholding[END_REF]). So that this is the largest domain on which we can obtain the near-minimax optimality of the LMPE (up to the constraint p ≥ 2). Interestingly, the proof of the initial result [START_REF] Monnier | Classification via local multi-resolution projections[END_REF]Corollary 7.1] hinged on an integration of the exponential control of the probability of deviation of the LMPE f @ j (x) from f (x) uniformly when x ∈ E (see [START_REF] Monnier | Classification via local multi-resolution projections[END_REF]Theorem 7.1]). The latter exponential control is very stringent and was initially introduced to prove results in the classification setting. It is however unnecessary in the regression setting and can thus be relaxed. The following proofs hinge in fact on a direct inspection of the integrated L p -loss and are thus obtained by very different means from the ones used in [START_REF] Monnier | Classification via local multi-resolution projections[END_REF]. In particular, they rely on the recombination of the integrated approximation errors over the regression cells O j,k of the partition of E (see proof of Theorem 2.1). In what follows, and for any τ > 0, we define j r , j s , j s,τ , J such that

2 jr ∼ n 1 2r+d , 2 js ∼ n 1 2s+d , 2 js,τ ∼ n 1 2(s+ d 2 -d τ ) , 2 Jd ∼ n κπ 2 n log n ,
where κ > 0 is a constant to be made more precise later. By a n ∼ b n , we mean that there exist two absolute constants independent of n such that ca n ≤ b n ≤ Ca n . Furthermore we define the grid J n of resolution levels such that J n = {j r , j r + 1, . . . , J}. Of course, j s , j s,τ ∈ J n under the assumption that s ∈ (0, r).

In Theorem 2.1, we show that the LMPE is nearly minimax optimal in L p -norm, p ∈ [2, ∞) over a wide Besov scale. This result contains [7, Corollary 7.1] as a particular case (take τ = q = ∞) and thus generalizes it to larger smoothness classes.

Theorem 2.1. Assume (CS1) holds true. Let f @ j stand for the local multi-resolution estimator of f defined in Section 1.2 and B s τ,q (E, M ) for the ball of radius M > 0 of B s τ,q (E). Then for all j ∈ J n , p ∈ [2, ∞), s > 0, τ ≥ p and q > 0, we have the following result,

sup f ∈B s τ,q (E,M ) E f -f @ j p Lp(E,µ) ≤ C(p)π p n 2 j d 2 √ n p + 2 -jsp ,
where the constant C(p) is given explicitly in the proof. In particular, for j = j s , we obtain

sup f ∈B s τ,q (E,M ) E f -f @ js p Lp(E,µ) ≤ C(p)π p n n -sp 2s+d .
The corresponding lower-bound result is well-known (see [START_REF] Yang | Information-theoretic determination of minimax rates of convergence[END_REF][START_REF] Korostelev | Minimax theory of image reconstruction[END_REF][START_REF] Monnier | Classification via local multi-resolution projections[END_REF]), which finishes to prove the minimax optimality of the LMPE.

In Theorem 2.2, we show that the LMPE is nearly minimax optimal in sup-norm over a wide Besov scale. Notice interestingly that, until now, there were no results available in sup-norm for the LMPE.

Theorem 2.2. Assume (CS1) holds true. Let f @ j stand for the local multi-resolution estimator of f defined in Section 1.2 and B s τ,q (E, M ) for the ball of radius

M > 0 of B s τ,q (E). For all f ∈ B s τ,q (E, M ), s > d/τ , sup f ∈B s τ,q (E,M ) E f -f @ j z L∞(E) ≤ C(z)π z n [log n] z 2 2 j d 2 √ n z + 2 -j(s-d τ )z ,
where the constant C(z) is given explicitly in the proof. In particular, for j = j s,τ , we obtain

sup f ∈B s τ,q (E,M ) E f -f @ js,τ z L∞(E) ≤ C(z)π z n (log n) z 2 n - z(s-d τ ) 2(s+ d 2 -d τ ) .
The corresponding lower-bound result is well-known (see [START_REF] Yang | Information-theoretic determination of minimax rates of convergence[END_REF][START_REF] Korostelev | Minimax theory of image reconstruction[END_REF][START_REF] Monnier | Classification via local multi-resolution projections[END_REF]), which finishes to prove the minimax optimality of the LMPE.

Both theorems prove the optimality of the estimators f @ js and f @ js,τ , whose resolution levels depend on the regularity s of the unknown regression function f . In the following theorem, we show that this dependence in s can be removed at the cost of a log n factor in the upper-bounds. The LMPE is thus said to be adaptive near minimax optimal. To be more explicit, the adaptation hinge on the data-driven choice j @ of the global resolution level j of the LMPE (see Theorem 2.3), which itself hinges on a slightly modified version of Lepski's method (see [START_REF] Lepski | Optimal spatial adaptation to inhomogeneous smoothness: an approach based on kernel estimates with variable bandwidth selectors[END_REF]).

Theorem 2.3. Assume (CS1) holds true. For all f ∈ B s τ,q (E, M ), s, q > 0, τ ≥ p, p ≥ 2, we define the global resolution index j @ from the data D n as follows for γ > 0,

j @ = inf j ∈ J n : f @ j -f @ k Lp ≤ γ log n 2 j d 2 √ n + 2 k d 2 √ n , ∀k > n, k ∈ J n .
Then, for γ large enough, we obtain,

E f @ j @ -f p Lp(E,µ) γ p (log n) p π p n n -sp 2s+d , p ∈ [2, ∞), E f @ j @ -f z L∞(E) γ z (log n) z π z n n - z(s-d τ ) 2(s+ d 2 -d τ ) .
So that f @ j @ is an adaptive near minimax optimal estimator of f . In what follows, we detail the proofs of these three theorems. In order to alleviate notations, we will denote throughout the sequel by H a cell O j,k of the partition of [0, 1] d at level j and by G H the associated local regression matrix (see eq. ( 2)). Furthermore, we will denote by F j the partition of [0, 1] d into hyper-cubes O j,k at resolution level j.

3 Proofs Remark 3.1. Recall that for any p ∈ [1, ∞], there exist two absolute constants c p , C p such that

c p 2 jd( 1 2 -1 p ) ≤ ϕ j,k Lp ≤ C p 2 jd( 1 2 -1 p ) .
Throughout the paper, constants of the form c p , C p will exclusively refer to these constants. Furthermore, we will write ϑ p := E|ξ| p , where the noise ξ has been defined in eq. (1).

Proof of Theorem 2.1

Proof of Theorem 2.1. Notice first that the regression loss can be broken up as follows,

E f -f @ j p L P ≤ H E f -f @ j p L P (H) 1 {λ min (G H )<π -1 n } , + 2 p-1 H E P j f -f @ j p L P (H) 1 {λ min (G H )≥π -1 n } + 2 p-1 R j f p L P .
As described in the proof of [7, Theorem 7.1], we have, for f ∈ B s τ,q (E, M ),

f -f @ j p Lp(H) 1 {λ min (G H )<π -1 n } ≤ M p µ(H)1 {λ min (G H )<π -1 n } , |P j f (x) -f @ j (x)| p 1 {λ min (G H )≥π -1 n } ≤ π p n W H p ℓ 2 ϕ H (x) p ℓ 2 , ∀x ∈ H, (3)
where W H = (W j,k 1 , . . . , W j,km ), ϕ H (x) = (ϕ j,k 1 (x), . . . , ϕ j,km (x)), the ϕ j,k i , 1 ≤ i ≤ m, are the scaling functions whose supports intercept H and we have written

W j,k = 1 n n i=1 Z j,k i , Z j,k i = ϕ j,k (X i )1 H (X i )(R j f (X i ) + ξ i ).
So that, putting everything together, we obtain,

E f -f @ j p L P ≤ M p n sup H∈F j P(λ min (G H ) < π -1 n ) + 2 p-1 π p n H H ϕ H (x) p ℓ 2 µ(x)dx E W H p ℓ 2 + 2 p-1 R j f p L P = I + II + III.
I is of the right order since, according to Lemma 3.3, it can be made as small as desired for κ large enough. III is also of the right order according to Lemma 4.1. Let us now turn to II. Write S j (H) = {k i , i = 1, . . . , m} and notice that, with m = #S j (H), we have,

ϕ H (x) p ℓ 2 ≤ ϕ H (x) p ℓ 1 ≤ m p-1 ϕ H (x) p ℓp .
We thus obtain

II ≤ µ max 2 p-1 π p n H   k∈S j (H) ϕ j,k p Lp   E W H p ℓ 2 ≤ µ max 2 p-1 π p n mC p p 2 jd( p 2 -1) E W H p ℓ 2 ≤ C(p, µ max , m, ϑ p , p)π p n     2 j d 2 √ n 2(p-1) + 2 j d 2 √ n p   (1 + R j f p Lp ) + R j f p Lp   ,
where the last inequality follows from Proposition 3.1, eq. ( 5) and we can choose

C(p, µ max , m, ϑ p , p) = C (1) ∨ C (2) ∨ C (3) , C (1) = µ 2 max m p+1 2 2(p-1) C p p C p p ′ , C (2) = µ 2 max m p+1 2 4(p-1) C p p C p ∞ (1 ∨ ϑ p ), C (3) = µ 2 max m p+1 2 7 2 p-3 C p p (C p 2[p/2] ′ ∨ [C p 2 ϑ p 2 p ]).
To conclude, notice that for j ∈ J n , 2 jd/2 / √ n ≤ 1, 2(p -1) ≥ p since p ≥ 2 and R j f Lp ≤ M 2 -js since f ∈ B s τ,q (E, M ) and τ ≥ p (see Lemma 4.1). In particular, we can choose

C(p) = (C(p, µ max , m, ϑ p , p) + 1)(1 ∨ M p ).
3.2 Useful results for the proof of Theorem 2.1 Proposition 3.1. Remark that we have

E W H p ℓ 2 n -p+1 2 jd p 2 1 H R j f p Lp + 2 jd( p 2 -1) + n -p 2 2 jd 1 H R j f p Lp + 1 + 2 jd(1-p 2 ) 1 H R j f p Lp , (4)
where the upper-bound constants are detailed in the proof. We obtain the following result as a direct consequence of eq. ( 4),

H E W H p ℓ 2 n -p+1 2 jd p 2 R j f p Lp + 2 jd( p 2 ) + n -p 2 2 jd R j f p Lp + 2 jd + 2 jd(1-p 2 ) R j f p Lp . (5)
Proof. Recall first that we have written m = #S j (H) = (2r -1) d . It is enough to notice that . ℓ 2 ≤ . ℓ 1 and use Jensen inequality to get,

E W H p ℓ 2 ≤ m p-1 k∈S j (H) E|W j,k | p .
In addition, a triangular inequality leads to,

E|W j,k | p ≤ 2 p-1 n -p E| n i=1 Z j,k i -EZ j,k i | p + 2 p-1 |EZ j,k i | p .
Now, eq. ( 4) follows from eq. ( 10) and eq. ( 13) in Lemma 3.1 below, and the constants can be read off these latter equations.

Lemma 3.1. We have got the following four inequalities,

|EZ j,k i | p 2 jd(1-p 2 ) 1 H R j f p Lp , (6)
E|Z j,k i | p 2 jd p 2 1 H R j f p Lp + 2 jd( p 2 -1) , (7)
E|Z j,k i | 2 p 2 2 jd 1 H R j f p Lp + 1, p ≥ 2, ( 8
)
E| n i=1 Z j,k i -EZ j,k i | p n 2 jd p 2 1 H R j f p Lp + 2 jd( p 2 -1) + n p 2 2 jd 1 H R j f p Lp + 1 , (9)
where the upper-bound constants can be read from eq. ( 10), eq. ( 11), eq. ( 12) and eq. ( 13) respectively. Notice interestingly that all upper bounds are independent of k.

Proof. The proof of eq. ( 6) follows from Hölder's inequality with (p ′ ) -1 + p -1 = 1. Notice indeed that,

|EZ j,k i | p = |Eϕ j,k (X i )1 H (X i )R j f (X i )| p ≤ µ max ϕ j,k 1 H R j f p L 1 ≤ µ max ϕ j,k p L p ′ 1 H R j f p Lp ≤ µ max C p p ′ 2 jd(1-p 2 ) 1 H R j f p Lp . ( 10
)
The proof of eq. ( 7) is a straightforward consequence of the triangular inequality. Notice indeed that,

E|Z j,k i | p = E|ϕ j,k (X i )1 H (X i )(R j f (X i ) + ξ i )| p ≤ 2 p-1 E|ϕ j,k (X i )1 H (X i )R j f (X i )| p + 2 p-1 E|ϕ j,k (X i )1 H (X i )ξ i | p ≤ µ max 2 p-1 ϕ j,k p L∞ 1 H R j f p Lp + ϑ p µ max ϕ j,k 1 H p Lp ≤ µ max 2 p-1 C p ∞ 2 jd p 2 1 H R j f p Lp + ϑ p µ max 2 p-1 C p ∞ 2 jd( p 2 -1) . ( 11
)
The proof of eq. ( 8) is a direct consequence of Hölder's inequality with

([p/2] ′ ) -1 + (p/2) -1 = 1, p ≥ 2.
Notice indeed that

E|Z j,k i | 2 p 2 ≤ 2 p-1 E|ϕ j,k (X i )1 H (X i )R j f (X i )| 2 p 2 + 2 p-1 ϑ p 2 2 E|ϕ j,k (X i )| 2 p 2 ≤ µ max 2 p-1 ϕ j,k p L 2[p/2] ′ 1 H R j f p Lp + µ max C p 2 2 p-1 ϑ p/2 (Hölder) ≤ µ max 2 p-1 C p 2[p/2] ′ 2 jd 1 H R j f p Lp + µ max C p 2 2 p-1 ϑ p/2 , (12)
where the last inequality follows from the fact that

ϕ j,k p L 2[p/2] ′ ≤ C p 2[p/2] ′ 2 jd( 1 2 -1 2[p/2] ′ )p = C p 2[p/2] ′ 2 jd .
Let us now turn to the proof of eq. ( 9). Notice first that a direct application of Rosenthal's inequality leads to,

E| n i=1 Z j,k i -EZ j,k i | p ≤ n i=1 E|Z j,k i -EZ j,k i | p + n i=1 E|Z j,k i -EZ j,k i | 2 p/2 ≤ n2 p-1 E|Z j,k i | p + n p 2 2 p 2 E|Z j,k i | 2 p/2 (Jensen) ≤ nµ max 2 2(p-1) C p ∞ (1 ∨ ϑ p )(2 jd p 2 1 H R j f p L p p + 2 jd( p 2 -1) ) + n p 2 µ max 2 3p 2 -1 (C p 2[p/2] ′ ∨ [C p 2 ϑ p 2 ])(2 jd 1 H R j f p L p p + 1), (13)
where the last inequality follows from both eq. ( 11) and eq. (12).

Proof of Theorem 2.2

Proof of Theorem 2.2. Let us denote by F j the partition of [0, 1] d associated to the r-MRA at hand and by H a generic cell of this partition. Start with

E f -f @ j z L∞ = E sup H∈F j ,x∈H |f (x) -f @ j (x)| z ≤ E sup H∈F j ,x∈H |P j f (x) -f @ j (x)| z + R j f z L∞
The last term is of the right order according to Lemma 4.1. Focus now on the first one. Using the same reasoning (and notations) as at the beginning of the proof of Theorem 2.1, we obtain

E sup H∈F j ,x∈H |f j (x) -f @ j (x)| z ≤ M P( inf H∈F j λ min (G H ) ≤ π -1 n ) + E sup H∈F j π z n W H z ℓ 2 sup x∈H ϕ H (x) z ℓ 2 = I + II.
A direct application of Lemma 3.3 shows that I is of the right order for κ large enough. Let us now turn to II and notice that

II ≤ m z 2 C z ∞ 2 jd z 2 π z n E sup H W H z ℓ 2 ≤ m z C z ∞ 2 jd z 2 π z n E sup H∈F j ,k∈S j (H) |W j,k | z .
Notice besides that

|W j,k | z ≤ 2 z-1 | 1 n n i=1 Z j,k i -EZ j,k i | z + 2 z-1 |EZ j,k i | z .
The rhs is handled directly thanks to eq. ( 14). As regards the lhs, notice that #{H ∈ F j , k ∈ S j (H)} = m2 jd and, given eq. ( 15), apply Proposition 4.1 (with K = 2 j d 2 ) conclude that

E sup H∈F j ,k∈S j (H) | 1 n n i=1 (Z j,k i -EZ j,k i )| z ≤ 2 j d 2 log(m2 jd + e z-1 ) n + 2 log(m2 jd + e z-1 ) n z .
Finally, putting everything together, we obtain

E f -f @ j z L∞ π z n R j f z L∞ + (log n) z 2 2 j d 2 √ n z .
3.4 Useful results for the proof of Theorem 2.2 Lemma 3.2. We have the following inequalities

E|Z j,k i | z ≤ C z 1 2 -jd z 2 R j f z L∞ , (14)
E|Z j,k i -EZ j,k i | z ≤ C(z)(2 j d 2 ) z-2 (1 + R j f z L∞ ), (15)
where we have written C(z) = µ max 2 2z-1 C z z (ϑ z ∨ 1). Proof. For the first inequality,

|EZ j,k i | z = |Eϕ j,k (X i )1 H (X i )R j f (X i )| z ≤ µ max R j f z L∞ ϕ j,k z L 1 ≤ µ max C z 1 2 -jd z 2 R j f z L∞ .
For the second one,

E|Z j,k i -EZ j,k i | z ≤ 2 z E|Z j,k i | z ≤ 2 2z-1 E|ϕ j,k (X i )1 H (X i )R j f (X i )| z + 2 2z-1 E|ϕ j,k (X i )1 H (X i )ξ i | z ≤ µ max 2 2z-1 C z z 2 jd( z 2 -1) R j f z L∞ + µ max 2 2z-1 ϑ z C z z 2 jd( z 2 -1) = µ max 2 2z-1 C z z (2 j d 2 ) z-2 (1 ∨ ϑ z )( R j f z L∞ + 1).
Lemma 3.3. Let us denote by F j the partition of [0, 1] d into hyper-cubes O j,k at resolution level j.

For j ∈ J n = {j r , . . . , J} where 2 Jd = n/(κπ 2 n log n), and any H ∈ F j , and for

κ ≥ κ(2µ max m 4 + 4 3 m 2 ), κ > 0,
we have got

P(λ min (Q H ) ≤ π -1 n ) ≤ 2m 2 n -κ , P( inf H∈F j λ min (Q H ) ≤ π -1 n ) ≤ 2m 2 n -κ+1 .
Proof. We know from [START_REF] Monnier | Classification via local multi-resolution projections[END_REF]Proposition 12.3] that for all 0 < t ≤ g min 2 ,

P(λ min (Q H ) ≤ t) ≤ 2m 2 exp(-n2 -jd t 2 2µ max m 4 + 4 3 m 2 t
).

For n large enough, we have π n ≤ g min 2 and the result follows directly from the latter inequality.

Proof of Theorem 2.3

Proof of Theorem 2.3. Assume first that p ∈ [2, ∞) and write,

f -f @ j @ p Lp = f -f @ j @ p Lp 1 {j @ ≤js} + f -f @ j @ p Lp 1 {j @ >js} = I + II.
As regards I, notice that

I ≤ 2 p-1 f -f @ js p Lp + 2 p-1 f @ js -f @ j @ p Lp 1 {j @ ≤js} ≤ 2 p-1 f -f @ js p Lp + 2 p-1 2γ p (log n) p π p n 2 js d 2 √ n p .
The left term is of the right order thanks to Theorem 2.1 and the last term as well by definition of j s .

As regards II, we proceed as in the proof of [7, Theorem 7.2] and notice that,

E f -f @ j @ p Lp 1 {j @ >js} ≤ j>js E f -f @ j p Lp 1 {j @ =j} ≤ j>js E f -f @ j 2p
Lp P(j @ = j).

The expectation is bounded by a constant according to Theorem 2.1. And we have besides

P(j @ = j) ≤ k≥j P f @ j -f @ k Lp > γ(log n)π n 2 j d 2 √ n + 2 k d 2 √ n ≤ k≥j P f @ j -f Lp > γ(log n)π n 2 j d 2 √ n + P f @ k -f Lp > γ(log n)π n 2 k d 2 √ n ,
which can be made as small as desired for γ large enough according to Proposition 3.2. For p = ∞, the proof follows the same lines with j s,τ in place of j s .

3.6 Useful results for the proof of Theorem 2.3 Proposition 3.2. For all f ∈ B s τ,q (E, M ), s, q > 0, τ ≥ p, p ≥ 2 and all j ≥ j s (resp. j ≥ j s,τ ) for p < ∞ (resp. p = ∞), we have

P( f @ j -f Lp ≥ γ(log n)π n 2 j d 2 √ n ) ≤ mn -C(p,r,σ)γ n 1 {p=∞} ,
where the constant C(p, r, σ) can be found in the proof. In any case, the above term can thus be made as small as possible for γ large enough.

Proof. Case where p ∈ [2, ∞). Recall that #F j = 2 jd and notice first that for δ/2 ≥ Rf j Lp ,

P( f @ j -f Lp ≥ δ) ≤ P( f @ j -f j p Lp ≥ δ p 2 -p ) = P( H f @ j -f j p Lp(H) ≥ δ p 2 -p ) = H P( f @ j -f j p Lp(H) ≥ δ p 2 -jd 2 -p ) ≤ H P( f @ j -f j p Lp(H) ≥ δ p 2 -jd 2 -p , λ min (G H ) ≥ π -1 n ) + H P(λ min H (G H ) < π -1 n ) = I + II.
II can be made as small as desired thanks to Lemma 3.3. For the first term, we deduce from eq. ( 3) that

I ≤ H P(π p n W H p ℓ 2 k∈S j (H) ϕ j,k p Lp ≥ 2 -jd δ p 2 -p ) ≤ H P(π p n W H p ℓ 2 C p p 2 jd( p 2 -1) m ≥ 2 -jd δ p 2 -p ) ≤ H P( W H ℓ 2 ≥ 2 -j d 2 δ 2π n C p m 1 p ) ≤ m sup k∈S j (H) P(|W j,k | ≥ 2 -j d 2 δ 2π n C p m 1 p +1
). Now, notice that for j ≥ j s , we have 2 j Case where p = ∞. The reasoning is similar as the one described above, with however a few slight modifications. For δ/2 > 2 -j(s-d τ ) ≥ R j f L∞ , we have,

P( f -f @ j L∞ ≥ δ) ≤ P( f -f @ j z L∞ ≥ δ z 2 -z , inf H λ min (G H ) ≥ π -1 n ) + P(inf H λ min (G H ) < π -1 n ) = I + II.
II is of the right order thanks to Lemma 3.3. Moreover, similar arguments as the ones described in the proof of Theorem 2.2 allow to write, I ≤ P sup We recall that for all d ≥ 1, τ, q ∈ (0, ∞], s > d/τ ,

f ∈ B s τ,q (M ) ⇒ R j f L∞ ≤ M 2 -j(s-d τ ) . (16)
And for all d ≥ 1, q ∈ (0, ∞], τ ∈ [p, ∞), s > 0,

f ∈ B s τ,q (M ) ⇒ R j f Lp ≤ M 2 -js . (17)
Proof. These results can be found in [START_REF] Cohen | Numerical analysis of wavelet methods[END_REF] for example. Eq. ( 16) is a straight consequence of the embedding B s τ,q (M ) ⊂ B s-d τ ∞,∞ (M ).

Uniform moment bound

Proposition 4.1 (see [START_REF] Van De Geer | Uniform probability inequalities, with applications in high-dimensional statistical models[END_REF]). Let Z 1 , . . . , Z n be a set of n independent random variables such that, for all i and p ∈ N, Eγ j (Z i ) = 0, 1 n

Figure 1 :

 1 Figure 1: Each point of this figure at coordinates (s, 1/τ ) stands for a Besov space B sτ,∞ (E). Assume that the regression loss is measured in L p -norm. Generalized Lipschitz spaces Lip s (E) are defined to be the Besov spaces B s ∞,∞ (E) and thus correspond to the vertical coordinate axis 1/τ = 0 (see[START_REF] Monnier | Quelques contributions en classification, régression et étude d'un problème inverse en finance[END_REF]). Besov spaces B s τ,∞ (E) get larger and larger along the arrows drawn on the figure. In [7, Corollary 7.1] the LMPE was proved to be near minimax optimal over generalized Lipschitz spaces (thick vertical red line). Here we show that these results can be extended to the whole domain {(1/τ, s) : 1/τ ≤ 1/p}.

d 2 / 1 p

 21 √ n ≥ 2 -js . Hence we can apply [7, Proposition 12.5]δ = γ(log n)2 j d 2 / √ n to conclude that I ≤ mn -C(p,r,σ)γ , where C(p, r, σ) = (1 ∧ σ -2 )/C p m +1 .

  H∈F j ,k∈S j (H)|W j,k | ≥ δ2 -j d 2 2mπ n C ∞ ≤ m2 jd sup H∈F j ,k∈S j (H) P |W j,k | ≥ δ2 -j d 2 2mπ n C ∞ .Now, notice that for j ∈ J n , 2 jd ≤ n/ log n. Notice besides that for j ≥ j s,τ , we have 2j d 2 / √ n ≥ 2 -j(s-d τ ). Hence, following similar arguments as in [7, Proposition 12.5] and choosingδ = γ(log n)2 j d 2 / √ n,we can conclude that I ≤ mn -C(∞,r,σ)γ+1 , whereC(∞, r, σ) = (1 ∧ σ -2 )/mC ∞ .4Appendix 4.1 Properties of Besov spaces Lemma 4.1.

  Z i )| p ≤ K log(N + e p-1 ) n + 2 log(N + e p-1) n p .


Marta Severo

Timothée Giraud

Nicolas Douay

Citizen protest in the online networks: the case of the China's bloody map

scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Citizen protest in the online networks:

the case of the China's bloody map

Research purpose

In the last few years, cyber-activism has become a very hot topic. In countries with authoritarian regimes, the Internet has offered new spaces of expression [START_REF] Benkler | The Wealth of Networks: How Social Production Transforms Markets and Freedom[END_REF].

The recent emergence of social media and the Web 2.0 has increased this phenomenon. Social media offer innovative terrains of expression, less standardized and controlled.

Particularly where public venues are too dangerous to express one's opinions, the blogs, Facebook pages and Twitter accounts may give voice to citizen" needs and ideas in a safer way.

But what makes the Internet a powerful and dreaded tool in censorship environments is his potential in disseminating information. Thanks to its vast and interconnected nature [START_REF] Barabasi | Linked: the new science of networks[END_REF], the Web immediately connects local protests in a global network promoting local issues to a worldwide visibility [START_REF] Beutz Land | Networked Activism[END_REF]. Once the protest is published in a webpage, what makes it interesting and relevant are the connections from and toward this webpage. The passage from a personal to a public contestation, from a punctual to a global issue is not just the result of being published on the Web, but of being included in a network of links.

This paper aims at investigating the dynamics of the dissemination of information concerning citizen contestations through the Web. How is dissent information coming from countries where the use of Internet is subject to censorship transmitted around the world? Which network is created by protesting website and by their hyper-links? Which network is created by the links received by such websites? Which types of actors are involved? How the network of actors is developing in time and in space?

These issues will be investigated through the analysis of the Bloody Map of violent evictions in China [START_REF] Douay | Urbanisme et cyber-citoyens chinois, la contestation 2.0 s"organise[END_REF]. Such case constitutes an excellent example of citizen contestation about urban planning made possible by Web 2.0 technologies [START_REF] Haski | Internet et la Chine[END_REF][START_REF] Yang | The Power of the Internet in China: Citizen Activism Online[END_REF] and disseminated around the whole World through the Internet. Special attention will be paid to the networks of actors generated by this map.

Methodology

Our analysis will be performed through an innovative methodology based on digital methods [START_REF] Rogers | Internet Research: The Question of Method[END_REF]. By "digital methods" we refer to a series of methods designed to explore the landscapes drawn by the digital traces left by online interactions around a given topic. Among digital methods we chose the cartography of the Web.1 This method helps designing a network of relationships among entities such as institutions, associations, media and individuals based on hypertext connections among their websites.

The idea is that the decision of adding a hyperlink to a website reveals the presence of a relationship, at least of knowledge, between the two entities represented by the websites.

By identifying the key actors and relations and labelling them according to an "ad hoc" codebook, digital methods help tracing the interactions between the actors concerned by a given phenomenon. In our case, websites have been categorized according to their type (journal, community, news portal etc.) and their country (identified on the basis of the content of the website). Although digital methods cannot provide an exhaustive description of social networks, they may suggest interesting research directions to be investigated through further interpretative work. In investigating recent, vast and everchanging phenomena such us cyber-citizenry in China, these methods have the advantage of offering a global overview, drawing a tentative map of actors and partially overcoming the linguistic diversity that hinder the study of such field.

In our presentation, we will use digital methods to explore the hyperlinks networks around the Bloody map of violent evictions in China and in particular the network of actors involved in the dissemination of the information published on the map. The analysis will concentrate on two main aspects: (1) the network of "sources", that is to say the websites that are mentioned in the map as sources of information;2 (2) the network of "opinion leaders", that is to say the websites that talk about the map around the world. 3 By analysing the linking strategies of actors, we hope to identify the specific topology of both networks, showing which actors are central and peripheral, whether clusters or cliques are formed and who plays the role of authority and hub.

Finally, a crucial originality in our approach is the attention paid to the geography of online networks. As for the network of "sources", we identified the geographical region where each accident took place and we related the website to it. As for the network of "opinion leaders", we tried to identify their location. By georeferencing the data retrieved by digital methods, we make it possible to analyze them also through the techniques of geographical investigation. Our objective is to explore how the analysis of the nongeographical space of the Web may contribute to the understanding of territorial issues such as the one related by urban planning policies.

Findings

In 2010, an anonymous Internet contributor using the pseudonym Xuefangditu, or "real estate blood map", compiled a list of all the violent evictions linked to property development projects in China and promoted it in his blog (http:// /t.sina.com.cn/bloodymap). This blogger's motive was to denounce the rapid pace of Chinese urbanisation, which is destroying the lives of many citizens, and to create a movement to boycott those new developments where there had been bloodshed. The "open" version of the Bloody Map of violent evictions in China (retrieved 28 th April 2011)

In the revised map, on the basis of about a hundred pages-sources (belonging to 46 different websites), a total of 85 accidents have been identified. A dozen cases of riots and demonstrations, 25 cases of illegal evictions or demolitions (sometimes several buildings) and 30 deaths (including 15 immolations) are represented across 24 different provinces. The websites, mentioned as sources of information, generate an interconnected network dominated by 70 news portals, a dozen of community websites and so many journals. In our communication we will describe the topology of the network and we will show how the credibility of the citizen protest is based on such a network that is constituted mainly by media.

The Bloody map was published on October 8th 2010, and on October 20th the New China news agency published an article about it, ad this led to a further ten Chinese publications taking up the story a month later. By late December 2010, typing in "bloody map" (in Chinese) on Google China, more than 1,640,000 hits was showed. In the same days, the news went around the globe. We identified 139 websites (from 19 countries) mentioning the map. In our communication, we will discuss how citizen protest is amplified by the connection to the worldwide network of media and may consequently become part of the public agendas.

  The project consists of two maps (both based on Google Maps): an "open" version 4 that anyone can add to or edit and a "revised" version 5 edited by the blogger that shows only verified cases. Little volcanoes represent sites where people were evicted violently, with water canons or Molotov cocktails. Beds indicate incidents that resulted in at least one death. Flames indicate immolations. Every accident has to be supported by the link to an online sources document the event. After the verification of such sources, the blogger publish the accident in the revised map. All maps and sources are in Chinese.

The web networks have been retrieved with the Navicrawler, an assisted navigation tool, and the Issue Crawler, an automatic tool crawling the web. The resulting networks have been visualised and analysed by a software for exploring graphs (Gephi).

The source websites have been identified and labelled by two Chinese students Li Jishen & Wang Yuanyuan of the Master of Geography of the Université Paris Diderot in the context of the graduation thesis "Cyber-activism in Chinese urban planning".

These websites have been identified thanks to the combined use of several online tools: Yahoo site explorer and SEO Open explorer (that retrieve links toward a url) and Tineye (that retrieves occurrences of an image over the Web).

http://maps.google.com/maps/ms?msa=0&msid=111560301092049321699.0004921f02f43f6c4f07e

http://ditu.google.com/maps/ms?brcurrent=3,0x31508e64e5c642c1:0x951daa7c349f366f,0%3B5,0,0&ie=UTF8&hl= zh-CN&msa=0&msid=111560301092049321699.000492290963f3883a9c6&ll=31.466154,121.992188&spn=25.2824 73,36.035156&z=5


Sébastien Gambs

Marc-Olivier Killijian
email: marco.killijian@laas.fr

Miguel Núñez

Del Prado Cortez

I Mobility

Markov Chains

Towards Temporal Mobility Markov Chains

In [START_REF] Gambs | Show me how you move and i will tell you who you are[END_REF], we defined a type of mobility model that we coined as mobility Markov chain (MMC), which can represent in a compact yet precise way the mobility behaviour of an individual. In short, a MMC is a probabilistic automaton in which states represent points of interest (POIs) of an individual and transitions between states corresponds to a movement from one POI to another one. The automaton is probabilistic in the sense that a transition between POIs is non deterministic but rather that there is a probability distribution over the transitions that corresponds to the probability of moving from one POI to another (edges are directed). Note that Markov models are a popular technique that have been used in the past for the study of motion (for instance see [START_REF] Yan | SeMiTri: A Framework for Semantic Annotation of Heterogeneous Trajectories[END_REF] for a recent work using hidden Markov networks to extract POIs from geolocated data).

More formally, a MMC is a transition system composed of:

• A set of states P = {p 1 , . . . , p n }, in which each state p i corresponds to a POI (or a set of POIs). These POIs may have been learned for instance by running a clustering algorithm on the trail of mobility traces from an individual or simply by collecting the locations that he has posted on a geolocated social network such as Foursquare or Gowalla. Each state (i.e. POI) is therefore associated with a physical location.Moreover, it is often possible to attach a semantic label to the states of the mobility Markov chain, such as for instance "home" instead of simply p 1 or "work" instead of p 2 . • A set of transitions, T = {t 1,1 , . . . , t n,n }, where each transition t i,j represents a movement from the state p i to the state p j . Each transition t i,j has a probability assigned to it that corresponds to the probability of moving from state p i to state p j . Sometimes an individual can move from one POI, go somewhere else (but not to one of his usual POIs) and come back later to the same POI. For example, an individual might leave his house to go wash his car in a facility near his home and come back 30 minutes later. This type of behaviour is materialized in the mobility Markov chain by a transition from one state to itself. A MMC can be represented either as a transition matrix or as a directed graph in which nodes correspond to states and there is a directed weighted edge between two nodes if and only if the transition probability between these two nodes is non-null. The sum of all the edges' weights leaving from a state is equal to 1.

For instance, consider for illustration purpose, an individual, that we refer thereafter as "Alice", who has a set of 4 important POIs that she visits often plus some other POIs that are less important to her mobility. In order to represent her mobility behaviour, we could define a MMC composed of 5 states, one for each important POI plus a last one that will contain all the infrequent POIs. Suppose now that we have been able to collect her trail of mobility traces (e.g., by tracking her mobile phone [START_REF] Killijian | Beyond san francisco cabs : Building a *-lity mining dataset[END_REF]), then possibly we could have learnt the following MMC (Figure 1). For more details, about MMC we refer the reader to [START_REF] Gambs | Show me how you move and i will tell you who you are[END_REF].

II. INTRODUCING TIME INTO MOBILITY MARKOV CHAINS

In this section, we describe an algorithm for learning Temporal Mobility Markov Chains (TMMC). This algorithm is an extension of the one described in [START_REF] Gambs | Show me how you move and i will tell you who you are[END_REF] to which we add the temporal aspect. Basically, the gist of this algorithm is to decompose time into n different discrete timeslices. For example, with n = 4, we can observe mobility in one of the following timeslices: morning, afternoon, evening and night. Each POI from the original MMC will thus be represented by n different states in the TMMC, one for each timeslice. end if 13: end for 14: Sort the clusters in f reqP OIs by decreasing order according to their densities 15: for each cluster C i in f reqP OIs (for end if 29: end for 30: Squash all the successive mobility traces sharing the same (time and space) label into a single occurrence 31: Compute all the transition probabilities between each pair of states of the Markov chain 32: return the mobility Markov chain computed take Alice's home for example, which is state p 1 on Figure 1., it will be represented by the states P 1morning , P 1af ternoon , P 1evening and P 1night . Remark that the scale of the timeslicing can be tuned to match the required level of detail. For example, the timeslices can also be winter, spring, summer, autumn or even months or years, . . . In a nutshell, Algorithm 1 starts (line 1) by applying a clustering algorithm on a trail of traces of an individual in order to identify clusters of locations that are significant. Then, in order to reduce the number of resulting clusters, the algorithm merges clusters whose medoids are within a predefined distance d of each other (line 2). Each resulting cluster is considered as a POI, and the medoid of the cluster is considered to be the physical location of the POI. For each cluster (lines 4 to 6), we compute the number of mobility traces inside the cluster (which we call the density of the cluster) and the time interval (measured in days) between the earliest and the latest mobility traces of the cluster (line 5). The POIs (i.e. clusters) are then split (lines 7 to 13) into two categories; the frequent POIs that correspond to POIs whose time interval is above or equal to a certain threshold mintime and the infrequent POIs whose time interval is below this threshold mintime. In the set of frequent POIs (line 14), we sort the POIs by decreasing order according to their densities. Therefore, the first POI will be the denser and the last POI the less dense. Now, we can start to build the temporal mobility Markov chain by creating a state for each tuple < P OI, timeslice > within the set of frequent POIs (lines 15 to 19) and also a last state representing the set of infrequent POIs (line 20). Each state is then assigned a weight that is set to its density. Afterwards (line 21), we come back to the trail of traces that have been used to learn the POIs and we remove all the moving points (whose speed is above , for a small predefined value). Then, we traverse the trail of traces in a chronological order (lines 22 to 29) labeling each of the mobility traces either with the tag of closest POI and the appropriate timeslice (line 25) or with the tag "unknown" if the mobility trace is not within d-distance of one of the frequent or infrequent POIs (line 27). From this labeling, we can extract sequences spatio-temporal chunks that have been visited by the individual in which all the successive mobility traces sharing the same label are merged into a single occurrence (line 30). For example, a typical day could be summarized by the following sequence "p home/morning ⇒ p work/morning ⇒ p work/af ternoon ⇒ p sport/af ternoon ⇒ p sport/evening ⇒ "unknown ⇒ p home/evening ". From the set of sequences extracted, we compute the transition probabilities between the different states of the MMC by counting the number of transitions between each pair of states and then normalizing these probabilities (line 31). If we observe a subsequence in the form of "p i/t ⇒ "unknown" ⇒ p i/t " then we increment the count from the state p i/t to itself (which translates in the graph representation by a self-arrow).

1 ≤ i ≤ n -1)

Fig. 1 .

 1 Fig. 1. Alice's Mobility Markov Chain.

If we Algorithm 1

 1 Temporal mobility Markov chain algorithm Require: Trail of (mobility) traces M , merging distance d, speed threshold , time interval threshold mintime, time slices definition timeslices 1: Run a clustering algorithm on M to learn the most significant clusters 2: Merge all the clusters that are within d distance of each other 3: Let listP OIs be the list of all remaining clusters 4: for each cluster C in listP OIs do 5: Compute the time interval and the density of C 6: end for 7: for each cluster C in listP OIs do 8: if C.time interval > mintime then 9: Add C to f reqP OIs (the list of frequent POIs) C to inf reqP OIs (the list of infrequent POIs) 12:

  do Create a state p inf requent representing all the clusters within inf reqP OIs 21: Let M be the trail of traces obtained from M by removing all the traces whose speed is above 22: for each mobility trace in M do 23:if the distance between the trace and the state p i is less than d and the state p i is the closest state then

	16:	for each time slice t in timeslices do
	17:	Create a state p i/t in the mobility Markov chain
	18:	end for
	19: end for
	20: 24:	determine t the appropriate time slice for the trace
	25:	label the trace with "p i/t "
	26:	else
	27:	label the state with the value "unknown"
	28: