Arnaud Marsiglietti
email: arnaud.marsiglietti@ima.umn.edu

A note on an L p -Brunn-Minkowski inequality for convex measures in the unconditional case

Keywords: Brunn-Minkowski-Firey theory, L p -Minkowski combination, convex body, convex measure, (B)-conjecture

We consider a different L p -Minkowski combination of compact sets in R n than the one introduced by Firey and we prove an L p -Brunn-Minkowski inequality, p ∈ [0, 1], for a general class of measures called convex measures that includes log-concave measures, under unconditional assumptions. As a consequence, we derive concavity properties of the function t → µ(t 1 p A), p ∈ (0, 1], for unconditional convex measures µ and unconditional convex body A in R n . We also prove that the (B)-conjecture for all uniform measures is equivalent to the (B)conjecture for all log-concave measures, completing recent works by Saroglou.

Introduction

The Brunn-Minkowski inequality is a fundamental inequality in Mathematics, which states that for every convex subset A, B ⊂ R n and for every λ ∈ [0, 1], one has

|(1 -λ)A + λB| 1 n ≥ (1 -λ)|A| 1 n + λ|B| 1 n , (1)
where

A + B = {a + b; a ∈ A, b ∈ B}
denotes the Minkowski sum of A and B and where | • | denotes the Lebesgue measure. The book by Schneider [START_REF] Saroglou | Remarks on the conjectured log-Brunn-Minkowski inequality[END_REF] and the survey by Gardner [START_REF] Gardner | The Brunn-Minkowski inequality[END_REF] famously reference the Brunn-Minkowski inequality and its consequences.

Several extensions of the Brunn-Minkowski inequality have been developed during the last decades by establishing functional versions (see e.g. [START_REF] Henstock | On the measure of sum-sets. I. The theorems of Brunn, Minkowski, and Lusternik[END_REF], [START_REF] Dubuc | Critères de convexité et inégalités intégrales[END_REF], [START_REF] Dancs | On a class of integral inequalities and their measuretheoretic consequences[END_REF], [START_REF] Uhrin | Curvilinear extensions of the Brunn-Minkowski-Lusternik inequality[END_REF]), by considering different measures (see e.g. [START_REF] Borell | Convex measures on locally convex spaces[END_REF], [START_REF] Borell | Convex set functions in d-space[END_REF]), by generalizing the Minkowski sum (see e.g. [START_REF] Firey | Mean cross-section measures of harmonic means of convex bodies[END_REF], [START_REF] Firey | p-means of convex bodies[END_REF], [START_REF] Firey | Some applications of means of convex bodies[END_REF], [START_REF] Lutwak | The Brunn-Minkowski-Firey theory. I. Mixed volumes and the Minkowski problem[END_REF], [START_REF] Lutwak | The Brunn-Minkowski-Firey theory. II. Affine and geominimal surface areas[END_REF]), among others.

In this paper, we will combine these extensions to prove an L p -Brunn-Minkowski inequality for a large class of measures, including the log-concave measures.

Firstly, let us consider measures other than the Lebesgue measure. Following Borell [START_REF] Borell | Convex measures on locally convex spaces[END_REF], [START_REF] Borell | Convex set functions in d-space[END_REF], we say that a Borel measure µ in R n is s-concave, s ∈ [-∞, +∞], if the inequality µ((1 -λ)A + λB) ≥ M λ s (µ(A), µ(B))

holds for every λ ∈ [0, 1] and for every compact subset A, B ⊂ R n such that µ(A)µ(B) > 0, where M λ s (a, b) denotes the s-mean of the non-negative real numbers a, b with weight λ, defined as

M λ s (a, b) = ((1 -λ)a s + λb s ) 1 s if s / ∈ {-∞, 0, +∞}, M λ -∞ (a, b) = min(a, b), M λ 0 (a, b) = a 1-λ b λ , M λ +∞ (a, b) = max(a, b).
Hence the Brunn-Minkowski inequality tells us that the Lebesgue measure in R n is

1 n -concave.
As a consequence of the Hölder inequality, one has M λ p (a, b) ≤ M λ q (a, b) for every p ≤ q. Thus every s-concave measure is -∞-concave. The -∞concave measures are also called convex measures.

For s ≤ 1 n , Borell showed that every measure µ, which is absolutely continuous with respect to the n-dimensional Lebesgue measure, is s-concave if and only if its density is an α-concave function, with

α = s 1 -sn ∈ [- 1 n , +∞], (2)
where a function f :

R n → R + is said to be α-concave, with α ∈ [-∞, +∞], if the inequality f ((1 -λ)x + λy) ≥ M λ α (f (x), f (y))
holds for every x, y ∈ R n such that f (x)f (y) > 0 and for every λ ∈ [0, 1].

Secondly, let us consider a generalization of the notion of the Minkowski sum introduced by Firey, which leads to an L p -Brunn-Minkowski theory. For convex bodies A and B in R n (i.e. compact convex sets containing the origin in the interior), the L p -Minkowski combination, p ∈ [-∞, +∞], of A and B with weight λ ∈ [0, 1] is defined by

(1 -λ) • A ⊕ p λ • B = {x ∈ R n ; x, u ≤ M λ p (h A (u), h B (u)), ∀u ∈ S n-1 },
where h A denotes the support function of A defined by

h A (u) = max x∈A x, u , u ∈ S n-1 .
Notice that for every p ≤ q,

(1 -λ) • A ⊕ p λ • B ⊂ (1 -λ) • A ⊕ q λ • B.
The support function is an important tool in Convex Geometry, having the property to determine a convex body and to be linear with respect to Minkowski sum and dilation:

A = {x ∈ R n ; x, u ≤ h A (u), ∀u ∈ S n-1 }, h A+B = h A +h B , h µA = µh A ,
for every convex body A, B in R n and every scalar µ ≥ 0. Thus,

(1 -λ) • A ⊕ 1 λ • B = (1 -λ)A + λB.
In this paper, we consider a different L p -Minkowski combination. Before giving the definition, let us recall that a function f :

R n → R is unconditional if there exists a basis (a 1 , • • • , a n ) of R n (the canonical ba- sis in the sequel) such that for every x = n i=1 x i a i ∈ R n and for ev- ery ε = (ε 1 , • • • , ε n ) ∈ {-1, 1} n , one has f ( n i=1 ε i x i a i ) = f (x). For p = (p 1 , • • • , p n ) ∈ [-∞, +∞] n , a = (a 1 , • • • , a n ) ∈ (R + ) n , b = (b 1 , • • • , b n ) ∈ (R + ) n and λ ∈ [0, 1], let us denote (1 -λ)a + p λb = (M λ p 1 (a 1 , b 1 ), • • • , M λ pn (a n , b n )) ∈ (R + ) n .
For non-empty subsets A, B ⊂ R n , for p ∈ [-∞, +∞] n and for λ ∈ [0, 1], we define the L p -Minkowski combination of A and B with weight λ, denoted by (1 -λ) • A + p λ • B, to be the unconditional subset (i.e. the indicator function is unconditional) such that

((1-λ)•A+ p λ•B)∩(R + ) n = {(1-λ)a+ p λb ; a ∈ A∩(R + ) n , b ∈ B ∩(R + ) n }.
This definition is consistent with the well known fact that an unconditional set (or function) is entirely determined on the positive octant (R + ) n . Moreover, this L p -Minkowski combination coincides with the classical Minkowski sum when p = (1, • • • , 1) and A, B are unconditional convex subsets of R n (see Proposition 2.1 below).

Using an extension of the Brunn-Minkowski inequality discovered by Uhrin [START_REF] Uhrin | Curvilinear extensions of the Brunn-Minkowski-Lusternik inequality[END_REF], we prove the following result:

Theorem 1.1. Let p = (p 1 , • • • , p n ) ∈ [0, 1] n and let α ∈ R such that α ≥ - n i=1 p -1 i -1
. Let µ be an unconditional measure in R n that has an α-concave density function with respect to the Lebesgue measure. Then, for every unconditional convex body A, B in R n and for every λ ∈ [0, 1],

µ((1 -λ) • A + p λ • B) ≥ M λ γ (µ(A), µ(B)), (3)
where γ =

n i=1 p -1 i + α -1 -1 .
The case of the Lebesgue measure and p = (0, • • • , 0) is treated by Saroglou [START_REF] Saroglou | Remarks on the conjectured log-Brunn-Minkowski inequality[END_REF], answering a conjecture by Böröczky, Lutwak, Yang and Zhang [START_REF] Böröczky | The log-Brunn-Minkowski inequality[END_REF] in the unconditional case.

Conjecture 1.2 (log-Brunn-Minkowski inequality [START_REF] Böröczky | The log-Brunn-Minkowski inequality[END_REF]). Let A, B be symmetric convex bodies in R n and let λ ∈ [0, 1]. Then,

|(1 -λ) • A ⊕ 0 λ • B| ≥ |A| 1-λ |B| λ . (4)
Useful links have been discovered by Saroglou [START_REF] Saroglou | Remarks on the conjectured log-Brunn-Minkowski inequality[END_REF], [START_REF] Saroglou | More on logarithmic sums of convex bodies[END_REF] between Conjecture 1.2 and the (B)-conjecture.

Conjecture 1.3 ((B)-conjecture [START_REF] Latała | On some inequalities for Gaussian measures[END_REF], [START_REF] Cordero-Erausquin | The (B) conjecture for the Gaussian measure of dilates of symmetric convex sets and related problems[END_REF]). Let µ be a symmetric log-concave measure in R n and let A be a symmetric convex subset of R n . Then the function t → µ(e t A) is log-concave on R.

The (B)-conjecture was solved by Cordero-Erausquin, Fradelizi and Maurey [START_REF] Cordero-Erausquin | The (B) conjecture for the Gaussian measure of dilates of symmetric convex sets and related problems[END_REF] for the Gaussian measure and for the unconditional case. As a variant of the (B)-conjecture, one may study concavity properties of the function t → µ(V (t)A) where V : R → R + is a convex function. As a consequence of Theorem 1.1, we deduce concavity properties of the function t → µ(t

1 p A), p ∈ (0, 1]
, for every unconditional s-concave measure µ and every unconditional convex body A in R n (see Proposition 2.4 below).

Saroglou [START_REF] Saroglou | More on logarithmic sums of convex bodies[END_REF] also proved that the log-Brunn-Minkowski inequality for the Lebesgue measure (inequality (4)) is equivalent to the log-Brunn-Minkowski inequality for all log-concave measures. We continue these kinds of equivalences by proving that the (B)-conjecture for all uniform measures is equivalent to the (B)-conjecture for all log-concave measures (see Proposition 3.1 below).

We also investigate functional versions of the (B)-conjecture, which may be read as follows:

Conjecture 1.4 (Functional version of the (B)-conjecture). Let f, g : R n → R + be even log-concave functions. Then the function

t → R n f (e -t x)g(x) dx is log-concave on R. We prove that Conjecture 1.4 is equivalent to Conjecture 1.3 (see Propo- sition 3.2 below).
Let us note that other developments in the use of the earlier mentioned extensions of the Brunn-Minkowski inequality have been recently made as well (see e.g. [START_REF] Bobkov | Quermassintegrals of quasi-concave functions and generalized Prékopa-Leindler inequalities[END_REF], [START_REF] Caglar | Divergence for s-concave and log concave functions[END_REF], [START_REF] Caglar | Functional versions of L p -affine surface area and entropy inequalities[END_REF], [START_REF] Gardner | The Orlicz-Brunn-Minkowski theory: A general framework, additions, and inequalities[END_REF]).

