G Chierchia
email: chierchi@telecom-paristech.fr

N Pustelnik
email: nelly.pustelnik@ens-lyon.fr

J.-C Pesquet

B Pesquet-Popescu

Epigraphical splitting for solving constrained convex optimization problems with proximal toolsextended version

Keywords: Iterative methods, Optimization, Epigraph, Projection, Proximal algorithms, Restoration, Total variation, Non-local regularization, Patch-based processing, Parallel algorithms

We propose a proximal approach to deal with a class of convex variational problems involving nonlinear constraints. A large family of constraints, proven to be effective in the solution of inverse problems, can be expressed as the lower level set of a sum of convex functions evaluated over different blocks of the linearly-transformed signal. For such constraints, the associated projection operator generally does not have a simple form. We circumvent this difficulty by splitting the lower level set into as many epigraphs as functions involved in the sum. In particular, we focus on constraints involving q -norms with q ≥ 1, distance functions to a convex set, and 1,p -norms with p ∈ {2, +∞}. The proposed approach is validated in the context of image restoration by making use of constraints based on Non-Local Total Variation. Experiments show that our method leads to significant improvements in term of convergence speed over existing algorithms for solving similar constrained problems. A second application to a pulse shape design problem is provided in order to illustrate the flexibility of the proposed approach.

Introduction

As an offspring of the wide interest in frame representations and sparsity promoting techniques for data recovery, proximal methods have become popular for solving large-size non-smooth convex optimization problems [START_REF] Combettes | Proximal splitting methods in signal processing[END_REF][START_REF] Parikh | Proximal algorithms[END_REF]. The efficiency of these methods in the solution of inverse problems has been widely studied in the recent signal and image processing literature (see e.g. [START_REF] Guerquin-Kern | A fast wavelet-based reconstruction method for magnetic resonance imaging[END_REF][START_REF] Dupé | A proximal iteration for deconvolving Poisson noisy images using sparse representations[END_REF][START_REF] Aujol | Structure-texture image decomposition -modeling, algorithms, and parameter selection[END_REF][START_REF] Briceño-Arias | Proximal algorithms for multicomponent image recovery problems[END_REF][START_REF] Theodoridis | Adaptive learning in a world of projections[END_REF][START_REF] Chaux | A parallel proximal splitting method for disparity estimation from multicomponent images under illumination variation[END_REF] and references therein). For instance, in the context of image restoration, when the noise is assumed to be zero-mean additive white Gaussian, the target signal can be recovered from the blurred and noisy observations z ∈ R N by solving the following non-smooth optimization problem:

minimize x∈R N Ax -z 2 2 + λ Fx 1 ,
where A ∈ R N×N is the matrix associated with the degradation blur, F ∈ R M×N (with M ≥ N) is an analysis frame operator that sparsifies the target signal [START_REF] Mallat | A wavelet tour of signal processing[END_REF][START_REF] Jacques | A panorama on multiscale geometric representations, intertwining spatial, directional and frequency selectivity[END_REF], and λ is a positive regularization parameter. A constrained formulation of the above problem may be also considered [START_REF] Van Den | Probing the Pareto frontier for basis pursuit solutions[END_REF], yielding minimize

x∈R N Ax -z 2 2 s. t. Fx 1 ≤ η,
where η is a positive constraint bound. Both optimization problems are equivalent for some specific values of λ and η, since there exist some conceptual Lagrangian equivalences between regularized and constrained formulations [START_REF] Ciak | Homogeneous penalizers and constraints in convex image restoration[END_REF]. However, it has been recognized for a long time that incorporating constraints directly on the solution, instead of considering regularized functions, may often facilitate the choice of the involved parameters [START_REF] Youla | Image restoration by the method of convex projections. Part I -theory[END_REF][START_REF] Trussell | The feasible solution in signal restoration[END_REF][START_REF] Combettes | Inconsistent signal feasibility problems : leastsquares solutions in a product space[END_REF][START_REF] Teuber | Minimization and parameter estimation for seminorm regularization models with I-divergence constraints[END_REF][START_REF] Stück | The iteratively regularized Gauss-Newton method with convex constraints and applications in 4Pi microscopy[END_REF][START_REF] Ono | Poisson image restoration with likelihood constraint via hybrid steepest descent method[END_REF][START_REF] Harizanov | Epigraphical projection for solving least squares anscombe transformed constrained optimization problems[END_REF][START_REF] Ono | Second-order total generalized variation constraint[END_REF][START_REF] Tofighi | Signal reconstruction framework based on Projections onto Epigraph Set of a Convex cost function[END_REF]. Indeed, the bound η may be easier to set than the parameter λ , as the former may be related to some physical properties of the target solution. This is one of the primary motivations in considering constrained formulations of convex optimization problems.

Proximal algorithms

The wide class of proximal algorithms can efficiently deal with constrained convex optimization problems, as they provide a unifying framework that allows one to address nonsmooth functions as well as hard constraints [START_REF] Combettes | Proximal splitting methods in signal processing[END_REF][START_REF] Chen | A proximal-based decomposition method for convex minimization problems[END_REF][START_REF] Daubechies | An iterative thresholding algorithm for linear inverse problems with a sparsity constraint[END_REF][START_REF] Chaux | A variational formulation for frame-based inverse problems[END_REF][START_REF] Combettes | A Douglas-Rachford splitting approach to nonsmooth convex variational signal recovery[END_REF][START_REF] Figueiredo | Gradient projection for sparse reconstruction: application to compressed sensing and other inverse problems[END_REF][START_REF] Beck | A fast iterative shrinkage-thresholding algorithm for linear inverse problems[END_REF][START_REF] Fornasier | Subspace correction methods for total variation and 1 -minimization[END_REF][START_REF] Steidl | Removing multiplicative noise by Douglas-Rachford splitting methods[END_REF][START_REF] Pesquet | A parallel inertial proximal optimization method[END_REF][START_REF] Esser | A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science[END_REF][START_REF] Chambolle | A first-order primal-dual algorithm for convex problems with applications to imaging[END_REF][START_REF] Briceño-Arias | A monotone + skew splitting model for composite monotone inclusions in duality[END_REF][START_REF] Combettes | Primal-dual splitting algorithm for solving inclusions with mixtures of composite, Lipschitzian, and parallel-sum type monotone operators[END_REF][START_REF] Vũ | A splitting algorithm for dual monotone inclusions involving cocoercive operators[END_REF][START_REF] Condat | A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms[END_REF][START_REF] Chen | A primal-dual fixed point algorithm for convex separable minimization with applications to image restoration[END_REF][START_REF] Alghamdi | A primal-dual method of partial inverses for composite inclusions[END_REF]. The key tool in these methods is the proximity operator [START_REF] Moreau | Proximité et dualité dans un espace hilbertien[END_REF] of a proper lower-semicontinuous convex function ϕ from a real Hilbert space H to ]-∞, +∞], defined as

(∀y ∈ H ) prox ϕ (y) = argmin u∈H 1 2 u -y 2 + ϕ(u).
The proximity operator can be interpreted as a sort of subgradient step for the function ϕ, as p = prox ϕ (y) is uniquely defined through the inclusion yp ∈ ∂ ϕ(p). When the function is smooth, some proximal algorithms allow one to replace the proximity operator with a simpler gradient-descent computation. When a hard constraint is involved, instead, the proximity operator reduces to the orthogonal projection onto a nonempty closed convex subset C ⊂ H , in the sense that

(∀y ∈ H ) prox ι C (y) = P C (y) = argmin u∈C 1 2 u -y 2 ,
where ι C denotes the indicator function of C, equal to 0 on C and +∞ otherwise.

In order to solve a convex optimization problem, proximal algorithms iterate a sequence of steps in which the proximity operators of the involved functions are evaluated at every iteration (e.g. prox •-z 2 2 and P { • 1 ≤η} in the constrained formulation mentioned earlier). The efficient computation of these operators is thus essential for dealing with large-size problems. Unfortunately, it turns out that a closedform expression of the projection onto a closed convex set is available in a limited number of instances. Some well-known examples are the projections onto an hypercube, a closed half-space, an hyperslab, an affine set, a simplex and an 2norm ball [START_REF] Parikh | Proximal algorithms[END_REF][START_REF] Theodoridis | Adaptive learning in a world of projections[END_REF][START_REF] Bauschke | Convex Analysis and Monotone Operator Theory in Hilbert Spaces[END_REF]. However, more sophisticated convex sets are usually necessary in a large number of inverse problems (e.g. the 1 -ball in the above example), raising the issue of computing the associated projection operators.

When an expression of the direct projection is not available, a possible solution is to approximate the convex set by a half-space, which leads to the concept of subgradient projection. The main limitation of this approach is that the objective function must be strictly convex [START_REF] Combettes | A block-iterative surrogate constraint splitting method for quadratic signal recovery[END_REF]. Recent works have proposed specific numerical methods to deal with an 1 -ball [START_REF] Van Den | Probing the Pareto frontier for basis pursuit solutions[END_REF][START_REF] Kopsinis | Online sparse system identification and signal reconstruction using projections onto weighted 1 balls[END_REF] and an 1,∞ -ball [START_REF] Quattoni | An efficient projection for 1,∞ regularization[END_REF], but they may prove inefficient in large-size problems, due to inner iterations.

Contributions

The objective of this paper is to propose an efficient splitting technique for solving the following class of constrained convex optimization problems:

