Marc Arnaudon
email: marc.arnaudon@math.u-bordeaux.fr

Anton Thalmaier
email: anton.thalmaier@uni.lu

Gradient Estimates on Feng-Yu Wang
email: wangfy@tju.edu.cn

Dirichlet Eigenfunctions

Gradient Estimates on Dirichlet Eigenfunctions

Keywords: AMS subject Classification: 35P20, 60H30, 58J65 Eigenfunction, gradient estimate, diffusion process, curvature, second fundamental form

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

Let D be a d-dimensional compact Riemannian manifold with boundary ∂D. We write (φ, λ) ∈ Eig(∆) if φ is a Dirichlet eigenfunction of -∆ in D with eigenvalue λ > 0. According to [START_REF] Shi | Gradient estimate of a Dirichlet eigenfunction on a compact manifold with boundary[END_REF], there exist two constants c 1 (D), c 2 (D) > 0 such that (1.1)

c 1 (D) √ λ φ ∞ ∇φ ∞ c 2 (D) √ λ φ ∞ , (φ, λ) ∈ Eig(∆).
An analogous statement for Neumann eigenfunctions has been derived in [START_REF] Hu | The gradient estimate of a Neumann eigenfunction on a compact manifold with boundary[END_REF].

Concerning Dirichlet eigenfunctions, an explicit upper constant c 2 (D) can be derived from the uniform gradient estimate of the Dirichlet semigroup in an earlier paper [START_REF] Wang | Gradient estimates of Dirichlet semigroups and applications to isoperimetric inequalities[END_REF] of the third named author. More precisely, let K, θ 0 be two constants such that

(1.2) Ric D -K, H ∂D -θ,
where Ric D is the Ricci curvature on D and H ∂D the mean curvature of ∂D. Let (1.3) α 0 = 1 2 max θ, (d -1)K .

Consider the semigroup P t = e t∆ for the Dirichlet Laplacian ∆. According to [START_REF] Wang | Gradient estimates of Dirichlet semigroups and applications to isoperimetric inequalities[END_REF]Theorem 1.1] where c = 2α 0 , for any nontrivial f ∈ B b (D) and t > 0, the following estimate holds:

∇P t f ∞ f ∞ 9.5α 0 + 2 √ α 0 (1 + 4 2/3 ) 1/4 (1 + 5 × 2 -1/3 ) (tπ) 1/4 + 1 + 2 1/3 (1 + 4 2/3 ) 2 √ tπ =: c(t).
Consequently, for any (φ, λ) ∈ Eig(∆),

∇φ ∞ φ ∞ inf t>0 c(t)e λt .
In particular, when Ric D 0, H ∂D 0, (1.4) ∇φ ∞ e (1 + 2 1/3 ) (1 + 4 2/3 ) √ 2π √ λ φ ∞ , (φ, λ) ∈ Eig(∆).

In this paper, by using stochastic analysis of the Brownian motion on D, we develop two-sided gradient estimates; the upper bound given below in (1.8) improves the one in (1.4). Our result will also be valid for α 0 ∈ R satisfying (1.5) 1 2 ∆ρ ∂D α 0 outside the focal set, where ρ ∂D is the distance to the boundary. The case α 0 < 0 appears naturally in many situations, for instance when D is a closed ball with convex distance to the origin. Note that by [10, Lemma 2.3], if under (1.2) we define α 0 by (1.3) then condition (1.5) holds as a consequence. For x 0, in what follows in the limiting case x = 0 we use the convention

1 1 + x 1/x := lim r↓0 1 1 + r 1/r = 1 e .
Theorem 1.1. Let K, θ 0 be two constants such that (1.2) holds and let α 0 be given by (1.3) or more generally satisfy (1.5). Then, for any nontrivial (φ, λ) ∈ Eig(∆), (1.6)

λ de(λ + K) λ d(λ + K) λ λ + K λ/(2K) ∇φ ∞ φ ∞ and (1.7) ∇φ ∞ φ ∞ e(λ + K) if √ λ + K 2A √ e A + λ+K 4A if √ λ + K 2A,
where

A := 2α + 0 + 2(λ + K) √ π exp - α 2 0 2(λ + K) .
In particular, when Ric D 0, H ∂D 0,

(1.8)

√ λ √ de ∇φ ∞ φ ∞ √ λ √ 2e √ π + √ πe 4 √ 2 , (φ, λ) ∈ Eig(∆).
Proof. This result follows from Theorem 2.1 and Theorem 2.2 below in the special case V = 0. In this case, Ric

c 1 (D) = 1 √ de , c 2 (D) = √ 2e √ π + √ πe 4 √ 2 .
To give explicit values of c 1 (D) and c 2 (D) for positive K or θ, let λ 1 > 0 be the first Dirichlet eigenvalue of -∆ on D. Then Theorem 1.1 implies that (1.1) holds for

c 1 (D) = √ λ 1 de(λ 1 + K) , c 2 (D) = e(λ 1 + K) √ λ 1 1 {B>2A} + √ e √ λ 1 2α + 0 + 2(λ 1 + K) π + λ 1 + K 4 2α + 0 + 2(λ 1 + K)/π 1 {B 2A} with B = λ 1 + K and A = 2α + 0 + 2(λ 1 + K) π .
This is due to the fact that the expression for c 1 (D) is an increasing function of λ and the expression for c 2 (D) a decreasing function of λ. Since there exist explicit lower bound estimates on λ 1 (see [START_REF] Wang | Estimates of the first Dirichlet eigenvalue by using diffusion processes[END_REF] and references within), this gives explicit lower bounds of c 1 (D) and explicit upper bounds of c 2 (D). The lower bound for ∇φ ∞ will be derived by using Itô's formula for |∇φ| 2 (X t ) where X t is a Brownian motion (with drift) on D, see Subsection 2.1 for details. To derive the upper bound estimate, we will construct some martingales to reduce ∇φ ∞ to ∇φ ∂D,∞ := sup ∂D |∇φ|, and to estimate the latter in terms of φ ∞ , see Subsection 2.2 for details.

Next, we consider the Neumann problem. Let Eig N (∆) be the set of non-trivial eigenpairs (φ, λ) for the Neumann eigenproblem, i.e. φ is non-constant, ∆φ = -λφ with N φ| ∂D = 0 for the unit inward normal vector field N of ∂D. Let I ∂D be the second fundamental form of ∂D,

I ∂D (X, Y ) = -∇ X N, Y , X, Y ∈ T x ∂M, x ∈ ∂M.
With a concrete choice of the function f , the next theorem implies (1.1) for (φ, λ) ∈ Eig N (∆) together with explicit constants c 1 (D), c 2 (D).

Theorem 1.2. Let K, δ ∈ R be constants such that (1.9) Ric D -K, I ∂D -δ.

For f ∈ C 2 b ( D) with inf D f = 1 and N log f | ∂D δ, let c ε (f ) = sup D 4ε|∇ log f | 2 1 -ε + K -2∆ log f , ε ∈ (0, 1), K(f ) = sup D 2|∇ log f | 2 + K -∆ log f .
Then for any non-trivial (φ, λ) ∈ Eig N (∆), we have λ + c ε (f ) > 0 and sup ε∈(0,1)

ελ 2 de(λ + c ε (f )) f 2 ∞ sup ε∈(0,1) ελ 2 d(λ + c ε (f )) f 2 ∞ λ λ + c ε (f ) λ/cε(f ) ∇φ 2 ∞ φ 2 ∞ 2 f 2 ∞ (λ + K(f )) π 1 + K(f ) λ λ/K(f ) 2e f 2 ∞ λ + K(f ) π .
Proof. Under the conditions (1.2), Theorem 3.3 below applies with L = ∆, K V = K and n = d.

The desired estimates are immediate consequences.

When ∂D is convex, i.e. I ∂D 0, we may take f ≡ 1 in Theorem 1.2 to derive the following result. According to Theorem 3.2 below, this result also holds for ∂D = ∅ where Eig(∆) is the set of eigenpairs for the closed eigenproblem.

Corollary 1.3. Let ∂D be convex or empty. If Ric V D -K for some constant K, then for any non-trivial (φ, λ) ∈ Eig N (∆), we have λ + K > 0 and

λ 2 de(λ + K + ) λ 2 d(λ + K) λ λ + K λ/K ∇φ 2 ∞ φ 2 ∞ 2(λ + K) π 1 + K λ λ/K 2e(λ + K + ) π .
2 Proof of Theorem 1.1

In general, we will consider Dirichlet eigenfunctions for the symmetric operator L := ∆ + ∇V on D where V ∈ C 2 (D). We denote by Eig(L) the set of pairs (φ, λ) where φ is a Dirichlet eigenfunction of -L on D with eigenvalue λ.

In the following two subsections, we consider the lower bound and upper bound estimates respectively.

Lower bound estimate

In this subsection we will estimate ∇φ ∞ from below using the following Bakry-Émery curvaturedimension condition:

(2.1) 1 2 L|∇f | 2 -∇Lf, ∇f -K|∇f | 2 + (Lf ) 2 n , f ∈ C ∞ (D),
where K ∈ R, n d are two constants. When V = 0, this condition with n = d is equivalent to Ric D -K. Consequently, for K + := max{0, K} there holds

(2.3) ∇φ 2 ∞ λ 2 φ 2 ∞ n(λ + K + ) λ λ + K + λ/K + λ 2 φ 2 ∞ ne(λ + K + ) , (φ, λ) ∈ Eig(L).
Proof. Let X t be the diffusion process generated by 1 2 L in D, and let τ D := inf{t 0 : X t ∈ ∂D}. By Itô's formula, we have

(2.4) d|∇φ| 2 (X t ) = 1 2 L|∇φ| 2 (X t ) dt + dM t , t τ D ,
for some martingale M t . By the curvature dimension condition (2.1) and Lφ = -λφ, we obtain

(2.5) 1 2 L|∇φ| 2 = 1 2 L|∇φ| 2 -∇Lφ, ∇φ -λ|∇φ| 2 -(K + λ)|∇φ| 2 + λ 2 n φ 2 .
Therefore, (2.4) gives

d|∇φ| 2 (X t ) λ 2 n φ 2 -(K + λ)|∇φ| 2 (X t ) dt + dM t , t τ D .
Hence, for any t > 0,

e (K+λ) + t ∇φ 2 ∞ E |∇φ| 2 (X t∧τ D )e (K+λ)(t∧τ D ) λ 2 n E t∧τ D 0 e (K+λ)s φ(X s ) 2 ds = λ 2 n E t 0 1 {s<τ D } e (K+λ)s φ(X s ) 2 ds .
Since φ| ∂D = 0 and Lφ = -λφ, by Jensen's inequality we have

E 1 {s<τ D } φ(X s ) 2 E[φ(X s∧τ D )] 2 = e -λs φ(x) 2 ,
where x = X 0 ∈ D is the starting point of X t . Then, by taking x such that φ(x) 2 = φ 2 ∞ , we arrive at

e (K+λ) + t ∇φ 2 ∞ λ 2 n t 0 e (K+λ)s e -λs φ(x) 2 ds = λ 2 φ 2 ∞ n t 0 e Ks ds = λ 2 (e Kt -1) nK φ 2 ∞ .
This completes the proof of (2.2). Since (2.1) holds for K + replacing K, we may and do assume that K 0. By taking the optimal choice t =

1 K log(1 + K λ ) (by convention t = λ -1 if K = 0) in (2.
2), we obtain

∇φ 2 ∞ λ 2 φ 2 ∞ λ + K λ λ + K λ/K λ 2 φ 2 ∞ ne(λ + K) .
Hence (2.3) holds.

Upper bound estimate