The rest of the paper is organized as follows: In the next section, we prove Theorem 1.1 and we extend it to m sets, m ≥ 2. We also compare our L p -Minkowski combination to the Firey combination and derive an L p -Brunn-Minkowski inequality for the Firey combination. We then discuss the consequences of a variant of the (B)-conjecture, namely we deduce concavity properties of the function t → µ(t 1 p A), p ∈ (0, 1]. In Section 3, we prove that the (B)-conjecture for all uniform measures is equivalent to the (B)conjecture for all log-concave measures, and we also prove that the (B)conjecture is equivalent to its functional version Conjecture 1.4.

(1 -λ) • A + 1 λ • B = (1 -λ)A + λB, where 1 = (1, • • • , 1). Proof. Since the sets (1 -λ) • A + 1 λ • B and (1 -λ)A + λB are unconditional, it is sufficient to prove that ((1 -λ) • A + 1 λ • B) ∩ (R + ) n = ((1 -λ)A + λB) ∩ (R + ) n . Let x ∈ ((1 -λ)A + λB) ∩ (R + ) n . There exists a = (a 1 , • • • , a n ) ∈ A and b = (b 1 , • • • , b n ) ∈ B such that x = (1-λ)a+λb and for every i ∈ {1, • • • , n}, (1-λ)a i +λb i ∈ R + . Let ε, η ∈ {-1, 1} n such that (ε 1 a 1 , • • • , ε n a n ) ∈ (R + ) n and (η 1 b 1 , • • • , η n b n ) ∈ (R + ) n . Notice that for every i ∈ {1, • • • , n}, 0 ≤ (1 -λ)a i + λb i ≤ (1 -λ)ε i a i + λη i b i . Since the sets A and B are convex and unconditional, it follows that x ∈ (1 -λ)(A ∩ (R + ) n ) + λ(B ∩ (R + ) n ) = ((1 -λ) • A + 1 λ • B) ∩ (R + ) n .
The other inclusion is clear due to the definition of the set

(1 -λ) • A + 1 λ • B. Proof of Theorem 1.1. Let λ ∈ [0, 1] and let A, B be unconditional convex bodies in R n .
It has been shown by Uhrin [24] that if f, g, h : (R + ) n → R + are bounded measurable functions such that for every x, y

∈ (R + ) n , h((1 -λ)x + p λy) ≥ M λ α (f (x), g(y)), then (R + ) n h(x) dx ≥ M λ γ (R + ) n f (x) dx, (R + ) n g(x) dx , where γ = n i=1 p -1 i + α -1 -1 .
Let us denote by φ the density function of µ and let us set h = 1 (1-λ)•A+pλ•B φ, f = 1 A φ and g = 1 B φ. By assumption, the function φ is unconditional and α-concave, hence φ is non-increasing in each coordinate on the octant (R + ) n . Then for every x, y ∈ (R + ) n , one has

φ((1 -λ)x + p λy) ≥ φ((1 -λ)x + λy) ≥ M λ α (φ(x), φ(y)). Hence, h((1 -λ)x + p λy) ≥ M λ α (f (x), g(y)
). Thus we may apply the result mentioned at the beginning of the proof to obtain that

(R + ) n h(x) dx ≥ M λ γ (R + ) n f (x) dx, (R + ) n g(x) dx , where γ = n i=1 p -1 i + α -1 -1 .
In other words, one has

µ(((1 -λ) • A + p λ • B) ∩ (R + ) n ) ≥ M λ γ (µ(A ∩ (R + ) n ), µ(B ∩ (R + ) n )).
Since the sets (1 -λ)

• A + p λ • B, A and B are unconditional, it follows that µ((1 -λ) • A + p λ • B) ≥ M λ γ (µ(A), µ(B)).
Remark. One may similarly define the L p -Minkowski combination

λ 1 • A 1 + p • • • + p λ m • A m , for m convex bodies A 1 , . . . , A m ⊂ R n , m ≥ 2, where λ 1 , . . . , λ m ∈ [0, 1] are such that m i=1 λ i = 1
, by extending the definition of the p-mean M λ p to m non-negative numbers. By induction, one has under the same assumptions of Theorem 1.1 that

µ(λ 1 • A 1 + p • • • + p λ m • A m ) ≥ M λ γ (µ(A 1 ), • • • , µ(A m )), (5)
where γ = n i=1 p -1 i + α -1 -1 . Indeed, let m ≥ 2 and let us assume that inequality (5) holds. Notice that

λ 1 • A 1 + p • • • + p λ m • A m + p λ m+1 • A m+1 = m i=1 λ i • A + p λ m+1 • A m+1 ,
where

A := λ 1 m i=1 λ i • A 1 + p • • • + p λ m m i=1 λ i • A m .
Thus,

µ m i=1 λ i • A + p λ m+1 • A m+1 ≥ m i=1 λ i µ( A) γ + λ m+1 µ(A m+1 ) γ 1 γ ≥ m+1 i=1 λ i µ(A i ) γ 1 γ
.

Consequences

The following result compares the L p -Minkowski combinations ⊕ p and + p .

Lemma 2.2. Let p ∈ [0, 1] and set p = (p, • • • , p) ∈ [0, 1] n .
For every unconditional convex body A, B in R n and for every λ ∈ [0, 1], one has

(1 -λ) • A ⊕ p λ • B ⊃ (1 -λ) • A + p λ • B.
Proof. The case p = 0 is proved in [START_REF] Saroglou | Remarks on the conjectured log-Brunn-Minkowski inequality[END_REF]. Let p = 0. Since the sets

(1 -λ) • A ⊕ p λ • B and (1 -λ) • A + p λ • B are unconditional, it is sufficient to prove that ((1 -λ) • A ⊕ p λ • B) ∩ (R + ) n ⊃ ((1 -λ) • A + p λ • B) ∩ (R + ) n . Let u ∈ S n-1 ∩ (R + ) n and let x ∈ ((1 -λ) • A + p λ • B) ∩ (R + ) n . One has, x, u = n i=1 ((1 -λ)a p i + λb p i ) 1 p u i = n i=1 ((1 -λ)(a i u i ) p + λ(b i u i ) p ) 1 p = (1 -λ)X + λY 1 p 1 p
, where X = ((a

1 u 1 ) p , • • • , (a n u n ) p ) and Y = ((b 1 u 1 ) p , • • • , (b n u n ) p ). Notice that X 1 p ≤ h A (u) p , Y 1 p ≤ h B (u) p and that • 1 p is a norm. It follows that x, u ≤ (1 -λ) X 1 p + λ Y 1 p 1 p ≤ ((1 -λ)h A (u) p + λh B (u) p ) 1 p . Hence, x ∈ ((1 -λ) • A ⊕ p λ • B) ∩ (R + ) n .
From Lemma 2.2 and Theorem 1.1, one obtains the following result:

Corollary 2.3. Let p ∈ [0, 1].
Let µ be an unconditional measure in R n that has an α-concave density function, with α ≥ -p n . Then for every unconditional convex body A, B in R n and for every λ ∈ [0, 1],

µ((1 -λ) • A ⊕ p λ • B) ≥ M λ γ (µ(A), µ(B)), (6)
where

γ = n p + 1 α -1 .
Remarks.

1. By taking α = 0 in Corollary 2.3 (corresponding to log-concave measures), one obtains

µ((1 -λ) • A ⊕ 0 λ • B) ≥ µ(A) 1-λ µ(B) λ .
2. By taking α = +∞ in Corollary 2.3 (corresponding to 1 n -concave measures), one obtains that for every p ∈ [0, 1],

µ((1 -λ) • A ⊕ p λ • B) p n ≥ (1 -λ)µ(A) p n + λµ(B) p n .
Equivalently, for every p ∈ [0, 1], for every unconditional convex body A, B in R n and for every unconditional convex set

K ⊂ R n , |((1 -λ) • A ⊕ p λ • B) ∩ K| p n ≥ (1 -λ)|A ∩ K| p n + λ|B ∩ K| p n .
Let us recall that the function t → µ(e t A) is log-concave on R for every unconditional log-concave measure µ and every unconditional convex body A in R n (see [START_REF] Cordero-Erausquin | The (B) conjecture for the Gaussian measure of dilates of symmetric convex sets and related problems[END_REF]). By adapting the argument of [START_REF] Marsiglietti | On the improvement of concavity of convex measures[END_REF], Proof of Proposition 3.1 (see Proof of Corollary 2.5 below), it follows that the function t → µ(t

1 p A) is p
n -concave on R + , for every p ∈ (0, 1], for every unconditional s-concave measure µ, with s ≥ 0, and for every unconditional convex body A in R n . However, no concavity properties are known for the function t → µ(e t A) when µ is an s-concave measure with s < 0. Instead, for these measures we prove concavity properties of the function t → µ(t

1 p A).
Proposition 2.4. Let p ∈ (0, 1], let µ be an unconditional measure that has an α-concave density function, with α ∈ [-p n , 0) and let A be an unconditional convex body in R n . Then the function t → µ(t

1 p A) is n p + 1 α -1 - concave on R + .
Proof. Let t 1 , t 2 ∈ R + . By applying Corollary 2.3 to the sets t

1 p 1 A and t 1 p 2 A, one obtains µ(((1 -λ)t 1 + λt 2 ) 1 p A) = µ((1 -λ) • t 1 p 1 A ⊕ p λ • t 1 p 2 A) ≥ M λ γ (µ(t 1 p 1 A), µ(t 1 p 2 A))
,

where γ = n p + 1 α -1
. Hence the function t → µ(t

1 p A) is γ-concave on R + .
As a consequence, we derive concavity properties for the function t → µ(tA).

Corollary 2.5. Let p ∈ (0, 1], let µ be an unconditional measure that has an α-concave density function, with α ∈ [-p n , 0), and let A be an unconditional convex body in R n . Then the function t → µ(tA) is 1-p n + γ -concave on

R + , where γ = n p + 1 α -1
.

Proof. We adapt [START_REF] Marsiglietti | On the improvement of concavity of convex measures[END_REF], Proof of Proposition 3.1. Let us denote by φ the density function of the measure µ and let us denote by F the function t → µ(tA). From Proposition 2.4, the function t → F (t

1 p
) is γ-concave, hence the right derivative of F , denoted by F ′ + , exists everywhere and the function t

→ 1 p t 1 p -1 F ′ + (t 1 p )F (t 1 p ) γ-1 is non-increasing. Notice that F (t) = t n A φ(tx) dx,
and that t → φ(tx) is non-increasing, thus the function t

→ 1 t 1-p F (t) 1-p n is non-increasing. Since F ′ + (t)F (t) 1-p n +γ-1 = t 1-p F ′ + (t)F (t) γ-1 • 1 t 1-p F (t) 1-p n , it follows that F ′ + (t)F (t)
1-p n +γ-1 is non-increasing as the product of two non-negative non-increasing functions. Hence F is 1-p n + γ -concave.