Problem 1 minimize x∈H R ∑ r=1 g r (T r x) s. t. h(Fx) ≤ η,
where η ∈ R and, for every r ∈ {1, . . . , R}, -T r (resp. F) is a bounded linear operator from H to R N r (resp. R M ), g r is a proper lower-semicontinuous convex function from R N r to ]-∞, +∞], h is a proper lower-semicontinuous function from R M to ]-∞, +∞] having a block-wise decomposable structure:

(∀y ∈ R M ) h(y) = L ∑ =1 h ( ) (y ( ) ), with y ( ) ∈ R M for each ∈{1, . . . , L} and M 1 + • • • +M L = M.
Numerous constraints usually involved in the formulation of inverse problems can be modelled by a blockdecomposable function. Popular examples are the Kullback-Leibler divergence [START_REF] Teuber | Minimization and parameter estimation for seminorm regularization models with I-divergence constraints[END_REF], 2 -norm composed by Anscombe transformation [START_REF] Harizanov | Epigraphical projection for solving least squares anscombe transformed constrained optimization problems[END_REF], 1 -norm [START_REF] Van Den | Probing the Pareto frontier for basis pursuit solutions[END_REF], 1,∞ -norm [START_REF] Quattoni | An efficient projection for 1,∞ regularization[END_REF], and total variation [START_REF] Tofighi | Signal reconstruction framework based on Projections onto Epigraph Set of a Convex cost function[END_REF] or total generalized variation [START_REF] Ono | Second-order total generalized variation constraint[END_REF] semi-norms. A possible solution to deal with these constraints is to exploit the Lagrangian equivalence between projection and proximity operator, which boils down to the problem of finding the zero of a nonlinear equation [2, Section 6.6.1]. However, this approach turns out to be efficient only when the proximity operator admits a simple form, which is the case of Kullback-Leibler divergence [START_REF] Teuber | Minimization and parameter estimation for seminorm regularization models with I-divergence constraints[END_REF] and 1 -norm [START_REF] Van Den | Probing the Pareto frontier for basis pursuit solutions[END_REF].

The present work aims at designing an efficient method to address Problem 1 when the projection onto the involved constraint does not have a closed-form expression and the standard approach mentioned above is infeasible or inefficient. More specifically: (i) We propose a splitting technique that replaces the constraint in Problem 1 with a collection of epigraphs and a closed half-space constraint. So doing, we trade the problem of computing the projection onto the original constraint with the problem of computing the projection onto smaller epigraphs. (ii) We enrich the list of functions for which the projection onto the associated epigraph can be efficiently computed.