Let Ric V D = Ric D -Hess V . For K 0 , θ 0 such that Ric D -K 0 and H ∂D -θ, let (2.6) α = 1 2 max θ, (d -1)K 0 + ∇V ∞ We note that 1 2 Lρ ∂D α by [10, Lemma 2.3]. Theorem 2.2 (Upper bound estimate). Let K V , θ 0 be constants such that Ric V D -K V , H ∂D -θ. Let α ∈ R be such that (2.7) 1 2 Lρ ∂D α.
1. Assume α 0. Then, for any nontrivial (φ, λ) ∈ Eig(L),

(2.8) ∇φ ∞ φ ∞ e(λ + K V ) if √ λ + K V 2A √ e A + λ+K V 4A if √ λ + K V 2A,
where (2.9)

A := α + 2(λ + K V ) √ π exp - α 2 2(λ + K V ) + |α| ∧ √ 2α 2 π(λ + K V ) .
In particular, (2.8) holds with A replaced by (2.10)

A := 2α + 2(λ + K V ) √ π exp - α 2 2(λ + K V )
.

We also have

(2.11) ∇φ ∞ φ ∞ √ e 2α + 2(λ + K V ) √ π + λ + K V 4 √ π 2α + 2(λ + K V ) . 2. Assume α 0. Then, for any nontrivial (φ, λ) ∈ Eig(L), (2.12) ∇φ ∞ φ ∞ e(λ + K V ) if √ λ + K V 2A * √ e A * + λ+K V 4A * if √ λ + K V 2A * ,
where (2.13)

A * := 2(λ + K V ) √ π exp - α 2 2(λ + K V ) .
In particular,

(2.14) ∇φ ∞ φ ∞ λ + K V 2 π + 1 4 π 2 √ e.
In addition, the following estimate holds:

(2.15) ∇φ ∞ φ ∞ e(λ + K V ) if √ λ + K V 2 √ e  e  + λ+K V 4  if √ λ + K V < 2 √ e Â,
where

(2.16) Â := α + √ 2λ √ π e -α 2 2λ + |α| ∧ √ 2α 2 √ πλ .
The strategy to prove Theorem 2.2 will be to first estimate ∇φ ∞ in terms of φ ∞ and ∇φ ∂D,∞ (see estimate (2.24) below) where f ∂D,∞ := 1 ∂D f ∞ for a function f on D. The this end we construct appropriate martingales in terms of φ and ∇φ.

We start by recalling the necessary facts about the diffusion process generated by 1 2 L, see for instance [START_REF] Arnaudon | Gradient estimates and Harnack inequalities on non-compact Riemannian manifolds[END_REF][START_REF] Hsu | Stochastic Analysis on Manifolds[END_REF]. For any x ∈ D, the diffusion X t solves the SDE (2.17)

dX t = 1 2 ∇V (X t ) dt + u t • dB t , X 0 = x, t τ D ,
where B t is a d-dimensional Brownian motion, u t is the horizontal lift of X t onto the orthonormal frame bundle O(D) with initial value u 0 ∈ O x (D), and

τ D := inf{t 0 : X t ∈ ∂D}
is the hitting time of X t to the boundary ∂D. Setting Z := ∇V , we have

(2.18) du t = 1 2 Z * (u t ) dt + d i=1 H i (u t ) • dB i t where Z * (u) := h u (Z π(u)
) and H i (u) := h u (ue i ) are defined by means of the horizontal lift

h u : T π(u) D → T u O(D) at u ∈ O(D). Note that formally h ut (u t • dB t ) = i h ut (u t e i ) • dB i t = i H i (u t ) • dB i t . For f ∈ C ∞ (D), let a := df ∈ Γ(T * D). Setting m t := u -1
t a(X t ), we see by Itô's formula that

(2.19) dm t m = 1 2 u -1 t ( a + ∇ Z a)(X t ) dt
where a = tr ∇ 2 a denotes the so-called connection (or rough) Laplacian on 1-forms and m = equality modulo the differential of a local martingale.

Denote by Q t : T x D → T Xt D the solution, along the paths of X t , to the covariant ordinary differential equation

DQ t = - 1 2 (Ric V D ) Q t dt, Q 0 = id TxD , t τ D ,
where D := u t du -1 t and where by definition

(Ric V D ) v = Ric V D (•, v) , v ∈ T x D. Thus, condition Ric V D -K V implies (2.20) |Q t v| e K V 2 t |v|, t τ D .
Finally, note that for any smooth function f on D, we have by the Weitzenböck formula:

d ∆ + Z f = d -d * df + (df )Z = ∆ (1) df + ∇ Z df + ∇ . Z, ∇f = ( + ∇ Z )(df ) -Ric V D (•, ∇f ) = -Ric V D + ∇ Z (df ) (2.21)
where ∆ (1) denotes the Hodge-deRham Laplacian on 1-forms. Now let (φ, λ) ∈ Eig(L), i.e. Lφ = -λφ, where L = ∆ + Z. For v ∈ T x D, consider the process

n t (v) := (dφ)(Q t v).
Then

n t (v) = ∇φ(X t ), Q t v = u -1 t (∇φ)(X t ), u -1 t Q t v
t (v) m = 1 2 ( dφ + ∇ Z dφ)(X t ) Q t v dt + dφ(X t )(DQ t v) dt = - λ 2 n t (v) dt.
It follows that

(2.22) e λt/2 n t (v) = e λt/2 ∇φ(X t ), Q t v , t τ D , is a martingale. Lemma 2.3. Let (φ, λ) ∈ Eig(L).
We keep the notation from above. Then, for any function

h ∈ C 1 ([0, ∞); R), the process N t (v) := h t e λt/2 ∇φ(X t ), Q t v -e λt/2 φ(X t ) t 0 ḣs Q s v, u s dB s , t τ D , (2.23)
is a martingale. In particular, for fixed t > 0 and h ∈ C 1 ([0, t]; [0, 1]) monotone such that h 0 = 1 and h t = 0, we have

∇φ ∞ ∇φ ∂D,∞ P{t > τ D } e (λ+K V ) + t/2 + φ ∞ e λt/2 P{t τ D } 1/2 t 0 | ḣs | 2 e K V s ds 1/2 . (2.24)
Proof. Indeed, from (2.22) we deduce that

h t e λt/2 ∇φ(X t ), Q t v - t 0 ḣs e λs/2 ∇φ(X s ), Q s v ds, t τ D ,
is a martingale as well. By the formula e λt/2 φ(X t ) = φ(X 0 ) + t 0 e λs/2 ∇φ(X s ), u s dB s we see then that N t (v) is a martingale. To check inequality (2.24), we deduce from the martingale property of

{N s∧τ D (v)} s∈[0,t] that ∇φ ∞ ∇φ ∂D,∞ E 1 {t>τ D } e λτ D /2 |h τ D | |Q τ D | + φ ∞ e λt/2 E 1 {t τ D } sup |v| 1 t 0 ḣs Q s v, u s dB s 2 1/2 .
The claim follows by using (2.20).

To estimate the boundary norm ∇φ ∂D,∞ , we shall compare φ(x) and ψ(t, x) := P(τ x D > t), t > 0, for small ρ ∂D (x) := dist(x, ∂D). Let P D t be the Dirichlet semigroup generated by 1 2 L. Then

ψ(t, x) = P D t 1 D (x), so that (2.25) ∂ t ψ(t, x) = 1 2 Lψ(t, •)(x), t > 0.
Lemma 2.4. For any (φ, λ) ∈ Eig(L),

(2.26) ∇φ ∂D,∞ φ ∞ inf t>0 e λt/2 ∇ψ(t, •) ∂D,∞ .
Proof. To prove (2.26), we fix x ∈ ∂D. For small ε > 0, let x ε = exp x (εN ), where N is the inward unit normal vector field of ∂D. Since φ| ∂D = 0 and ψ(t, •)| ∂D = 0, we have

(2.27) |∇φ(x)| = |N φ(x)| = lim ε→0 |φ(x ε )| ε , |∇ψ(t, •)(x)| = lim ε→0 |ψ(t, x ε )| ε .
Let X ε t be the L-diffusion starting at x ε and τ ε D its first hitting time of ∂D. Note that

N t := φ(X ε t∧τ ε D ) e λ(t∧τ ε D )/2 , t 0,
is a martingale. Thus, for each fixed t > 0, we can estimate as follows:

|∇φ(x)| = lim ε→0 |φ(x ε )| ε = lim ε→0 E[φ(X ε t ) 1 {t<τ ε D } ] e λ(t∧τ ε D )/2 ε φ ∞ e λt/2 lim ε→0 E[1 {t<τ ε D } ] ε φ ∞ e λt/2 lim ε→0 ψ(t, x ε ) ε = φ ∞ e λt/2 |∇ψ(t, •)|(x).
Taking the infimum over t gives the claim.

We now work out an explicit estimate for ∇ψ(t, •) ∂D,∞ . Let cut(D) be the cut-locus of ∂D, which is a zero-volume closed subset of D such that ρ

∂D := dist(•, ∂D) is smooth in D \ cut(D). Proposition 2.5. Let α ∈ R such that (2.28) 1 2 Lρ ∂ D α.
Then

∇ψ(t, •) ∂D,∞ α + √ 2 √ πt + t 0 1 -e -α 2 s 2 √ 2πs 3 ds α + √ 2 √ πt e -α 2 t 2 + min |α|, α 2 √ 2t √ π , (2.29) and (2.30) ∇ψ(t, •) ∂D,∞ √ 2 √ πt + α + √ t √ 2π α 2
Notice that by [10, Lemma 2.3] the condition 1 2 Lρ ∂D α holds for α defined by (2.6).

Proof. Let x ∈ D and let X t solve SDE (2.17). As shown in [START_REF] Kendall | The radial part of Brownian motion on a manifold: a semimartingale property[END_REF], (ρ ∂D (X t )) t τ D is a semimartingale satisfying

(2.31) ρ ∂D (X t ) = ρ ∂D (x) + b t + 1 2 t 0 Lρ ∂D (X s ) ds -l t , t τ D ,
where b t is a real-valued Brownian motion starting at 0, and l t a non-decreasing process which increases only when X x t ∈ cut(D). Setting ε = ρ ∂D (x), we deduce from (2.31) together with

1 2 Lρ ∂D α, that (2.32) ρ ∂D (X t (x)) Y α t (ε) := ε + b t + αt, t τ D .
Consequently, letting T α (ε) be the first hitting time of 0 by Y α t (ε), we obtain