Remark. For every s-concave measure µ and every convex subset A ⊂ R n , the function t → µ(tA) is s-concave. Hence Corollary 2.5 is of value only if

1-p n + γ ≥ α 1+αn (see relation (2)
). Notice that this condition is satisfied if α ≥ -p n(1+p) . We thus obtain the following corollary:

Corollary 2.6. Let p ∈ (0, 1], let µ be an unconditional measure that has an α-concave density function, withp n(1+p) ≤ α < 0 and let K be an unconditional convex body in R n . Then, for every subsets A, B ∈ {µK; µ > 0} and every λ ∈ [0, 1], one has

µ((1 -λ)A + λB) ≥ M λ 1-p n +γ (µ(A), µ(B)), where γ = n p + 1 α -1
.

In [START_REF] Marsiglietti | On the improvement of concavity of convex measures[END_REF], the author investigated improvements of concavity properties of convex measures under additional assumptions, such as symmetries. Notice that Corollary 2.6 follows the same path and completes the results that can be found in [START_REF] Marsiglietti | On the improvement of concavity of convex measures[END_REF]. Let us conclude this section by the following remark, which concerns the question of the improvement of concavity properties of convex measures.

Remark. Let µ be a Borel measure that has a density function with respect to the Lebesgue measure in R n . One may write the density function of µ in the form e -V , where V : R n → R is a measurable function. Let us assume that V is C 2 . Let γ ∈ R\{0}. The function e -V is γ-concave if Hess(γe -γV ), the Hessian of γe -γV , is non-positive (in the sense of symmetric matrices). One has

Hess(γe -γV ) = -γ 2 ∇ • (∇V e -γV ) = γ 2 e -V (γ∇V ⊗ ∇V -Hess(V )),
where ∇V ⊗ ∇V = ∂V ∂x i ∂V ∂x j 1≤i,j≤n . Hence the matrix Hess(γe -γV ) is nonpositive if and only if the matrix γ∇V ⊗ ∇V -Hess(V ) is non-positive.

Let us apply this remark to the Gaussian measure

dγ n (x) = 1 (2π) n 2 e -|x| 2 2 dx, x ∈ R n .
Here V (x) = |x| 2 2 +c n , where c n = n 2 log(2π). Thus, ∇V ⊗∇V = (x i x j ) 1≤i,j≤n and Hess(V ) = Id the Identity matrix. Notice that the eigenvalues of γ∇V ⊗ ∇V -Hess(V ) are -1 (with multiplicity (n -1)) and γ|x| 2 -1. Hence if γ|x| 2 -1 ≤ 0, then γ∇V ⊗ ∇V -Hess(V ) is non-positive. One deduces that for every γ > 0, for every compact sets A, B ⊂ 1 √ γ B n 2 and for every λ ∈ [0, 1], one has

γ n ((1 -λ)A + λB) ≥ M λ γ 1+γn (γ n (A), γ n (B)), (7)
where B n 2 denotes the Euclidean closed unit ball in R n . Since the Gaussian measure is a log-concave measure, inequality [START_REF] Caglar | Functional versions of L p -affine surface area and entropy inequalities[END_REF] is an improvement of the concavity of the Gaussian measure when restricted to compact sets A, B ⊂ 1 √ γ B n 2 .

Equivalence between (B)-conjecture-type problems

In the following proposition, we demonstrate that it is sufficient to prove the (B)-conjecture for all uniform measures in R n , for every n ∈ N * , to obtain the (B)-conjecture for all symmetric log-concave measures in R n , for every n ∈ N * . This completes recent works by Saroglou [START_REF] Saroglou | Remarks on the conjectured log-Brunn-Minkowski inequality[END_REF], [START_REF] Saroglou | More on logarithmic sums of convex bodies[END_REF].

In the following, we say that a measure µ satisfies the (B)-property if the function t → µ(e t A) is log-concave on R for every symmetric convex set A ⊂ R n . Proposition 3.1. If every symmetric uniform measure in R n , for every n ∈ N * , satisfies the (B)-property, then every symmetric log-concave measure in R n , for every n ∈ N * , satisfies the (B)-property.

Proof. The proof is inspired by [START_REF] Artstein-Avidan | The Santaló point of a function, and a functional form of the Santaló inequality[END_REF], beginning of Section 3.

Step 1: Stability under orthogonal projection Let us show that the (B)-property is stable under orthogonal projection onto an arbitrary subspace.

Let F be a k-dimensional subspace of R n . Let us define for every compactly supported measure µ in R n and every measurable subset A ⊂ F ,

Π F µ(A) := µ(Π -1 F (A)),
where Π F denotes the orthogonal projection onto F and Π -1

F (A) := {x ∈ R n ; Π F (x) ∈ A}.
Notice that Π -1 F (e t A) = e t (A × F ⊥ ), where F ⊥ denotes the orthogonal complement of F . Hence if µ satisfies the (B)-property, then Π F µ satisfies the (B)-property.

Step 2: Approximation of log-concave measures Let us show that for every compactly supported log-concave measure µ in R n there exists a sequence (K p ) p∈N * of convex subsets of R n+p such that lim p→+∞ Π R n µ Kp = µ in the sense that the density function of µ is the pointwise limit of the density functions of (µ Kp ) p∈N * , where µ Kp denotes the uniform measure on K p (up to a constant).

Let µ be a compactly supported log-concave measure in R n with density function f = e -V , where V : R n → R ∪ {+∞} is a convex function. Notice that for every x ∈ R n , e -V (x) = lim p→+∞ (1 -V (x) p ) p + , where for every a ∈ R, a + = max(a, 0). Let us define for every p ∈ N * ,

K p = {(x, y) ∈ R n × R p ; |y| ≤ 1 - V (x) p + }.
One has for every x ∈ R n , 1 -V (x) p Notice that K p is a symmetric convex subset of R n+p . The change of variable x = e -t x and y = e -t y leads to G p (t) = e t(n+p) v p µ p (e -t K p ), where µ p is the measure with density function h(x, y) = f (x)1 R p (y), (x, y) ∈ R n × R p .

Since a pointwise limit of log-concave functions is log-concave, we conclude that the function G is log-concave on R as the pointwise limit of the logconcave functions G p , p ∈ N * .

Recall that the (B)-conjecture holds true for the Gaussian measure and for the unconditional case (see [START_REF] Cordero-Erausquin | The (B) conjecture for the Gaussian measure of dilates of symmetric convex sets and related problems[END_REF]). It follows from Proposition 3.2 that Conjecture 1.4 holds true if one function is the density function of the Gaussian measure or if both functions are unconditional.

2

  Proof of Theorem 1.1 and consequences 2.1 Proof of Theorem 1.1 Before proving Theorem 1.1, let us show that our L p -Minkowski combination coincides with the classical Minkowski sum when p = (1, • • • , 1), for unconditional convex sets. Proposition 2.1. Let A, B be unconditional convex subsets of R n and let λ ∈ [0, 1]. Then,

v p R p 1 v p 1

 11 Kp (x, y) dy, the last inequality follows from an integration in polar coordinates, where v p denotes the volume of the Euclidean closed unit ball in R p . By denoting µ Kp the measure in R n+p with density function1 Kp (x, y), (x, y) ∈ R n × R p , where K p := {(x, y) ∈ R n × R p ; |y| ≤ 1 -V (x) p +} and where v p denotes the volume of the Euclidean closed unit ball in R p . Hence,G p (t) = 1 v p Kpf (e -t x)1 R p (y) dx dy.

This research was supported in part by the Institute for Mathematics and its Applications with funds provided by the National Science Foundation.

it follows that for every p ∈ N * , the measure Π R n µ Kp has density function

We conclude that lim p→+∞ Π R n µ Kp = µ.

Step 3: Conclusion Let n ∈ N * and let µ be a symmetric log-concave measure in R n . By approximation, one can assume that µ is compactly supported. Since µ is symmetric, the sequence (K p ) p∈N * defined in Step 2 is a sequence of symmetric convex subsets of R n+p . If we assume that the (B)-property holds for all uniform measures in R m , for every m ∈ N * , then for every p ∈ N * , µ Kp satisfies the (B)-property. It follows from Step 1 that for every p ∈ N * , Π R n µ Kp satisfies the (B)-property. Since lim p→+∞ Π R n µ Kp = µ (c.f. Step 2) and since a pointwise limit of log-concave functions is log-concave, we conclude that µ satisfies the (B)-property.

Similarly, let us prove that the functional form of the (B)-conjecture (Conjecture 1.4) is equivalent to the classical (B)-conjecture (Conjecture 1.3). Proposition 3.2. One has equivalence between the following properties:

1. For every n ∈ N * , for every symmetric log-concave measure µ in R n and for every symmetric convex subset A of R n , the function t → µ(e t A) is log-concave on R.

2. For every n ∈ N * , for every even log-concave functions f, g : R n → R + , the function t → R n f (e -t x)g(x) dx is log-concave on R.

Proof. 2. =⇒ 1. This is clear by taking f = 1 A , the indicator function of a symmetric convex set A, and by taking g to be the density function of a log-concave measure µ. 1. =⇒ 2. Let f, g : R n → R + be even log-concave functions. By approximation, one may assume that f and g are compactly supported. Let us write g = e -V , where V : R n → R ∪ {+∞} is an even convex function. One has

where for every a ∈ R, a + = max(a, 0). Let us denote for t ∈ R,

f (e -t x) 1 -V (x) p p + dx.

We have seen in the proof of Proposition 3.1 that


Mathieu Guidère

The Timbuktu Letters : New Insights about AQIM

Al-Qaeda in the Islamic Maghreb (AQIM) is the main terrorist organization in both North Africa and the Sahel. Allied to other local groups, its fighters occupied northern Mali for nearly a year since January 2012, imposing their law on the people. But in January 2013, the French army were successful in expelling them from the area. In their flight, AQIM left behind a number of documents which have cast new light on the inner-workings of the terrorist organization. By cross-checking information found in these unique documents, 1 it is possible to pinpoint AQIM's 'project' for the region and better understand the issues raised during the organization's internal debates.

Relying on the official documents found in Timbuktu after the Jihadists' departure, this article attempts to answer questions about the 'real state' of AQIM just before the French military intervention in Mali. These documents are a collection of letters, written in Arabic, and exchanged between the Advisory Board of AQIM led by Algeria's Abdelmalek Droukdel (a.k.a. Abu Musab Abdelwadud) and the Advisory Board of the Al-Mulathamin Brigade led by Droukdel's fellow citizen, Mokhtar Belmokhtar (a.k.a. Khaled Abu Al-Abbas). Both men are considered veterans of the Jihad as they have been known figures since during the Algerian civil war (1992-2002). In their exchanges, the two men discuss at length the "Jihadist project in the region, its challenges and unresolved issues" and detail their views on "several key issues" including kidnapping and ransom activity, weapons procurement, communications security, and the organization's development plan.

The documents left behind when the Jihadists fled Timbuktu provide ample evidence of disagreements and struggles for supremacy between the two leaders. They illustrate the deep divisions between the different brigades of AQIM, whilst also revealing important aspects of the secret internal functioning of the organization. Below, the key elements of these findings are outlined and discussed.

The Issue of Hostage Management