In this regard, we provide some theoretical results concerning the epigraphical projection of several functions of practical interest, such as the absolute value raised to a power q ∈ [1, +∞[, the distance to a convex set and the p -norm with p ∈ {2, +∞}. (iii) We illustrate through an image restoration example that regularity constraints based on Total Variation [START_REF] Rudin | Nonlinear total variation based noise removal algorithms[END_REF] and Non-Local Total Variation [START_REF] Gilboa | Nonlocal Operators with Applications to Image Processing[END_REF] can be efficiently handled by the proposed epigraphical splitting, which significantly speeds up the convergence (in terms of execution time) with respect to standard numerical solutions [START_REF] Van Den | Probing the Pareto frontier for basis pursuit solutions[END_REF][START_REF] Quattoni | An efficient projection for 1,∞ regularization[END_REF].

Organization

The paper is organized as follows. In section 2, we detail a new splitting approach to deal with a constraint expressed as the lower level set of a decomposable function. Since the proposed splitting introduces some epigraphs in the minimization process, we provide in Section 3 the expression of specific epigraphical projections. To demonstrate the flexibility of our approach, we illustrate some numerical experiments in Sections 4 and 5: the former concerns an image recovery problem, while the latter is related to a pulse shape design for digital communications. Finally, some conclusions are drawn in Section 6.

Notation: Let H be a real Hilbert space endowed with the norm • and the scalar product

= (y, ζ ) ∈ H × R ϕ(y) ≤ ζ . A subgra- dient of ϕ at y ∈ H is the subset of H defined as ∂ ϕ(y) = t ∈ H (∀u ∈ H ) ϕ(u) ≥ ϕ(y) + t | u -y . When ϕ is Gâteaux-differentiable at y, ∂ ϕ(y) = {∇ϕ(y)}.

Proposed method

We now turn our attention to the constraint in Problem 1 and we illustrate how to deal with it when the associated projection does not have a closed form. More precisely, we assume that the function h in Problem 1 can be modelled as:

(∀y ∈ R M ) h(y) = L ∑ =1 h (y ( ) ), (1)
where the generic vector y is decomposed into blocks of coordinates as follows

y = y (1) size M 1 , . . . , y (L) size M L ∈ R M , (2)
with M 1 + • • • + M L = M and, for every ∈ {1, . . . , L}, y ( ) ∈ R M and h ∈ Γ 0 (R M ) is such that ri(dom h ) = ∅.

Epigraphical splitting

Our approach consists of introducing an auxiliary vector ζ = ζ ( ) 1≤ ≤L ∈ R L in the minimization process, so that the constraint in Problem 1 can be decomposed into a collection of block-wise convex sets and a closed half-space:1

L ∑ =1 h (y ( ) ) ≤ η ⇔      (∀ ∈ {1, . . . , L}) h (y ( ) ) ≤ ζ ( ) , L ∑ =1 ζ ( ) ≤ η. (3)
Consequently, Problem 1 can be equivalently formulated in the following form: minimize

(x,ζ )∈H ×R L R ∑ r=1 g r (T r x) s. t.      (∀ ∈ {1, . . . , L}) h [Fx] ( ) ≤ ζ ( ) , L ∑ =1 ζ ( ) ≤ η. (4)
Note that the above minimization problem is defined with respect to x and ζ , so we have increased the dimensionality of our problem and we have replaced the lower level set of h with simpler constraints given by the epigraphs of h 1 , . . . , h L .

Connections with proximal algorithms

Within the proposed constrained optimization framework, Problem (4) can be rewritten in a more compact form as follows:

Problem 2 minimize (x,ζ )∈H ×R M R ∑ r=1 g r (T r x) s. t. (Fx, ζ ) ∈ E, ζ ∈ V,
where

E = {(y, ζ ) ∈ R M × R L | (∀ ∈ {1, . . . , L}) (y ( ) , ζ ( ) ) ∈ epi h }, (5)
V = ζ ∈ R L 1 L ζ ≤ η , (6)
with

1 L = (1, . . . , 1) ∈ R L .
The resolution of Problem 2 requires an efficient algorithm for dealing with large-size problems involving possibly nonsmooth functions and linear operators. As already mentioned in the introduction, we resort to proximal algorithms, which allow us to deal individually with the operators (T r ) 1≤r≤R , F, (prox g r ) 1≤r≤R , P E , and P V . In the present case, we assume that (prox g r ) 1≤r≤R have closed-form expressions. In addition, the projection onto V is well-known [2, Section 6.2.3], whereas the projection onto E is given by

(∀(y, ζ ) ∈ R M × R L ) P E (y, ζ ) = (p, θ ), (7)
where θ = (θ ( ) ) 1≤ ≤L ∈ R L , p = (p ( ) ) 1≤ ≤L ∈ R M is blockwise decomposed as in (2), and

(∀ ∈ {1, . . . , L}) (p ( ) , θ ( ) ) = P epi h (y ( ) , ζ ( ) ). (8)
Therefore, in order to solve Problem 2, we need to compute the projection onto epi h for each ∈ {1, . . . , L}, which yields two potential benefits with respect to Problem 1. Firstly, the epigraphical projection involves the lower-dimensional problem of determining the projection onto the convex subset epi h of R M × R. Secondly, these projections can be computed in parallel, since they are defined over disjoint blocks [START_REF] Gaetano | Parallel implementations of a disparity estimation algorithm based on a proximal splitting method[END_REF]. An example of an algorithm that converges to a solution to Problem 2 (and thus to a solution of Problem 1) will be provided in Section 4.

Examples of epigraphical constraints

We now illustrate some examples of functions that can be handled with the epigraphical splitting presented above. The mathematical expression of the associated projection will be derived in Section 3.

(i) q -norm. Let q ∈ [1, +∞[, (τ ( ) ) 1≤ ≤M ∈ ]0, +∞[ M , and

(∀y ∈ R M ) h(y) = M ∑ =1 τ ( ) |y ( ) | q . ( 9
)
Then, the above function can be modelled as in [START_REF] Combettes | Proximal splitting methods in signal processing[END_REF] with L = M and, for every ∈ {1, . . . , M},

(∀y ( ) ∈ R) h (y ( ) ) = τ ( ) |y ( ) | q . ( 10
)
The corresponding epigraphical projection will be given in Proposition 2 for q = 1 and Proposition 3 for q > 1.

Note that the 1 and 2 norms are widely used for the regularization of inverse problems [START_REF] Candès | Enhancing sparsity by reweighted 1 minimization[END_REF][START_REF] Tikhonov | Regularization of incorrectly posed problems[END_REF].

(ii) Distance function. Let L ∈ N * , (τ ( ) ) 1≤ ≤L ∈ ]0, +∞[ L , (q ( ) ) 1≤ ≤L ∈ [1, +∞[ L
and, for every ∈ {1, . . . , L}, let C ( ) be a nonempty closed convex subset of R M , and

(∀y ∈ R M ) h(y) = L ∑ =1 τ ( ) d q ( ) C ( ) (y ( ) ). (11)
Then, the above function can be modelled as in [START_REF] Combettes | Proximal splitting methods in signal processing[END_REF] with, for every ∈ {1, . . . , L},

(∀y ( ) ∈ R M ) h (y ( ) ) = τ ( ) d q ( ) C ( ) (y ( ) ). (12)
The corresponding epigraphical projection will be given in Proposition 4. Such a function is relevant for relaxing constraints on support or dynamics range [START_REF] Combettes | A proximal decomposition method for solving convex variational inverse problems[END_REF].

(iii) 1,2 -norm. Let L ∈ N * , (τ ( ) ) 1≤ ≤L ∈ ]0, +∞[ L , and

(∀y ∈ R M ) h(y) = L ∑ =1 τ ( ) y ( ) 2 . (13)
Then, the above function can be modelled as in [START_REF] Combettes | Proximal splitting methods in signal processing[END_REF] with, for every ∈ {1, . . . , L},

(∀y ( ) ∈ R M ) h (y ( ) ) = τ ( ) y ( ) 2 . ( 14
)
The associated epigraphical projection will be given in Corollary 1. Note that the 1,2 -norm is useful to define multivariate sparsity constraints [START_REF] Wu | Multivariate compressive sensing for image reconstruction in the wavelet domain[END_REF] or total variation bounds [START_REF] Rudin | Nonlinear total variation based noise removal algorithms[END_REF], which typically involve a sum of functions like ( 14) composed with linear operators corresponding to analysis transforms or gradient operators. (iv) 1,∞ -norm. Let L ∈ N * and, for each ∈ {1, . . . , L}, let (τ ( ,m) ) 1≤m≤M ∈ ]0, +∞[ M . We assume that:

(∀y ∈ R M ) h(y) = L ∑ =1 max 1≤m≤M τ ( ,m) |y ( ,m) |. (15)
Then, the above function can be modelled as in [START_REF] Combettes | Proximal splitting methods in signal processing[END_REF] with, for every ∈ {1, . . . , L},

(∀y ( ) ∈ R M ) h (y ( ) ) = max 1≤m≤M τ ( ,m) |y ( ,m) |. (16)
The corresponding epigraphical projection will be given in Proposition 5. When τ ( ,m) ≡ 1, the function in [START_REF] Teuber | Minimization and parameter estimation for seminorm regularization models with I-divergence constraints[END_REF] reduces to the standard infinity norm

g 1 (T 1 x) + g 2 (x)
by resorting to the following reformulation minimize

(x,v)∈H ×R N 1 g 1 (v) + g 2 (x) s. t. T 1 x = v.
This kind of splitting has been often used in image restoration [START_REF] Afonso | An augmented Lagrangian approach to the constrained optimization formulation of imaging inverse problems[END_REF] and, more recently, for distributed optimization problems [START_REF] Boyd | Distributed optimization and statistical learning via the alternating direction method of multipliers[END_REF]. A similar form of splitting has been considered in [START_REF] Briceño-Arias | Proximal algorithms for multicomponent image recovery problems[END_REF],

where the constraint T 1 x = v is handled by computing the projection onto the nullspace of [T 1 -Id ], which has a closedform expression for some specific choices of T 1 , such as circulant matrices involved in image restoration.

The solution that we propose in this work also introduces auxiliary variables. However, our objective is not to deal with linear transformations, but rather with a projection that does not have a closed-form expression. Consequently, the proposed solution departs from the usual splitting methods, in the sense that our approach leads to a collection of epigraphs, while the usual splitting techniques involve linear constraints.

Epigraphical projections

The key point in the proposed splitting is the introduction of some epigraphs in the minimization process, in order to facilitate the computational steps. Therefore, it is of paramount importance that the projection onto the epigraph can be efficiently computed. The problem of determining such an epigraphical projection is formalized in the following proposition (all the proofs are given in appendix). 2 Proposition 1 Let H be a real Hilbert space and let H ×R be equipped with the standard product space norm. Let ϕ be a function in Γ 0 (H ) such that dom ϕ is open. For every (y, ζ ) ∈ H × R, the projector P epi ϕ onto epi ϕ is given by:

P epi ϕ (y, ζ ) = (p, θ ) , (17)
where

p = prox 1 2 (max{ϕ-ζ ,0}) 2 (y), θ = max{ϕ(p), ζ }. (18)
The previous result shows that the proximity operator in [START_REF] Ono | Poisson image restoration with likelihood constraint via hybrid steepest descent method[END_REF] plays a prominent role in the calculation of the projection onto epi ϕ. We now provide several examples of function ϕ for which this proximity operator admits a simple form.

Proposition 2 Let τ ∈ ]0, +∞[. Assume that (∀y ∈ R) ϕ(y) = τ|y|. (19)
For every (y,

ζ ) ∈ R × R, P epi ϕ (y, ζ ) = (p, θ ) is given by p =    y, if τ|y| ≤ ζ , sign(y) 1 + τ 2 max{|y| + τζ , 0}, otherwise. (20)
and θ = max{τ|p|, ζ }.

The above result follows by the fact that 1 2 (max{τ|y|-ζ , 0}) 2 = (τ 2 /2) y 2τζ |y| + ζ 2 /2 if τ|y| > ζ and 0 otherwise, for which the proximity operator is known [START_REF] Chaux | A variational formulation for frame-based inverse problems[END_REF]Example 4.6]. This example clearly shows that Proposition 1 allows us to leverage the results on proximity operators already known in the literature. The following proposition considers the case when the absolute value is raised by a positive power. 2 Alternative characterizations of the epigraphical projection can be found in [40, Prop. 9.17 and 28.28], whereas the result reported in [2, Section 6.6.2] refers to a preliminary version of this paper.

Proposition 3 Let q ∈ ]1, +∞[ and τ ∈ ]0, +∞[. Assume that

(∀y ∈ R) ϕ(y) = τ|y| q . ( 21
)
For every (y,

ζ ) ∈ R × R, P epi ϕ (y, ζ ) = (p, θ ) is given by p =      sign(y)χ 0 , if ζ ≤ 0, y, if ζ > 0 and τ|y| q ≤ ζ , sign(y)χ ζ , otherwise, (22)
and θ = max{τ|p| q , ζ }, where χ • is the unique solution on [(•/τ) 1/q , +∞[ of the following equation

qτ 2 χ 2q-1 -qτζ χ q-1 + χ = |y|. (23)
Note that, when q is a rational number, ( 23) is equivalent to a polynomial equation for which either closed form solutions are known or standard numerical solutions exist.

The previous propositions allows us to establish a result concerning the distance function to a convex set.

Proposition 4 Let C be a nonempty convex subset of H . Let q ∈ [1, +∞[, τ ∈ ]0, +∞[, and ζ ∈ R. Assume that (∀y ∈ H ) ϕ(y) = τ d q C (y). (24)
For every (y,

ζ ) ∈ H × R, P epi ϕ (y, ζ ) = (p, θ ) is given by p = y, if y ∈ C, αy + (1 -α)P C (y), otherwise, (25)
and θ = max{τ d q C (p), ζ }, where

α = prox 1 2 (max{τ|•| q -ζ ,0}) 2 d C (y) d C (y) (26)
and the above expression is provided by Propositions 2-3.

In the case when q = 1 and C = {z} for some z ∈ H , the previous result can be specialized with d C (y) = yz and P C (y) = z. So doing, we obtain a corollary about the Euclidean norm, for which the corresponding epigraph is called the Lorentz cone and the associated epigraphical projection is known in the literature (see e.g. [2, Section 6.3.2]).

Corollary 1 Let τ ∈ ]0, +∞[, ζ ∈ R and z ∈ H . Assume that (∀y ∈ H ) ϕ(y) = τ y -z . ( 27
)
For every

(y, ζ ) ∈ H × R, P epi ϕ (y, ζ ) = (p, θ ) is given by p =      z, if y = z, y, if τ y -z ≤ ζ , αy + (1 -α)z, otherwise, (28)
and θ = max{τ pz , ζ }, where

α = 1 1 + τ 2 max 1 + τζ y -z , 0 . (29)
We conclude the section with a result about the weighted maximum of absolute values. When the weights are all equal, this function reduces to the standard infinity norm • ∞ , for which the expression of the epigraphical projection has been recently given in [START_REF] Ding | An introduction to a class of matrix cone programming[END_REF]. The following proposition provides a slightly more general result.

Proposition 5 Let (τ (m) ) 1≤m≤M ∈ ]0, +∞[ M . Assume that (∀y ∈ R M ) ϕ(y) = max 1≤m≤M τ (m) |y (m) |, (30)
where the values (ν (m) = τ (m) |y (m) |) 1≤m≤M are in ascending order. Then, for every

(y, ζ ) ∈ R M × R, P epi ϕ (y, ζ ) = (p, θ ) is given by p = sign(y (m) ) min |y (m) |, θ /τ (m) 1≤m≤M ( 31
)
and

θ = max          ζ + M ∑ m=m ν (m) (τ (m) ) -2 1 + M ∑ m=m (τ (m) ) -2 , 0          , ( 32
)
where m is the unique integer in {1, . . . , M + 1} such that

ν (m-1) < ζ + M ∑ m=m ν (m) (τ (m) ) -2 1 + M ∑ m=m (τ (m) ) -2 ≤ ν (m) (33)
(with the conventions

∑ 0 m=1 • = ∑ M m=M+1 • = 0, ν (0) = -∞ and ν (M+1) = +∞).

Image recovery problems

We propose to evaluate the performance of the proposed epigraphical solution in the context of image restoration, where H = R N , x ∈ R N denotes the image to be recovered, and z ∈ R K is an observation vector such that

z = DA x + b. (34)
We assume that A ∈ R N×N is a blurring operator, D ∈ R K×N is a decimation operator, 3 and b ∈ R K is a realization of zero-mean white Gaussian noise.

3 D thus corresponds to K ≤ N lines of the identity N × N matrix.

Constrained formulation

A usual approach to recover x from the degraded observations is to follow a variational approach that aims at solving a convex optimization problem defined as:

minimize x∈[0,255] N DA x -z 2 2 s. t. h(Fx) ≤ η, (35)
where η ≥ 0 and F ∈ R M×N is the linear operator associated with an analysis transform. Hereabove, the quadratic term aims at insuring that the solution is close to the observations, while the constraint imposes some regularity on the solution.

Regularization is essential for solving such an ill-posed problem, as it allows one to select, among competing solutions, the one that presents some form of parsimony or smoothness.

Natural images usually exhibit a smooth spatial behaviour, except around some locations (e.g. object edges), where discontinuities arise. Therefore, the quality of the results obtained through the aforementioned variational approach strongly depends on the ability of the operator F and the function h to model such a specific kind of regularity. Among the sophisticated regularization terms that have been recently developed in the field of image restoration, the most commonlyused ones can be generalized as

(∀y ∈ R M ) h(y) = L ∑ =1 y ( ) q p , (36)
where q ≥ 1, p ≥ 1 and y is block-decomposed as in [START_REF] Parikh | Proximal algorithms[END_REF].

The above function can model the q -norm in (9) when p = q and L = M. This norm has been largely used in combination with a sparsifying transform F, such as frames [START_REF] Chaux | A variational formulation for frame-based inverse problems[END_REF] or Laplacian operators. Indeed, the case q = 2 leads to Tikhonov regularization, whereas the case q = 1 yields a sparsityinducing regularization [START_REF] Donoho | De-noising by soft-thresholding[END_REF][START_REF] Bach | Optimization with sparsity-inducing penalties[END_REF].

The above function also matches the 1,2 -norm in (13) when q = 1 and p = 2. Such a mixed-norm is used in the classical total variation (TV) regularization to penalize the image gradient [START_REF] Rudin | Nonlinear total variation based noise removal algorithms[END_REF]. Although TV has emerged as a simple and successful convex optimization tool, it often fails to preserve textures, details and fine structures, because they are hardly distinguishable from noise. To improve this behaviour, the TV model has been extended by using some generalizations based on higher-order spatial differences [59] or a non-locality principle [START_REF] Gilboa | Nonlocal Operators with Applications to Image Processing[END_REF][START_REF] Buades | A review of image denoising algorithms, with a new one[END_REF][START_REF] Gilboa | Nonlocal linear image regularization and supervised segmentation[END_REF]. The latter yields the non-local-TV operator, defined as

Fx =   F 1 x . . . F N x   =    ω 1,n (x (1) -x (n) ) n∈N 1 . . . ω N,n (x (N) -x (n) ) n∈N N    , (37)
where, for every ∈ {1, . . . , N}, N ⊂ {1, . . . , N} \ { } denotes the neighborhood of and (ω ,n ) n∈N are positive weights. Note that (37) reduces to the classical gradient operator when N only contains the horizontal/vertical nearest neighbours of and ω ,n ≡ 1. 4 Several types of q,p -norms can be used to penalize the nonlocal gradient. The case q = p = 2 (i.e. the 2 -norm) may be seen as a variational extension of NonLocal Means [START_REF] Buades | A review of image denoising algorithms, with a new one[END_REF], while the case q = p = 1 (i.e. the 1 -norm) leads to NonLocal Medians [START_REF] Li | A new median formula with applications to pde based denoising[END_REF]. The case q = 1 and p ∈ {2, +∞} (i.e. the 1,pnorm) is instead preferred in color imagery [START_REF] Bresson | Fast dual minimization of the vectorial total variation norm and applications to color image processing[END_REF][START_REF] Miyata | Vectorized total variation defined by weighted L-infinity norm for utilizing inter channel dependency[END_REF]. In our experiments, we will present the results of q,p -non-local-TV for several values of q and p, in order to show that the proposed epigraphical splitting may be more efficient that the existing solutions for handling this class of constraints.

Optimization method

As mentioned in the introduction, proximal algorithms can efficiently solve Problem [START_REF] Vũ | A splitting algorithm for dual monotone inclusions involving cocoercive operators[END_REF] as long as the proximity operator of the involved functions can be efficiently computed. Unfortunately, the projection onto the lower level set of ( 36) cannot be computed in closed form. A possible approach to circumvent this issue is given by the epigraphical splitting presented in Section 2. Indeed, Problem [START_REF] Vũ | A splitting algorithm for dual monotone inclusions involving cocoercive operators[END_REF] can be rewritten as Problem 2 with R = 2,

T 1 = A, T 2 = I, g 1 = D • -z 2 2 , g 2 = ι [0,255] N and h = |•| q (for p = q ≥ 1) or h = • p (for q = 1
and p ∈ {2, +∞}). In order to solve this specific instance of Problem 2, we will consider two proximal methods: the primal-dual algorithm called Monotone+Lipschitz Forward Backward Forward (M+LFBF) [START_REF] Combettes | Primal-dual splitting algorithm for solving inclusions with mixtures of composite, Lipschitzian, and parallel-sum type monotone operators[END_REF], and the primal algorithm called Simultaneous-Direction Method of Multipliers (SDMM) [START_REF] Combettes | Proximal splitting methods in signal processing[END_REF]. According to the general results in [START_REF] Combettes | Primal-dual splitting algorithm for solving inclusions with mixtures of composite, Lipschitzian, and parallel-sum type monotone operators[END_REF]Theorem 4.2] and [START_REF] Combettes | Proximal splitting methods in signal processing[END_REF], the sequence x [i] i∈N generated by M+LFBF or SDMM is guaranteed to converge to a (global) minimizer of Problem 2.

Numerical results

The aim of our experiments is twofold. Firstly, we will display an example of image reconstructed with the different types of non-local-TV regularization, in order to evaluate the visual impact of each regularization. Secondly, in order to show the efficiency of the proposed epigraphical splitting, we will compare the execution time required by M+LFBF and SDMM to solve Problem (35) using: 1) the epigraphical approach, and 2) the standard approach that employs specific numerical methods to deal with a 1 -or 1,2 -ball [START_REF] Van Den | Probing the Pareto frontier for basis pursuit solutions[END_REF] and a 1,∞ -ball [START_REF] Quattoni | An efficient projection for 1,∞ regularization[END_REF]. 4 Methods for building N and setting the associated weights are described in [START_REF] Buades | A review of image denoising algorithms, with a new one[END_REF][START_REF] Gilboa | Nonlocal linear image regularization and supervised segmentation[END_REF][START_REF] Foi | Foveated self-similarity in nonlocal image filtering[END_REF]. In our experiments, we use the q,p -TV regularization to obtain an estimate of x, which we subsequently use to compute the weights through the self-similarity measure proposed in [START_REF] Foi | Foveated self-similarity in nonlocal image filtering[END_REF].

Fig. 1 illustrates the restoration of a RGB color image (N = 320 × 480 × 3) degraded by a 3 × 3 uniform blur (applied component-by-component), a decimation that randomly removes 60% of the pixels (K = 0.4 × N) and an additive white Gaussian noise with variance 10 2 . The constraint bounds η for the several q,p -balls were hand-tuned in order to achieve the best SNR values. These results show the interest of considering non-local operators and 1,∞ -norms for modelling the regularity present in color images.

Fig. 2 compares the speed of the considered algorithms (w.r.t. the example in Fig. 1), showing the distance x [i]x [∞] as a function of the execution time for the epigraphical approach and the approach based on the direct computation of projections. The stopping criterion is set to

x [i+1] -x [i] ≤ 10 -5 x [i]
, and x [∞] denotes the solution obtained when such a criterion is reached. Note that x [∞] may not be unique, hence it was computed for each algorithm independently. These plots indicate that the proposed epigraphical approach yields a faster convergence.

Since the constraint bound η may not be known precisely, it is important to evaluate the impact of its choice on our method performance (it is out of the scope of this paper to devise an optimal strategy to set this bound). In Tables 1234, we compare the execution times of epigraphical and direct approaches for different choices of regularization constraints and values of η. However, in order to reduce the computation burden of the direct projection onto the 1,∞ball, we present the results obtained with the grayscale image boat cropped at 256 × 256. 5 The stopping criterion is set to

x [i+1] -x [i] ≤ 10 -4 x [i]
. For more readability, the values of η are expressed as a multiplicative factor of the q,p -nonlocal-TV semi-norm evaluated on the original image.

-Tables 1 and2 report the comparison for 1,2 -TV and 1,∞ -TV, respectively. The convergence times indicate that the epigraphical approach yields a faster convergence although it requires more iterations in order to converge. This can be explained by the computational cost of the subiterations required by the direct projections onto the 1,p -ball. Moreover, the numerical results show that errors within ±20% from the optimal value for η lead to SNR variations within 2%.

-Tables 3 and4 collects the results of 1,2 -non-local-TV and 1,∞ -non-local-TV for different sizes of the neighbourhood N . The convergence times show that the epigraphical approach is faster than the direct one for both considered algorithms. Moreover, it can be noticed that errors within ±20% from the optimal bound value lead to SNR variations within 1%.

Note that our codes were developed in MATLAB R2011b (the operators F and F are implemented in C) and executed on an Intel Xeon CPU at 2.80 GHz and 8 GB of RAM.

Pulse shape design

We revisit the problem of a pulse shape design for digital communications presented in [START_REF] Combettes | A proximal decomposition method for solving convex variational inverse problems[END_REF], where it was addressed in terms of constrained convex optimization. Denote by x = x ( ) 0≤ ≤N-1 ∈ R N the pulse, by χ = χ ( ) 0≤ ≤N-1 its discrete Fourier transform, and assume that the underlying sampling rate is 2560 Hz. The following constraints arise from engineering specifications [START_REF] Combettes | A proximal decomposition method for solving convex variational inverse problems[END_REF].

(i) The modulus of the Fourier transform should not exceed the bound γ = 10 -3/2 beyond 300 Hz. This leads to

(∀ ∈ D 1 ) C ( ) 1 = x ∈ R N |χ ( ) | ≤ γ , (38)
where D 1 represents frequencies beyond 300 Hz. (ii) Vanishing frequencies of χ at the zero frequency and at integer multiples of 50 Hz:

C 2 = x ∈ R N (∀ ∈ D 2 ) χ ( ) = 0 ( 39
)
where D 2 denotes the frequencies where the Fourier transform χ vanishes. (iii) Symmetry of the pulse and its mid-point value should be equal to 1:

C 3 = {x ∈ R N | x (N/2) = 1 and (∀ ∈ {0, . . . , N/2}) x ( ) = x (N-1-) )}. (40)
(iv) Pulse duration should be 50 ms and it should have periodic zero crossings every 3.125 ms:

C 4 = x ∈ R N (∀ ∈ D 4 ) x ( ) = 0 , (41)
where D 4 is the set of time indices in the zero areas. (v) Pulse energy should be as small as possible, in order to avoid interference with other systems.

Optimization method

Some of the aforementioned constraints are incompatible (e.g. the second and the fourth ones). Hence, in order to make the problem feasible, we propose to replace the convex sets (C ( )

1 ) 1≤ ≤N with the following constraint:

C 1 = x ∈ R N ∑ ∈D 1 d q C ( ) 1 (χ ( ) ) ≤ η , (42)
where η > 0 and q ∈ [1, +∞[. Therefore, the resulting optimization problem reads minimize

x∈R N x 2 2 + 4 ∑ s=1 ι C s (x). (43)
As mentioned in the introduction, proximal algorithms can efficiently solve the above problem as long as the projection associated to each constraint (C s ) 1≤s≤5 can be efficiently computed. Unfortunately, the projection onto C 1 cannot be computed in closed form. We thus propose to circumvent this issue by using the epigraphical splitting presented in Section 2. Indeed, (43) can be rewritten as Problem 2 with

R = 4, T 1 = • • • = T 4 = I, g 1 = • 2 2 , g s = ι C s for each s ∈ {2, . . . , 4}, L = N and E = (y, ζ ) ∈ R N × R N (∀ ∈ D 1 ) (y ( ) , ζ ( ) ) ∈ epi d q C ( ) 1 , (44)
V = ζ ∈ R N 1 D 1 ζ ≤ η . (45)

Numerical results

Fig. 3 presents state-of-the-art results (from [START_REF] Combettes | A proximal decomposition method for solving convex variational inverse problems[END_REF]), while Fig. 4 presents the results obtained with the proposed solution for q = 2 and different values of η. Note that for large values of η, the solutions converge to a solution of the unconstrained (without imposing C 1 ) problem (cf. . It is also interesting to experimentally observe that the estimated pulse for the smallest value of η leading an admissible solution (cf. is similar to the solution proposed in [START_REF] Combettes | A proximal decomposition method for solving convex variational inverse problems[END_REF] (cf. Fig. 3 -middle). As illustrated by these experiments, the proposed approach allows us to gain more design flexibility at the expense of a small additional computational cost.

Conclusions

We have proposed a new epigraphical technique to deal with constrained convex optimization problems with the help of proximal algorithms. In particular, we have turned our attention to constraints based on distance functions and weighted q,p -norms. In the context of 1D signals, we have shown that constraints based on distance functions are useful for pulse shape design. In the context of images, we have used 1,pballs to promote block-sparsity of analysis representations. The obtained results demonstrate the good performance (in terms of image quality) of non-local measures and 1,∞ -norm in color imagery. Nevertheless, it would be also interesting to consider alternative applications of 1,∞ -norms, such as regression problems [START_REF] Yuan | Model selection and estimation in regression with grouped variables[END_REF].

Furthermore, the experimental part indicates that the epigraphical method converges faster than the approach based on the direct computation of the projections via standard iterative solutions. Parallelization of our codes should even allow us to accelerate them [START_REF] Gaetano | Parallel implementations of a disparity estimation algorithm based on a proximal splitting method[END_REF]. Note that, although the considered application involves two constraint sets, the proposed approach can handle an arbitrary number of convex constraints. In addition, the epigraphical approach could also be used to develop approximation methods for addressing more general convex constraints.

  Let C be a nonempty closed convex subset C of H . The relative interior of C is denoted by riC. For every y ∈ H , the proximity operator of ϕ reads prox ϕ (y) = argmin u∈H 1 2 uy 2 + ϕ(u). The indicator function ι C ∈ Γ 0 (H ) of C is equal to 0 for y ∈ C and +∞ otherwise. The projection onto C reads P C (y) = argmin u∈C uy . The distance to C is given by d C (y) = y -P C (y) .

Fig. 1

 1 Fig. 1 Comparison of SNR (dB) -SSIM [66] indices for an example of restoration.

Fig. 2

 2 Fig.2Plots (distance to x[∞] vs execution time) comparing the epigraphical and direct approaches implemented with M+LFBF and SDMM.

Fig. 3 k∈D 1 C (k) 1 ∩C 2 . (b) Minimizer of x 2 2 + ∑ k∈D 1 d 2 C k 1 (Fig. 4

 31122214 Fig.3State-of-the-art results: pulse x (top) and its Fourier transform χ (bottom). (a) Minimizer ofx 2 2 + d C 3 (x) + d C 4 (x) subject to x ∈ k∈D 1 C (k) 1 ∩C 2 . (b) Minimizer of x 2 2 + ∑ k∈D 1 d 2 C k 1 (x) subject to x ∈ C 2 ∩C 3 ∩C 4 . (c) Minimizer of x 2 2 subject to x ∈ C 2 ∩C 3 ∩C 4 .

  • | • . Γ 0 (H ) denotes the set of proper lower-semicontinuous convex functions from H to ]-∞, +∞]. Recall that a function ϕ : H → ]-∞, +∞] is proper if dom ϕ = y ∈ H ϕ(y) < +∞ is nonempty. The lower level set of ϕ at height ζ ∈ R is the closed convex subset of H defined as lev ≤ζ ϕ = y ∈ H ϕ(y) ≤ ζ , and the epigraph of ϕ ∈ Γ 0 (H ) is the closed convex subset of H ×R defined as epi ϕ

Table 1

 1 Results for the 1,2 -TV constraint and different values of η (w.r.t. the grayscale image boat cropped at 256 × 256)

				SDMM			M+LFBF
	η	SNR (dB) -SSIM	direct	epigraphical speed up	direct	epigraphical speed up
			# iter. sec.	# iter. sec.		# iter. sec.	# iter. sec.
	0.45	19.90 -0.733	107 6.07	174 2.03	2.99	113 6.15	182 3.49	1.76
	0.50	20.18 -0.745	117 6.95	159 1.95	3.57	116 6.97	168 3.44	2.03
	0.56	20.23 -0.745	129 8.36	153 1.90	4.41	124 8.17	159 3.01	2.72
	0.62	20.16 -0.737	141 9.44	155 1.83	5.16	131 8.62	159 3.26	2.65
	0.67	20.00 -0.724	154 10.20	162 2.17	4.71	140 10.00	164 2.84	3.52

Table 2

 2 Results for the 1,∞ -TV constraint and different values of η (w.r.t. the grayscale image boat cropped at 256 × 256)

				SDMM			M+LFBF
	η	SNR (dB) -SSIM	direct	epigraphical speed up	direct	epigraphical speed up
			# iter. sec.	# iter. sec.		# iter. sec.	# iter. sec.
	0.45	19.52 -0.726	160 312.55	231 3.89	80.43	183 347.10	252 6.43	53.96
	0.50	19.71 -0.728	168 342.01	215 3.75	91.31	185 368.24	236 5.83	63.17
	0.56	19.71 -0.734	180 373.60	211 3.49 106.93	189 386.29	229 5.53	69.91
	0.62	19.59 -0.715	196 412.68	216 3.67 112.50	198 411.04	229 5.86	70.15
	0.67	19.39 -0.698	211 448.77	223 3.76 119.27	207 437.66	234 5.76	75.96

Table 3

 3 Results for the 1,2 -non-local-TV constraint and different values of η (w.r.t. the grayscale image boat cropped at 256 × 256)

				SDMM			M+LFBF
	η	SNR (dB) -SSIM	direct	epigraphical speed up	direct	epigraphical speed up
			# iter. sec.	# iter. sec.		# iter. sec.	# iter. sec.
				Neighbourhood size: 3 × 3
	0.43	20.82 -0.757	208 20.67	211 10.93	1.89	82 6.95	93	3.76	1.85
	0.49	20.97 -0.765	167 16.84	177 9.01	1.87	75 6.61	83	3.47	1.91
	0.54	21.02 -0.767	147 15.31	157 7.93	1.93	71 6.45	77	3.15	2.04
	0.59	20.98 -0.764	134 14.44	148 7.67	1.88	72 6.58	77	3.24	2.03
	0.65	20.88 -0.757	133 14.82	136 7.11	2.08	76 7.53	80	3.27	2.30
				Neighbourhood size: 5 × 5
	0.43	21.00 -0.766	301 56.03	343 45.18	1.24	82 8.51	90	5.43	1.57
	0.49	21.15 -0.773	260 49.03	302 39.64	1.24	75 7.90	81	4.90	1.61
	0.54	21.20 -0.775	242 46.31	283 37.72	1.23	71 8.26	75	4.47	1.85
	0.59	21.17 -0.773	231 46.20	268 36.56	1.26	70 7.94	74	4.49	1.77
	0.65	21.08 -0.767	220 44.64	252 34.46	1.30	73 8.40	76	4.59	1.83

Table 4

 4 Results for the1,∞ -non-local-TV constraint and different values of η (w.r.t. the grayscale image boat cropped at 256 × 256)

				SDMM		M+LFBF
	η	SNR (dB) -SSIM	direct	epigraphical speed up	direct	epigraphical speed up
			# iter. sec.	# iter. sec.	# iter. sec.	# iter. sec.

Note that the linear inequality over the auxiliary vector ζ can be also replaced by an equality, even though it makes little difference in our approach.

Note that the 1,2 -norm performs better on grayscale images.

which shows that [START_REF] Ono | Poisson image restoration with likelihood constraint via hybrid steepest descent method[END_REF] holds. Let us now consider the case when ϕ(y) > ζ . From the definition of the projection, we get

From the Karush-Kuhn-Tucker theorem [68, Theorem 5.2], 6 there exists α ∈ [0, +∞[ such that

where the Lagrange multiplier α is such that α(ϕ(p)-θ )=0.

Since the value α = 0 is not allowable (otherwise it would lead to p = y and θ = ζ ), it can be deduced from the above equality that ϕ(p) = θ . In addition, differentiating the Lagrange functional in [START_REF] Tikhonov | Regularization of incorrectly posed problems[END_REF]

Furthermore, as ϕ(y) > ζ , we obtain

where we have used the fact that P lev ≤ζ ϕ (y) belongs to the boundary of lev ≤ζ ϕ which is equal to

Altogether, ( 49) and ( 51) lead to

which is equivalent to (18) since 1 2 (max{ϕ -ζ , 0}) 2 ∈ Γ 0 (H ).

6 By considering u 0 ∈ dom ϕ and ξ 0 > ϕ(u 0 ), the required qualification condition is obviously satisfied.

Proof of Proposition 3

Since (max{ϕ -ζ , 0}) 2 is an even function, prox 1 2 (max{ϕ-ζ ,0}) 2 is an odd function [START_REF] Chaux | A variational formulation for frame-based inverse problems[END_REF]Remark 4.1(ii)]. In the following, we thus focus on the case when y ∈ ]0, +∞[. 2 is differentiable and, according to the fact that p = prox f (y) is uniquely defined as

where p ≥ 0 by virtue of [START_REF] Combettes | Proximal thresholding algorithm for minimization over orthonormal bases[END_REF]Corollary 2.5]. This allows us to deduce that p = χ 0 .

Let us now focus on the case when

= 0, we have p = y. On the other hand if y > (ζ /τ) 1/q , as the proximity operator of a function from R to R is continuous and increasing [69, Proposition 2.4], we obtain

Since (max{ϕζ , 0}) 2 is and, for each v ≥ (ζ /τ) 1/q , (max{ϕ(v)ζ , 0}) 2 = (τv qζ ) 2 , we deduce that p is the unique value in [(ζ /τ) 1/q , +∞[ satisfying (53).

Proof of Proposition 4

Let us notice that 1 2

where α =

. In addition, we have

and, according to Proposition 2, when ζ<0 and d C (y)≤-τζ , prox ψ d C (y) = 0. This shows that (55) reduces to (25).

Proof of Proposition 5

For every (y, ζ ) ∈ R M × R, in order to determine P epi ϕ (y, ζ ), we have to find

|p (1) |≤θ /τ (1) ...

For all θ ∈ [0, +∞[, the inner minimization is achieved when, ∀m ∈ {1, . . . , M}, p (m) is the projection of y (m) onto the range [-θ /τ (m) , θ /τ (m) ], as given by [START_REF] Esser | A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science[END_REF]. Then, (57) reduces to

which is equivalent to calculate θ = prox φ +ι [0,+∞[ (ζ ) where

The function φ belongs to Γ 0 (R) since, for each m∈{1, . . . , M}, max{(τ (m) ) -1 (ν (m) -•), 0} is finite convex and (•) 2 is finite convex and increasing on [0, +∞[. In addition, φ is differentiable and such that, for every v ∈ R and k ∈ {1, . . . , M + 1},

By using [25, Prop. 12], θ = P [0,+∞[ (χ) with χ = prox φ (ζ ).

Therefore, there exists an m ∈ {1, . . . , M + 1} such that ν (m-1) < χ ≤ ν (m) and ζχ = φ (χ), so leading to

and ν (m-1) < χ ≤ ν (m) ⇔ (33). The uniqueness of m ∈ {1, . . . , M + 1} follows from that of prox φ (ζ ).


Boucherit, Gilles FER BENN AND THE DEER CULT IN BUILE SUIBHNE

In his introduction to the 1996 reprint of the middle-Irish romance Buile Suibhne, Nagy writes that Chadwick is the first to "conjure the notion of Suibhne as shaman, of the geilt as both possessed by and possessor of supernatural inspiration and power, a practitioner of ‗archaic techniques of ecstasy', to use Mircea Eliade's phrase, comparable to similar practitioners both in and well beyond the Celtic world 1 .‖ When examining her 1942 article -Geilt‖ 2 , nowhere have we found the word shaman 3 . It is true, however, that in her 1952 book -Poetry and prophecy‖, Nora Chadwick studies different traditions throughout the world related to vision, but more globally, the origin of "the inspiration of the seer" which can be "derived from a variety of sources, 4 ‖ for instance "inspiration received in a vision during a battle" as in Irish and Welsh traditions. But, as Nagy says, she does not confine herself to the Celtic world, she also explores "the most interesting figure in Norse mantic tradition of the God Othin, whose most obvious affinities are with the Siberian shamans whom he resembles in a remarkable degree 5 ". This means that shamanistic and Geilt traditions are parallel or comparable to Siberian, Turkish, or even Polynesian ones for instance. It would be more relevant to speak of all these people in their different traditions in terms of Seers, and Nora Chadwick wonders whether these traditions were ever derived from a single one. One will have to wait for Brigit Beneš' 1961 article 'Spuren von Schamanismus in der Sage "Buile Suibhne"', to realise that in spite of everything, one cannot evidence the equation of a geilt with a shaman : -Es sei gleich vorweggenommen, daß nicht exakt bewiesen werden kann, daß ein geilt ein wirklicher Schamane ist [...] 6 ." However, Nagy writes in his 1982 article -The wisdom of the geilt‖ that ‖the sacerdos Rónán creates a shaman out of the king Suibhne, who is ultimately fostered and guided by another sacerdos Moling, a kind of shaman himself 7 .‖ This is conceivable theoretically even if shamanism 8 is not a very old phenomenon. Therefore, in order to find an answer to this open question, we are going to show that there is a deer cult in the romance Buile Suibhne which originates in Siberia and that we can trace it from there to the Atlantic thanks to archaeological finds. Then with the help of a cylindrical jet seal and the Early Hittites deer cult we'll try to show that the Fer Benn in Buile Suibhne and in Cath Magh Tuired is at the crossroad between two civilisations, the hunter and the pastoralist ones.

THE SIBERIAN TRAIL

But in order to make our point, we have to let aside the fictitious character Suibne the geilt, who grew mad at the battle of Magh Rath (637 AD) and -went, like any bird of the air, in madness and imbecility 9 ,‖ and focus our attention on Fer Benn, Suibhne's real name, who speaks to the mother of a herd of deer, which he seems to be the guardian of when he says at paragraph 40 : "Cidh iomdha dom dhamraidh-si / Though many are my stags 10 ", and later on : "A mathair na groidhi-si / rolíatha do lenn, / ni fhuil damh at dheagaidh-si / gan dá fhichead benn" "O mother of this herd, / thy coat has become grey, / there is no stag after thee / without two score antler-points 11 .‖ This situation is strikingly similar to the Siberian one, in Anisimov's 1959 article 'Cosmological concepts of the people of the north' where -the mistress of the earth has a husband-the nameless shepherd of her herd. Together with assistants, likewise nameless shepherds, he tends countless droves of all sorts of animals which the mistress of the earth has at her disposal [START_REF] Anisimov | Cosmological concepts of the people of the North[END_REF] ". Contrary to Siberia, Fer Benn is no husband since he speaks to a mother, and his name means -man of the peaks‖, that is peaks of mountains as well as peaks or tops of antler-points, as this play on words will show :

"síu nobheinn for udmhaille / ag siredh na mbenn".

-before I restlessly / wandered over the mountain-peaks 13 ‖.

maith an t-ionadh foradhán (?) / I mullach do bhenn.

-pleasant is the place for seats / on the top of thy antler-points 14 ‖.

Among the Tungus (or Evenks) of Siberia, this mistress of the earth is one of the two clan's female spirits who are supposed to be living under the roots of the sacred clan tree [START_REF] Anisimov | See also Alexandra BERGHOLM[END_REF] , namely the mistress-mother of the clan, the so-called bugady enintyn [START_REF] Jacobson | The Deer Goddess of Ancient Siberia[END_REF] , and the mistress of the clan lands, the so-called dunne mushunin (musunin). The mistress of the clan lands, was thought to be anthropomorphic by the Evenks, while the mythical mother of people and animals 17 , was conceived in one and the same zoomorphic image of an elk cow or the doe of a wild deer. But as a consequence of the decline of the matrilineal clan structure, the image of the zoomorphic clan mother is transformed by degrees into that of a mistress, loosing thereby its former function of motherhood 18 , while her zoomorphic features are gradually displaced by anthropomorphic ones. Fer Benn is very like one of the Evenk's spirit-ancestors who dwell in the nether world and are linked with the image of the clan tree or cosmic tree: -they sit on its branches, guarding the life and well-being of the clan.‖ This is exactly what Fer Benn does actually, guarding the stags of the mother of the clan or of the universe: -When necessary, the spirits change their zoomorphic form, transforming themselves into people, kinsmen, assistants of the mythical old woman, the mistress of the clan's settlement of the spirits 19 ‖. This is probably one of the best description one can make of Fer Benn, which suits well the image he gives of himself, feathered and swift like a bird when he says in the poem :

" Therefore, now we can say that Fer Benn is originally a spirit turning at will from a zoomorphic to an anthropomorphic aspect, bird or guardian of the herds of the mother of the clan. The analogy between the branches of the tree and the antlers of the elk or maral is quite obvious when we know as we said that among the Evenks the mother animal of the clan is conceived as an elk cow or the doe of a wild deer and that she is supposed to be dwelling under the roots of the sacred clan tree.

The rite shingkelavun 22 deserves mention here because -the Evenki hunters, like the Paleolithic «sorcerers» portrayed in the Trois Frères caves, much alike the hunting Amerindian decoy runner, wore ritual costumes, with caps made from the skulls of reindeer or elks, imitating the heads of these animals 23 .‖ The object was to perform ritual pantomimes -supposed to bring all the animals of the taiga to the clan's hunting grounds.‖ -This rite lasted many days, and was carried out by the entire clan near the rock, cliffs, and trees sacred to itthe bugady (sacred objects of the clan). In essence, this ritual corresponded to the legend of the pursuit of the sun-animal by hunters, its killing and death, and then the sacrificial meal, with the subsequent solemn burial of the bones and the miraculous resurrection of the buried animal 24 .‖ The myth of the Cosmic hunt referred to here ‖was a form of personification of the sun cycle which corresponded to and reflected the forms of economic activities of primitive man 25 .‖ And this is no epiphenomenon since -Siberian ethnographic materials show that the link of the elk-maral image with the sun is one of the most ancient elements of the cosmological concepts of the peoples of Siberia 26 .‖ Therefore, since everything brings us to the conclusion that the Irish 'mother of this herd' whom Fer benn addresses is a spirit-mother of the Siberian kind, archaeology should allow us to pass from the one world to the other. that the Europoid migrants from Repin met with Mongoloid people of the forest belt and that the boundary between them was by no means permanent. For instance, "the neolithic population of the taiga west of Lake Baïkal, in particular, shows a Europoid admixture. In their turn, the Mongoloid elements penetrated into the steppe regions [START_REF] Levin | The peoples of Siberia[END_REF] Epokha Bronzy Kavkaza I Srednei Azii, ed. Kushnareva, Markovin, 1994.

-The most likely date for grave 4 is evidently the beginning of the third millennium B.C.‖ explains to us Nekhaev 36 because of the technology of the seal from Mesopotamia which cannot be older than that. David Anthony speaks of radiocarbon post-Maikop dates, 3000-2800 BCE 37 . This chronology coincides with the pre-transformational period in Siberia, when matrilineal tribal life still prevailed. At the same period on the Middle Don there happens -the second spread of the Repin culture‖ at the final Eneolithic of the Black Sea steppe 38 in several directions, especially to the North Caucasus at the Novosvobodnaya 39 or post Maikop period which is exactly that of the jet seal. The association in a tomb of these two symbols Tree and Deer recall the mother animal dwelling under the roots of the sacred clan tree, with yet no shepherd. Besides, since we know that -the ranges of the red deer and European fallow deer do not extend into the Mesopotamian lowlands, and Mesopotamian fallow deer are not found in Anatolia 40 ‖, we can but being convinced that the origin of Cervus elaphus on the jet seal with its well developed antlers is different from that of the technique of the seal. All the more so as the early Hittites who will appear a few centuries later in Anatolia will bring with them their totemic deer cult. Moreover, for historians, before their identification as Indo-Europeans, -The Hittites were an -ugly‖ people -with yellow skins and ‗Mongoloid' features,‖ with -receding foreheads, oblique eyes, and protruding upper jaws [START_REF] Collins | The Hittites and their world[END_REF] .‖

THE HITTITES

A brief study of the early Hittites (2.300-1.900 B.C.), precisely between the middle of the third and the beginning of the second millennium B.C., will strengthen our analysis of the deer and tree jet seal since : « The richness and grave type of the Maikop royal tomb is comparable to that of Alaca Höyük in northern central Anatolia, which itself probably belonged to an Indo-European (pre-or early Hittite) ruler 42 .» It appears quite clearly that if the 9 figurations of deer at Alaca Höyük are associated with sun discs, this is not the case for the bull. This means that the symbolic function of the two animals is different :

As a hunted animal, the deer is paramount, as well as symbolizing a deity. These two aspects for us seem to be the two faces of a unique function where the sacred animal is killed and sacrificed, and the hunted animal is deified [START_REF] Crepon | Le cerf est en effet l'animal chassé par excellence et il est aussi l'animal symbolisant une divinité. Ces deux rôles nous semblent cependant être les deux pôles d'une même fonction où l'animal sacré est tué et sacrifié, et l'animal chassé est déifié» in Le thème du cerf dans l'iconographie anatolienne des origines à l'époque Hittite[END_REF] .

The author, Pierre Crepon, goes on saying that there are numerous other similar cases in different cultures, for instance the bear among the Ainus. But he could have mentioned the red deer among the Tungus as well.

On top of that the hinds are milked within the Hittites sacred enclosures as attested on Puşatly altar of the fifth century A.D. reminding of Pedachtoe enclosures for sacred animals [START_REF] Thierry | Le culte du cerf en Anatolie et la vision de saint-Eustathe[END_REF] of the third century A.D., being themselves a very old heritage going back at least to the middle of the third millennium B.C. as testified on numerous painted pottery found at Alishar Höyük, Boghazkeuï and elsewhere 45 .Therefore we can safely say that like the Tungus, the deer among the ancient Hittites is a sacred animal, that is the zoomorphic epiphany of the spirit-mother dwelling under the tree, as totem centre of the clan or tribe.

As for the bull now, later on as we know, the -roaring bull‖ will be associated with thunder, ‖but may be at this phase of symbolism the manlike storm-god picturing the male principle did not still exist in Anatolia [START_REF]Le disque solaire Hittite d'après les documents archéologiques[END_REF] .‖ In a first step of the hibridization process the male principle will appear associated with the male deer. Later on, the hart will be replaced by the bull, and :

Finally at Doliche in Commagene, the cult of which is linked to Anatolia by its Hittites origins, Hadad, the thunderbolt god, pictured staying on a bull, is accompanied by a goddess, staying often on a hind [START_REF]Enfin à Doliché en Gomagène, dont le culte se rattache par ses origines hittites à [celui] d'Anatolie, Hadad, le dieu de la foudre, figuré debout sur le taureau, a pour parèdre une déesse[END_REF] .

In the final phase coinciding with the Empire, the male principle will overcome. This evolution of the male principle will strengthen our forthcoming hypothesis about Fer Benn as Dagda's first name in Cath Magh Tuired.

THE DEER TRAIL

But contrary to the Hittites who reached southward the Caucasus Mountains, some other Proto-Indo-European of the Yamnaya groups went westward, and one of them in eastern Hungary could have spawned both pre-Italic and pre-Celtic. Therefore from now on, following the deer trail means following the Indo-Europeans to the Atlantic, as in the Usatovo tumuli: -The bull and stag were the chief animals in burial rites [...] in the Crimea and the district of Odessa 48 (...). » -The general character of the symbolism is reminiscent of Val Camonica and south Scandinavian rock engravings 49 .‖ In Polonia there has been found a deer in a burial at Pikutkowo 50 brought there by the Corded pottery (or Battle Axe) people before the complex reached Scandinavia, where ‖the stag was involved in the general complex of ideas which surrounded the ship 51 [...], and sometimes replaces the horse as the sun animal 52 .‖ In the Val Camonica, the relationship between the deer and the sun will prove fundamental although mysterious, as shown by a figure carved in Paspardo whereon the symbolized beams of a sun take the shape of antler-tines 53 . Now Cernunnos, whose etymology is the same as Hittite Kurunta from PIE *ker 54 , is by far the most famous deer related deity in Gaul, on the Gundestrup cauldron for instance.

In the meantime, deer rock drawings had appeared in the Iberian peninsula as early as 2000 B.C.E. in Galicia [START_REF] Buhígas | Corpus petroglyphorum Gallaciae. A Coruña: Seminario de estudos Galecos[END_REF] , and consequently, the deer cult became widespread in the whole of the pre-roman peninsula where -the deer was considered the mythic ancestor of the Celts and Germans, since it is one of the most popular symbols of fecundity, as the funeral animal, and the guide of the dead [START_REF]Enfin, pour convaincre de l'importance du cerf, il suffit de nous rappeler la lutte très dure et prolongée de l'église contre les rituels de déguisement du cerf[END_REF] .‖ From Galicia the rock drawings will sail to Ireland and Scotland : in Scotland there are deer carvings at Ford, and they are linked with the Food-vessels like in Galicia [START_REF]Scotland about 800 BC and Yorkshire about 500/400 BC[END_REF] .

FER BENN / DAGDA

This being said, we cannot fail to mention the other Fer Benn, namely the Dagda : both Suibhne and the Dagda have a problem with their real name which actually is Fer Benn, or should I say which begins with Fer Benn concerning the Dagda, since his written full name with its 22 terms [START_REF] Sayers | Cerrce, an archaic epithet of the Dagda, Cernunnos and Conall cernach[END_REF] is two lines long [START_REF]Cath Maige Tuired : the Second Battle of Mag Tuired[END_REF] .

We have just seen that the Hittite male principle is the direct ancestor of Zeus or Jupiter Dolichenos the god father, which corresponds in Ireland to the Daghdha Ollathair (i.e. universal father). This male principle will appear in the first place standing on a male deer, holding the bow and the thunderbolt staying on a deer it keeps on the leash [...]. So that this name Fer Benn stuck to the Dagda, does not look that unexpected after all. We may have in Ireland the remains of a popular tradition in which -Fer benn‖ could have acted as a kind of graft in the course of the hybridization process along the centuries between the matricentered Siberian hunters and the patricentered Kurgan pastoralists, the origin of which is to be seeked in the Yamanaya horizon. I suggest that the male principle would have appeared in an early phase of the evolution as the son of the animal-mother, whereas in a later phase this male principle would have turned into an insignificant husband of the mistress of the earth Dunne mushunin. Interestingly, among the early Hittites, -the Mother Goddess came before her spouse, the Storm God. Whether this situation reflects a matriarchal system has not yet been settled, but certain scholars accept this idea 60 .‖ Even in Ireland the Dagda's symbolism is close enough by some aspects to the deer one, in so far as his very name, Celtic *Dago-dēwos means good god, but also good day since día -god‖ and día -day‖ come from the same *deiwo-s: -the Indo-European name of the blue sky and the day god [START_REF] Lambert | Lexique étymologique de l'irlandais ancien de J. Vendryès[END_REF] .‖ This way the link of the Dagda with the sun becomes conspicuous, -the sky god, storm god, earth god, and the sun [START_REF] Simmons | Celtic culture: a historical encyclopedia[END_REF] ,‖ rising sun but also setting sun wherefrom he would get his association with death and regeneration. And this is another common feature the Dagda shares with the deer symbolism, which relation with the sun and the nether world is pervading. To such an extent as one may ask whether the Irish Dagda is the same god as the Gaulish Taranis 63 , whose association with the thunder of the roaring bull is complete.

This possible part played by Fer Benn as a graft with the pastoral kurgan mythology represented in Ireland by the Dagda of the Tutha Dé Danann, is given more potency by the name of the (mistress-)mother of the clan Bugady Enintyn and the mistress of the clan lands Dunne mushunin. First, -the synonym for buga is dunne (dunda),‖ and moreover :

The stem dun || don is apparently of very ancient origin, and existed before the crystallization of the linguistic stocks [which form the basis of] modern language families. In Sanskrit the word dhuni meant -river.‖ A. Afanasyev points out that [the] word dhuni was introduced into the Slavic languages from the east (-Don,‖ -Danube,‖ and, in general, -river‖ in the songs of the Poles and Galicians) [START_REF] Vasilevich | Early concepts about the universe among the Evenks (materials), in Studies in Siberian shamanism. Ibid. : -As it developed further, its original meaning, -surrounding nature‖ (mountains, rivers, forests) was restricted differently in the different linguistic stocks: in some[END_REF] .

The name of the river Danube is said to come from the older form *Dānouio,- If this common inherited word as it seems was the Tungus -dunne,‖ it would appear therefore that there is a linguistic link between Tungus -dunne,‖ Proto-Celtic Dānouio-, and Welsh Donwy‖. This of course would be quite a strong case for a deer cult in the Celtic countries coming from Siberia.

CONCLUSION

All this brings us back to Nora Chadwick's analysis of the mythological situation in North Western Medieval Europe where connections between Celtic and Norse mantic traditions for example can clearly be evidenced. We have just shown from the Celtic point of view that in order to explain these connections, one does not need the help of a shaman 67 , a Siberian personage who cannot be older than the Bronze Age [START_REF] Diószegi | Tracing shamans in Sibiria[END_REF] , that is the first half of the second millennium BCE, and whose name is not attested before the second part of the first millenium B.C 69 . Our opinion is justified by the fact that beyond the pastoralist tradition originating in the Kurgan civilisations from the steppes as shown by Marija Gimbutas, there is also connected to it a hunting tradition very much apparent among the Early Hittites, and among the Irish with Fer Benn and also in the Leinster or Finn cycle. This tradition, I think goes back as far as the end of the fourth millenium B.C. in Western Siberia, involving Europoid and Mongoloid people as well. It is true however that if the pre-Christian Celts are not concerned with shamanism, they are much concerned with totemism or ancestors cults, the deer cult being one of them.

In the same time, I feel very much concerned with Nora Chadwick's theme of research ‗the inspiration of the seer', neutral and universal as it is it takes into account a wide range of completely different traditions throughout the world. After all, seeking a vision is the accomplishment of a seer or seeress, whether he or she be named locally a shaman, a file or whatever :

The Ket [for example] are broadly similar to other early hunter-gatherers across the globe, where certain members of the tribe are regarded as being endowed with special powers to heal the sick through spiritual intervention, normally accomplished through magical singing [START_REF] Vajda | The Ket are broadly similar to other early hunter-gatherers across the globe, where certain members of the tribe are regarded as being endowed with special powers to heal the sick through spiritual intervention, normally accomplished through magical singing[END_REF] .

In this respect, the Native Northern American civilisations, in which visions [START_REF] Turner | Les Indiens d'Amérique du Nord[END_REF] , dreams and magical songs [START_REF]Le grand livre des Indiens d'Amérique[END_REF] are central in the relation to the spirits, as in the Celtic countries never involved a shaman.

E koun PER DENEZ (1921-2011), tad ar c'helenn brezhoneg

FIGURE 1 :

 1 FIGURE 1 : Afanasievo emigration (3700-3300 B.C.E.) (Anthony, 2007, p. 308)

  ." This chronology enables the mixed Europoid-Mongoloid population of the Afanasievo-Serovo cultural world to have taken part -[...] about 3300 BC [to] the rapid diffusion of the early Yamnaya horizon across the Pontic-Caspian steppes‖ and -after a pause of only a century or two, about 3100-3000 BC [to a] large migration stream [which] flowed up the Danube valley and into the Carpathian basin during the Early Bronze Age 34 ,‖ which we'll find again later on. Therefore, from these archaeological considerations we can draw the conclusion that the Siberian trail is confirmed by chronology. THE CYLINDRICAL JET SEAL The next step that archaeology enables us to follow is this jet cylindrical seal found in Krasnogvardeisk near Maikop Northern Caucasus, in the tomb of a man near his skull, with engraved images of a deer and, [...], the tree of life 35 ‖.

FIGURE 4 :

 4 FIGURE 4: 1-Krasnogvardeisk, mound 4; 2, 3-Tepe-Gawra (after A. Tobler); 4-Egypt (after P. Amiet).

  Fer[a]n eidhinn iomuallach / an tan eirghius duinn, / goirid bhim da ttarrachtain / o rofas mo chluimh. When the proud turtle-dove / rises for us, / quickly do I overtake it / since my feathers have grown20 .‖ O little fawn, O little long-legged one, / I was able to catch thee / riding upon thee / from one peak to another 21 .‖

	And elsewhere :
	"A ellteóg, a luirgnechóg, / fuarauss-[s]a do ghreim, / misi ort ag marcaighecht / as gach
	beinn a mbeinn.

  ). The great petroglyphic representations of elk and in particular of female elk are dated to the Serovo stage; during the Kitoy, that image lost its impressive monumentality,» p. 91.

29

Ibid., p. 32

30

ANTHONY, David W. The horse, the wheel and language: how Bronze Age riders from the Eurasian steppes shaped the modern world. Princeton and Oxford, 2007, p. 306.

31

Ibid., pp. 308-309.

32

Ibid., p. 311

  The Welsh river-name Donwy reflects this same original form Dānouio-, which is thus shown to have existed in Proto-Celtic 65 .‖ The Slavic river-names Don, Dniepr, and Dniestr are borrowings from Scythian *dānu, *dānu apara ‗upper river', *dānu nazdya ‗lower river'. Although these three river names are loans from Scythian [...], Welsh Donwy leaves no doubt that Celtic and Iranian had the same inherited river-name [...] 66 .

DINNEEN Foclóir gaedhilge agus béarla GEALT, g. -eilte, d. -eilt, pl. -a, geilte-(anna), f. : a madman or lunatic, a crazy person; a preternatural being in folklore, a sylph Génie de l'air de la mythologie gauloise et germanique (petit robert 1989, p. 1903) Suibhne geilt S. The mad A GEILT : one who goes mad from terror ; a panic striken fugitive from battle ; a crazy person living in the woods and supposed to be endowed with the power of levitation ; a lunatic ; translated volatilis Magh Rath Dal Riada Domnall Brecc, Lough Neagh Ui Neill Domhnall son of Aedh Fer Benn adresses a prayer to a mother of a herd of deer... The Yamna culture ( Ukrainian: Ямна культура, Russian: Ямная культура, "Pit [Grave] Culture", from Russian/Ukrainian яма, "pit") is a late copper age/early Bronze Age culture of the Southern Bug/Dniester/Ural region (the Pontic steppe), dating to the 36th-23rd centuries BC. The name also appears in English as Pit Grave Culture or Ochre Grave Culture.

Dana mère mythique de la dernière génération des dieux qui régnèrent sur l'Irlande. pre chretiens TDD / Fomoire