(2.33) ψ(t, x) P(t < T α (ε)).
On the other hand, since ψ(t,

P(t < T α (ε)) ε α + √ 2 √ πt + t 0 1 -e -α 2 s 2 √ 2πs 3 ds.
It is well known that the (sub-probability) density

f α,ε of T α (ε) is (2.36) f α,ε (s) = ε exp -(ε + αs) 2 /(2s) √ 2πs 3 ,
which can be obtained by the reflection principle for α = 0 and the Girsanov transform for α = 0. Thus

P(t T α (ε)) = ε t 0 exp -(ε + αs) 2 /(2s) √ 2πs 3 ds = ε exp(-αε) t 0 e -α 2 s/2 √ 2πs 3 exp - ε 2 2s ds = exp(-αε) 2t/ε 2 0 e -1/r √ πr 3 exp - α 2 ε 2 r 4 dr, (2.37)
where we have made the change of variable r = 2s/ε 2 . With the change of variable v = 1/r we easily check that (2.38)

∞ 0 r -3/2 e -1/r dr = Γ(1/2) = √ π,
and this allows to write (2.39)

P(t T α (ε)) = exp(-αε) 1 - ∞ 2t/ε 2 e -1/r √ πr 3 dr - 2t/ε 2 0 e -1/r √ πr 3
1 -e -α 2 ε 2 r/4 dr .

As ε → 0, ∞ 2t/ε 2 e -1/r √ r 3 dr = ∞ 2t/ε 2 1 √ r 3 dr + o(ε) = ε √ 2 √ t + o(ε),
and with change of variable s

= 1 2 ε 2 r 2t/ε 2 0 e -1/r √ πr 3 1 -e -α 2 ε 2 r 4 dr = ε t 0 e -ε 2 2s √ 2πs 3 1 -e -α 2 s 2 ds = ε t 0 1 -e -α 2 s 2 √ 2πs 3 ds + o(ε)
by monotone convergence. Combining these with e -αε = 1 -αε + o(ε), we deduce from (2.39) that (2.40)

P(t T α (ε)) = 1 -ε   α + √ 2 √ πt + t 0 1 -e -α 2 s 2 √ 2πs 3 ds   + o(ε)
which yields (2.35).

Next, an integration by parts yields (2.41)

t 0 1 -e -α 2 s 2 √ 2πs 3 ds = α 2 √ 2π t 0 1 √ u e -α 2 u 2 du - √ 2 √ πt 1 -e -α 2 t 2 .
With the change of variable s = |α| u t in the first term in the right we obtain

(2.42) α 2 √ 2π t 0 1 √ u e -α 2 u 2 du = |α| 2t π |α| 0 e -s 2 t 2 ds.
We arrive at

(2.43) f (α) := α + √ 2 √ πt + t 0 1 -e -α 2 s 2 √ 2πs 3 ds = √ 2 √ πt e -α 2 t 2 + α + |α| 2t π |α| 0 e -s
f (0) = √ 2 √ πt , f (0) = 1, f (α) = √ 2t √ π e -α 2 t 2
Using the fact that f (α) -α is even, we also get

(2.45) f (α) = √ 2 √ πt + α + |α| 0 √ 2t √ π e -s 2 t 2 s ds √ 2 √ πt + α + √ t √ 2π α 2 .
which yields (2.30).

Remark 2.6. One could use estimate (2.24) (optimizing the right-hand side with respect to t) together with Lemma 2.4 (again optimizing with respect to t) to estimate ∇φ ∞ in terms of φ ∞ . We prefer to combine the two steps.

Lemma 2.7. Assume Ric V D -K V for some constant K V ∈ R. Let α be determined by (2.28).

(a) If α 0, then for any (φ, λ) ∈ Eig(L),

∇φ ∞ inf t>0 max ε∈[0,1] e (λ+K + V )t 2 ε α + √ 2 √ πt e -α 2 t 2 + min |α|, α 2 √ 2t √ π + 1 -ε t φ ∞ ,
as well as

∇φ ∞ inf t>0 max ε∈[0,1] e (λ+K + V )t/2 ε α + 2 πt + √ t √ 2π α 2 + 1 -ε t φ ∞ and ∇φ ∞ inf t>0 max ε∈[0,1] e (λ+K + V )t/2 ε 2α + 2 πt + 1 -ε t φ ∞ . (b) If α 0, then ∇φ ∞ inf t>0 max ε∈[0,1] e (λ+K + V )t/2 ε 2 πt e -α 2 t 2 + 1 -ε t φ ∞ .
In particular,

∇φ ∞ inf t>0 max ε∈[0,1] e (λ+K + V )t/2 ε 2 πt + 1 -ε t φ ∞ .
Proof. For fixed t > 0 in (2.23), we take h ∈ C 1 ([0, t]; [0, 1]) such that h 0 = 1 and h t = 0. Then, by the martingale property of {N s∧τ D (v)} s∈[0,t] , we obtain

|∇ v φ|(x) = |N 0 (v)| = |EN t∧τ D (v)| = E 1 {t>τ D } e λτ D /2 h τ D ∇φ(X τ D ), Q τ D v -1 {t τ D } e λt/2 φ(X t ) t 0 ḣs Q s v, u s dB s . (2.46)
Note that using (2.20) along with Lemma 2.4 we may estimate

E 1 {t>τ D } e λτ D /2 h τ D ∇φ(X τ D ), Q τ D v E 1 {t>τ D } e λτ D /2 |h τ D | ∇φ ∂D,∞ e K V τ D /2 |v| E 1 {t>τ D } e λτ D /2 |h τ D | φ ∞ ∇ψ(t -τ D , •) ∂D,∞ e λ(t-τ D )/2 e K V τ D /2 |v| = E 1 {t>τ D } |h τ D | φ ∞ ∇ψ(t -τ D , •) ∂D,∞ e λt/2 e K V τ D /2 |v| e (λ+K + V )t/2 φ ∞ E 1 {t>τ D } |h τ D | ∇ψ(t -τ D , •) ∂D,∞ |v| ,
as well as

E 1 {t τ D } e λt/2 φ(X t ) t 0 ḣs Q s v, u s dB s e λt/2 φ ∞ P{t τ D } 1/2 t 0 | ḣs | 2 e K V s ds 1/2 .
Taking

h s = t -s t , s ∈ [0, t],
we obtain thus from (2.46)

|∇φ(x)| e (λ+K + V )t/2 t φ ∞ E 1 {t>τ D } (t -τ D ) ∇ψ(t -τ D , •) ∂D,∞ + e λt/2 φ ∞ P{t τ D } 1/2 1 t e K + V t -1 K + V 1/2 . Note that e K + V t -1 K + V te K + V t .
(i) By (2.29), assuming that α 0, we have on {t > τ D }:

t -τ D t ∇ψ(t -τ D , •) ∂D,∞ α t -τ D t + √ 2 √ π √ t -τ D t + t -τ D t t-τ D 0 1 -e -α 2 s 2 √ 2πs 3 ds α + √ 2 √ πt + t 0 1 -e -α 2 s 2 √ 2πs 3 ds α + √ 2 √ πt e -α 2 t 2 + min α, α 2 √ 2t √ π .
Thus, letting ε = P(t > τ D ), we obtain

|∇φ(x)| e (λ+K + V )t/2 φ ∞ ε α + √ 2 √ πt e -α 2 t 2 + min α, α 2 √ 2t √ π + 1 -ε t .
(ii) Still under the assumption α 0, this time using estimate (2.30), we have on {t > τ D }:

∇ψ(t -τ D , •) ∂D,∞ √ 2 π(t -τ D ) + α + √ t -τ D √ 2π α 2 ,
and thus letting ε = P(t > τ D ), we get

|∇φ(x)| e (λ+K + V )t/2 t φ ∞ E 1 {t>τ D } 2 π √ t -τ D + α(t -τ D ) + (t -τ D ) 3/2 √ 2π α 2 + e λt/2 φ ∞ P{t τ D } 1/2 1 t e K + V t -1 K + V 1/2 e (λ+K + V )t/2 φ ∞ ε 2 πt + α + √ t √ 2π α 2 + 1 -ε t .
(iii) In the case α 0, we get from (2.29) in a similar way:

|∇φ(x)| e (λ+K + V )t/2 φ ∞ ε √ 2 √ πt e -α 2 t 2 + 1 -ε t .
This concludes the proof of Lemma 2.7.

Proposition 2.8. We keep the assumptions of Lemma 2.7.

(a) If α 0, then for any (φ, λ) ∈ Eig(L),

∇φ ∞ √ e max ε∈[0,1]    ε   α + 2(λ + K + V ) √ π exp - α 2 2(λ + K + V ) + min |α|, √ 2α 2 π(λ + K + V )   + √ 1 -ε (λ + K + V ) φ ∞ ,
as well as

∇φ ∞ √ e max ε∈[0,1]    ε   α + 2(λ + K + V ) √ π + α 2 2π(λ + K + V )   + √ 1 -ε (λ + K + V )    φ ∞ and ∇φ ∞ √ e max ε∈[0,1]    ε   2α + 2(λ + K + V ) √ π   + √ 1 -ε (λ + K + V )    φ ∞ (b) If α 0, then ∇φ ∞ √ e max ε∈[0,1]    ε 2(λ + K + V ) √ π exp - α 2 2(λ + K + V ) + √ 1 -ε (λ + K + V )    φ ∞ . Proof. Take t = 1/(λ + K + V ) in Lemma 2.7.
We are now ready to complete the proof of Theorem 2.2.

Proof of Theorem 2.2. The claims of Theorem 2.2 (with the exception of estimate (2.15)) follow directly from the inequalities in Proposition 2.8 together with the fact that for any A, B 0,

(2.47) max ε∈[0,1] εA + √ 1 -εB = B 1 {B>2A} + A + B 2 4A 1 {B 2A} .
Finally, to check (2.15) we may go back to (2.24) from where we have

∇φ ∞ εe (λ+K V ) + t/2 ∇φ ∂D,∞ + √ 1 -ε e λt/2 φ ∞ t 0 | ḣs | 2 e K V s ds 1/2 . Taking h s = e -K V t -e -K V s e -K V t -1 , s ∈ [0, t],
we obtain

∇φ ∞ inf t>0 max ε∈[0,1] εe (λ+K V ) + t/2 ∇φ ∂D,∞ + φ ∞ e λt/2 √ 1 -ε K V 1 -e -K V t 1/2 . Noting that K V 1 -e -K V t K + V 1 -e -K + V t t -1 e K + V t ,
and taking t = (K

+ V + λ) -1 we obtain ∇φ ∞ √ e max ε∈[0,1] ε ∇φ ∂D,∞ + (1 -ε)(λ + K + V ) φ ∞ .
Applying Lemma 2.4 and Proposition 2.5 with t = 1/λ, we arrive at

∇φ ∞ φ ∞ max ε∈[0,1] eε α + √ 2λ √ π e -α 2 2λ + |α| ∧ α 2 √ 2 √ πλ + e(1 -ε)(λ + K + V ) .
The proof is then finished as above with observation (2.47).

3 Proof of Theorem 1.2

As in Section 2, we consider L = ∆ + ∇V and let Eig N (L) be the set of the corresponding nontrivial eigenpairs for the Neumann problem of L. We also allow ∂D = ∅, then we consider the eigenproblem without boundary. We first consider the convex case, then extend to the general situation. In this

Q t exp 1 2 t 0 K V (X s )ds + t 0 δ(X s )d s , s 0,
such that for any t > 0 and h ∈ C 1 ([0, t]) with h(0) = 0, h(t) = 1, there holds

(3.3) ∇P t f = E f (X t ) t 0 h (s)Q s dB s , f ∈ B b (D).

The case with convex or empty boundary

In this part we assume that ∂D is either convex or empty. When ∂D is empty, D is a Riemannian manifold without boundary and Eig N (L) denotes the set of eigenpairs for the eigenproblem without boundary. In this case, if Ric V K V for some constant K V ∈ R, then λ + K V 0 for (φ, λ) ∈ Eig N (L), see for instance [START_REF] Wang | Application of coupling method to the Neumann eigenvalue problem[END_REF].

Theorem 3.2. Assume that ∂D is either convex or empty.

(1) If the curvature-dimension condition (2.1) holds, then for any (φ, λ) ∈ Eig N (L),

∇φ 2 ∞ λ 2 φ 2 ∞ n(λ + K) λ λ + K λ/K λ 2 φ 2 ∞ ne(λ + K + )
.

(

) If Ric V D -K V for some constant K V ∈ R, then for any (φ, λ) ∈ Eig N (L), ∇φ 2 ∞ φ 2 ∞ 2(λ + K V ) π 1 + K V λ λ/K V 2e(λ + K + V ) π . 2
Proof. (a) We start by establishing the lower bound estimate. By Itô's formula, for any (φ, λ) ∈ Eig N (L) we have

(3.4) d|∇φ| 2 (X t ) = 1 2 L|∇φ| 2 (X t ) dt + 2 I ∂D (∇φ, ∇φ)(X t ) d t + dM t , t 0,
where t is the local time of X t at ∂D, which is an increasing process. Since I ∂D 0, and since (2.1) and Lφ = -λφ imply

1 2 L|∇φ| 2 -(K + λ)|∇φ| 2 + λ 2 n φ 2 , we obtain d|∇φ| 2 (X t ) λ 2 n φ 2 -(λ + K)|∇φ| 2 (X t ) dt + dM t , t 0.
Noting that for X 0 = x ∈ D we have

E[φ(X s ) 2 ] (E[φ(X s )]) 2 = e -λs φ(x) 2 ,
we arrive at

e (λ+K)t ∇φ 2 ∞ e (λ+K)t E[|∇φ| 2 (X t )] λ 2 n t 0 e (λ+K)s E[φ 2 (X s )] ds λ 2 n t 0 e Ks φ(x) 2 ds = λ 2 (e Kt -1) nK φ(x) 2 .
Multiplying by e -(λ+K)t , choosing t = 1 K log(1 + K λ ) (noting that λ + K 0, in case λ + K = 0 taking t → ∞), and taking the supremum over x ∈ D, we finish the proof of (1).

(b) Let ∂D be convex and Ric V D -K V for some constant K V . Then Theorem 3.1 holds for δ = 0, so that

σ t := E t 0 |h (s)| 2 Q s 2 ds 1/2 t 0 |h (s)| 2 e K V s ds 1/2 . Taking h(s) = s 0 e -K V r dr t 0 e -K V r dr we obtain σ t K V 1 -e -K V t 1/2 . Therefore, ∇P t f ∞ f ∞ E t 0 h (s)Q s dB s f ∞ 2 √ 2π σ t ∞ 0 s exp - s 2 2σ 2 t ds = f ∞ σ t √ 2 √ π , t > 0, f ∈ B b (D). (3.5)
Applying this to (φ, λ) ∈ Eig N (L), we obtain

e -λt/2 |∇φ| φ ∞ σ t √ 2 √ π φ ∞ 2K V π(1 -e -2K V t ) 1/2 , t > 0. Consequently, λ + K V 0. Taking t = 1 K V log(1 + K V λ ) as above, we arrive at ∇φ 2 ∞ φ 2 ∞ 2(λ + K V ) π 1 + K V λ λ/K V .

The non-convex case

When ∂D is non-convex, a conformal change of metric may be performed to make ∂M convex under the new metric; this strategy has been used in [START_REF] Cheng | Functional inequalities on manifolds with non-convex boundary[END_REF][START_REF] Wang | Estimates of the first Neumann eigenvalue and the log-Sobolev constant on non-convex manifolds[END_REF][START_REF] Wang | Harnack inequalities on manifolds with boundary and applications[END_REF][START_REF] Wang | Semigroup properties for the second fundamental form[END_REF] for the study of functional inequalities on non-convex manifolds. According to [15, Theorem 1.2.5], for a strictly positive function f ∈ C ∞ ( D) with I ∂D +N log f | ∂D 0, the boundary ∂D is convex under the metric f -2 •, • . For simplicity, we will assume that f 1. Hence, we take as class of reference functions

D := f ∈ C 2 ( D) : inf f = 1, I ∂D +N log f 0 .

Assume (2.1) and Ric

V D -K V for some constants n d and K, K V ∈ R. For any f ∈ D and ε ∈ (0, 1), define c ε (f ) := sup D 4ε|∇ log f | 2 1 -ε + εK + (1 -ε)K V -2L log f .
We let λ N 1 be the smallest non-trivial Neumann eigenvalue of -L. The following result implies λ 1 -c ε (f ). (1) If (2.1) and Ric V D -K V hold for some constants n d and K, K V ∈ R. Then for any non-trivial (φ, λ) ∈ Eig N (L), we have λ + c ε (f ) 0 and

f 2 ∞ ∇φ 2 ∞ φ 2 ∞ sup ε∈(0,1) ελ 2 n(λ + c ε (f )) λ λ + c ε (f ) λ/cε(f ) sup ε∈(0,1) ελ 2 ne(λ + c ε (f ) + ) . (2) Let Ric V D -K V for some K V ∈ C( D), and
K(f ) = sup D 2|∇ log f | 2 + K V -L log f .
Then for any non-trivial (φ, λ) ∈ Eig N (L), we have λ + K(f ) 0 and

∇φ 2 ∞ φ 2 ∞ f 2 ∞ 2(λ + K(f )) π 1 + K(f ) λ λ/K(f ) 2e(λ + K(f ) + ) π .
Proof. Let f ∈ D and (φ, λ) ∈ Eig N (L).

(1) On ∂D we have

N (f 2 |∇φ| 2 ) = (N f 2 )|∇φ| 2 + f 2 N |∇φ| 2 = f 2 (N log f 2 )|∇φ| 2 + 2 I ∂D (∇φ, ∇φ) = 2f 2 (N log f )|∇φ| 2 + I ∂D (∇φ, ∇φ) 0. (3.6)
Next, by the Bochner-Weitzenböck formula, using that Ric V D -K V and Lφ = -λφ, we observe Combining this with (2.5), for any ε ∈ (0, 1), we obtain

f 2 2 L|∇φ| 2 + ∇f 2 , ∇|∇φ| 2 -f 2 (εK + (1 -ε)K V + λ)|∇φ| 2 + ελ 2 n f 2 φ 2 + (1 -ε)f 2 Hess φ 2 HS -2 Hess φ HS × |∇f 2 | × |∇φ| - |∇ log f 2 | 2 1 -ε + εK + (1 -ε)K V + λ f 2 |∇φ| 2 + ελ 2 n f 2 φ 2 .
Combining this with (3.6) and applying Itô's formula, we obtain

d(f 2 |∇φ| 2 )(X t ) m = 1 2 L(f 2 |∇φ| 2 )(X t ) dt + N (f 2 |∇φ| 2 )(X t ) d t - 1 2 f 2 L|∇φ| 2 + 2 ∇f 2 , ∇|∇φ| 2 + |∇φ| 2 Lf 2 (X t ) dt ελ 2 n f 2 φ 2 - |∇ log f 2 | 2 1 -ε + εK + (1 -ε)K V + λ -f -2 Lf 2 f 2 |∇φ| 2 (X t ) dt ελ 2 n φ 2 -λ + c ε (f ) f 2 |∇φ| 2 (X t ) dt.
Hence, for X 0 = x ∈ D, f 2 ∞ ∇φ 2 ∞ e (λ+cε(f ))t E e cε(f )t (f 2 |∇φ| 2 )(X t ) ελ 2 n t 0 e (λ+cε(f ))s E[φ(X s ) 2 ] ds ελ 2 n t 0 e cε(f )s φ(x) 2 ds = ελ 2 (e cε(f )t -1) nc ε (f ) φ(x) 2 .

This implies λ + c ε (f ) 0 and

f 2 ∞ ∇φ 2 ∞ φ 2 ∞ sup t>0
ελ 2 e -λt -e -(λ+cε(f ))t nc ε (f ) = ελ 2 n(λ + c ε (f ))

λ λ + c ε (f ) λ/cε(f ) ελ 2 ne(λ + c ε (f ) + )
.

(2) The claim could be derived from [2, inequality (2.12)]. For the sake of completeness we include a sketch of the proof. For any p > 1, let

K p (f ) = sup D K V + p|∇ log f | 2 -L log f .
Note that p|∇ log f | 2 -L log f = p -1 f p Lf -p . Since f ∈ D implies I ∂D -N log f , we have Therefore, repeating step (b) in the proof of Theorem 3.2 with K(f ) replacing K V , we finish the proof of (2).

Q t 2 exp t 0 K V (X s ) ds + 2 t 0 N log f (X s ) d s exp K p (f )t

Theorem 3 . 1 (

 31 [START_REF] Wang | Analysis for Diffusion Processes on Riemannian Manifolds[END_REF]). Let Ric V D -K V and I ∂D -δ for some K V ∈ C( D) and δ ∈ C(∂D). Then there exists a R d ⊗ R d -valued adapted continuous process Q s with(3.2)

Theorem 3 . 3 .

 33 Let f ∈ D.

2 φ 2 HS

 22 L|∇φ| 2 -∇Lφ, ∇φ -λ|∇φ| Hess -(K V + λ)|∇φ| 2 .

= f -p (x) 1 ,Q t 2 eds f 2 ∞ t 0 |h

 1220 since f 1 by assumption. This shows that E Kp(f )t f p ∞ , t 0. Combining this for p = 2 with Theorem 3.1 and denoting K(f ) = K 2 (f ), we obtainσ 2 t := E t 0 |h (s)| 2 Q s 2(s)| 2 e K(f )s ds.

  V D = Ric D -K is equivalent to (2.1) with n = d. More sophisticated upper bounds are given below in Theorem 2.2. By (1.8), if D is convex with non-negative Ricci curvature then (1.1) holds with

  . Using (2.19), we see by Itô's formula and formula (2.21) that dn

  section, P t denotes the (Neumann if ∂D = ∅) semigroup generated by L/2 on D. Let X t be the corresponding (reflecting) diffusion process which solves the SDE ) dt + N (X t ) d t , where B t is a d-dimensional Euclidean Brownian motion, u t the horizontal lift of X t onto the orthonormal frame bundle, and t the local time of X t on ∂D.We will apply the following Bismut type formula for the Neumann semigroup P t , see [15, Theorem 3.2.1], where the multiplicative functional process Q s was introduced in[START_REF] Hsu | Multiplicative functional for the heat equation on manifolds with boundary[END_REF].

	(3.1)	dX t = u t • dB t +	1 2	∇V (X t

  Proceeding as in the proof of [15, Corollary 3.2.8] or [2, Theorem 2.4], we get

	f -p ∞ E exp -	1 2

exp -1 p t 0 (f p Lf -p )(X s ) ds + 2 t 0 N log f (X s ) d s . As df -p (X t ) m = 1 2 Lf -p (X t ) dt + N f -p (X t ) d t = -f -p (X t ) -1 2 f p Lf -p (X t ) dt + pN log f (X t ) d t ,

we obtain that

M t := f -p (X t ) exp -1 2 t 0 f p (X s )Lf -p (X s ) ds + p t 0 N log f (X s ) d s is a (local) martingale. t 0 f p (X s )Lf -p (X s ) ds + p t 0 N log f (X s ) d s E f -p (X t ) exp -1 2 t 0 f p (X s )Lf -p (X s ) ds + p t 0 N log f (X s ) d s

This work was supported by Fonds National de la Recherche Luxembourg (Grant No. O14/7628746 GEOMREV) and the University of Luxembourg (Grant No. IRP R-AGR-0517-10/AGSDE. Feng-Yu Wang acknowledges support in part by NNSFC (11771326, 11431014).

1


David Poirier-Quinot
email: david.poirier-quinot@upmc.fr

Brian F G Katz

David Poirier

Impact of HRTF individualization on player performance in a VR shooter game I

. Results indicate significant performance improvement (speed and movement efficiency) with best-match HRTF binaural rendering sessions.

Introduction

"Binaural hearing" refers to the capability of integrating information from the two ears to perceive a sound in three-dimensional space (azimuth, elevation, and distance). Psychophysical studies have shown that various mechanisms are involved in the human auditory system for sound localization [START_REF] Blauert | Spatial Hearing: The psychophysics of human sound localization[END_REF]. To infer the angular direction of a sound source, these mechanisms rely on directiondependent audio cues, resulting from the propagation of an acoustic wave from the source to both ears. Using digital signal processing, these cues can be applied to any audio input to simulate a sound object at a virtual position in a listener's 3D auditory space (experienced over headphones). The set of these direction-dependent cues for a given person is typically referred to as a Head Related Transfer Function (HRTF).

HRTFs are individual, directly resulting from the interactions between a person's morphology and an impinging acoustic wave during its propagation around the head [START_REF] Blauert | Spatial Hearing: The psychophysics of human sound localization[END_REF]. Individuals listening to a binaural audio scene rendered using their own HRTF will perceive each of its components with more spatial precision than those presented with a random HRTF set [START_REF] Begault | Direct comparison of the impact of head tracking, reverberation, and individualized headrelated transfer functions on the spatial perception of a virtual speech source[END_REF]. Various methods have been proposed to select a "best-match" HRTF from an existing database [START_REF] Seeber | Subjective selection of non-individual head-related transfer functions[END_REF][START_REF] Zotkin | HRTF personalization using anthropometric measurements[END_REF], as measuring an individual's actual HRTF is a demanding operation [START_REF] Carpentier | Measurement of a head-related transfer function database with high spatial resolution[END_REF]. This process of selection and use of a best-match HRTF for binaural synthesis is here referred to as HRTF individualization.

This study is part of a larger research project aiming to characterize the impact of binaural rendering quality in the context of different Virtual Reality (VR) application contexts. This study focuses on the impact of HRTF individualization on performance in the context of a VR shooter game. While the core of the gameplay is built around an audio-visual localization task, it extends the existing literature [START_REF] Wenzel | Localization using nonindividualized head-related transfer functions[END_REF][START_REF] Xu | Individualization of head-related transfer function for threedimensional virtual auditory display: a review[END_REF][START_REF] Härmä | Personalization of headphone spatialization based on the relative localization error in an auditory gaming interface[END_REF][START_REF] Mehra | Comparison of localization performance with individualized and non-individualized headrelated transfer functions for dynamic listeners[END_REF] in that the final experience is truly a game, where participants are placed under increasingly difficult time and performance constraints. Besides improving localization accuracy, the underlying hypothesis of this study is that using individualized HRTFs will result in participants more readily relying on their reflexes to e.g. dodge enemies or sightlessly aim when incoming targets arrive too quickly for the basic sequence: hear → search → f ocus → aim → shoot.

Experimental design

The experiment consisted of two sequential parts. The objective of Part 1 was to identify the best and worst match HRTFs from a subset of 7 for each participant. Part 2 was the VR shooter game. A total of 30 participants undertook the experiment (13 female, mean age 33.2 ± 11.4 years).

HRTF classification

The HRTF subset database was assembled from the LISTEN database, defined from a "perceptually orthogonal" optimized HRTF collection [START_REF] Katz | Perceptually based head-related transfer function database optimization[END_REF]. Per-participant best and worst match HRTF sets were selected based on the method elaborated in [START_REF] Andreopoulou | Subjective HRTF evaluations for obtaining global similarity metrics of assessors and assessees[END_REF], establishing a classification based on perceptual-space distance between a spatialized audio trajectory and a described reference. Two trajectories were presented: horizontal plane (12 angles [0°:30°:330°] ) and median plane (19 angles [-45°:15°:225°]), as illustrated in Fig. 1.

Each audio trajectory was generated with the 7 HRTFs from the subset. Participants were instructed to rate the 7 resulting versions of each trajectory on a fixed 9-point scale. They were encouraged to distribute their notations on that scale, and required to indicate at least one best [START_REF] Härmä | Personalization of headphone spatialization based on the relative localization error in an auditory gaming interface[END_REF] and one worst (1) match. Both median and horizontal rating sessions were repeated 3 times, to take into account HRTF rating consistency [START_REF] Andreopoulou | Investigation on Subjective HRTF Rating Repeatability[END_REF]. Participants completed the study in a listening booth, ambient noise level < 30 dBA using Sennheiser HD600 headphones and RME Fireface UC audio interface.

VR Shooter Game

During the VR shooter game, participants were equipped with an Oculus CV1 Head Mounted Display (HMD), a pair of headphones (those of the CV1), and a pair of hand tracked devices (Oculus Touch controllers). The game started with participants immersed in a virtual scene, standing on a 0.5 m radius platform mounted on a pole at the center of a 20 m radius spherical structure. Enemy targets could "spawn" from any of the 29 evenly distributed holes in the structure, flying in straight lines towards the participant until collision, either with a bullet or the participant. Enemy targets emitted specific event-based sounds for: spawning, launching, flight, and collision. All sounds were spatialized using the freely available Anaglyph binaural audio engine v0.9 [START_REF] Poirier-Quinot | The Anaglyph binaural audio engine[END_REF]. Anechoic conditions were employed, no room effect was included to keep the study's focus on HRTF effects. Participants were instructed to shoot at the incoming targets using the pair of hand-held blasters, the avatar representations of the hand tracked devices in the virtual scene, destroying as many as possible, as fast as possible, in the given time limit. If unable to shoot at an incoming target (e.g. when the game accelerated), participants where advised to try and dodge them to avoid collisions.

The game was designed using the Unity v2017.3.0 game engine with modelled assets designed in Blender v2.79. The OSC (Open Sound Control) protocol [START_REF] Wright | Open Sound Control: an enabling technology for musical networking[END_REF] was used for communications between Unity and the Anaglyph engine running as a VST in Cycling'74 Max v7.3. Figure 2 depicts the game setup and the VR scene.

A video extract showing a game session is available 1 .

1 https://youtu.be/q6muds1qW-w A short training session introduced the controls and the difficulty level mechanism, implemented so that the overall game dynamic (enemy spawn interval, flight speed, etc.) increased as the game progressed and participant's skill ("in-game level" below) improved. The 5 min game was played in two sessions, once with participant's best match HRTF, once with the worst. Best/worst match presentation order was evenly balanced among participants, resulting in two groups. The game was kept short to avoid fatigue on this rather demanding task (see video extract).

Preliminary Results

Performance assessment was based on 3 metrics, calculated from sessions logs: in-game level, spawn-spot reaction time and spawn-spot travelled angular distance.

The in-game level was related to the number of enemies destroyed versus those that hit participants: increasing one unit for every three consecutive kills, decreasing one unit for every two consecutive fails.

The spawn-spot reaction time corresponded to the time interval between the spawn of a target and its entering the visual field of view, defined as a 50°cone centered around the current forward view axis. The event of seeing the target, rather than destroying it, was chosen so as to remove the impact of skill at aiming and destroying targets from the analysis (being independent of the acoustic rendering quality). Targets spawned in the current field of view were discarded from spawn-spot reaction time analysis. For targets that never entered the field of view, the spawn-to-collision time was used as the spawn-spot reaction time. For events where participants destroyed the target without seeing it (representing 0.3% of the total number of target destroyed), the spawn-shoot time was used as the spawn-spot reaction time.

The associated spawn-spot travelled angular distance metric corresponds to the angular distance traversed by the participant's head from spawn to spot events. This last metric represented movement efficiency, and served to differentiate between participants using binaural cues to localize targets and those randomly looking around [START_REF] Katz | The use of 3D-audio in a multi-modal teleoperation platform for remote driving/supervision[END_REF]. Table 1 summarizes the independent and dependent variables of the experimental protocol.

Result significance was assessed using a Wilcoxon signed rank test (p-value threshold of 0.05) as all compared paired-sample distributions proved to follow a non-normal (skewed) distribution.

HRTF Classification

Results of the HRTF ratings of Part 1 are summarized in Fig. 3, focusing on the scores obtained by each participant's best and worst HRTF match for both trajectories. Participants were consistent in their classification with regards to these extrema. As audio sources in Part 2 of the experiment were to arrive from all directions, an average best-and worst-HRTF match across trajectories was established for each participant. The rating statistics for selected best-and worst-HRTF matches are shown in Fig. 3. Participants proved consistent in their ratings to clearly distinguish between best and worst match for both horizontal and median trajectories. As reported in [START_REF] Andreopoulou | Subjective HRTF evaluations for obtaining global similarity metrics of assessors and assessees[END_REF], participant HRTF ratings for the horizontal and the median trajectories were not correlated. This explains the observed decrease in rating values for the trajectory mean results as compared to the individual horizontal and median plane trajectory ratings. For almost all participants, average-best and average-worst HRTF scores remained sufficiently distinct to distinguish both populations (Fig. 3c).

VR Shooter Game

Figure 4 illustrates the evolution of game level during the course of each session. As can be seen, large inter-participant differences can be observed for the VR shooter game results.

Statistical analysis across participants

Analyzing the average statistical metrics per participant between the two sessions across both groups, mean spawn-spot reaction time significantly decreased between Sessions 1 and 2 (1.40 s vs. 1.35 s). Mean spawn-spot angular distance traversed (averaged per participant's session) also significantly decreased between both session (155°vs. 144°). No significant differences in mean level were observed between sessions. These results highlight the game task learning effect independent of the HRTF condition.

Repeating the same analysis as a function of HRTF across both groups showed no significant impact of the HRTF on these metrics. These results would suggest at first glance that there was no benefit to using individual HRTFs in the VR shooter game.

Statistical analysis by event

Combining the results of each event (from target spawn to target destruction) for all participants, the event-wise analysis also reflects the impact of the game learning effect on performance for spawn-spot angular distance traversed (154.7°vs. 143.4°) and reaction time (1.38 s vs 1.34 s). Contrary to mean participant results (see Section 3.2.1), event-wise statistics show that the impact of HRTF quality on reaction time (1.39 s vs. 1.34 s) and angular distance traversed (151°vs. 147°) is significant.

HRTF×Session interaction analysis

Subsequent analysis examines the interaction effect of HRTF order. The event-wise mean and 95% confidence intervals for reaction time and angular distance traversed are shown in Fig. 5. These results show a clear interaction effect, with an advantage to using best-match HRTF in Session 2. Analysis of eventwise reaction time and angular distance traversed by HRTF×session shows that:

• Session 1: Participants starting with their best match HRTF showed performances comparable to those of participants who started with their worst match.

• Session 2: Participants using their best-match HRTF exhibit a clear improvement in performance.

• Session 2: Participants using their worst-match HRTF showed no improvement.

These results suggest that Group 1 (who commenced the game with their worst-match HRTF) was able to benefit from their best-match HRTF after an initial game training period in Session 1. Commencing the game with a best-match HRTF (Group 2) did not improve participants performance immediately, as there was an apparent game task learning effect which appears to supersede that of spatial audio rendering quality. This leads to a potential conclusion that a worst match HRTF negates the benefit that should result from training. Further tests are currently underway to examine this question.

Conclusion

We have presented preliminary results of an experiment designed to assess the impact of individualized binaural rendering on player performance in the context of a VR "shooter game". Participants performed two game sessions, using once their best-match HRTF and once using their worst-match HRTF. During the game, participants had to locate and shoot at successive enemy targets approaching from random directions within a sphere. Results indicate that the use of a best-match HRTF improved participants performance regarding the time they needed to localise the targets and the angular distance they travelled before doing so (average of 1.34 s and 147°with best-HRTF vs. 1.39 s and 151°w ith worst).

Preliminary participant-based analysis has shown promising results concerning the creation of an overall metric to rate participants "affinity" with binaural hearing. Using this metric, the authors are investigating how participants who focused on the auditory scene (Part 1) and were comfortable with VR game mechanisms (Part 2) can be identified from the participant pool in order to examine the benefit of HRTF individualization for this sub-group. The hypothesis of this ongoing analysis is that the benefits of HRTF individualization for this sub-group of "aware listeners" exceed those of the average participant.

The impact of the learning effect along with the research for a metric to evaluate the participants receptiveness to binaural hearing individualization point towards an extension of this study. The extended study will consider roughly the same number of participants but exposing them longer / on repeated occasions to the VR game until the uncontrolled impact of the learning effect can be discarded. A control group will be added to this second study to fully understand the impact of the learning effect during the early stages of the game.

A more thorough statistical analysis on participants results will then be conducted, absent in this preliminary presentation.

Fig. 1 :

 1 Fig. 1: Descriptions for HRTF quality ratings: horizontal (left) and median (right) plane trajectories indicating the start/stop position and trajectory direction (-→).

Fig. 2 :

 2 Fig. 2: Game scene overview: (upper-left) overall view of the virtual environment, (upper-right) focus on the platform atop which participants stand during the game, (lower-left) participant in the VR room, (lower-middle) virtual environment during gameplay, and (lower-right) in-game screenshot,

Fig. 3 :

 3 Fig. 3: Results of the HRTF classification task for all participants. The reported rating value corresponds to the average normalized rank given by participants to their best/worst HRTF. A value of 0 (resp. 1) indicates that the HRTF was always rated as the least (resp. most) representative of the described trajectory across the 3 rating repetitions. Scores for the best and worst HRTF matches for the (a) horizontal and (b) median trajectory. (c) Combined mean score results for the selected best and worst match HRTF.

Fig. 4 :

 4 Fig. 4: Evolution of each participants' level throughout the game (from 6 to approx. 30). Each pair of bars represents Session 1 & 2 of a participant. Participants are separated according to group, sorted (top to bottom) based on individual maximum session-wise mean level.

Fig. 5 :

 5 Fig. 5: Reaction time and traversed angular distance (mean and 95% CI) across session and HRTF for each event.

Table 1 :

 1 Independent and dependent variables of the experimental protocol.

	Independent variables
	Participant ID	30	random variable
	HRTF ID	2	best, worst
	Session ID	2	first, second
	Dependent variables
	angular distance	event-wise	raw and norm
	time	event-wise	raw and norm
	mean level	session-wise	raw and norm

Acknowledgements

This work was funded in part through a fundamental research collaboration partnership between Sorbonne Université, CNRS, Institut ∂ 'Alembert and Oculus VR, LLC.


Victor Codocedo
email: victor.codocedo@inria.fr

Jaume Baixeries

Mehdi Kaytoue

Amedeo Napoli

Characterizing Covers of Functional Dependencies using FCA

Functional dependencies (FDs) can be used for various important operations on data, for instance, checking the consistency and the quality of a database (including databases that contain complex data). Consequently, a generic framework that allows mining a sound, complete, non-redundant and yet compact set of FDs is an important tool for many different applications. There are different definitions of such sets of FDs (usually called cover).

In this paper, we present the characterization of two different kinds of covers for FDs in terms of pattern structures. The convenience of such a characterization is that it allows an easy implementation of efficient mining algorithms which can later be easily adapted to other kinds of similar dependencies. Finally, we present empirical evidence that the proposed approach can perform better than state-ofthe-art FD miner algorithms in large databases.

Introduction

Functional Dependencies (FDs) are a keystone of the relational database model, since they allow to check the consistency and maintain the quality of a database [START_REF] Fan | Dependencies revisited for improving data quality[END_REF][START_REF] Fan | Foundations of Data Quality Management[END_REF][START_REF] Fan | Data quality: From theory to practice[END_REF], and to guide the database design [START_REF] Mannila | The Design of Relational Databases[END_REF]. In addition, they have been used to study information integration in the Web of data with varying degrees of quality [START_REF] Yu | Extending functional dependency to detect abnormal data in RDF graphs[END_REF][START_REF] Yu | Detecting abnormal semantic web data using semantic dependency[END_REF], or to check the completeness in DBpedia [START_REF] Alam | Mining definitions from RDF annotations using formal concept analysis[END_REF]. Therefore, the computation of a succinct representation of a set of FDs (usually refered to as a cover), is of interest to various fields of knowledge discovery and representation, specially, if this computation can easily be extended to other kinds of dependencies.

The computation of covers for FDs is a popular topic in database literature. As a reference, in [START_REF] Papenbrock | Functional Dependency Discovery: An Experimental Evaluation of Seven Algorithms[END_REF], seven algorithms to mine FDs and compute their covers are reviewed and grouped into three families: lattice transversal algorithms, difference/agree sets algorithms, and dependency induction algorithms. The characterization of FDs with FCA and pattern structures has also be presented in [START_REF] Baixeries | Computing Functional Dependencies with Pattern Structures[END_REF] which in turn, have been generalized to other types of FDs [START_REF] Codocedo | Characterization of Order-like Dependencies with Formal Concept Analysis[END_REF]. For a more detailed review on the characterization of FDs and FCA, see [START_REF] Baixeries | Characterizing Functional Dependencies in Formal Concept Analysis with Pattern Structures[END_REF].

In this paper, we characterize these representations of FD covers using pattern structures, an extension of FCA dealing with complex object representations [START_REF] Kuznetsov | Galois Connections in Data Analysis: Contributions from the Soviet Era and Modern Russian Research[END_REF]. On the one hand, in Section 3.2 we discuss on the relation between the Stem Base of implications [START_REF] Ganter | Conceptual Exploration[END_REF] with the Minimal Cover of dependencies, a sound, complete, non-redundant set of FDs that has minimum cardinality w.r.t. any other equivalent cover. Our main contribution shows that the latter can be characterized by pseudo-extents of a partition pattern structure.

On the other hand, in Section 3.1 we adapt the definition of a canonical direct basis of implications with proper premises [START_REF] Bertet | The multiple facets of the canonical direct unit implicational basis[END_REF][START_REF] Ryssel | Fast algorithms for implication bases and attribute exploration using proper premises[END_REF] to the formalism of pattern structures, in order to prove that this basis is equivalent to a reduced non-redundant cover of FDs.

Finally, in Section 5 we empirically compare these two ways of computing a cover for a set of FDs with the algorithm TANE [START_REF] Huhtala | TANE: An Efficient Algorithm for Discovering Functional and Approximate Dependencies[END_REF]. This algorithm is one of the most popular FD mining algorithms and according to [START_REF] Papenbrock | Functional Dependency Discovery: An Experimental Evaluation of Seven Algorithms[END_REF], it is the base for the family of "lattice transversal algorithms" and serves as the base to compare our proposal with a state-of-the-art algorithm for computing covers for FDs.

Theoretical Background

Let U be a set of attributes, and let Dom be a set of values (a domain). For the sake of simplicity, we assume that Dom is a numerical set. A tuple t is a function t : U Þ Ñ Dom, and a table T is a set of tuples. Usually a table is represented as a matrix, as in Table 1, where the set of tuples (or objects) is T " t t 1 , t 2 , . . . , t 7 u and U " t a, b, c, d, e u is the set of attributes. We use table, dataset, set of tuples as equivalent terms. We overload the functional notation of a tuple in such a way that, given a tuple t P T , we say that tpXq (for all X Ď U) is a tuple with the values of t in the attributes x i P X:

tpXq " xtpx 1 q, tpx 2 q, . . . , tpx n qy

For example, we have that t 2 pt a, c uq " xt 2 paq, t 2 pcqy " x2, 1y. In this article, the set notation is dropped: instead of t a, b u we use ab.

Functional Dependencies and their covers

Definition 1 ([20]). Let T be a set of tuples, and X, Y Ď U. A functional dependency (FD) X Ñ Y holds in T if: @t, t 1 P T : tpXq " t 1 pXq ùñ tpY q " t 1 pY q For instance, the functional dependency d Ñ e holds in T , whereas the functional dependency e Ñ d does not hold since t 4 peq " t 5 peq but t 4 pdq ‰ t 5 pdq.

For a given set of functional dependencies F , we can use the three Armstrong's axioms (reflexivity, augmentation and transitivity) to derive a larger set of FDs [START_REF] Mannila | The Design of Relational Databases[END_REF]. We will call F ˚the set of FDs derived from F by reflexivity and augmentation, and F the set of FDs derived by reflexivity augmentation and transitivity. Two sets of FDs F and H are said to be equivalent F " H ðñ F `" H `.

Let F be a set of FDs from a database with tuples T . F is said to be sound if all FDs in F hold in T . In addition, F is said to be complete if all FDs that hold in T can be derived from F . Let X Ñ Y be any FD in F , then F is said to be non-redundant if

F ztX Ñ Y u ı F for any X Ñ Y . Additionally, F is said to be non-redundant w.r.t. augmentation iff pF ztX Ñ Y uq ˚‰ F Å set F is said to be left-reduced if @X Ñ Y P F and Z Ă X we have that pF ztX Ñ Y uq Y tZ Ñ Y u ı F . Dually, it is said to be right-reduced if @X Ñ Y P F and Z Ă Y we have that pF ztX Ñ Y uq Y tX Ñ Zu ı F . F is said to be reduced if it is simultaneously left and right-reduced.
Let F be a reduced set of FDs, then we can derive G " tX Ñ y | @X Ñ Y P F, y P Y u. G is the splitting of F and both sets are equivalent. Let F be a reduced set, its splitting is called a canonical cover. A canonical cover is a left-reduced, nonredundant w.r.t. augmentation set of FDs with a single element in their right hand side (a split set). Notice that canonical covers can be redundant w.r.t. transitivity. For example the canonical cover of Table 1 contains tc Ñ b, c Ñ e, d Ñ e, bd Ñ c, be Ñ cu where bd Ñ e is redundant w.r.t. transitivity, i.e. bd Ñ bde Ñ c.

Finally, a set F is said to be a minimum cover if it has as few FDs as any other equivalent set of FDs. For example, the minimum cover of Table 1 contains FDs tc Ñ be, d Ñ e, be Ñ cu. Notice that the minimum cover is not restricted to be reduced, so it is not presented with split sets. Secondly, the cardinality of the example minimum cover contains exactly one fewer FD than the canonical cover, namely bd Ñ c.

Formal Concept Analysis (FCA)

For the sake of brevity we do not provide a description of the FCA framework. The notation used in this article follows [START_REF] Ganter | Formal Concept Analysis[END_REF] where K " pG, M, Iq is a formal context of objects G, attributes M and incidence relation I, with formal concepts pA, Bq.

Implication Systems

Implications are relations established between attribute sets from a formal context K. Implications are analogous to FDs and they can be used to characterize the latter [START_REF] Baixeries | Computing Functional Dependencies with Pattern Structures[END_REF]. Implication systems (sets of implications) can also characterize FD covers [START_REF] Bertet | The multiple facets of the canonical direct unit implicational basis[END_REF].

An implication

X Ñ Y holds in K for X, Y Ď M if Y Ď X 2 .
Notice that we maintain the notation of FDs to denote the relation between X and Y , the reason for this will become apparent in what follows. Let T be a set of tuples and U, a set of attributes in a table (such as the one in Table 1). We define the set P airpT q " T ˆT as the Cartesian product of the set of tuples T and incidence set I such that ppt i , t j q, xq P I ðñ t i rxs " t j rxs, @x P U, @t i , t j P T . It can be shown that an FD X Ñ Y holds in the database if and only if X Ñ Y is an implication of the formal context K " pP airpT q, U, Iq [START_REF] Ganter | Formal Concept Analysis[END_REF]. K is called the binary codification of table T . For example, Table 3 contains the binary codification of Table 1. In Table 3 we can observe the implication d Ñ e which can be verified as an FD in Table 1.

The previous statement entails that FDs and implications in K are in 1-1 correspondence. Moreover, the corresponding definition of a canonical cover of FDs is equivalent to that of a canonical-direct unitary basis of implications as shown in [START_REF] Bertet | The multiple facets of the canonical direct unit implicational basis[END_REF].

a b c d e t1 1 1 1 1 1 t2 2 1 1 1 1 t3 3 1 2 2 2 t4 3 2 3 2 2 t5 3 1 2 3 2 t6 1 1 2 2 2 t7 1 1 2 4 2

Partition Pattern Structures

Partition Pattern Structures (PPS) is a type of pattern structure [START_REF] Kuznetsov | Galois Connections in Data Analysis: Contributions from the Soviet Era and Modern Russian Research[END_REF] that deals with, as the name suggests, object representations in the form of set partitions. PPS have shown to be useful for mining biclusters [START_REF] Codocedo | Lattice-based biclustering using Partition Pattern Structures[END_REF] and, more importantly for this article, relations between partition pattern concepts have been used to characterize FDs of different kinds [START_REF] Baixeries | Characterizing Functional Dependencies in Formal Concept Analysis with Pattern Structures[END_REF].

The formalization of a database with tuples T and attributes U as a PPS is as follows. A partition d of T is a set d Ď ℘pT q of disjoint subsets of T such that for any two different elements K i , K j P d we have that K i X K j " H and Ť KiPd K i " T . Let D be the set of all possible partitions of T , they can be ordered by a coarser/finer relation denoted

d i Ď d j (d i is finer than d j for d i , d j P D) iff @ K i P d i , D K j P d j : K i Ď K j . The similarity operator is defined as d i [ d j " tK i X K j | K i P d i , K j P d j u.
From this, it follows that pD, [q is a complete lattice with supremum and infimum defined respectively as J " tttu | t P T u and K " ttT uu.

The set of attributes U is mapped onto pD, [q through a function δ which for a given attribute x P U yields its equivalence relations over T . With this, we can configure the PPS pU, pD, [q, δq where pX, dq is a partition pattern concept with X ˝" d denoting the equivalence relations implied by attributes in X, and d ˝" X denoting all attributes with associated equivalence relations finer than d.

Theorem 1. Let pP airpT q, U, Iq be the binary codification of a table within a database, and pU, pD, [q, δq its PPS representation: pW, Xq P pP airpT q, U, Iq ðñ pX, dq P pU, pD, [q, δq The proof of Theorem 1 can be found in [START_REF] Baixeries | Characterizing Functional Dependencies in Formal Concept Analysis with Pattern Structures[END_REF]. Theorem 1 presents an important property of the PPS that states that X Ď U is an extent in pU, pD, [q, δq if and only if it is also an intent in pP airpT q, U, Iq (the relation between the set of tuple pairs W Ď P airpT q and the partition d P D can be formalized as well but it is of no interest for our development). Theorem 1 is very important since it entails that the lattices derived from pP airpT q, U, Iq and pU, pD, [q, δq are isomorphic. Consequently, implication X Ñ Y in pP airpT q, U, Iq can be found as a relation between extents in pU, pD, [q, δq (extent implication) such that Y Ď X ˝˝.

Covers and Pattern Structures

In this section we present two different kinds of covers for FDs: canonical covers (Subsection 3.1) and minimal covers (Subsection 3.2), as well as their characterization in terms of Pattern Structures. This section uses existing well-known results in FCA, which are reviewed here for the sake of readability.

First, we present how a canonical cover for FDs can be computed with pattern structures, according to the results in [START_REF] Bertet | The multiple facets of the canonical direct unit implicational basis[END_REF][START_REF] Ryssel | Fast algorithms for implication bases and attribute exploration using proper premises[END_REF]. Then, in Subsection 3.2 we present a novel characterization of a minimum cover of FDs by means of pseudo-intents [START_REF] Ganter | Formal Concept Analysis[END_REF]. The interest of these results are not only limited to computing covers for FDs, but also for computing covers for generalizations of FDs.

Mining a Canonical Cover of FDs

The characterization of a canonical cover of FDs using FCA is straightforward and it has been previously studied in [START_REF] Bertet | The multiple facets of the canonical direct unit implicational basis[END_REF][START_REF] Ryssel | Fast algorithms for implication bases and attribute exploration using proper premises[END_REF]. In a nutshell, a canonical direct basis of implications with proper premises is analogous to a reduced non-redundant cover of FDs, i.e. a canonical cover. In this section we recall some of these ideas and show how they can be simply adapted to the framework of partition pattern structures.

Firstly, let pU, pD, [q, δq be a PPS, we define D " td P D | d ˝˝" du as the set of all closed partition patterns in D, then the triple pU, D, Jq with pd, xq P J ðñ d Ď δpxq is called a representation context of pU, pD, [q, δq and their corresponding concept lattices are isomorphic [START_REF] Kuznetsov | Galois Connections in Data Analysis: Contributions from the Soviet Era and Modern Russian Research[END_REF]. For the sake of readability of the following definitions, we will prefer to define the representation context as pD, U, Jq instead of pU, D, Jq. By transitivity of equivalence, it is clear that pD, U, Jq is isomorphic to pP airpT q, U, Iq as defined in Section 2.4 and as such, implications in pD, U, Jq correspond to FDs. For example, Table 2 (not considering elements Ö) contains the representation context pD, U, Jq of the partition pattern structure derived from Table 1. Notice that objects are closed intersections of object representations, e.g. δpdq is not present since δpdq ˝˝" de (thus d Ñ e). With this, the canonical direct basis of implications in pD, U, Jq (and thus, canonical cover of FDs) is determined by the set of proper premises of elements in U.

Theorem 2 ([19]

). X Ď Uztyu is a premise of y P U iff X is a hypergraph transversal of H Ö y defined as :

H Ö y " tppUztyuqqzd 1 | d P D, d Ö yu
The set of all proper premises of y is exactly the minimum hypergraph transversal T rpH Ö y q.

Detailed descriptions of the development of Theorem 2 can be found in [START_REF] Ryssel | Fast algorithms for implication bases and attribute exploration using proper premises[END_REF]. Providing a formal definition of hypergraph transversals is out of the scope of this article, however we briefly mention that this formalization can also be made considering set collections (instead of hypergraphs) and minimum hitting sets (instead of minimum hypergraph transversals) [START_REF] Gainer-Dewar | The minimal hitting set generation problem: Algorithms and computation[END_REF]. Alternatively, this problem is analogous to the vertex cover problem [START_REF] Ganter | Conceptual Exploration[END_REF].

Theorem 2 provides a formal description for the proper premises of a given attribute y P U that in turn yields the canonical cover of functional dependencies. However this approach requires the creation of the representation context which creates a middle step in the overall mining process. Actually, by analyzing the arrow relation between d and y we can observe that the representation context is not really necessary. The last result shows that d Ö y in pD, U, Jq can be defined directly over the PPS. Intuitively, this definition corresponds to y Õ d in pU, D, Jq and thus, in pU, pD, [q, δq. With these elements we can finally propose a characterization for the canonical cover of functional dependencies in pU, pD, [q, δq as follows.

Corollary 1. Let pU, pD, [q, δq be a partition pattern structure and T rpHq denote the hypergraph transversal of H, then with

L cc " tX Ñ y | y P U, X P T rpH Õ y qu H Õ y " tppUztyuqqzd 1 | d P D, y Õ du y Õ d ðñ d Ę δpyq and if h Ĺ d then h Ď δpyq
L cc is a canonical cover of functional dependencies.

For the running example, let us calculate the proper premises of attribute c using the arrow relations in Table 3. We have c Õ pδpaq [ δpbqq and c Õ pδpaq [ δpdq [ δpeqq. With this, we have the hypergraph H Õ c " ttd, eu, tbuu for which the minimum transversal hypergraph is T rpH Õ c q " ttb, du, tb, euu. Correspondingly, we have the FDs bd Ñ c and be Ñ c which are included in the canonical cover.

Characterizing a Minimum Cover of FDs with FCA

We introduce a novel characterizations of a minimum cover of FDs by means of pseudointents, and its generalization using pseudo-extents in a PPS.

The stem base of implications, or Duquenne-Guigues basis [START_REF] Guigues | Familles minimales d'implications informatives résultant d'un tableau de données binaires[END_REF], is a sound, complete and non-redundant basis which also has minimum cardinality among the sets of implications for a given formal context. We show how this can be used to characterize a minimum cover of FDs in a rather simple manner. Prior to introducing the stem base, let us define pseudo-closed sets [START_REF] Ganter | Formal Concept Analysis[END_REF]. Definition 2. (Pseudo-closed sets) Let P Þ Ñ P 2 be a closure operator over a set M, then P is a pseudo-closed set if and only if (Q Ă P " Q Ď P and Q ‰ P ):

P ‰ P 2 (1) Q Ă P and Q is a pseudo-closed set ùñ Q 2 Ď P (2)
Given a formal context pG, M, Iq, pseudo-closed sets A Ď G are called pseudoextents, while pseudo-closed sets B Ď M are called pseudo-intents. A stem base of implications, or Duquenne-Guigues basis, can be defined as follows:

Theorem 3 ( [START_REF] Ganter | Formal Concept Analysis[END_REF]). (Duquenne-Guigues Basis) The set of implications:

L " tP Ñ P 2 | P is a pseudo-intentu (3)
is sound, complete and non-redundant.

Theorem 4 ([12]

). Every complete set of implications contains an implication X Ñ Y with X 2 " P 2 for every pseudo-intent P of pG, M, Iq Theorem 4 entails that the stem base of implications has minimum cardinality with respect to any equivalent set of implications of pG, M, Iq. With this and the previous observation that FDs are in 1-1 correspondence with implications in pP airpT q, U, Iq, we can derive the following corollary.

Corollary 2. Let pP airpT q, U, Iq be the formal context derived from a database with tuples T and attributes U. The set of functional dependencies L " tP Ñ P 2 u is a minimum cover of tuples T .

Corollary 2 provides a novel characterization of the minimum cover of functional dependencies through pseudo-intents of a formal context. At this point, we are in the position to use the FCA machinery to calculate this minimum cover, however we would like to propose a generalization of the stem base using PPS which allows for a more direct representation of the database, avoiding the creation of the costly formal context pP airpT q, U, Iq which grows quadratically w.r.t. the number of tuples in T .

Noticeably, in the PPS pU, pD, [q, δq, we can maintain the notion of pseudo-extents for a pseudo-closed set X Ď U with X Þ Ñ X ˝˝.

Proposition 1. Let pU, pD, [q, δq be the PPS representation of a database, then the set of functional dependencies:

L " tX Ñ X ˝˝| X is a pseudo-extentu (4)
is a minimum cover.

The proof of Proposition 1 follows from Theorem 1 and the observation that there is a bijective mapping between extents in pP airpT q, U, Iq and intents in pU, pD, [q, δq. Moreover, for a set X P U the closure operator X Þ Ñ X 2 is exactly equivalent to X Þ Ñ X ˝˝and consequently, the set of pseudo-intents in pP airpT q, U, Iq is the same as the pseudo-extents in pU, pD, [q, δq. Thus, because of Corollary 2, Proposition 1 holds.

Mining a Minimum Cover of FDs

We describe the mechanisms and algorithms through which we are able to implement the ideas exposed in Section 3 to build a Minimum Cover Miner.

Identifying Pseudo-Closed Sets

Pseudo-closed sets can be identified by means of pre-closed sets. For the sake of readability, we do not provide a full characterization of pre-closed sets. We simply introduce the properties that render them useful for identifying pseudo-closed sets. A thorough description of pre-closed sets can be found in [START_REF] Ganter | Conceptual Exploration[END_REF].

Proposition 2. Let Q Þ Ñ Q 2 be a closure operator. A set Q is pre-closed if
and only if it is either a pseudo-closed set or a closed set.

Proposition 2 states that the set of pre-closed sets is composed by the union of the set of pseudo-closed sets and the set of closed sets considering given an arbitrary closure operator. The usefulness of this proposition is apparent since, given a mechanisms to identify pre-closed sets, we can simply test those that are not closed sets to identify pseudo-closed sets. Fortunately, pre-closed sets form a closure system itself and thus, this mechanisms exists and it is described in Proposition 3. Proposition 3. Let L " tP Ñ P 2 u be the stem base of implications, then L ' pXq is the pre-closure of X when:

X L " X Y ď tP 2 | P Ñ P 2 P L, P Ă Xu X LL " X L Y ď tP 2 | P Ñ P 2 P L, P Ă X L u . . . L ' pXq " X LL...L s.t. L ' pXq L " L ' pXq
The pre-closure of a set X corresponds to a fixed point that is iteratively calculated using the stem base of implications. While it seems odd that in order to calculate the stem base of implications we need it in the first place, it is important to notice that we only need a part of the stem base, particularly those rules such that P Ă X and L ' pXq. This is achieved by means of a lectical enumeration of the powerset of X.

Lectical Enumeration of Pre-Closures

Pre-closures are enumerated in lectical order using the PreviousClosure algorithm, a variation of NextClosure [START_REF] Ganter | Conceptual Exploration[END_REF][START_REF] Sergei | Comparing Performance of Algorithms for Generating Concept Lattices[END_REF]. The lectical order of the powerset of U lists all the subsets of a set X before listing X for any X Ď U. In addition, incomparable elements w.r.t. Ď are listed in inverted to the lexicographical order ď l . Thus, the lectical order ă between two sets X, Y Ď U is defined as:

X ă Y ðñ X Ď Y or Y ď l X
For example, given U " ta, b, c, du, the lectical order of ℘pUq is:

d, c, cd, b, bd, bc, bcd, a, ad, ac, acd, ab, abd, abc, abcd

Algorithms

Algorithm 1 depicts a brief summary of PreviousClosure. It receives a partial stem base L and a list of candidates in lectical order. For each candidate X , it calculates its preclosure L ' pXq using the stem-base. If the pre-closure is lexicographically greater than the candidate, then firstly, all remaining candidates that are lectically lower than the preclosure are discarded for future enumerations (pruning), and secondly, the pre-closure is returned. When no more candidates are available, the algorithm returns null.

The pruning mechanism works by removing from the candidate list elements Y that would yield redundant pre-closures, i.e. elements X Ď Y Ď L ' pXq for which L ' pY q " L ' pXq. This efficient pruning mechanism is possible due to the following proposition.

Proposition 4. Let X Ď Y and Xď l Y , then for all elements Z such that X ă Z ă Y it holds that X Ď Z Ď Y .

Firstly, we show that Z ă Y and Z Ę Y implies Z ă X and secondly, that X ă Z and

X Ę Z implies that Y ă Z. Sets Z ă Y such that Z Ę Y require that Y ď l Z.
Since Xď l Y , then Xď l Z and thus Z ă X. Dually, sets X ă Z such that X Ę Z require that Zď l Xď l Y and thus, Y ă Z.

Algorithm 1: PreviousClosure algorithm

Input: Stem base L, candidates ordered w.r.t. ă Output: Pre-closure L ' pXq or null when enumeration is over, and updated list of

candidates 1 for X P candidates do 2 if X ď l L ' pXq then 3 candidates " tY P candidates | L ' pXq ă Y u return L ' pXq 4 end 5 end
Optimizations for Algorithm 1 are not described for the sake of simplicity. However, we mention that the set of candidates is dynamically built.

Algorithm 2 presents the mechanisms used to calculate the stem base L. The algorithm receives the partition pattern structure as an input and initializes an empty stem base and a list of lectically ordered candidates (powerset of attributes). Then, it calls the PreviousClosure procedure defined in Algorithm 1 until a null value is returned. Once a pre-closure is found, the algorithm tests if it is not a closure (line 5) which means that it is a pseudo-closure. In such a case, a new implication is added to the stem base (line 6) and the algorithms iterates.

Notice that the correct calculation of pre-closures is secured by the lectical order of the candidates and the fact that P Ď X ùñ P ă X. Thus, in Algorithm 1, we are certain that for calculating L ' pXq, we have all P Ă X required by Proposition 3.

Algorithm 2: Stem Base Miner Algorithm

Input: Partition Pattern Structure pU, pD, [q, δq Output: For example, consider the database in Table 1 with 5 attributes. The set of candidates contain 2 5 " 32 elements to be tested. The first candidate is e. At this point L is empty, so L ' peq " e is a pre-closure. Since e ˝˝" e, no rules are added to the stem base. For the candidate d we have that L ' pdq " d and d ˝˝" de, meaning that the pre-closure d is pseudo-closed. Thus, rule d Ñ e is added to L. As an example of pruning, consider candidate cd. Since L " td Ñ eu, we have L ' pcdq " cde. Line 3 of Algorithm 1 removes from the set of candidates cde and the next candidate is b.

Stem base L 1 L " H 2 candidates " p℘pUq, ăq 3 X " previous closurepL, candidatesq 4 while X is not null do 5 if X ‰ X ˝˝then 6 L " L Y tX Ñ X ˝˝u

Experimental Evaluation

We compare our approach to TANE [START_REF] Huhtala | TANE: An Efficient Algorithm for Discovering Functional and Approximate Dependencies[END_REF], a state-of-the-art FD miner. TANE is a highly optimized apriori-based algorithm that generates a canonical cover of FDs. A canonical cover usually contains many more dependencies than those in a minimum cover such as the one we are able to mine using our approach. Nevertheless, a canonical cover can be reduced to a minimum cover using an algorithm that has quadratical complexity w.r.t. its cardinality [START_REF] Ganter | Conceptual Exploration[END_REF].

The goal of this evaluation is to study the comparative benefits of using our approach versus a traditional approach such as TANE. TANE was re-implemented for our experiments 4 . This implementation and our approach were coded in Python. The software is freely available 5 .

We performed experiments over 12 datasets extracted from the UCI Machine Learning repository 6 , the JASA Data Archive7 and Metanome's repeatability Web page 8 . Details on the number of rows and columns for each dataset are provided in the first two columns of Table 4. In addition to these datasets, we created synthetic versions by multiplying the rows or the columns of a given dataset. Experiments were run over an Intel Core i7 running at 2.2 Ghz and equipped with 16 GB of RAM memory.

Results & Discussion

Table 4 presents the main results of applying our approach and TANE on each dataset to mine the Minimum Cover and the Canonical Cover, respectively. The table contains the execution times of each algorithm and the number of dependencies mined. Datasets in boldface represent those for which FCA performed better than TANE. For the Mushroom dataset, TANE was not able to obtain results before running out of memory, thus no information is provided in the table. Table 4 also reports in two synthetic datasets, namely PGLW (2x Attributes) which contains two horizontal copies of the PGLW dataset resulting in twice as many attributes. Forest Fires (2x Tuples) contains two vertical copies of Forest Fires resulting in twice as many tuples. All mined Canonical Covers mined by TANE have been reduced to a Minimum Cover to verify the consistency of our approach.

Out of the 12 datasets, our approach performs better in the largest (both in rows and columns). This is better depicted by Figure 1a datasets are represented as points in a rows-columns space. Circles represent datasets for which our approach performed better while diamonds, where TANE did. Notice that the X axis is provided in logarithmic scale. The figure shows that most of the datasets where TANE performs better are in the lower-left region of the figure, representing small datasets. Our approach performs better in datasets on all other regions, including the upper-right which contains datasets with many rows and columns.

Synthetic datasets in Table 4 show evidence that our approach scales better when duplicating the dataset. When duplicating attributes the difference is particularly dramatic since TANE is over 13 times slower while our approach, only 3. To study this further, we created two sets of 19 synthetic datasets. The first set (Vertical set) incrementally multiplied vertically the Diagnostics datasets (with 8 attributes and 120 tuples) generating versions of 240, 360, 480 tuples, and so on up to a dataset containing 2400 tuples. The second set (horizontal set) of datasets did the same in a horizontal manner generating versions of 16, 24, 32, up to 160 attributes. Since most of the datasets of the second set were too big for TANE, they were trunked to just 40 tuples.

Figure 1b depicts the increasing time for TANE and FCA on the vertical set, i.e. when increasing the number of tuples. We can observe that both approaches scale linearly w.r.t. the number of tuples, even when our approach seems to have a much more stable behavior. Vertical multiplication of datasets yield the same number of FDs than the original set, since the relation between attributes remains unchanged. Thus, we can assume that other algorithms based on TANE could achieve a similar performance than our approach provided some optimizations.

On the other hand, this may not to be the case for the horizontal set. Figure 1c shows that our approach remains very stable when varying the number of attributes, while TANE's execution time grows exponentially. Indeed, this great difference in performance is due to the way in which our approach finds FDs which differs from TANE's strategy. Consider the synthetic dataset with many copies of a given attribute. In this case, the pruning mechanism described in Section 4.3 quickly removes thousands of candidates by means of the closure operator. Instead, TANE computes each attribute combination rendering the exponential growth in the computation time.

We stress that this is not simply an extreme case from which our approach takes advantage, but actually a very good illustration of the benefits of using a closure operator to navigate the space of FDs. Closures enable our approach to avoid unnecessary computations not only when we have redundant attributes, but also whenever possible in the lattice of the powerset of attributes.

Conclusions

We have presented a new characterization of a minimum cover of functional dependencies (FDs) by means of the stem base (or Duquenne-Guigues basis) of a partition pattern structure. We have presented the mechanisms through which this characterization can be exploited to efficiently mine the minimum cover. Furthermore, we have described the algorithms that implement these mechanisms and show empirical evidence that our characterization performs better than a state-of-the-art FD miner, namely TANE, in larger databases containing many rows and columns.

d

  Ö y ðñ pd, yq R J and if d 1 Ĺ h 1 then ph, yq P J We have that in pD, U, Jq, d 1 " tx P U | pd, xq P Jp ðñ d Ď δpxqqu and thus d 1 " d ˝for any d P D. Moreover, in pU, pD, [q, δq, d ˝Ĺ h ˝ðñ h Ĺ d since h " h ˝˝and d " d ˝˝. With this, we can rewrite the previous definition as follows. d Ö y ðñ pd, yq R J and if , d 1 Ĺ h 1 then ph, yq P J ðñ d Ę δpyq and if d ˝Ĺ h ˝then h Ď δpyq ðñ d Ę δpyq and if h Ĺ d then h Ď δpyq

  (a) Datasets and the number of rows and columns they contain. (b) Performance Comparison when increasing tuples: FCA vs TANE (c) Performance Comparison when increasing attributes: FCA vs TANE

Table 1 :

 1 Example of a table T

			a b c d e
			pt1, t2q	ˆˆˆp
			t1, t3q	pt1,
			t4q
			pt1, t5q	pt1,
			t6q ˆpt1,
			t7q ˆpt2,
			t3q	pt2,
			t4q
			pt2, t5q	pt2,
		a b c d e	t6q	pt2,
	δpaq δpaq [ δpeq [ δpbq [ δpeq [ δpdq [ δpeq	t7q t4q ˆˆp pt3, δpeq δpbq t3, t5q ˆˆˆp δpaq ˆˆÖ t3, t6q ˆˆˆp Ö t3, t7q ˆˆp ˆδpdq t4, t5q ˆpt4, ˆδpaq ˆÖ Ö ˆδpbq t6q ˆpt4,
	[ δpcq [ δpeq	ˆˆδ t7q	pt5,
	paq [ δpbq [ δpcq [ δpeq	ˆˆˆÖ δpbq t6q ˆˆp
	[ δpcq [ δpdq [ δpeq	Ö ˆˆˆδ t5, t7q	ˆˆp
	paq [ δpbq [ δpcq [ δpdq [ δpeq ˆˆˆˆT	t6, t7q ˆˆˆT
	able 2: Representation context

able 3: Binary codification of Table

1

Table 4 :

 4 Dataset details, Execution Times in Seconds, and Number of Mined Rules for FCA, FCA/Pattern Structures and TANE. CC: Canonical Cover, MC: Minimum Cover. Datasets in boldface represent those in which FCA performed better than TANE.

https://github.com/anonexp/fudep

https://github.com/anonexp/fd_miner

https://archive.ics.uci.edu/ml/index.php

http://lib.stat.cmu.edu/jasadata/

https://hpi.de/naumann/projects/repeatability/data-profiling/ fds.html

Acknowledgments. This research work has been supported by the SGR2014-890 (MACDA) project of the Generalitat de Catalunya, and MINECO project APCOM (TIN2014-57226-P) and partially funded by the French National Project FUI AAP 14 Tracaverre 2012-2016.