Kidnapping and ransom became a tool of the Jihadists in North Africa in 2003, when the first major kidnap and ransom operation was conducted by a group led by Amari Saifi, a.k.a. Abderrazak El Para. A former Algerian special forces soldier, El Para engaged

in radical Islam and is currently incarcerated in Algiers.2 At the time, his second-incommand was Abdelhamid Abu Zeid, a rising figure of the GSPC (Salafist Group for Preaching and Combat3 ), who, within a few years, became the head of one of the largest and most active AQIM brigades in the Sahel: the Tariq Ibn Ziyad Brigade. 4 From 2007-2008, just one year after the official creation of AQIM, Abu Zeid was leading the kidnappings of foreigners (particularly Westerners) throughout sub-Saharan Africa. However, he was facing opposition regarding these kidnappings from other Jihadist commanders, particularly from the Al-Mulathamin Brigade's commander: Belmokhtar, Abu Zeid's Algerian compatriot and competitor.

Belmokhtar soon challenged Abu Zeid's strategy and requested arbitration from AQIM's Legal Committee on two key concerns. Firstly, Belmokhtar did not consider kidnapping and ransom to be part of "Jihad" (holy war) since the hostages were generally non-combatants or civilians. Secondly, he believed that such practices would attract unwanted attention from Western countries on emerging Jihadist groups in the Sahel, inevitably turning them into priority targets. He believed that, for these reasons, development of "the Islamist agenda in the region" would be impeded.

After much internal and external debate, Droukdel, head of AQIM, ruled that : First, as for the status of hostages, the Legal Committee considers that any Western citizen is an 'enemy combatant' because Western countries have all declared to be engaged into the 'war on terror' and their political and military actions globally target the Islamist and Jihadist groups. In addition, the head of AQIM is of the opinion that, since the democratic system prevailing in the West makes the elected president the supreme commander of the armed forces, any adult Western citizen supports in principle, by his vote, the policy of the government of his country, and he is therefore responsible and accountable for this policy in the Middle-East, whether he likes it or not.

Second, as for the status of kidnapping, the Legal Committee of AQIM believes, based on various Quranic verses and prophetic traditions, that all actions that aim to defend or extend Islam are legitimate "Jihad" actions. Consequently, kidnapping is admissible practice under the condition that it be subject to the "Law of War in Islam", especially regarding the treatment of "prisoners of war" (hostages) and the modalities of their liberation or execution (following the internal theology of the organization).

Third, as for the reaction of Western countries, AQIM's Advisory Board replies to Belmokhtar that there is no need to fear confrontation when it comes to defending or extending the "domain of Islam". Therefore, if a particular type of action serving Jihadist purposes attracts the attention of Western powers, it must be pursued, not avoided, through fear or political calculation, because the credibility of the Islamist cause is at stake. AQIM sided with Abu Zeid in all of the concerns raised by Belmokhtar and even went on to appoint Abu Zeid as its main representative in the Sahel. As a result, Abu Zeid's star continued to rise in the Jihadist galaxy until his death in February 2013 at the hands of the French military in northern Mali. 5 Belmokhtar never forgave AQIM's command for dismissing his concerns and effectively marginalizing him (for years) in favour of Abu Zeid. As a result, he intensified his efforts to prove his worth by conducting large-scale hostage-taking operations and generally ignored the instructions of AQIM, especially with respect to kidnap and ransom operations.

The leaders of AQIM's Advisory Board, in a letter dated 3 November 2012, strongly reprimanded Belmokhtar for "a particular case". Namely, the liberation of Canadian diplomats Robert Fowler (the UN Secretary General's Special Envoy to Niger) and Louis Gray who were kidnapped in December 2008 west of Niamey and released four months later.

In seemingly angry and ironic terms, the AQIM leaders wrote :

Just for the record about the kidnapping and then the liberation of the Canadians by the Al-Mulathamin Brigade [Belmokhtar]: the organization [AQIM] has paid particular attention to this kidnapping because of the importance of the hostages, one of whom was the personal representative of the Secretary General of the UN. We wanted to give an international dimension to this case, and we tried to coordinate our efforts with the central command of al-Qaeda [Bin Laden]. Unfortunately and to our deep regret, we encountered a major obstacle, that of Khaled Abu al-Abbas [Belmokhtar]. Indeed, instead of following the plan we put in place, he [Belmokhtar] has handled this case in his own way, despite our repeated insistence that this type of actions [kidnap and ransom] is within the exclusive jurisdiction of the central command. Ignoring all that, he chose to bypass the organization and reached an agreement without even taking into account the advice of the Emirate [AQIM]. Without the protection of Allah Almighty and the wisdom of the other emirs in the region, there would have been serious consequences. This raises the question of his incompetence in the management of this important case : isn't the Central Command right when trying to pressure the Crusaders' coalition to ease the pain of our brothers in Afghanistan and get satisfaction for other demands such as the release of imprisoned brothers and a ransom equal to the value of hostages who were worth far more ? Who is incompetent ? We, who wanted to consult and stressed the need for coordination in this type of case, or someone who acted alone, in his corner, as did our brother Khaled [Belmokhtar] ? The obvious incompetence is to have negotiated the release of the most important hostages in the history of AQIM, the Canadian diplomats, at the low price of only 700,000 euros [one million dollars] ! This paragraph is very informative as it details the payment of a ransom by the Canadian government and it provides the exact amount which AQIM received. The use of irony by the leaders of AQIM to refer to the amount of the ransom received by Belmokhtar suggests that countries have paid far higher amounts in the past. For example, in 2010, for the liberation of three Spanish humanitarian hostages, media outlets with sources close to the negotiations cited that the ransom was up to $10 million, meaning the 'price' of each hostage was over three million each. 6 For the French hostages kidnapped by an AQIM commando in Arlit, Niger, in September 2010, the first contacts with the kidnappers put the ransom at 90,000,000€ ($120 million) for six hostages.7 This equates to an average price of approximately $20 million per hostage, and to a rapid escalation in price per hostage in less than a year.

Truly, ransom amounts do fluctuate based on the identity and status of hostages, as well as on the ransom policy of their country of origin. However, it is clear that the amounts paid rapidly inflated between 2008 and 2013 from a few hundred thousand euros per hostage up to several million. There was also a clear focus on kidnapping nationals from countries that were the most willing to paymainly the European countries, in particular France. AQIM has thus identified these nationalities as priority targets.

The Issue of Weapons Procurement

While the issue of kidnapping has focused the attention of AQIM, despite the internal divergent views, money has been the real crux of the matter. The financial resources that are secured are used to buy arms and ammunition for the jihadists' continued fight to the death in holy war. In this regard, with the exception of the 2011 Libyan episode which allowed various Islamist groups to loot Gaddafi's arsenals, most of AQIM's weapons come from purchases on the African black market-the largest in the world due to the many rebellions and conflicts on the continent.8

Until the 2013 French intervention, most of this arms trafficking took place in West Africa and the Sahel, particularly in northern Mali. There, the market was fuelled particularly by dealers from Russia, China, and some formerly Soviet countries in Eastern Europe.

Since its formal establishment in late 2006, AQIM has struggled to obtain arms and explosives due to the relatively effective control exercised by the authoritarian regimes of the Maghreb. In fact, the only viable source of AQIM's armament was through Algeria. There, weapons were stolen from Algerian national arsenals or from the Algerian Army during convoy attacks. However, this sometimes cost the Jihadists a significant number of fighters resulting in AQIM to rely on its subsidiary in the south, the so-called "Emirate of the Sahara." Doubly beneficial, the Jihadists can also take advantage of the relative freedom of movement this immense desert space affords its traffickers.9

In 2007, AQIM designated specific circuits and areas for the purchase and delivery of weapons from the south (Sahel) to the north (Maghreb). So not to arouse suspicions, the organization employed corruption on a large scale. It also adopted tactics of 'relays' and 'caches': some members of the organization were permanently assigned to a place and lived there, among the local population, with the sole job of taking care of the concealment. Other freight intermediaries were engaged in other trades in other regions as well. These include drug trafficking (cocaine from South America) and human trafficking (illegal immigration from sub-Saharan Africa to Europe). This allowed the organization to minimize risks and confused the authorities as to the identity and actual activity of the smugglers.

By 2008, AQIM tightened its control over their funding-raising by imposing a 'shift tax' on any convoy, whatever its cargo, in the territories it controlled. This fee varies from one to ten percent depending on the goods, the identity of the conveyor, the declared destination, and the service requested. Such services include, a simple rite of passage or request for protection against any attacks or banditry (very common in the region).

Another financial administrative shift occurred in 2009 when AQIM decided to allocate a portion of its ransom monies to buy weapons and ammunition. This 'refinancing' can be seen in an accounting report that was left in Timbuktu. Indeed, the system requires allegiance of the vassal (the various heads of brigades of the Sahara) to his 'lord' (the leader of AQIM), which translates into refunding a portion of the resources obtained. For example, each 'emir' of the Sahel paid a sum equivalent to 10 percent (a rate fixed in agreement with the Central Command) of the funds secured in exchange for the release of Western hostages. Once the Central Command is paid, the head of AQIM transfers a share of that tax (about half, in 2010) to the various vassal emirs, so that they can buy weapons and ammunition with the money specifically earmarked for their team by the Central Command. This fiscal agreement set the stage for one of the major arguments between Belmokhtar and Droukdel. Indeed, in a letter dated November 3, 2012, the Advisory Board of the organization writes:

"Just for the record, we recall that the Central Command [of AQIM] has granted brother Abu al-Abbas [Belmokhtar] a large sum of money he requested to buy weapons, in spite of the great need in which the organization was at the time. Despite all this, with hindsight, Abu al-Abbas did not contribute efficiently to the arms purchase activity. He did not do anything despite the presence and anchoring he enjoys in the region, which he can use to play a crucial role in this area [purchasing weapons]. Unlike other Sahel emirs contributing to weapons procurement efficiently and in large quantities, the contribution of Khaled [Belmokhtar] is virtually nonexistent.

The Issue of Communications Security

The Timbuktu letters also showed that AQIM leaders use several modes and means of communication, each with their own advantages and disadvantages.

The first mode of communication favoured by AQIM is the human messenger. Carrying orders or specific information back and forth between local leaders of the organization and the Central Command, this mode has the advantage of safety because the message is not subject to electronic eavesdropping. However, it has several drawbacks: slow transmission of orders and data, risk of capture or death of the messenger, infiltration by intelligence services in the region, or of alteration of the initial message depending on the context of reception.

In a long letter, dated November 3, 2012, sent to the head of the Al-Mulathamin Brigade by the Central Command of AQIM (Droukdel), the latter complains that the head of the brigade (Belmokhtar) was not always available to receive the human messenger that was sent to him and even blames Belmokhtar for deliberately delaying the reception of the orders issued by the organization: "There are countless contacts and meetings to which Abu Al-Abbas [Belmokhtar] was invited to clarify the situation and manage internal affairs, but he always refused to attend, ignoring the orders of his superiors."

The second mode of communication is the satellite telephone. Again, AQIM leaders complain that Belmokhtar can hardly ever be reached on his mobile phone: "Why this lack of communication with the Central Command ? And why is your phone only turned on when you need us, whereas you are permanently available for the media?" Here, it seems that Belmokhtar 'selectively communicates' with his superiors.

The third mode of communication is the Internet (e-mails, chats, etc.), AQIM's extensive use of which Belmokhtar strongly dislikes. In his letter to the Central Command, sent in early September 2012, he wrote :

To protect the secrets of the Mujahideen and our action plans in the region, we believe that these issues should not be discussed or sent via the Internet because they are likely to end up in the hands of the enemy, not to mention the fact that Sheikh Ayman [al-Zawahiri, the successor to Bin Laden and current Al-Qaeda leader] also emphasized this point in his last letter of recommendations.

The AQIM Command's response (page six of November 3, 2012 letter) to this security reminder from subordinate Belmokhtar is scathing :

It is really surprising that those like you who boast about their commitment to protecting the secrets of the Mujahideen by not having confidence in the methods of communication via the internet, should also be the ones who reveal all the secrets of our Jihad to young ignorant people whose identity nobody seems certain about ! Haven't you contacted the Ansar Al-Mujahideen network, urging them to have your own correspondent ? Didn't you tell the network managers of Jihad Net that you were in conflict with the Central Command of the organization ? [...] Is the idea to give yourself the image of a field commander while painting the organization's Central Command as incompetent and lazy ? If we did not have our own contacts, our secrets would have been disclosed long ago ! We attach to this reply amazing snippets of your communications on the Internet.

To drive the nail home, Droukdel derides Belmokhtar's wish to communicate directly with the Central Command of al-Qaeda (Zawahiri), even as he complains about the lack of secure communications within AQIM :

You delude yourself if you imagine that communication with the Central Command of Al-Qaeda will be faster and easier than exchanges with the Regional Command [AQIM] that is in your close vicinity. For your information, since the oath of allegiance [September 2006] and to this day, we have received from our leaders in Afghanistan only few letters signed by Sheikh Osama [Bin Laden, killed in May 2011]may God rest his souland by Sheikh Ayman [al-Zawahiri], may Allah protect him. At the time, we also received few letters of Sheikh Atiyyatullah [number three in Al-Qaeda Central] and Sheikh Abu Yahya [number four in Al-Qaeda Central], may their souls rest in peace [both killed in drone strikes in AFPAK], despite our numerous letters asking them to help us effectively manage the issues of Jihad here. It was in vain.

In short, Belmokhtar complains about the lack of security in various means of communication used in AQIM, while the organization criticizes him for using a pretext to enter into contact directly with Al-Qaeda Central. Reading the entire correspondence, the informed reader comes away with the impression of a dialogue of the deaf and of a lack of mutual trust where each assumes the worst intentions on the other's part.

The Issue of Internal Organization

In September 2012, Belmokhtar wrote to Al-Qaeda Central, justifying his decision to break with AQIM and the founding of his own group : "Signers in Blood".10 He argued that his proposals for structural reforms in the organization "were never taken into account" and gives a historical overview of the implementation of AQIM's objectives in the Sahel, putting into perspective his past and present proposals for restructuring.

First, he mentions that he had always been in favour of a "highly decentralized organization" in terms of control, command and communication. The pyramidal structure of AQIM seems, to him, archaic and unsuited to the political and social organization that prevails in the Sahara. Hence, he calls for a cross-collaboration between brigades and for the elimination of the command's intermediate levels.

In response, AQIM's Advisory Board states :

The answer to the question of centralization versus decentralization in the management of military affairs depends on the spatial and temporal context, on the strength or weakness of the organization, on the possession or otherwise of the appropriate means of communication and coordination. In this case, the decision to review the organizational structure [of AQIM] is due to the decrease in the number of fighters (Mujahideen) in relation to the vast land in the north [of Mali] ; this is a fact. As for the decision to merge the three 'Jihadi regions' [in the Sahara] into one region, it is motivated by the overlapping interests of each and the desire of our brothers in these regions to join this new unique region.

Belmokhtar then challenges the credibility of the members of AQIM's command (located in northern Algeria) in managing their Jihad in the Sahel as they are thousands of miles away from the region and the land is completely unknown to them. In his September 2012 letter, he writes: "Your board gives orders whereas there is no single leader in it who knows this area [the Sahel] or lived here."

To this fundamental critique, AQIM's Advisory Board replied in November that Belmokhtar has been repeatedly invited to serve on the Board but "he has always refused to go to the meetings. And after six years, he just blames his brothers, finding fault with the fact that he was not consulted on matters that he could have challenged by at the time ! ".

Yet despite all of this, the main disagreement seems to lie in the Advisory Board's 2008 decision to authorize the establishment of new Jihadist groups from the north (in Algeria) in the Sahel region (mainly in northern Mali). Due to this, Belmokhtar never accepted the establishment of the Tariq ibn Ziyad Brigade, led by the charismatic Abu Zeid until his death. Abu Zeid was, in fact, close to the leader of AQIM, Abdelmalek Droukdel, and his brigade is thus regarded as Droukdel's creation in the Sahel. Rather than grin and bear it, Belmokhtar preferred to develop an autonomous command in the south.

AQIM's Advisory Board justifies the Sahel appointment of Abu Zeid in a letter thusly :

In this regard, we would like to draw your attention to the fact that the decision confirming the activities of the Tariq ibn Ziyad Brigade in the Sahara cannot be disputed from a legal point of view, nor from a practical one, because it falls within the exclusive jurisdiction of the emir of the organization [Droukdel], especially since it came after extensive consultations and after an analysis of the current situation in the region in general and in the Sahara in particular. Moreover, since its establishment, this brigade has shown its effectiveness, as evidenced by our enemies themselves [...]. Thanks to Allah, it has made great achievements since its entry into the Sahara and has purchased large quantities of weapons, ammunition and military equipment; [Abu Zeid's] brigade has also contributed heavily to revive activity in the field of Jihad, including kidnapping and ransoming activities.

The AQIM Board also addresses Belmokhtar's objection to the proliferation of Jihadist groups in the Sahara, which, from his point of view, is wrongly encouraged by the Central Command of the organization :

As for the number of groups, it is in our opinion the result of a fair and justified decision [...] especially if one takes into account the geographical extent of the area and the diversity of interests it contains. It is unimaginable that a region whose area is equal to that of France and Belgium combined, could become too narrow for four or five Jihadist groups ! Lastly, Belmokhtar has always argued for a direct connection between the "Emirate of the Sahara" and the Central Command of al-Qaeda (Zawahiri) and not to the Regional Command (AQIM and Droukdel) for reasons that are both military and practical. He dwells on this at length in his September 2012 letter. But the allegiance system that Belmokhtar is working in 11 does not allow such direct connection and given the fact that only Zawahiri could possibly unbind the oath (that Belmokhtar made to AQIM), Belmokhtar is prepared to do anything to get Zawahiri's approval for his project.

An interesting example took place in June 2011, when Zawahiri, newly appointed after the death of Bin Laden, called on all Jihadists in the region to help their brothers in Libya fight against Gaddafi's forces. 12 Wanting to appease Zawahiri, Belmokhtar decided to contact the Libyan Jihadists and even took a special trip to Libya. He then reports his initiatives to Zawahiri but not to Droukdel, his official and direct superior. The problem began when, at the same time, the Board of AQIM (represented by Droukdel) having also heard "Zawahiri's Call", decided to establish Jihadist cells in Libyanot knowing that it was being "overtaken" by one of their own. So, when Belmokhtar, in his letter to the Central Command a year later, cited his mission in Libya as an example of his Jihadist activism, the Board's response to him was bitter :

The Mujahideen were first called and encouraged to intervene in Libya by the Central Command of our organization [AQIM]. Its role was not limited to providing incentives and drawing attention to this opportunity, it took the form of decisions and actions that led the organization to form groups of fighters, which were sent to the heart of the Libyan territory. In fact, we sent two platoons from Tebessawhich were not quite successful in securing a foothold thereand another two from the Tariq ibn Ziyad Brigade [Abu Zeid], who managed to enter Libyan territory and to lay the foundation for our future actionsstill a work in progress. In this regard, we would like to draw your attention to a very important point, which our brother Abu Al-Abbas [Belmokhtar] brags about and keeps reminding us, namely that the entry of a platoon of his Al-Mulathamin Brigade inside Libyan territory was made without any order or any command from our emir [Droukdel], as usual, and even though the latter had formally and expressively allocated the 'Libyan assignment' to our brother Abdelhamid Abu Zeid. Behaviour of this sort from Abu Al-Abbas, without any theological or hierarchical justification, can rightly be termed lawless.

The Yemeni AQAP Model

Belmokhtar's model for the establishment of an independent branch of Al-Qaeda in the Sahel had a precedent that he wanted to replicate : Al-Qaeda in the Arabian Peninsula (AQAP). In January 2009, AQAP was formed as an autonomous branch of Al-Qaeda in Yemen to save the moribund Saudi branch, which had not withstood the blows of the Wahhabi kingdom's security services, and the 2004 rise of the Iraqi branch (Al-Qaeda in Mesopotamia) under the command of Jordan's Abu Musab al-Zarqawi. 13 For Belmokhtar, AQIM in 2012 was exactly in the same situation. He believed they were isolated and surrounded/rolled back by the Algerian Army and security services. For him, the organization would come out on top by moving the organization's centre of 11 Guidère, M. "The Tribal Allegiance System within AQIM", CTC Sentinel 4(2), pp.9-11. gravity from the Maghreb to the Sahel (north to south). This was the case in the Arabian Peninsula, where Al-Qaeda shifted from the Najd region, north of Saudi Arabia, to the Hadramawt region in southern Yemen. This displacement had been successful for AQAP and Belmokhtar was considering the same type of transfer and growth for the new organization that he wanted to establish. Therefore, upon taking control of the major cities in northern Mali, Belmokhtar gathered an Advisory Board for his Al-Mulathamin Brigade and detailed his project of a new organization directly affiliated to Al-Qaeda Central. First, he proposed to impose formal separation from AQIM (dissociated from Droukdel's leadership), then requested a direct connection to the Central Command of Al-Qaeda (Zawahiri), and soon proceeded to create a new branch of the organization called "Al-Qaeda in the Islamic Sahel" (AQIS). 14 The long letter that Belmokhtar sent in September 2012 to both AQIM's Advisory Board and the Central Command of Al-Qaeda includes a detailed business plan aimed to justify the relevance and urgency of his project. Also, to show the strength of his commitment, he required a unanimous vote of his group's Advisory Board.

The AQIM Board immediately reacted to the proposal by calling for a sacred union of all the armed groups active in northern Mali. Droukdel did this by recalling the threat of a French military intervention, then under preparation. He also provided a common and inclusive platform for all of the groups in the region by switching the focus from the "Jihad argument" to the "Shariah argument", a concept that seemed more popular to his commanders in the wake of the 2011 Arab Spring. The nuanced difference between the two concepts is significant and it indicates a shift in the organization's ideology and justification system.

In order to finalize a common governance platform and unify the various groups acting in the Sahel region, several meetings were convened during the Spring of 2012 by AQIM's Emir of the Sahara, Abu Yahya al-Hammam. 15 The stakes were high because this shift meant a fusion of all the groups and members of AQIM into a new entity called the Islamic State of Azawad,16 to be headed by Islamist Tuareg leader Iyad Ag Ghali, founder of the Ansar Eddine group. 17

With this in mind, the Advisory Board of AQIM wrote in response to Belmokhtar : "We discussed a project [the Islamic State of Azawad] that goes further than yours with the three brigades of the Emirate of the Sahara and to consider the latest developments in the region, we have even come to an agreement with our brothers from Ansar Eddine".

So, contrary to the Yemeni AQAP model promoted by Belmokhtar, Droukdel instead intended to build a copy of Al-Qaeda in Mesopotamia which set up an "Islamic State of Iraq" (ISI) in 2007, effectively fusing all the Jihadist groups into this new entity and dismissing Belmokhtar's desire. 18 Belmokhtar was then blamed by the Board of AQIM for showing a decade's worth of "too much independence, having no link other than in name with the organization's command, showing no interest, no consideration, no respect to the guidance and to the orders issued by the Emirate [AQIM]". He was also accused of not being interested in Jihad and not being active enough :

For whoever follows Jihadist activity in the Sahara, it becomes clear that the Al-Mulathamin Brigade [that of Belmokhtar] did not achieve any major operations, despite the considerable resources of the region in terms of fighters, money, weapons and accessible strategic targets [...]. Despite all our incentives and our regular recommendations, your brigade has not once demonstrated its operational effectiveness and worth in action. Whose fault is it ? Is it the command's fault or your fault ?

In response to these charges, Belmokhtar relied on supreme leader Zawahiri. He formally asked him to approve of the independence of the "Emirate of the Sahara" from "the Emirate of the Islamic Maghreb". This meant the establishment of his new branch of the organization in the Sahel and a formal disapproval of the Islamic State in the Azawad project.

The Emirate of the Islamic Maghreb had already been approved, in September 2006, by Bin Laden himself, as the governing body of the region. It extends from Tripoli in the east to the Sahara in the west, thus encompassing the countries of North Africa but not all of Libya and Mauritania. The Mauritanian north (El Djouf) and the Libyan south (El Fezzan) do not fall under the command of the Emirate of the Islamic Maghreb but under the Emirate of the Sahara. In the act of creation, the latter also includes the main countries of the Sahel, from Senegal to Niger through Mali and Burkina Faso. 19 While these "Jihadist Emirates" are led by different "Emirs" (commanders), it still is the case that the "Emir of the Sahara" will remain hierarchically subordinated to "the Emir of the Maghreb" and, thus, appointed and co-opted by the AQIM Board (Majlis al-A'yan). This was the case of the various successive heads of the "Emirate of the Sahara" from Abu Ammar (2006-2008), and Abu Nabil Alqama (2008-2012), to Abu al-Hammam (2012-2013). But Belmokhtar has always denied these appointments and never pledged allegiance to these "Emirs" as he believes that they should be appointed by the Central Command of Al-Qaeda, not by AQIM's Board.

With Jihadists in control of northern Mali since early 2012, Belmokhtar considered the time had come to "separate the two Emirates". In support of his request to Zawahiri, he used several arguments, all found in his September 2012 letter. First, that "the Maghreb Emirate is isolated, surrounded and helpless"; secondly, that "its role in managing the Jihad in the Sahara is minimal or, in some cases, non-existent"; and finally, that the Emirate (AQIM) is "an obstacle to the development of Jihadist action in the Sahel". These are serious accusations from one of the organization's top leaders in the region for over a decade.

In his official correspondence with Zawahiri, Droukdel vehemently denied Belmokhtar's accusations and said that "what Abu Al-Abbas [Belmokhtar] is calling for is unjustified, and all that he invokes to justify it, is a shame."

The Meeting in Timbuktu

The break between Belmokhtar and Droukdel became clear for all to see on 2 April 2012the day Timbuktu was taken by AQIM's force. That day, the main military leaders in the region came together to celebrate20 this major event for the Jihadist movement and to develop a strategy for the future of the territory they now dominated with their Tuareg and Moorish tribal allies in the region. They met at the invitation of Iyad Ag Ghali, the Ansar Eddine group's leader, to discuss how to govern the Islamic State of Azawad.

The AQIM option seemed to prevail, since it was vigorously defended by the Tariq ibn Ziyad Brigade's commander, Abu Zeid, then at the height of his glory.21 But Belmokhtar did not back down. He withdrew from ongoing negotiations and attempted to impose himself through actions. First, he approached the only Jihadist groups not associated with AQIM, and mounted joint operations with their leaders to essentially show his experience and capacity for action. Then, he organized an attack (a major operation at In Amenas22 in January 2013) in the south-eastern part of Algeria, the land of his competitor Abu Zeid, followed by the twin bombings in Agadez and Arlit in May 2013. 23 The attack against the gas site at In Amenas was already a show of force and an attempt to assert his leadership in the Sahara against Abu Zeid. In addressing his home province (Abu Zeid was born in the Illizi region), he challenged both the Tariq ibn Ziyad Brigade's commander and Droukdel. Later, the operation in Agadez and Arlit24 was, by the name that he gave to it (that of his now deceased rival Abu Zeid), aimed to make peace with the brigade's sub-commanders and attract their fighters, under the nose of the new leader appointed by AQIM for the region, Abu al-Hammam.

As one can see, Belmokhtar seeks to impose himself by using symbols and exploits. He is helped by the fact that the common enemy of all these groups in the Sahel remains the same: France and the armies of ECOWAS/ MINUSMA, the African forces operating there under a UN mandate. 25

AQIM's New Frontlines

In light of this, and in order to avoid a fratricidal war with Belmokhtar, the AQIM Command decided in early 2013 to focus on North Africa. To use Droukdel's words, this is because some regions have become "more conducive to Jihad ". AQIM's Command was thinking primarily about Libya and Tunisia, where the political instability had maintained a climate of uncertainty and insecurity. Taking advantage of the change-over, the leader of AQIM was quick to issue a message of support for the Tunisian group Ansar al-Shariah ("Supporters of Shariah", led by Abu Iyadh 26 ), and offered assistance and shelter. In April 2013, he ordered them (as well a Saheli platoon of the mostly Algerian and Tunisian Tariq ibn Ziyad Brigade) to move north to Mount Chaâmbi at the Algerian-Tunisian border, which was already a haven for the Ansar al-Shariah group. The junction of the two groups gave rise to the Uqba ibn Nafi Brigade. 27 It is named after the Muslim general (d. 683) who conquered North Africa and founded the first Muslim city, Kairouan, and its great mosque both of which still bear his name.

During the following months, the brigade received logistical and military support from members of AQIM that were established in the border region of Tebessa. It also received the backing of Tunisian fighters who were returning from the Libyan and Syrian fronts. The whole structure, which functions like an AQIM brigade, barricaded itself on Mount Chaâmbi and initiated actions against the Tunisian Army (ambushes, IEDs, landmines, etc.) that rigorously followed the tactical and operational modus operandi of AQIM in Algeria. Occasionally, members of this new brigade also descended from the mountains to conduct targeted actions like assassinating certain political figures who were fiercely opposed to the Islamists in general and to the Jihadists in particular. As in Algeria, Tunisia began to experience the evils of Jihadist terrorism and feared civil war. 28 On 12 July 2013, during the month of Ramadan, the Algerian authorities informed their Tunisian counterparts of possible terrorist attacks conducted by Belmokhtar's "Signers in Blood". Meanwhile, Belmokhtar was taking advantage of the death of his rival Abu Zeid (and of the anarchy prevailing in Libya), expanded his influence in the Sahel, and now wanted to challenge AQIM on its own grounds in the Maghreb. He also benefited from the logistical and financial support of some Islamist militias that control a number of localities on the Libyan border between Tunisia and Algeria. In August 2011, Belmokhtar imposed the unification of all groups under his command or that of the MUJAO as part of a new entity called Al-Murabitun ("The Sentinels"), 29 named after the medieval dynasty of the Almoravids. 29 See : http://www.ani.mr/?menuLink=9bf31c7ff062936a96d3c8bd1f8f2ff3&idNews=22616 [23 Oct. 2013, in Arabic]. 30 The Almoravids were a Berber dynasty of the 11 th and 12 th centuries that created an empire encompassing Western Sahara, a large part of North Africa, and the south of the Iberian Peninsula (Al-Andalus).

In response to this challenge, for the first time in its history AQIM posted a video online entirely devoted to Morocco. It stigmatized the King, "so called Commander of the Believers", and depicted the Kingdom of Morocco as a "land of disbelief ", calling on Moroccans to join its ranks to lead the "Jihad against the unbelievers". Al-Qaeda also reactivated its networks and cells in Libya, multiplying the attacks and killings, especially in the cities of Benghazi and Tripoli, the capital. Its leaders also wanted to impose their "project" onto the elected Parliament (Libyan General National Congress) by creating an Islamic State in Libya. AQIM actively supported this initiative and many of its leaders in the Sahel have already joined the Libyan Jihadist groups to contribute to the realization of this project. They were even coordinated in Libya by Abu Anas Al-Libi, a former veteran of the Afghan jihad and a "historical member" of Al-Qaeda Central. To counter this initiative, on 10 October 2013, American Special Forces conducted an operation to arrest Al-Libi. This triggered the ire of the Jihadist groups and the worsening of violence in Libya and the Sahel.

Conclusion

Having moved south due to pressure from the Algerian military in the 2000s, the Jihadi terrorists are now heading north because of the French and international military pressure in the Sahel. In this context, the Jihadist project still has a bright future ahead of it as AQIM's mutation is still in its infancy. Documents left behind during the Jihadists' flight from Timbuktu reveal a deep division among the various leaders of AQIM. In particular, the exchange of letters between the two main leaders, Droukdel and Belmokhtar, vividly reveals fundamental differences in the management of major "Jihad issues and actions" : kidnapping and ransom activity, weapons procurement, communications security, as well as the future development of the organization in the region.

It is on this last point that the strategic choices of the two leaders of AQIM diverge most. On the one hand, Belmokhtar proposes the creation of a new transnational branch of Al-Qaeda. On the other, Droukdel presents the counter-proposal of the establishment of an "Islamic State" that would be confined, at least to begin with, to a single "liberated territory" (in Azawad, northern Mali). For now, the two options seem to be failing, as they face national and international military vigilance, but nothing indicates a consolidated and sustainable stabilization of the region. The coming years will show whether the French military intervention in Mali has effectively reduced the terrorist threat in the Sahel or if it merely shifted the problem by accelerating the transformation of Jihadist terrorism in Africa.

  12 http://icsr.info/wp-content/uploads/2012/10/ICSR_Maher-Neumann-Paper_For-online-use-only1.pdf.13 See his biography on : http://www.theatlantic.com/magazine/archive/2006/07/the-short-violent-life-of-abumusab-al-zarqawi/304983/.

30 26

 30 See : http://thewasat.wordpress.com/tag/abu-iyad-al-tunisi/ [23 Oct. 2013]. 27 See : http://www.ctc.usma.edu/posts/al-qaida-in-the-islamic-maghrebs-tunisia-strategy [23 Oct. 2013].28 See detailed report on : http://www.trackingterrorism.org/group/katibat-uqbah-ibn-nafi[23 Oct. 2013].

http://news.bbc.co.uk/2/hi/africa/4622859.stm.

http://www.trackingterrorism.org/group/salafist-group-preaching-and-fighting-gspc-al-qaeda-lands-islamicmaghreb-see-separate-entry.

See the confirmation of his death by AQIM on http://www.huffingtonpost.com/2013/06/16/abou-zeid-deadaqim-confirms-death-of-al-qaeda-leader_n_3450611.html.

http://www.france24.com/en/20100824-spanish-hostages-freed-al-qaeda-return-home-mali-mauritania-aqmi.

http://www.france24.com/en/20110321-al-qaeda-demands-90-million-ransom-french-hostages-kidnappedniger-aqim

. 8 http://www.economist.com/node/

14416867.9 http://www.trackingterrorism.org/article/insecurity-and-rise-illegal-trafficking-sahel-maghreb.

http://www.trackingterrorism.org/group/signers-blood-battalion.

http://magharebia.com/en_GB/articles/awi/features/2012/12/11/feature-03.

http://www.rewardsforjustice.net/index.cfm?page=hammam&language=english.

http://www.nytimes.com/2012/05/27/world/africa/two-rebel-groups-in-mali-merge-to-form-islamic-state.html?_r=0.

See a brief history of the group at http://www.nctc.gov/site/groups/aqi.html.

http://studies.aljazeera.net/ResourceGallery/media/Documents/2012/4/30/2012430145241774734Al%20Qaeda%20and %20its%20allies%20in%20the%20Sahel%20and%20the%20Sahara.pdf [23 Oct. 2013].

See announcement on Twitter : https://twitter.com/martinvogl/status/210788300947062786 [23 Oct. 2013].

On this terrorist attack, see : http://www.aawsat.net/tag/signatories-in-blood[START_REF] Mandraud | Al-Qaida au Maghreb islamique menace pour la première fois le Maroc et son roi[END_REF]].

See : http://news.sky.com/story/1094772/al-qaeda-twin-bomb-attacks-in-niger-kill-25 [23 Oct. 2013].

See a detailed report on : http://www.trackingterrorism.org/article/detailed-assessment-abdulhamid-abuzaid-battle-2013 -signatories-blood-video [23 Oct. 2013].


Romain Negrel
email: romain.negrel@ensea.fr

David Picard
email: picard@ensea.fr

Philippe-Henri Gosselin
email: gosselin@ensea.fr

DIMENSIONALITY REDUCTION OF VISUAL FEATURES USING SPARSE PROJECTORS FOR CONTENT-BASED IMAGE RETRIEVAL

Keywords: Image retrieval, Image databases, Indexes, Sparse matrices

In web-scale image retrieval, the most effective strategy is to aggregate local descriptors into a high dimensionality signature and then reduce it to a small dimensionality. Thanks to this strategy, web-scale image databases can be represented with small index and explored using fast visual similarities. However, the computation of this index has a very high complexity, because of the high dimensionality of signature projectors. In this work, we propose a new efficient method to greatly reduce the signature dimensionality with low computational and storage costs. Our method is based on the linear projection of the signature onto a small subspace using a sparse projection matrix. We report several experimental results on two standard datasets (Inria Holidays and Oxford) and with 100k image distractors. We show that our method reduces both the projectors storage cost and the computational cost of projection step while incurring a very slight loss in mAP (mean Average Precision) performance of these computed signatures.

INTRODUCTION

In this paper, we focus on dimensionality reduction methods for content-based image retrieval (CBIR) on web scale datasets. CBIR is a very dynamic research field that rises many challenges, and which has proposed a variety of efficient methods to solve the problem of similarity search. Many of these methods are based on the use of highly discriminative local descriptors [START_REF] Mikolajczyk | A performance evaluation of local descriptors[END_REF] (e.g., HoG [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF], SIFT [START_REF] David G Lowe | Distinctive image features from scaleinvariant keypoints[END_REF]). Initially, the similarity between two images [START_REF] Henri Gosselin | Kernels on bags of fuzzy regions for fast object retrieval[END_REF] was computed directly on the sets of local descriptors extracted from the images. However, the computing cost of the pairwise similarity between two sets of local descriptors is prohibitive due to the large number of extracted local descriptors. To solve this problem, methods aggregating local descriptors in a unique signature [START_REF] Sivic | Video google: A text retrieval approach to object matching in videos[END_REF][START_REF] Wang | Locality-constrained linear coding for image classification[END_REF][START_REF] Perronnin | Fisher kernels on visual vocabularies for image categorization[END_REF][START_REF] Jégou | Aggregating local descriptors into a compact image representation[END_REF][START_REF] Picard | Improving image similarity with vectors of locally aggregated tensors[END_REF] were proposed. It has been shown that these signatures retain the discriminatory power of local descriptors with similarity measures of low computational cost (e.g., dot product). However signatures that perform well are very large [START_REF] Sánchez | High-dimensional signature compression for large-scale image classification[END_REF], and the storage cost becomes prohibitive for web scale datasets. As we detail later, several methods to reduce signatures dimensionality have been proposed. These methods provide low dimensional signatures with low storage cost and good discriminatory power. However, they incur a high projection cost: the memory required to store the projectors and the computational cost to perform the projection are often prohibitive, and this is precisely what we investigate in this paper.

More specifically, we propose a new method to dramatically reduce the memory footprint and the computational cost of such pro-jections. This method is based on the low-rank approximation of Gram matrix with a sparse projection matrix. Our main novel contributions are:

• The introduction of a sparsity constraint in the Gram matrix low-rank approximation problem;

• The introduction of a correction matrix to correct the errors induced by the coarse solution of the sparse low-rank approximation problem.

The rest of the paper is organized as follows: First, we give an overview of the related work in dimensionality reduction. Then we explain our proposed method in section 3. In section 4, we evaluate our method on Inria Holidays [START_REF] Jegou | Hamming embedding and weak geometric consistency for large scale image search[END_REF] and Oxford datasets and we discuss and compare the performance with the state of the art methods, before we conclude.

RELATED WORKS

In this section, we present current methods for the reduction of visual signatures, as well as their main advantages and drawbacks. More specifically, we focus on methods that compute linear projectors in Hilbert spaces:

y = P ⊤ x, (1)
with y the signature reduced at N dimensions, P the projectors matrix and x the original signature of W dimensions. The choice of linear projectors can be explained by their simplicity and their ability to deal with large datasets. The choice of unsupervised training can be explained by the difficulty of obtaining a ground truth for image similarity search. The most popular approach to learn the projection matrix is the Principal Component Analysis (PCA) [START_REF] Christopher | Pattern recognition and machine learning[END_REF] which selects components of largest variance. PCA is well known in data analysis as it provides a compact representation of the data while guaranteeing the lowest reconstruction error of the data. This approach has shown to retain the discriminating power of signatures while greatly reducing the dimensionality in many state of the art papers [START_REF] Jégou | Aggregating local descriptors into a compact image representation[END_REF][START_REF] Douze | Combining attributes and fisher vectors for efficient image retrieval[END_REF][START_REF] Sánchez | High-dimensional signature compression for large-scale image classification[END_REF]. However, the criterion of data reconstruction does not guarantee the preservation of the discrimination power of signatures.

To solve this problem, the authors of [START_REF] Negrel | Web-scale image retrieval using compact tensor aggregation of visual descriptors[END_REF] propose a similar approach based on the low-rank approximation of the Gram matrix. The authors propose to compute the projectors such that the original similarity between two signatures is retained. To this purpose, they propose to solve the following problem:

P * N = arg min P N ||X ⊤ X -X ⊤ PN P ⊤ N X|| 2 F s.t. PN ∈ MW,N with N < L ≪ W, (2)
with X the L signatures of the training set and PN the projectors matrix. The closed form solution of this problem is:

P * N = XTN L -1/2 N , (3)
with {TN , LN } the N principal eigenvectors and eingenvalues of Gram matrix XX ⊤ . Furthermore, they propose to use the dot product associated with Mahalanobis distance as a new similarity measure. This similarity measure gives a better discrimination power and it can be integrated in the projectors matrix as follows:

P ′ * N = P ′ * N L -1/2 N = XTN L -1 N . (4)
This method provides projectors which drastically reduce the size of original signature while retaining the similarity between two signatures. For example, visual signatures of hundreds of thousands of dimensions can be reduced to a few hundreds and with similar retrieval performance. However, all these current methods suffer from a major drawback: the size of projectors is as large as the size of visual features. This implies that the memory cost and computational cost of the projection have an order of O(W × N ) with N the dimension of subspace. Thus, given the high values of W (e.g. at least hundreds of thousands), the corresponding projection matrix quickly becomes very large, the projection itself is not scalable. For instance such matrix is thus difficult to spread on a computational grid, or simply too large to fit in the available memory.

PROPOSED METHOD

In this section, we present our main contribution: a new projection matrix for significantly reducing the size of large signatures with a low storage cost and computational cost. Our projection matrix is based on optimizing the reconstruction of the Gram matrix of a training set with a sparsity constraint.

In order to obtain the sparse projectors that provide a better approximation of the Gram matrix, we must solve problem (2) constrained with ℓ0 norm:

U * N = arg min U N ||X ⊤ X -X ⊤ UN U ⊤ N X|| 2 F s.t. UN ∈MW,N with N < L ≪ W ||ui||0 = M, ∀i, (5)
with M the number of non-zero entries by columns of matrix UN . However, since this problem is NP-hard, it is very complex to obtain an exact solution.

We propose to reformulate this problem by decomposing the projection matrix UN into two matrices:

UN = PN RN , (6)
with PN a sparse matrix of W by N , RN a full square matrix. Dimensionality reduction is then performed in two steps: (i) a first step of high dimensionality reduction with a sparse approximation of full projection matrix P * N and (ii) a second projection step with a low cost full matrix. The second projection step allows to correct the errors introduced by the sparse approximation P * N .

The sparse matrix PN

To compute the sparse projection matrix, we propose to compute the sparse approximation of the projectors P * N obtained by solving the problem without the constraint of sparsity. For this, we solve the following problem:

P * N = arg min PN ||P ′ * N -PN || 2 F s.t. ||pi||0 = M, ∀i. (7)
The problem [START_REF] Perronnin | Fisher kernels on visual vocabularies for image categorization[END_REF] has a closed form solution obtained by thresholding the smallest values of the original projectors:

pki = p ki h(|p ik | -∇i), ∀k (8)
with h the Heaviside step function, ∇i ∈ R + the threshold selected to satisfies the sparsity constraint. The solution of this problem is a very simple but coarse approximation of the solution of the problem [START_REF] Sivic | Video google: A text retrieval approach to object matching in videos[END_REF]. Indeed, this solution does not take into consideration the correlations between projectors.

The correction matrix RN

To correct the errors introduced by the sparse projection matrix, we propose to compute a correction matrix in the low dimensional space. For this, we propose to compute the matrix RN such that the Gram matrix of corrected signature,

G P * N R N = X ⊤ P * N RN R ⊤ N P * ⊤ N X
, is as close as possible to the Gram matrix of signature obtained with full projectors

G P ′ * N = X ⊤ P ′ * N P ′ * ⊤ N X.
To obtain this correction matrix, we solve the following problem:

W * = arg min W ||G P ′ * N -Y ⊤ P * N WY P * N || 2 F , (9)
with

Y P * N = P * ⊤ N X and W = RN R ⊤ N .
This problem is convex and, for S < L, it has a closed form solution:

W * = Y + P * N G P ′ * N Y +⊤ P * N , (10)
R * N = VD 1/2 , (11)
with {V, D} the eigenvectors and eigenvalues of W * . The full projection for the dimensionality reduction is then decomposed into two projections:

ŷi = P * ⊤ N xi yi =R * ⊤ N ŷi . ( 12
)
For convenience, we define the sparsity constraint independently from the dimension of the input vectors. To this end, we note by τ the rate of zero values in a sparse matrix:

τ ( P * N ) = Number of zero values in P * N Number of values in P * N . (13)
In the case of our matrix P * N constrained by ℓ0 norm, we have the following relation between M and τ :

τ ( P * N ) = W -M W . (14)
The cumulative computational cost of these two projections is

O ((N + (1 -τ ) × W ) × N ).
((N + 2 × (1 -τ ) × W ) × N )
, considering that the values of sparse projectors are stored in couples (index, value). Table 1 shows the computational and storage cost of the proposed method. We observe that high sparsity rate allows to strongly reduces the costs of dimensionality reduction step.

EXPERIMENTS

In this section, we present the reference datasets and the signatures we use to evaluate our proposed method. We discuss the performance of our method and compare it with the state of the art.

Datasets and Signatures

We use two well known benchmarks: Inria Holidays dataset and Oxford dataset. The Holidays dataset contains 1,491 images (typically personal holiday photographs) gathered in 500 groups. The Oxford dataset is a set of images (from Flickr) representing various Oxford landmarks; it contains 5,062 images of 11 landmarks. To evaluate the robustness of our method, we use 100k images distractor randomly extracted from ImageNet dataset. The ImageNet dataset is a set of high-quality images extracted from Flickr. For all training, we use Holidays Flickr60k dataset, which is a set of high-quality images randomly extracted from Flickr; it contains 60,000 images without ground truth. For all the above mentioned images, we perform a two step preprocessing: (a) image resizing (to a maximum width of 512 pixels); (b) histogram equalization. Furthermore, we use two types of local descriptors: a texture descriptor HOG (128-dimensional) [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF] and a color descriptor (96-dimensional) proposed by Perronnin et al. [START_REF] Perronnin | Improving the fisher kernel for large-scale image classification[END_REF]. We extract these descriptors on a regular dense grid of 3 × 3 pixels and at 4 scales. We use these descriptors to compute "Vectors of Locally Aggregated Tensors" (VLAT) [START_REF] Picard | Improving image similarity with vectors of locally aggregated tensors[END_REF] and "Fisher Vector" (FV) [START_REF] Perronnin | Large-scale image retrieval with compressed fisher vectors[END_REF] signatures as follows. For each descriptor, we compute: a VLAT signature with a cluster-wise PCA that preserves 80 dimensions by cluster; and a FV signature with a PCA on local descriptors that preserves 80 dimensions. The HOG and color signatures are subsequently concatenated. Then, we perform a powernormalization (for all experiments set to 0.1) and ℓ2-normalization of the concatenated signatures.

In the following, we denote the signatures used for the experiments by their abbreviations prefixed by the dimentionnality reduction method used if any, and as suffix the size of the visual codewords. More precisely, we use the prefix "C" to denote the dimentionnality reduction method proposed in [START_REF] Negrel | Web-scale image retrieval using compact tensor aggregation of visual descriptors[END_REF]; "CS" to denote our method without the correction matrix; and "CSR" to denote our method with the correction matrix. For example, "CS-VLAT-256" is Sign.

Dim. Holidays Oxford FV-64 [START_REF] Jégou | Aggregating local image descriptors into compact codes[END_REF] 4k 59.5 31.7 VLAD-64 [START_REF] Jégou | Aggregating local image descriptors into compact codes[END_REF] 4k 55.6 30.4 VLAD-64 [START_REF] Delhumeau | Revisiting the vlad image representation[END_REF] 8k 62.2 50.0 VLAD-64 [START_REF] Negrel | Web-scale image retrieval using compact tensor aggregation of visual descriptors[END_REF] 8k -36.6 VLAT-64 [START_REF] Negrel | Web-scale image retrieval using compact tensor aggregation of visual descriptors[END_REF] 528k Fig. 2. mAP evolution on Holidays dataset as function of dimensionality reduction step computational cost for different sparsity rates (i.e., τ ∈ {99.9%, 99%, 90%, 0%}).

a signature VLAT computed with 256 visual codewords and dimensionality of reduced with our proposed method without the correction matrix.

As a baseline, Table 2 shows the mAP on Holidays and Oxford datasets obtained by the unreduced signatures. This table is divided in two parts: in the top part, we report several results obtained in related state of the art; and, in the bottom part, we report the results of our implementation of the same methods. Comparing with the results of state of the art, we see that we obtain much better performance. This is mainly due to our use of two types of local descriptors as well as larger visual codebooks than those of the state of the art.

Parameter Analysis

Here, we study the behavior of the reduced signatures as function of the parameters of our method. All experiments are done using the Holidays dataset. We consider a web-scale context in which the final signature must be small (N = 256). We compute the sparse projectors P * N and the correction matrix R * N for different sparsity rates τ ∈ {99.9%, 99%, 90%, 0%} (note that for τ = 0%: P * N = P * N and R * N = I). Figure 2 shows the mAP evolution on Holidays Fig. 1. Images from Holidays dataset [START_REF] Jegou | Hamming embedding and weak geometric consistency for large scale image search[END_REF].

dataset as function of the computational cost of our dimentionality reduction method. This cost is induced by the two projection steps: the projection of the signature on the sparse projectors; and the projection on the correction matrix. The continuous and dashed curves represent the performance of the reduced signatures with and without the correction step respectively. We note that at equivalent computation cost, the high dimensional projectors are less sensitive to high sparsity rate. We see that the correction step allows to correct well the errors introduced by sparse projectors. Moreover, we observe that the higher the sparsity rate, the more effective the correction step. We also observe that the mAP performance is similar for any type of signatures. Thus, our method is not sensitive to a particular signature choice. For instance, with "CSR-FV-256" signature and a sparsity rate of 90%, the computational cost is divided by a factor of about 9 without any performance loss. With the same "CSR-VLAT-256" signature, but with a sparsity rate of 99.9%, the computational cost is divided by a factor of about 1000 while incurring a mAP loss of only 0.9.

Comparison with the State of the Art

In the following, we compare the performances of our dimensionality reduction method with state of the art methods. We compute the signatures: FV-64, FV-256, VLAT-64 and VLAT-256 reduced at 128 dimensions. We compute the performance of these signatures on Holidays and Oxford datasets with and without the addition of 100k distractors.

The performance results are reported in Table 3 which is divided in three parts. In the top part, we report several results obtained in related state of the art. The middle part illustrates the results obtained by reproducing the dimensionality reduction method proposed in [START_REF] Negrel | Web-scale image retrieval using compact tensor aggregation of visual descriptors[END_REF] for fairness of comparison. We note that this method preserves the performance of the original signature on Holidays dataset but on Oxford dataset the performance is degraded. This is probably caused by using the local color descriptor that is not relevant on this dataset. In the bottom part, we report the results of the proposed method. We observe, in the two datasets, that our method provides the same robustness as the state of the art when adding the distractors. However, our method has the great advantage of having a much lower dimensionality reduction cost. For example, in the case of C-VLAT-256, the loss in mAP performance is of 6.4 on Holidays and of 0.6 on Oxford. Using our method, in the case of CSR-VLAT-256, the loss in mAP performance is of 6.3 on Holidays and of 1.0 on Oxford while dividing the computational cost by a factor of around 1000.

Name

Dim. Holidays Oxford +100k +100k FV-64-PCA [START_REF] Jégou | Aggregating local image descriptors into compact codes[END_REF] 128 56.5 38.0 24.3 -VLAD-64-PCA [START_REF] Jégou | Aggregating local image descriptors into compact codes[END_REF] 64 44.7 32.0 --VLAD-64-PCA [START_REF] Delhumeau | Revisiting the vlad image representation[END_REF] 128 --32.5 26.6 C-VLAT-64 [START_REF] Negrel | Compact tensor based image representation for similarity search[END_REF] 256 72.3 58.0 --VLAD-64-PCA [START_REF] Negrel | Web-scale image retrieval using compact tensor aggregation of visual descriptors[END_REF] 128 --32.7 25.6 C-VLAT-64 [START_REF] Negrel | Web-scale image retrieval using compact tensor aggregation of visual descriptors[END_REF] 128 57. 128 77.5 69.9 35.9 34.7 CSR-FV-256, τ = 0.9 128 80.6 73.9 37.8 36.9 CSR-VLAT-64, τ = 0.99 128 75.6 68.8 40.9 39.9 CSR-VLAT-256, τ = 0.999 128 76.9 70.6 35.6 34.6 Table 3. Evaluation of the reduced signatures robustness by adding of 100k distractors and comparison of state-of-the-art results on Holidays and Oxford dataset (mAP in %).

CONCLUSION

In this paper, we introduce a method to reduce the dimensionality of image signatures with very low storage and computational complexities. Our method consists in a linear projection of the image signature in a low dimensional subspace thanks to sparse projectors. The sparse projectors are initialized using a sparse approximation of dense projectors, and then corrected using a small matrix. This second step allows to better recover the discriminative power of reduced signatures. We have carried out experiments on Inria Holidays and Oxford datasets, which showed that our dimensionality reduction method provides close performance to the state of the art, while reducing storage and computational complexities of a factor in between 10 to 1000 times.

  obtain the correction matrix R * N by factorization of W * to this propose we use the eigen decomposition:

  3 -54.3 46.6 C-FV-64 128 77.4 69.9 36.6 35.7 C-FV-256 128 79.9 74.0 38.0 37.2 C-VLAT-64 128 75.4 69.3 42.1 41.3 C-VLAT-256 128 78.2 71.8 39.0 38.4 CSR-FV-64, τ = 0.9

Table 1 .

 1 For high sparsity rate (e.g. τ = Costs of dimensionality reduction step as function of input signature size and sparsity rate with N = 256 (with Oc the computational cost in operations and Om the storage cost).

	W ❍ ❍ ❍ ❍ ❍ τ	Oc	82k	Om	Oc	415k Om	Oc	1.7M Om
	0.0%	21,1M 160MB 106M 811MB 435M 3,2GB
	90.0%	2,2M 16.3MB 10,7M 81.3MB 43,5M 332MB
	99.0%	275k 1.9MB 1,1M 8.4MB 4,4M 33.5MB
	99.9%	87k	420kB 172k 1.1MB 501k 3.6MB
	99%), this cost is very low in comparison with the computational
	cost with full projectors. The storage cost is also drastically re-
	duced: O

Table 2 .

 2 Evaluation of computed signatures and comparison of stateof-the-art results on Holidays and Oxford dataset (mAP in %).

			66.4	54.2
	FV-64	20k	78.6	43.3
	FV-256	82k	82.0	49.3
	VLAT-64	415k	81.6	58.4
	VLAT-256	1.7M	84.0	59.8