Pierre Stock
email: pstock@fb.com

Benjamin Graham

Rémi Gribonval

Hervé Jégou

EQUI-NORMALIZATION OF NEURAL NETWORKS

Modern neural networks are over-parametrized. In particular, each rectified linear hidden unit can be modified by a multiplicative factor by adjusting input and output weights, without changing the rest of the network. Inspired by the Sinkhorn-Knopp algorithm, we introduce a fast iterative method for minimizing the 2 norm of the weights, equivalently the weight decay regularizer. It provably converges to a unique solution. Interleaving our algorithm with SGD during training improves the test accuracy. For small batches, our approach offers an alternative to batchand group-normalization on CIFAR-10 and ImageNet with a ResNet-18.

INTRODUCTION

Deep Neural Networks (DNNs) have achieved outstanding performance across a wide range of empirical tasks such as image classification [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF], image segmentation [START_REF] He | [END_REF], speech recognition (Hinton et al., 2012a), natural language processing [START_REF] Collobert | Natural language processing (almost) from scratch[END_REF] or playing the game of Go [START_REF] Silver | Mastering the game of go without human knowledge[END_REF]. These successes have been driven by the availability of large labeled datasets such as ImageNet [START_REF] Russakovsky | Imagenet large scale visual recognition challenge[END_REF], increasing computational power and the use of deeper models (He et al., 2015b).

Although the expressivity of the function computed by a neural network grows exponentially with depth (Pascanu et al., 2013;[START_REF] Raghu | On the expressive power of deep neural networks[END_REF]Telgarsky, 2016), in practice deep networks are vulnerable to both over-and underfitting [START_REF] Glorot | Understanding the difficulty of training deep feedforward neural networks[END_REF][START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF]He et al., 2015b). Widely used techniques to prevent DNNs from overfitting include regularization methods such as weight decay [START_REF] Krogh | A simple weight decay can improve generalization[END_REF], Dropout (Hinton et al., 2012b) and various data augmentation schemes [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF][START_REF] Simonyan | Very deep convolutional networks for large-scale image recognition[END_REF][START_REF] Szegedy | Going deeper with convolutions[END_REF]He et al., 2015b). Underfitting can occur if the network gets stuck in a local minima, which can be avoided by using stochastic gradient descent algorithms [START_REF] Bottou | Large-scale machine learning with stochastic gradient descent[END_REF][START_REF] Duchi | Adaptive subgradient methods for online learning and stochastic optimization[END_REF][START_REF] Sutskever | On the importance of initialization and momentum in deep learning[END_REF][START_REF] Diederik | Adam: A method for stochastic optimization[END_REF], sometimes along with carefully tuned learning rate schedules (He et al., 2015b;[START_REF] Goyal | Accurate, large minibatch SGD: training imagenet in 1 hour[END_REF].

Training deep networks is particularly challenging due to the vanishing/exploding gradient problem. It has been studied for Recurrent Neural networks (RNNs) [START_REF] Hochreiter | Gradient flow in recurrent nets: the difficulty of learning long-term dependencies[END_REF] as well as standard feedforward networks (He et al., 2015a;[START_REF] Mishkin | All you need is a good init[END_REF]. After a few iterations, the gradients computed during backpropagation become either too small or too large, preventing the optimization scheme from converging. This is alleviated by using non-saturating activation functions such as rectified linear units (ReLUs) [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF] or better initialization schemes preserving the variance of the input across layers [START_REF] Glorot | Understanding the difficulty of training deep feedforward neural networks[END_REF][START_REF] Mishkin | All you need is a good init[END_REF]He et al., 2015a). Failure modes that prevent the training from starting have been theoretically studied by [START_REF] Hanin | How to start training: The effect of initialization and architecture[END_REF].

Two techniques in particular have allowed vision models to achieve "super-human" accuracy. Batch Normalization (BN) was developed to train Inception networks [START_REF] Ioffe | Batch normalization: Accelerating deep network training by reducing internal covariate shift[END_REF]. It introduces intermediate layers that normalize the features by the mean and variance computed within the current batch. BN is effective in reducing training time, provides better generalization capabilities after training and diminishes the need for a careful initialization. Network architectures such as ResNet (He et al., 2015b) and DenseNet [START_REF] Huang | Densely connected convolutional networks[END_REF] use skip connections along with BN to improve the information flow during both the forward and backward passes.

. . . " # . . . " # " # " # W k ⇥ 1 ↵ nk ⇥↵ nk ⇥ 1 ↵ 1 ⇥↵ 1 ⇥ 1 ↵ 2 ⇥↵ 2 ⇥1/↵ 2 ⇥1/↵ 1 ⇥1/↵ nk ⇥1/ nk ⇥1/ 1 ⇥1/ 2 ⇥ 2 ⇥ 1 ⇥ 1 nk ⇥ n k ⇥ 1 1 ⇥ 1 2 W k+1
Figure 1: Matrices W k and W k+1 are updated by multiplying the columns of the first matrix with rescaling coefficients. The rows of the second matrix are inversely rescaled to ensure that the product of the two matrices is unchanged. The rescaling coefficients are strictly positive to ensure functional equivalence when the matrices are interleaved with ReLUs. This rescaling is applied iteratively to each pair of adjacent matrices. In this paper, we address the more complex cases of biases, convolutions, max-pooling or skip-connections to be able to balance modern CNN architectures.

However, BN has some limitations. In particular, BN only works well with sufficiently large batch sizes [START_REF] Ioffe | Batch normalization: Accelerating deep network training by reducing internal covariate shift[END_REF]Wu & He, 2018). For sizes below 16 or 32, the batch statistics have a high variance and the test error increases significantly. This prevents the investigation of highercapacity models because large, memory-consuming batches are needed in order for BN to work in its optimal range. In many use cases, including video recognition [START_REF] Carreira | Quo vadis, action recognition? A new model and the kinetics dataset[END_REF] and image segmentation [START_REF] He | [END_REF], the batch size restriction is even more challenging because the size of the models allows for only a few samples per batch. Another restriction of BN is that it is computationally intensive, typically consuming 20% to 30% of the training time. Variants such as Group Normalization (GN) (Wu & He, 2018) cover some of the failure modes of BN.

In this paper, we introduce a novel algorithm to improve both the training speed and generalization accuracy of networks by using their over-parameterization to regularize them. In particular, we focus on neural networks that are positive-rescaling equivalent [START_REF] Behnam Neyshabur | Path-sgd: Path-normalized optimization in deep neural networks[END_REF], i.e. whose weights are identical up to positive scalings and matching inverse scalings. The main principle of our method, referred to as Equi-normalization (ENorm), is illustrated in Figure 1 for the fullyconnected case. We scale two consecutive matrices with rescaling coefficients that minimize the joint p norm of those two matrices. This amounts to re-parameterizing the network under the constraint of implementing the same function. We conjecture that this particular choice of rescaling coefficients ensures a smooth propagation of the gradients during training.

A limitation is that our current proposal, in its current form, can only handle learned skipconnections like those proposed in type-C ResNet. For this reason, we focus on architectures, in particular ResNet18, for which the learning converges with learned skip-connection, as opposed to architectures like ResNet-50 for which identity skip-connections are required for convergence.

In summary,

• We introduce an iterative, batch-independent algorithm that re-parametrizes the network within the space of rescaling equivalent networks, thus preserving the function implemented by the network; • We prove that the proposed Equi-normalization algorithm converges to a unique canonical parameterization of the network that minimizes the global p norm of the weights, or equivalently, when p = 2, the weight decay regularizer; • We extend ENorm to modern convolutional architectures, including the widely used ResNets, and show that the theoretical computational overhead is lower compared to BN (×50) and even compared to GN (×3); • We show that applying one ENorm step after each SGD step outperforms both BN and GN on the CIFAR-10 (fully connected) and ImageNet (ResNet-18) datasets. • Our code is available at https://github.com/facebookresearch/enorm.

The paper is organized as follows. Section 2 reviews related work. Section 3 defines our Equinormalization algorithm for fully-connected networks and proves the convergence. Section 4 shows how to adapt ENorm to convolutional neural networks (CNNs). Section 5 details how to employ ENorm for training neural networks and Section 6 presents our experimental results.

RELATED WORK

This section reviews methods improving neural network training and compares them with ENorm. Since there is a large body of literature in this research area, we focus on the works closest to the proposed approach. From early works, researchers have noticed the importance of normalizing the input of a learning system, and by extension the input of any layer in a DNN [START_REF] Lecun | Efficient backprop[END_REF]. Such normalization is applied either to the weights or to the activations. On the other hand, several strategies aim at better controlling the geometry of the weight space with respect to the loss function. Note that these research directions are not orthogonal. For example, explicitly normalizing the activations using BN has smoothing effects on the optimization landscape [START_REF] Santurkar | How does batch normalization help optimization?[END_REF].

Normalizing activations. Batch Normalization [START_REF] Ioffe | Batch normalization: Accelerating deep network training by reducing internal covariate shift[END_REF] normalizes the activations by using statistics computed along the batch dimension. As stated in the introduction, the dependency on the batch size leads BN to underperform when small batches are used. Batch Renormalization (BR) [START_REF] Ioffe | Batch renormalization: Towards reducing minibatch dependence in batch-normalized models[END_REF]) is a follow-up that reduces the sensitivity to the batch size, yet does not completely alleviate the negative effect of small batches. Several batch-independent methods operate on other dimensions, such as Layer Normalization (channel dimension) [START_REF] Lei | Layer normalization[END_REF] and Instance-Normalization (sample dimension) (Ulyanov et al., 2016). Parametric data-independent estimation of the mean and variance in every layer is investigated by [START_REF] Arpit | Normalization propagation: A parametric technique for removing internal covariate shift in deep networks[END_REF]. However, these methods are inferior to BN in standard classification tasks. More recently, Group Normalization (GN) (Wu & He, 2018), which divides the channels into groups and normalizes independently each group, was shown to effectively replace BN for small batch sizes on computer vision tasks.

Normalizing weights. Early weight normalization techniques only served to initialize the weights before training [START_REF] Glorot | Understanding the difficulty of training deep feedforward neural networks[END_REF]He et al., 2015a). These methods aim at keeping the variance of the output activations close to one along the whole network, but the assumptions made to derive these initialization schemes may not hold as training evolves. More recently, [START_REF] Salimans | Weight normalization: A simple reparameterization to accelerate training of deep neural networks[END_REF] propose a polar-like re-parametrization of the weights to disentangle the direction from the norm of the weight vectors. Note that Weight Norm (WN) does require mean-only BN to get competitive results, as well as a greedy layer-wise initialization as mentioned in the paper.

Optimization landscape. Generally, in the parameter space, the loss function moves quickly along some directions and slowly along others. To account for this anisotropic relation between the parameters of the model and the loss function, natural gradient methods have been introduced [START_REF] Amari | Natural gradient works efficiently in learning[END_REF]. They require storing and inverting the N × N curvature matrix, where N is the number of network parameters. Several works approximate the inverse of the curvature matrix to circumvent this problem (Pascanu & Bengio, 2013;[START_REF] Marceau-Caron | Practical riemannian neural networks[END_REF][START_REF] Martens | Optimizing neural networks with kronecker-factored approximate curvature[END_REF]. Another method called Diagonal Rescaling [START_REF] Lafond | Diagonal rescaling for neural networks[END_REF] proposes to tune a particular reparametrization of the weights with a block-diagonal approximation of the inverse curvature matrix. Finally, Neyshabur et al. (2015) propose a rescaling invariant path-wise regularizer and use it to derive Path-SGD, an approximate steepest descent with respect to the path-wise regularizer.

Positioning. Unlike BN, Equi-normalization focuses on the weights and is independent of the concept of batch. Like Path-SGD, our goal is to obtain a balanced network ensuring a good backpropagation of the gradients, but our method explicitly re-balances the network using an iterative algorithm instead of using an implicit regularizer. Moreover, ENorm can be readily adapted to the convolutional case whereas [START_REF] Behnam Neyshabur | Path-sgd: Path-normalized optimization in deep neural networks[END_REF] restrict themselves to the fully-connected case. In addition, the theoretical computational complexity of our method is much lower than the overhead introduced by BN or GN (see Section 5). Besides, WN parametrizes the weights in a polar-like manner, w = g × v/|v|, where g is a scalar and v are the weights, thus it does not balance the network but individually scales each layer. Finally, Sinkhorn's algorithm aims at making a single matrix doubly stochastic, while we balance a product of matrices to minimize their global norm.

EQUI-NORMALIZATION

We first define Equi-normalization in the context of simple feed forward networks that consist of two operators: linear layers and ReLUs. The algorithm is inspired by Sinkhorn-Knopp and is designed to balance the energy of a network, i.e., the p -norm of its weights, while preserving its function. When not ambiguous, we may denote by network a weight parametrization of a given network architecture.

NOTATION AND DEFINITIONS

We consider a network with q linear layers, whose input is a row vector x ∈ R n0 . We denote by σ the point-wise ReLU activation. For the sake of exposition, we omit a bias term at this stage. We recursively define a simple fully connected feedforward neural network with L layers by y

0 = x, y k = σ (y k-1 W k ) , k ∈ 1, q -1 , (1)
and y q = y q-1 W q . Each linear layer k is parametrized by a matrix W k ∈ R n k-1 ×n k . We denote by f θ (x) = y q the function implemented by the network, where θ is the concatenation of all the network parameters. We denote by D(n) the set of diagonal matrices of size n × n for which all diagonal elements are strictly positive and by I n the identity matrix of size n × n.

Definition 1. θ and θ are functionally equivalent if, for all

x ∈ R n0 , f θ (x) = f θ (x).
Definition 2. θ and θ are rescaling equivalent if, for all k ∈ 1, q -1 , there exists a rescaling matrix

D k ∈ D(n k ) such that, for all k ∈ 1, q -1 , W k = D -1 k-1 W k D k
(2) with the conventions that D 0 = I n0 and D q = I nq . This amounts to positively scaling all the incoming weights and inversely scaling all the outgoing weights for every hidden neuron.

Two weights vectors θ and θ that are rescaling equivalent are also functionally equivalent (see Section 3.5 for a detailed derivation). Note that a functional equivalence class is not entirely described by rescaling operations. For example, permutations of neurons inside a layer also preserve functional equivalence, but do not change the gradient. In what follows our objective is to seek a canonical parameter vector that is rescaling equivalent to a given parameter vector. The same objective under a functional equivalence constraint is beyond the scope of this paper, as there exist degenerate cases where functional equivalence does not imply rescaling equivalence, even up to permutations.

OBJECTIVE FUNCTION: CANONICAL REPRESENTATION

Given a network f θ and p > 0, we define the p norm of its weights as p (θ) = q k=1 W k p p . We are interested in minimizing p inside an equivalence class of neural networks in order to exhibit a unique canonical element per equivalence class. We denote the rescaling coefficients within the network as

d k ∈ (0, +∞) n k for k ∈ 1, q -1 or as diagonal matrices D k = Diag(d k ) ∈ D(n k ).
We denote δ = (d 1 , . . . , d q-1 ) ∈ R n , where n is the number of hidden neurons. Fixing the weights {W k }, we refer to {D -1 k-1 W k D k } as the rescaled weights, and seek to minimize their p norm as a function of the rescaling coefficients:

ϕ(δ) = q k=1 D -1 k-1 W k D k p p .
(3)

COORDINATE DESCENT: ENORM ALGORITHM

We formalize the ENorm algorithm using the framework of block coordinate descent. We denote by

W [:, j] (resp. W k [i, :]) the j th column (resp. i th row) of a matrix W k .
In what follows we assume that each hidden neuron is connected to at least one input and one output neuron. ENorm generates a sequence of rescaling coefficients δ (r) obtained by the following steps.

(1) Initialization. Define δ (0) = (1, . . . , 1).

(2) Iteration. At iteration r, consider layer ∈ 1, q -1 such that -1 ≡ r mod q -1 and define

     d (r+1) k = d (r) if k = d (r+1) = argmin t∈(0,+∞) n ϕ d (r) 1 , . . . , d (r) -1 , t, d (r) +1 , . . . , d (r)
q-1 .

Denoting uv the coordinate-wise product of two vectors and u/v for the division, we have

d (r+1) [i] = W +1 [i, :]d (r) +1 p W [:, i]/d (r) -1 p . ( 4
)
Algorithm 1: Pseudo-code of Equi-normalization Input: Current layer weights W 1 , . . . , W q , number of cycles C, choice of norm p Output: Balanced layer weights // Perform T ENorm cycles for t = 1 . . . T do // Iterate through the layers

for k = 2 . . . q do L[j] ←-W k-1 [:, j] p for all j ∈ R n k R[i] ←-W k [i, :] p for all i ∈ R n k D k-1 ←-Diag R/L W k-1 ←-W k-1 D k-1 W k ←-(D k-1 ) -1 W k
Algorithm and pseudo-code. Algorithm 1 gives the pseudo-code of ENorm. By convention, one ENorm cycle balances the entire network once from = 1 to = q -1. See Appendix A for illustrations showing the effect of ENorm on network weights.

CONVERGENCE

We now state our main convergence result for Equi-normalization. The proof relies on a coordinate descent Theorem by Tseng ( 2001) and can be found in Appendix B.1. The main difficulty is to prove the uniqueness of the minimum of ϕ. Theorem 1. Let p > 0 and (δ (r) ) r∈N be the sequence of rescaling coefficients generated by ENorm from the starting point δ (0) as described in Section 3.3. We assume that each hidden neuron is connected to at least one input and one output neuron. Then,

(1) Convergence. The sequence of rescaling coefficients δ (r) converges to δ * as r → +∞. As a consequence, the sequence of rescaled weights also converges;

(2) Minimum global p norm. The rescaled weights after convergence minimize the global p norm among all rescaling equivalent weights;

(3) Uniqueness. The minimum is unique, i.e. δ * does not depend on the starting point δ (0) .

HANDLING BIASES -FUNCTIONAL EQUIVALENCE

In the presence of biases, the network is defined as

y k = σ (y k-1 W k + b k ) and y q = y q-1 W q + b k where b k ∈ R n k .
For rescaling-equivalent weights satisfying (2), in order to preserve the inputoutput function, we define matched rescaling equivalent biases b k = b k D k . In Appendix B.2, we show by recurrence that for every layer k,

y k = y k D k , (5)
where y k (resp. y k ) is the intermediary network function associated with the weights W (resp. W ). In particular, y q = y q , i.e. rescaling equivalent networks are functionally equivalent. We also compute the effect of applying ENorm on the gradients in the same Appendix.

ASYMMETRIC SCALING

Equi-normalization is easily adapted to introduce a depth-wise penalty on each layer. We consider the weighted loss p,(c1,...,cq) (θ) = q k=1 c k W k p . This amounts to modifiying the rescaling coefficients as d(r+1

) [i] = d (r+1) [i] (c k+1 /c k ) 1/2p .
(6) In Section 6, we explore two natural ways of defining c k : c k = c p(q-k) (uniform) and c k = 1/(n k-1 n k ) (adaptive). In the uniform setup, we penalize layers exponentially according to their depth: for instance, values of c larger than 1 increase the magnitude of the weights at the end of the network. In the adaptive setup, the loss is weighted by the size of the matrices.

EXTENSION TO CNNS

We now extend ENorm to CNNs, by focusing on the typical ResNet architecture. We briefly detail how we adapt ENorm to convolutional or max-pooling layers, and then how to update an elementary block with a skip-connection. We refer the reader to Appendix C for a more extensive discussion. Sanity checks of our implementation are provided in Appendix E.1.

CONVOLUTIONAL LAYERS

Figure 2 explains how to rescale two consecutive convolutional layers. As detailed in Appendix C, this is done by first properly reshaping the filters to 2D matrices, then performing the previously described rescaling on those matrices, and then reshaping the matrices back to convolutional filters. This matched rescaling does preserve the function implemented by the composition of the two layers, whether they are interleaved with a ReLU or not. It can be applied to any two consecutive convolutional layers with various stride and padding parameters. Note that when the kernel size is 1 in both layers, we recover the fully-connected case of Figure 1.

MAX-POOLING

The MaxPool layer operates per channel by computing the maximum within a fixed-size kernel. We adapt Equation ( 5) to the convolutional case where the rescaling matrix D k is applied to the channel dimension of the activations y k . Then,

max ( y k ) = max (y k D k ) = max (y k ) D k . (7)
Thus, the activations before and after the MaxPool layer have the same scaling and the functional equivalence is preserved when interleaving convolutional layers with MaxPool layers.

SKIP-CONNECTION

We now consider an elementary block of a ResNet-18 architecture as depicted in Figure 3. In order to maintain functional equivalence, we only consider ResNet architectures of type C as defined in (He et al., 2015b), where all shortcuts are learned 1 × 1 convolutions. As detailed in Appendix C, rescaling two consecutive blocks requires (a) to define the structure of the rescaling process, i.e.

where to insert the rescaling coefficients and (b) a formula for computing those rescaling coefficients.

TRAINING PROCEDURE: EQUI-NORMALIZATION & SGD

ENorm & SGD. As detailed in Algorithm 2, we balance the network periodically after updating the gradients. By design, this does not change the function implemented by the network but will yield different gradients in the next SGD iteration. Because this re-parameterization performs a jump in the parameter space, we update the momentum using Equation ( 17) and the same matrices D k as those used for the weights. The number of ENorm cycles after each SGD step is an hyperparameter and by default we perform one ENorm cycle after each SGD step. In Appendix D, we also explore a method to jointly learn the rescaling coefficients and the weights with SGD, and report corresponding results.

Computational advantage over BN and GN. Table 1 provides the number of elements (weights or activations) accessed when normalizing using various techniques. Assuming that the complexity (number of operations) of normalizing is proportional to the number of elements and assuming all techniques are equally parallelizable, we deduce that our method (ENorm) is theoretically 50 times faster than BN and 3 times faster than GN for a ResNet-18. In terms of memory, ENorm requires no extra-learnt parameters, but the number of parameters learnt by BN and GN is negligible (4800 for a ResNet-18 and 26,650 for a ResNet-50). We implemented ENorm using a tensor library; to take full advantage of the theoretical reduction in compute would require an optimized CUDA kernel.

. . . . . .

Layer k C k filters C k 1 ⇥ S k ⇥ S k Layer k + 1 C k+1 filters C k ⇥ S k+1 ⇥ S k+1 ⇥ 2 ⇥ 1 ⇥ 1 n k ⇥ n k ⇥ 1 1 ⇥ 1 2 Figure 2:
Rescaling the weights of two consecutive convolutional layers that preserves the function implemented by the CNN. Layer k scales channel number i of the input activations by γ i and layer k+1 cancels this scaling with the inverse scalar so that the activations after layer k+1 are unchanged.

EXPERIMENTS

We analyze our approach by carrying out experiments on the MNIST and CIFAR-10 datasets and on the more challenging ImageNet dataset. ENorm will refer to Equi-normalization with p = 2.

MNIST AUTO-ENCODER

Training. We follow the setup of [START_REF] Desjardins | Natural neural networks[END_REF]. Input data is normalized by subtracting the mean and dividing by standard deviation. The encoder has the structure FC(784, 1000)-ReLU-FC(1000, 500)-ReLU-FC(500, 250)-ReLU-FC(250, 30) and the decoder has the symmetric structure. We use He's initialization for the weights. We select the learning rate in {0.001, 0.01, 0.1} et al., 2015) and we set the weight decay to zero. For GN, we cross-validate the number of groups among {5, 10, 20, 50}. For WN, we use BN as well as a greedy layer-wise initialization as described in the original paper.

Results. While ENorm alone obtains competitive results compared to BN and GN, ENorm + BN outperforms all other methods, including WN + BN. Note that here ENorm refers to Enorm using the adaptive c parameter as described in Subsection 3.6, whereas for ENorm + BN we use the uniform setup with c = 1. We perform a parameter study for different values and setups of the asymmetric scaling (uniform and adaptive) in Appendix E.2. Without BN, the adaptive setup outperforms all other setups, which may be due to the strong bottleneck structure of the network. With BN, the dynamic is different and the results are much less sensitive to the values of c. Results without any normalization and with Path-SGD are not displayed because of their poor performance.

CIFAR-10 FULLY CONNECTED

Training. We first experiment with a basic fully-connected architecture that takes as input the flattened image of size 3072. Input data is normalized by subtracting mean and dividing by standard deviation independently for each channel. The first linear layer is of size 3072 × 500. We then consider p layers 500 × 500, p being an architecture parameter for the sake of the analysis. The last classification is of size 500 × 10. The weights are initialized with He's scheme. We train for 60 epochs using SGD with no momentum, a batch size of 256 and weight decay of 10 -3 . Cross validation is used to pick an initial learning rate in {0.0005, 0.001, 0.005, 0.01, 0.05, 0.1}. Path-SGD, GN and WN are learned as detailed in Section 6.1. All results are the average test accuracies over 5 training runs.

Results. ENorm alone outperforms both BN and GN for any depth of the network. ENorm + BN outperforms all other methods, including WN + BN, by a good margin for more than p = 11 intermediate layers. Note that here ENorm as well as ENorm + BN refers to ENorm in the uniform setup with c = 1.2. The results of the parameter study for different values and setups of the asymmetric scaling are similar to those of the MNIST setup, see Appendix E.2.

CIFAR-10 FULLY CONVOLUTIONAL

Training. We use the CIFAR-NV architecture as described by [START_REF] Gitman | Comparison of batch normalization and weight normalization algorithms for the large-scale image classification[END_REF]. Images are normalized by subtracting mean and dividing by standard deviation independently for each channel. During training, we use 28 × 28 random crops and randomly flip the image horizontally.

At test time, we use 28 × 28 center crops. We split the train set into one training set (40,000 images) and one validation set (10,000 images). We train for 128 epochs using SGD and an initial learning rate cross-validated on a held-out set among {0.01, 0.05, 0.1}, along with a weight decay of 0.001. The learning rate is then decayed linearly to 10 -4 . We use a momentum of 0.9. The weights are initialized with He's scheme. In order to stabilize the training, we employ a BatchNorm layer at the end of the network after the FC layer for the Baseline and ENorm cases. For GN we cross-validate the number of groups among {4, 8, 16, 32, 64}. All results are the average test accuracies over 5 training runs. Training. Our experimental setup closely follows that of GN (Wu & He, 2018). We train on 8 GPUs and compute the batch mean and standard deviation per GPU when evaluating BN. We use the Kaiming initialization for the weights (He et al., 2015a) and the standard data augmentation scheme of [START_REF] Szegedy | Going deeper with convolutions[END_REF]. We train our models for 90 epochs using SGD with a momentum of 0.9. We adopt the linear scaling rule for the learning rate [START_REF] Goyal | Accurate, large minibatch SGD: training imagenet in 1 hour[END_REF] and set the initial learning rate to 0.1B/256 where the batch size B is set to 32, 64, 128, or 256. As smaller batches lead to more iterations per epoch, we adopt a similar rule and adopt a weight decay of w = 10 -4 for B = 128 and 256, w = 10 -4.5 for B = 64 and w = 10 -5 for B = 32. We decay the learning rate quadratically [START_REF] Gitman | Comparison of batch normalization and weight normalization algorithms for the large-scale image classification[END_REF] to 10 -5 and report the median error rate on the final 5 epochs. When using GN, we set the number of groups G to 32 and did not cross-validate this value as prior work (Wu & He, 2018) reports little impact when varying G from 2 to 64. In order for the training to be stable and faster, we added a BatchNorm at the end of the network after the FC layer for the Baseline and ENorm cases. The batch mean and variance for this additional BN are shared across GPUs. Note that the activation size at this stage of the network is B × 1000, which is a negligible overhead (see Table 1).

Results. We compare the Top 1 accuracy on a ResNet-18 when using no normalization scheme, (Baseline), when using BN, GN and ENorm (our method). In both the Baseline and ENorm settings, we add a BN at the end of the network as described in 6.3. The results are reported in

LIMITATIONS

We applied ENorm to a deeper (ResNet-50), but obtained unsatisfactory results. We observed that learnt skip-connections, even initialized to identity, make it harder to train without BN, even with careful layer-wise initialization or learning rate warmup. This would require further investigation.

CONCLUDING REMARKS

We presented Equi-normalization, an iterative method that balances the energy of the weights of a network while preserving the function it implements. ENorm provably converges towards a unique equivalent network that minimizes the p norm of its weights and it can be applied to modern CNN architectures. Using ENorm during training adds a much smaller computational overhead than BN or GN and leads to competitive performances in the FC case as well as in the convolutional case.

Discussion. While optimizing an unbalanced network is hard [START_REF] Behnam Neyshabur | Path-sgd: Path-normalized optimization in deep neural networks[END_REF], the criterion we optimize to derive ENorm is likely not optimal regarding convergence or training properties. These limitations suggest that further research is required in this direction. 0) be the starting point of the coordinate descent algorithm and X the level set X = x | f (x) ≤ f x (0) . We make the following assumptions:

(1) f is differentiable on D ;

(2) X is compact ;

(3) for each x ∈ D, each block coordinate function f : t → f (x 1 , . . . , x -1 , t, x +1 , . . . , x B ),

where 2 ≤ ≤ B -1, has at most one minimum.

Under these assumptions, the sequence (x (r) ) r∈N generated by the coordinate descent algorithm is defined and bounded. Moreover, every cluster point of (x (r) ) r∈N is a local minimizer of f . STEP 1. We apply Theorem 2 to the function ϕ. This is possible because all the assumptions are verified as shown below. Recall that

ϕ(δ) = q k=1 D -1 k-1 W k D k p p = q k=1 i,j d k [j] d k-1 [i] W k [i, j] p . (8)
Assumption (1). ϕ is differentiable on the open set D = (0, +∞) n .

Assumption (2). ϕ → +∞ when δ → +∞. Let δ such that ϕ(δ) < M p , M > 1. Let us show by induction that for all k ∈ 1, q -1 , d k ∞ < (CM ) k , where C = max(C 0 , 1) and

C 0 = max W k [i,j] =0 1 |W k [i, j]| (9)
• For the first hidden layer, index k = 1. By assumption, every hidden neuron is connected at least to one neuron in the input layer. Thus, for every j, there exists i such that W 1 [i, j] = 0.

Because ϕ(δ) < M p and d 0 [i] = 1 for all i,

(d 1 [j]) p |W 1 [i, j]| p = d 1 [j] d 0 [i] p |W 1 [i, j]| p < M p (10)
Thus d 1 ∞ < CM .

• For some hidden layer, index k. By assumption, every hidden neuron is connected at least to one neuron in the previous layer. Thus, for every j, there exists i such that

W k [i, j] = 0. Because ϕ(δ) < M , d k [j] d k-1 [i] p |W k [i, j]| p < M p (11)
Using the induction hypothesis, we get

d k ∞ < (CM ) k . Thus, δ ∞ < (M C) q because M C > 1. By contraposition, ϕ → +∞.
Thus, there exists a ball B such that δ / ∈ B implies ϕ(δ) > ϕ(δ 0 ). Thus, δ ∈ X implies that x ∈ B and X ⊂ B is bounded. Moreover, X is closed because ϕ is continuous thus X is compact and Assumption (2) is satisfied.

Assumption (3). We next note that

ϕ l (t) = ϕ d (r) 1 , . . . , d (r) -1 , t, d (r) +1 , . . . , d (r) q-1 (12)
has a unique minimum as shown in Section 3.3, see Equation ( 4). The existence and uniqueness of the minimum comes from the fact that each hidden neuron is connected to at least one input and one output neuron, thus all the row and column norms of the hidden weight matrices W k are non-zero, as well as the column (resp. row) norms or W 1 (resp. W q ). STEP 2. We prove that ϕ has at most one stationary point on D under the assumption that each hidden neuron is connected either to an input neuron or to an output neuron, which is weaker than the general assumption of Theorem 1.

We first introduce some definitions. We denote the set of all neurons in the network by V . Each neuron ν ∈ V belongs to a layer k ∈ 0, q and has an index i ∈ 1, n k in this layer. Any edge e connects some neuron i at layer k -1 to some neuron j at layer k, e = (k, i, j). We further denote by H the set of hidden neurons ν belonging to layers q ∈ 1, q -1 . We define E as the set of edges whose weights are non-zero, i.e.

E = {(k, i, j) | W (k) i,j = 0}. (13)
For each neuron ν, we define prev(ν) as the neurons connected to ν that belong to the previous layer.

We now show that ϕ has at most one stationary point on D. Directly computing the gradient of ϕ and solving for zeros happens to be painful or even intractable. Thus, we define a change of variables as follows. We define h as h : (0, +∞)

H → R H δ → log(δ)
We next define the shift operator S : R V → R E such that, for every

x ∈ R V , S(x) = (ν -ν ) ν,ν ∈V s.t. ν ∈prev(ν)
and the padding operator P as

P : R H → R V x → y where y ν = 0 if ν ∈ V \H; y ν = x ν otherwise.
We define the extended shift operator S H = S • P . We are now ready to define our change of variables. We define χ = ψ STEP 3. We prove that the sequence δ (r) converges.

Step 1 implies that the sequence δ (r) is bounded and has at least one cluster point, as f is continuous on the compact X.

Step 2 implies that the sequence δ (r) has at most one cluster point. We then use the fact that any bounded sequence with exactly one cluster point converges to conclude the proof.

S IS INJECTIVE. Let x ∈ ker S H . Let us show by induction on the hidden layer index k that for every neuron ν at layer k, x ν = 0.

• k = 1. Let ν be a neuron at layer 1. Then, there exists a path coming from an input neuron to ν 0 through edge e 1 . By definition, P (x) ν0 = 0 and P (x) ν = x ν , hence S H (x) e1 = x ν -0. Since S H (x) = 0 it follows that x ν = 0. • k → k + 1. Same reasoning using the fact that x ν k = 0 by the induction hypothesis.

The case where the path goes from neuron ν to some output neuron is similar.

B.2 FUNCTIONAL EQUIVALENCE

We show (5) by induction that for every layer k, i.e.,

y k = y k D k ,
where y k (resp. y k ) is the intermediary network function associated with weights W (resp. W ). This holds for k = 0 since D 0 = I n0 by convention. If the property holds for some k < q -1, then by (2) we have

y k W k+1 = y k D k W k+1 = y k W k+1 D k+1 hence, since b k+1 = b k+1 D k+1 , y k+1 = σ y k W k+1 + b k+1 = σ (y k W k+1 D k+1 + b k+1 D k+1 ) = σ (y k W k+1 + b k+1 ) D k+1 = y k+1 D k+1 .
The same equations hold for k = q -1 without the non-linearity σ.

Using the chain rule and denoting by the loss of the network, for every layer k, using (5), we have

∂ ∂ y k = ∂ ∂y k (D k ) -1 . (16)
Similarly, we obtain

∂ ∂ W k = D k-1 ∂ ∂W k (D k ) -1 and ∂ ∂ b k = ∂ ∂b k (D k ) -1 . (17)
Equation ( 17) will be used to update the momentum (see Section 5) and Equation ( 2) for the weights.

M k of size (C k-1 × S k × S k ) × C k ; (18) M k+1 of size C k × (C k+1 × S k+1 × S k+1 ) . (19)
For example, we first reshape T k as a 2D matrix by collapsing its last 3 dimensions, then transpose it to obtain M k . We then jointly rescale those 2D matrices using rescaling matrices D k ∈ D(k) as detailed in Section 3 and perform the inverse axis permutation and reshaping operations to obtain a right-rescaled weight tensor T k and a left-rescaled weight tensor T k+1 . See Figure 2 for an illustration of the procedure. This matched rescaling does preserve the function implemented by the composition of the two layers, whether they are interleaved with a ReLU or not. It can be applied to any two consecutive convolutional layers with various stride and padding parameters. Note that when the kernel size is 1 in both layers, we recover the fully-connected case of Figure 1.

C.2 SKIP-CONNECTION

We now consider an elementary block of a ResNet-18 architecture as depicted in Figure 3. In order to maintain functional equivalence, we only consider ResNet architectures of type C as defined in (He et al., 2015b), where all shortcuts are learned 1 × 1 convolutions.

Structure of the rescaling process. Let us consider a ResNet block k. We first left-rescale the Conv1 and ConvSkip weights using the rescaling coefficients calculated between blocks k -1 and k.

We then rescale the two consecutive layers Conv1 and Conv2 with their own specific rescaling coefficients, and finally right-rescale the Conv2 and ConvSkip weights using the rescaling coefficients calculated between blocks k and k + 1. We finally compare the evolution of the total 2 norm of the network when training it, with or without ENorm. We use the setup described in Subsection 6.2 and use p = 3 intermediary layers. The results are presented in Figure 10. ENorm consistently leads to a lower energy level in the network. MNIST auto-encoder. For the uniform setup, we test for three different values of c, without BN: c = 1 (uniform setup), c = 0.8 (uniform setup), c = 1.2 (uniform setup). We also test the adaptive setup. The adaptive setup outperforms all other choices, which may be due to the strong bottleneck structure of the network. With BN, the dynamics are different and the results are much less sensitive to the values of c (see Figures 11 and12). CIFAR10 Fully Convolutional. For the uniform setup, we test for three different values of c, without BN: c = 1 (uniform setup), c = 0.8 (uniform setup), c = 1.2 (uniform setup). We also test the adaptive setup (see Table 5). Once again, the dynamics with or without BN are quite different. With or without BN, c = 1.2 performs the best, which may be linked to the fact that the ReLUs are cutting energy during each forward pass. With BN, the results are less sensitive to the values of c.

Figure 3 :

 3 Figure 3: Rescaling an elementary block within a ResNet-18 consists of 3 steps. (1) Conv1 and Con-vSkip are left-rescaled using the rescaling coefficients between blocks k -1 and k; (2) Conv1 and Conv2 are rescaled as two usual convolutional layers; (3) Conv2 and ConvSkip are right-rescaled using the rescaling coefficients between blocks k and k + 1. Identical colors denote the same rescaling coefficients D. Coefficients between blocks are rescaled as detailed in Section C.2.

Theorem 2 .

 2 Let D ⊂ R n be an open set and f : D → R a real function of B block variables x b ∈ R n b with B b=1 n b = n. Let x (

  APPENDIX C EXTENSION OF ENORM TO CNNS C.1 CONVOLUTIONAL LAYERS Let us consider two consecutive convolutional layers k and k + 1, without bias. Layer k has C k filters of size C k-1 × S k × S k , where C k-1 is the number of input features and S k is the kernel size. This results in a weight tensor T k of size C k × C k-1 × S k × S k . Similarly, layer k + 1 has a weight matrix T k+1 of size C k+1 × C k × S k+1 × S k+1 . We then perform axis-permutation and reshaping operations to obtain the following 2D matrices:

Figure 9 :

 9 Figure 9: Iterating ENorm cycles on a randomly initialized ResNet-18 with no training.

Figure 10 :

 10 Figure 10: Training a fully-connected network on CIFAR-10, with (ENorm-1) or without (Baseline) Equi-normalization.

Figure 11 :

 11 Figure 11: Uniform vs adaptive scaling on MNIST, without BN.

Figure 12 :

 12 Figure 12: Uniform vs adaptive scaling on MNIST, with BN.

Table 4 .

 4 The Figure 6: ResNet-18 results on the ImageNet dataset, batch size 64.performance of BN decreases with small batches, which concurs with prior observations(Wu & He, 2018). Our method outperforms GN and BN for batch sizes ranging from 32 to 128. GN presents stable results across batch sizes. Note that values of c different from 1 did not yield better results.The training curves for a batch size of 64 are presented in Figure6. While BN and GN are faster to converge than ENorm, our method achieves better results after convergence in this case. Note also that ENorm overfits the training set less than BN and GN, but more than the Baseline case.

	Batch size	32	64	128	256
	Baseline	66.20 68.60 69.20 69.58
	BN	68.01 69.38 70.83 71.37
	GN	68.94 68.90 70.69 70.64
	ENorm-1 (ours) 69.70 70.10 71.03 71.14

Table 4 :

 4 ResNet-18 results on the ImageNet dataset (test accuracy).

  Matus Telgarsky. Benefits of depth in neural networks. CoRR, 2016. P. Tseng. Convergence of a block coordinate descent method for nondifferentiable minimization. J.Optim. Theory Appl., 2001.

	Dmitry Ulyanov, Andrea Vedaldi, and Victor S. Lempitsky. Instance normalization: The missing
	ingredient for fast stylization. CoRR, 2016.
	Yuxin Wu and Kaiming He. Group normalization. CoRR, abs/1803.08494, 2018.

  As χ is the composition of a strictly convex function, ψ, and a linear injective function, S H (proof after Step 3), it is strictly convex. Thus χ has at most one stationary point, which concludes this step.

		p
	and observe that
	so that its differential satisfies	ϕ = χ • h	(14)
		[Dϕ](δ) = [Dχ](h(δ))[Dh](δ).	(15)

• S H where ψ : R E → R x → e∈E exp(px e ) |w e | Since h is a C ∞ diffeomorphism, its differential [Dh](δ) is invertible for any δ. It follows that [Dϕ](δ) = 0 if, and only if, [Dχ](h(δ)) = 0.

Table 5 :

 5 Uniform vs adaptive scaling, CIFAR-10 fully convolutional

Note that what Tseng denotes as stationary point in his paper is actually defined as a point where the directional derivative is positive along every possible direction, i.e. a local minimum.

ACKNOWLEDGMENTS

We thank the anonymous reviewers for their detailed feedback, which helped us to significantly improve the paper's clarity and the experimental validation. We also thank Timothée Lacroix, Yann Ollivier and Léon Bottou for useful feedback on various aspects of this paper.

APPENDIX A ILLUSTRATION OF THE EFFECT OF EQUI-NORMALIZATION

We first apply ENorm to one randomly initialized fully connected network comprising 20 intermediary layers. All the layers have a size 500 × 500 and are initialized following the Xavier scheme. The network has been artificially unbalanced as follows: all the weights of layer 6 are multiplied by a factor 1.2 and all the weights of layer 12 are multiplied by 0.8, see Figure 7. We then iterate our ENorm algorithm on the network, without training it, to see that it naturally re-balances the network, see Figure 8. Computation of the rescaling coefficients. Two types of rescaling coefficients are involved, namely those between two convolution layers inside the same block and those between two blocks. The rescaling coefficients between the Conv1 and Conv2 layers are calculated as explained in Section 4.1. Then, in order to calculate the rescaling coefficients between two blocks, we compute equivalent block weights to deduce rescaling coefficients.

We empirically explored some methods to compute the equivalent weight of a block using electrical network analogies. The most accurate method we found is to compute the equivalent weight of the Conv1 and Conv2 layers, i.e., to express the succession of two convolution layers as only one convolution layer denoted as ConvEquiv (series equivalent weight), and in turn to express the two remaining parallel layers ConvEquiv and ConvSkip again as a single convolution layer (parallel equivalent weight). It is not possible to obtain series of equivalent weights, in particular when the convolution layers are interleaved with ReLUs. Therefore, we approximate the equivalent weight as the parallel equivalent weight of the Conv1 and ConvSkip layers.

APPENDIX D IMPLICIT EQUI-NORMALIZATION

In Section 3, we defined an iterative algorithm that minimizes the global p norm of the network

As detailed in Algorithm 2, we perform alternative SGD and ENorm steps during training. We now derive an implicit formulation of this algorithm that we call Implicit Equi-normalization. Let us fix p = 2. We denote by C(f θ (x), y) the cross-entropy loss for the training sample (x, y) and by 2 (θ, δ) the weight decay regularizer (20). The loss function of the network writes

where λ is a regularization parameter. We now consider both the weights and the rescaling coefficients as learnable parameters and we rely on automatic differentiation packages to compute the derivatives of L with respect to the weights and to the rescaling coefficients. We then simply train the network by performing iterative SGD steps and updating all the learnt parameters. Note that by design, the derivative of C with respect to any rescaling coefficient is zero. Although the additional overhead of implicit ENorm is theoretically negligible, we observed an increase of the training time of a ResNet-18 by roughly 30% using PyTorch 4.0 [START_REF] Paszke | Automatic differentiation in pytorch[END_REF]. We refer to Implicit Equi-normalization as ENorm-Impl and to Explicit Equi-normalization as ENorm.

We performed early experiments for the CIFAR10 fully-connected case. ENorm-Impl performs generally better than the baseline but does not outperform explicit ENorm, in particular when the network is deep. We follow the same experimental setup than previously, except that we additionally cross-validated λ. We also initialize all the rescaling coefficients to one.. Recall that ENorm or ENorm denotes explicit Equi-normalization while ENorm-Impl denotes Implicit Equinormalization. We did not investigate learning the weights and the rescaling coefficients at different speeds (e.g. with different learning rates or momentum). This may explain in part why ENorm-Impl generally underperforms ENorm in those early experiments.

APPENDIX E EXPERIMENTS

We perform sanity checks to verify our implementation and give additional results.

E.1 SANITY CHECKS

We apply our Equi-normalization algorithm to a ResNet architecture by integrating all the methods exposed in Section 4. We perform three sanity checks before proceeding to experiments. First, we randomly initialize a ResNet-18 and verify that it outputs the same probabilities before and after balancing. Second, we randomly initialize a ResNet-18 and perform successive ENorm cycles (without any training) and observe that the 2 norm of the weights in the network is decreasing and then converging, as theoretically proven in Section 3, see Figure 9.


Mohammad Safe

Pedro Neto
email: pedro.neto@dem.uc.pt

Member, IEEE Richard Bearee

Efficient Calculation of Minimum Distance Between Capsules and Its Use in Robotics

Keywords: Minimum distance, line-segments, capsules, robotics

The problem of minimum distance calculation between line-segments/capsules, in 3D space, is an important subject in many engineering applications, spanning CAD design, computer graphics, simulation, and robotics. In the latter, the human-robot minimum distance is the main input for collision avoidance/detection algorithms to measure collision imminence. Capsules can be used to represent humans and objects, including robots, in a given dynamic environment. In this scenario, it is important to calculate the minimum distance between capsules efficiently, especially for scenes (situations) that include a high number of capsules. This paper investigates the utilization of QR factorization for performing efficient minimum distance calculation between capsules. The problem is reformulated as a bounded variable optimization in which an affine transformation, deduced from QR factorization, is applied on the region of feasible solutions. A geometrical approach is proposed to calculate the solution, which is achieved by computing the point closest to the origin from the transferred region of feasible solutions. This paper is concluded with numerical tests, showing that the proposed method compares favorably with the most efficient method reported in the literature.

I. INTRODUCTION

The subject of minimum distance calculation between linesegments/capsules is important in many areas, for example in CAD design, computer graphics/games and in simulation. In such cases, minimum distance calculations are used to detect any overlap or collision between elements. This subject is also important in robotics for the problem of path planning and safety in human-robot interaction, where the minimum distance is used as a measure of collision imminence. In this scenario, calculating the minimum distance on-line is required for time critical applications such as human-robot collision avoidance and the path planning of robots navigating obstacles towards a goal. Most of collision avoidance methods require the calculation of the minimum distance between robot and surrounding environment (including humans), which are commonly represented by geometric primitives (capsules and/or spheres). By using higher number of geometric primitives the accuracy of representation increases. In such a case, the acquisition of more data from sensors is required, resulting in higher computational cost associated with sensor data processing and minimum distance calculation between the robot and the surrounding humans/objects. Outside computer graphics science the number of studies approaching human and object representation in real environment from real sensor data is very limited. In this context, quite a few methods had been proposed in literature. Ellipses have been utilized to represent the links of a robot while obstacles are represented by spheres [START_REF] Choi | Obstacle avoidance control for redundant manipulators using collidability measure[END_REF]. A computationally efficient solution is based on the representation of the robot and obstacles by segments of lines with spheres swept onto them [START_REF] Bosscher | Real-time collision avoidance algorithm for robotic manipulators[END_REF]. In [START_REF] Santis | The skeleton algorithm for self-collision avoidance of a humanoid manipulator[END_REF] and [START_REF] Fang | Efficient self-collision avoidance based on focus of interest for humanoid robots[END_REF] a humanoid robot is represented by capsules, while in [START_REF] Balan | Real-time 3D collision avoidance method for safe human and robot coexistence[END_REF] robot and human are represented by a collection of spheres. In [START_REF] Liu | Algorithmic safety measures for intelligent industrial co-robots[END_REF], an industrial manipulator and a human are represented by capsules. A novel method for evaluating the distances between dynamic obstacles using multiple depth cameras is presented in [START_REF] Fabrizio | Real-time computation of distance to dynamic obstacles with multiple depth sensors[END_REF].

A depth space oriented discretization of the Cartesian space is introduced, including occluded points. Robot and surrounding environment can be precisely described using mesh representation [START_REF] Kaldestad | Collision avoidance with potential fields based on parallel processing of 3D-point cloud data on the GPU[END_REF]. This method has the disadvantage of being costly for performing robot-obstacle minimum distance calculations. To speed up the computation, researchers have utilized the power of parallel processing, and GPU processors, to carry out the calculations [START_REF] Kaldestad | Collision avoidance with potential fields based on parallel processing of 3D-point cloud data on the GPU[END_REF]. A collision avoidance framework for mechanisms with complex geometries was demonstrated in simulation environment [START_REF] Sagardia | Realtime collision avoidance for mechanisms with complex geometries[END_REF]. Diverse geometries/shapes have been reported in literature for accurate representation of humans and objects, namely in computer graphics science [START_REF] Hu | Functionality representations and applications for shape analysis[END_REF]. However, concerning the application in real environment using real sensors, capsules and spheres continue to be the most common geometry applied. Previous studies in human-robot collision avoidance showed that the error derived from the representation of humans using capsules is relatively small compared to the human-robot minimum distance dimension, so that it can be considered not problematic for the collision avoidance process [START_REF] Safeea | Human-robot collision avoidance for industrial robots: A V-REP based solution[END_REF].

In this study, the human and the robot are represented by capsules. Capsules are considered a good geometric primitive to represent a human, as in Figure 1 (A), in which L'Uomo Vitruviano from Leonardo da Vinci is represented by 10 capsules. The human body can be represented roughly by a single capsule, Figure 1 (B). In this scenario the arms can extend out of the capsule volume for some configurations. A robot can roughly be represented by 2 capsules, Figure 1 (E), or by 3 capsules representing the main robot links (KUKA iiwa with 7 DOF), Figure 1 (F). The pose of the capsules covering the robot is obtained from forward kinematics calculation using the measured robot joint angles.

In [START_REF] Ennen | Efficient collision avoidance for industrial manipulators with overlapping workspaces[END_REF], it is proposed an algebraic method for minimum distance computation between two capsules. Another method for computing the minimum distance between cylinders with flat ends was proposed in [START_REF] Biermann | Fast distance computation between cylinders for the design of mold temperature control systems[END_REF]. Nevertheless, the aforementioned methods are lengthy because they consider the different configurations in which two capsules might collide with each other. A method to determine the minimum distance between multiple known (geometry, position, orientation and configuration) and multiple unknown objects within a camera image is presented in [START_REF] Kuhn | Fast vision-based minimum distance determination between known and unkown objects[END_REF]. The distance is estimated by searching for the largest expansion radius where the projected model does not intersect the object areas classified as unknown. A novel approach to approximate the minimum distance between robot links and obstacles is proposed in [START_REF] Tarbouriech | On bisection continuous collision checking method: Spherical joints and minimum distance to obstacles[END_REF]. Obstacles are represented by a bounding box, modeled as cylinders and boxes. Each part of the robot arm is subdivided into an optimal number of spheres that encompass the initial volume. The minimum distance between the robot and the objects is approximated by the minimum distance between the obstacle bounding box and the spheres. An algorithm for computing the minimum translational distance based on the Gilbert-Johnson-Keerthi algorithm between two spherically extended polytopes is introduced in [START_REF] Bernabeu | Hough transform for distance computation and collision avoidance[END_REF]. A wellknown methodology for efficiently computing the segment to segment (capsules) distance which is considered the most efficient method in literature concerning computational efficiency is detailed in [17, pp. 417-418].

In this study, Section II presents the proposed QR-based capsule-capsule minimum distance method. Experiments and results are reported in Section III, both qualitative and quantitative. Finally, the conclusion is in Section IV. The Media materials contain the detailed deduction of the proposed QR method and running code.

II. MINIMUM DISTANCE: CAPSULE-CAPSULE A. FORMULATION

Owing to their geometry, calculating the minimum distance between two capsules can be reduced to the calculation of the minimum distance between two line-segments at the capsules axes. In Figure 2 it is shown two line-segments representing the axes of two capsules and their associated common normal. Each capsule can be defined by two vectors (at the beginning and end of the capsule's axis-segment) and a radius ρ. Let's designate the position vectors defining the end points of the axis-segment of a capsule by p 1 and u 1 (capsule 1), and p 2 and u 2 (capsule 2). Then, we can define two vectors s 1 = u 1 -p 1 and s 2 = u 2 -p 2 .

Two points of interest, one in each axis segment of a capsule, are considered. Those points are represented relative to the base frame by two vectors, r 1 and r 2 :

r 1 = p 1 + s 1 λ 1 (1) r 2 = p 2 + s 2 λ 2 (2)
where λ 1 and λ 2 are scalar parameters. Each parameter has a value in the range from zero to one when the point it represents is confined in between the two ends of the axissegment of the capsule. The problem of calculating the minimum distance between the two capsules renders to a minimization problem:

min( ) = min(|p 2 + s 2 λ 2 -(p 1 + s 1 λ 1 )| -ρ 1 -ρ 2 ) (3)
where ρ 1 and ρ 2 are the radii of the capsules. Giving that ρ 1 and ρ 2 are constants, then the minimization problem can be reformulated:

min(| r|) = min(|p 2 + s 2 λ 2 -(p 1 + s 1 λ 1 )|) (4)
where r = r 2 -r 1 . We can rewrite the optimization function in the following equivalent quadratic form: where matrix A = s 2 -s 1 and vector y = p 2 -p 1 .

min(f ) = min((Ax + y) T (Ax + y)) (5)
The problem can be viewed as minimizing [START_REF] Balan | Real-time 3D collision avoidance method for safe human and robot coexistence[END_REF], subject to the constrains 0 < x 1 < 1 and 0 < x 2 < 1 (x 1 and x 2 are the components of the vector x). Figure 3 shows the level sets and the region of feasible solutions of the optimization problem (5).

B. QR FACTORIZATION

The function f can be reformulated by performing QR factorization on matrix A and fixing. Then, the optimization problem in ( 5) is equivalent to:

min(f 1 ) = min((Rx + Q T y) T (Rx + Q T y)) ( 6
)
where Q is a 3 × 2 matrix whose column vectors are of unit length and mutually orthogonal, and matrix R is a 2×2 upper triangular. By performing a variable change the optimization problem becomes:

min(f 1 ) = min(u T u) ( 7
)
where u is given by:

u = (Rx + Q T y) (8)
The modified optimization problem ( 7) is shown in Figure 4. We notice that after performing the transformation described in [START_REF] Kaldestad | Collision avoidance with potential fields based on parallel processing of 3D-point cloud data on the GPU[END_REF] the elliptical level sets of the cost function are transformed into circles and the rectangular end if 14 : end for 15 : end if region of feasible solutions is transformed into a parallelogram. The solution to the modified optimization problem ( 7) is reduced to finding that point of the parallelogram region closest to the origin, u min , efficiently calculated in 2D space, Algorithm 1. Finally, the minimum distance between two capsules is calculated from:

d min = u T min u min + y T y -y T QQ T y -ρ 1 -ρ 2 (9)
For a set of n line-segments/capsules it can be noticed that: 1) Minimum distance calculations shall be performed mutually between any two capsules of the set, resulting in O n 2 complexity; 2) QR factorization of matrix A i associated with a subset i of two capsules can be enhanced for efficiency since different A i have shared columns in their structure; 3) The vector u min is calculated in two dimensional space, while other algorithms calculate x min in the three dimensional space; 4) Vector operations in 2 are less costly than operations in 3 ; 5) We propose u min in 2 and take advantage of the fact that the area of feasible solutions is a parallelogram. A document with the full detail of the proposed QR method, including comparison with the method in [START_REF] Schneider | Geometric Tools for Computer Graphics[END_REF] and C++ running code is in Media materials.

III. EXPERIMENTS AND RESULTS

Performance was evaluated by comparing the proposed QR method with the method in [START_REF] Schneider | Geometric Tools for Computer Graphics[END_REF] to compute the segment to segment minimum distance. Three comparison criteria were considered: (1) computational complexity, (2) execution time using C++ and (3) numerical precision. The results for the computational complexity of the algorithms (number of floating point operations -addition, multiplication, division FIGURE 5. Execution time comparison for the proposed QR method, the method in [START_REF] Schneider | Geometric Tools for Computer Graphics[END_REF] and the modified method in [START_REF] Schneider | Geometric Tools for Computer Graphics[END_REF] as a function of of line-segments/capsules of the set. Algorithms implemented in C++.

Execution time ratio (Method [START_REF] Schneider | Geometric Tools for Computer Graphics[END_REF]/QR), (Modified method [START_REF] Schneider | Geometric Tools for Computer Graphics[END_REF]/QR) and (Method [START_REF] Schneider | Geometric Tools for Computer Graphics[END_REF]/Modified method [START_REF] Schneider | Geometric Tools for Computer Graphics[END_REF]) as a function of number of line-segments/capsules of the set. Algorithms implemented in C++.

and square root for QR) are in Table 1. For the second comparison criteria, a set of line-segments was randomly generated and the minimum distance (squared) between each two line-segments of the set was calculated using the proposed QR method and the method in [START_REF] Schneider | Geometric Tools for Computer Graphics[END_REF]. By implementing the algorithms in C++, results indicate that in terms of execution time the proposed QR method performed about 10% faster than the method in [START_REF] Schneider | Geometric Tools for Computer Graphics[END_REF], Figure 5 and Figure 6.

We noticed that method [START_REF] Schneider | Geometric Tools for Computer Graphics[END_REF] can be modified by promoting some of the operations from O(n 2 ) to O(n). The results of those operations can be stored in memory and used later in the O(n 2 ) part of the algorithm. In such a case, the O(n 2 ) computational complexity of method [START_REF] Schneider | Geometric Tools for Computer Graphics[END_REF] is reduced as shown in Table 1. Nevertheless, the proposed QR method is still more efficient in terms of execution time as shown in Figure 5 and Figure 6. The modified method in [START_REF] Schneider | Geometric Tools for Computer Graphics[END_REF] is detailed in the Media materials.

Considering the third comparison criteria, numerical precision, a group of 5000 line-segments/capsules has been generated randomly in 3D space. The (x, y, z) coordinates of the start and end point of each segment are in the TABLE 1. Computational complexity for the method in [START_REF] Schneider | Geometric Tools for Computer Graphics[END_REF], the modified method in [START_REF] Schneider | Geometric Tools for Computer Graphics[END_REF] and the proposed QR method.

FIGURE 7.

Average relative error between the method in [START_REF] Schneider | Geometric Tools for Computer Graphics[END_REF] and the proposed QR method as a function of the number of line-segments/capsules of the set. range [-100, 100]. The proposed QR method and the method in [START_REF] Schneider | Geometric Tools for Computer Graphics[END_REF] are used to calculate the minimum distance between each couple of segments from the set. For each couple of segments, the relative error is defined as the ratio of the absolute value of difference between calculations using the two methods: [START_REF] Hu | Functionality representations and applications for shape analysis[END_REF] where d qr min is the minimum distance calculated using the proposed QR method and d s min is the minimum distance calculated using the method in [START_REF] Schneider | Geometric Tools for Computer Graphics[END_REF]. Experimental tests resulted in a maximum value of the relative error of 1.059e -8 , a minimum value of the relative error of 1.11e -16 and an average error of 4.87e -10 . These values demonstrate that the error is negligible. The same test has been repeated for different groups of line-segments/capsules with different number of elements, Figure 7.

IV. CONCLUSION

In this study we proposed a novel method based on QR factorization for performing minimum distance calculations for a set of line-segments/capsules. Capsules demonstrated to be good solution to represent humans and objects in real environment having data from real sensors as input. Experimental results indicate that the proposed solution is more efficient than the existing most efficient method in literature. Such efficiency was measured in computationally complex-ity (reduced number of floating point operations), execution time (about 10% better) and numerical precision (the error is negligible).

  Figure 1 (C) shows a human represented by 3 capsules. In Figure 1 (D) the human is represented by 5 capsules, 2 capsules in each arm and 1 single capsule for the torso and head. A relatively precise representation of the human hand and forearm by 21 capsules is shown in Figure 1 (G).

FIGURE 1 .

 1 FIGURE 1. (A) L'Uomo Vitruviano from Leonardo da Vinci and its representation by 10 capsules, (B) human represented by 1 capsule, (C) human represented by 3 capsules, (D) human represented by 5 capsules, (E) robot represented by 2 capsules, (F) robot represented by 3 capsules and (G) human hand and forearm are represented by 21 capsules.

FIGURE 2 .

 2 FIGURE 2. Minimum distance between two capsules.

FIGURE 3 .

 3 FIGURE 3. Region of feasible solutions of optimization problem (5).

FIGURE 4 .

 4 FIGURE 4. Modified optimization problem (7).

Algorithm 1 :else 10 :

 110 Minimum distance calculation Input : R region of feasible solutions (Q, R) facorization matrices of A Output : u min vector of coefficients 01 : Transform R using the function f (x) = (Rx + Q T y) 02 : If Origin is inside R then 03 : u min ← [0, 0] T 04 : else 05 : for each boundary segment of R do 06 : c ← point of segment closest to origin 07 : If first iteration then 08 : u min ← c 09 : If norm(u min ) > norm(c) then 11 : u min ← c 12 : end if 13 :

This work was supported in part by the European Union's Horizon 2020 Research and Innovation Programme through the ColRobot project under Grant 688807, in part by the Portugal 2020 project DM4Manufacturing funded by UE/FEDER through the program COMPETE2020 under Grant POCI-01-0145-FEDER-016418, in part by the Portuguese Foundation for Science and Technology under Grant SFRH/BD/131091/2017, and in part by the Project COBOTIS under Grant PTDC/EME-EME/32595/2017.

MOHAMMAD SAFEEA received the M.S. degree in mechanical engineering from the University of Coimbra, Portugal, in 2016. He is currently pursuing the Ph.D. degree in robotics with the University of Coimbra and ENSAM ParisTech, Lille, France.

During his career, he has been involved in several projects, where he developed several software solutions for robotics, control, and interfacing with hardware and sensors. His main research topics are robot dynamics, robot control, and the issues of safety for human-robot collaboration.


Maradj Hicham

Carole Fauquet

Mostefa Ghamnia

Benedicte Ealet

Nabil Rochdi

Sébastien Vizzini

Jean-Paul Biberian

Bernard Aufray

Haik Jamgotchian
email: jamgotchian@cinam.univ-mrs.fr

Sebastien Vizzini

Structure of a Zn monolayer on Ag(111) and Ag(110) substrates: an AES, LEED and STM study

Keywords: Zn monolayer, Ag(111), Ag(110), STM, superstructure, Moiré pattern Auger Electron Spectroscopy, Low Energy Electron Diffraction and Scanning Tunneling

come   L'archive ouverte pluridisciplinaire

Introduction

Due to their important potential applications in the domain of catalysis or magnetism, the deposition of metal thin films on metallic substrates is of great interest. It is also very important from a fundamental point of view to the understanding of epitaxy mechanisms. Since the discovery of graphene [START_REF] Geim | The rise of graphene[END_REF][START_REF] Novoselov | Electric field effect in atomically thin carbon films[END_REF], and equivalent silicene [START_REF] Kara | A review on silicene -New candidate for electronics[END_REF], germanene [START_REF] Lin | Single-layer dual germanene phases on Ag(111)[END_REF], [START_REF] Cahangirov | Two-and one-dimensional honeycomb structures of silicon and germanium[END_REF], [START_REF] Balendhran | Elemental analogues of graphene: Silicene, germanene, stanene, and phosphorene[END_REF] …, films of one monolayer thickness have been studied with a particular attention due to their potential unexpected and new electronic properties: high 2D conductivity, Dirac fermions, Mott insulators [START_REF] Molitor | Electronic properties of graphene nanostructures[END_REF], [START_REF] Cao | Magic-angle graphene superlattices: a new platform for unconventional superconductivity[END_REF][START_REF] Cao | Correlated insulator behaviour at half-filling in magic-angle graphene superlattices[END_REF] ... Generally the deposition of a metal A on a metallic substrate B is related to the corresponding relative segregation phenomenon of both elements in AB alloy in particular when the substrate temperature allows atomic exchanges close to the surface. In this framework there are three driving forces which allow to predict the element which will have a tendency to segregate at the surface [START_REF] Wynblatt | Surface energy and solute strain energy effects in surface segregation[END_REF][START_REF] Tréglia | Alloy surfaces: Segregation, reconstruction and phase transitions[END_REF] (i) the surface energy difference; (ii) the atomic radius difference and (iii) the order or phase separation tendency. It is the coupling between these three effects which drives (in most cases) the behavior of the system. Many experimental studies have been interpreted at the light of these three driving forces and predictable maps have been drawn up for many bimetallic systems [START_REF] Roussel | Surface segregation maps derived from Tight-Binding Ising model[END_REF].

In the special case of the deposition of one monolayer of an element having a surface energy lower than the one of the substrate, the atomic structure of the deposited monolayer is strongly dependent on the atomic radius difference between elements. Indeed when the deposited element is larger than the one of the substrate (which is the most common case) the monolayer forms Moiré patterns directly related to the difference between adsorbate and substrate atomic radii (due to the Vernier effect). In contrary, when the deposited element is smaller than the one of the substrate (few systems present this characteristic), there is a coherent epitaxy (pseudomorphy) of the monolayer with formation of periodic linear defects in relation to the strain relaxation [START_REF] Goyhenex | Theoretical determination of two critical sizes for strain relaxation during Co/Pt(111) heteroepitaxy[END_REF]. In other words the monolayer of the deposited element presents in this case the same atomic parameters than the one of the substrate. In this paper we experimentally show that it is not always the case since we do not observe the expected coherent epitaxy when a Zn monolayer is deposited at room temperature on Ag(111) et Ag(110). The Zn on Ag system corresponds to the case where the deposited element presents a lower surface energy than the substrate one (0.99 and 1.25 J.m -2 respectively [START_REF] Tyson | Surface energies of solid metals[END_REF]) and Zn atoms are smaller than Ag atoms (0.266 and 0.289 nm in diameter respectively). Instead we observed Moiré patterns as expected when adsorbed atoms are larger than substrate ones.

In 1994, Zn deposition on Ag substrates was first studied by Kourouklis et al. [START_REF] Kourouklis | The growth and structure of ZnOx overlayers on low index silver surfaces[END_REF] using Auger Electron spectroscopy (AES), Low Energy Electron Diffraction (LEED) and Temperature Programmed Desorption (TDS). The main results can be summarized as follows: on the three low index Ag faces (110), (100) and (111) the growth kinetics (i.e. the variation of Ag and Zn intensities Auger peaks versus the deposition time) show at the beginning of the growth, a surprising delay; i.e. in the onset of the growth, there is no detected Zn Auger signal, whereas the Ag signal starts to decrease with respect to its initial value. No superstructure was observed by LEED at all deposited Zn amounts, substrate temperatures and Ag surface orientations. From their results the authors propose a growth mode starting with 3D Zn clusters formation on Ag surfaces.

Here we present a set of new experimental data obtained by AES, LEED and Scanning Tunneling Microscopy (STM) of Zn deposition at room temperature (RT) on Ag(111) and Ag(110) substrates. This paper is mainly dedicated to the atomic structure of the Zn monolayer on both silver faces, which was not observed by Kourouklis et al. [START_REF] Kourouklis | The growth and structure of ZnOx overlayers on low index silver surfaces[END_REF]. In a forthcoming paper we will focus on the first stages of the Zn growth.

In the following, we first describe the experimental set-up and then present and discuss the experimental results obtained by AES, LEED and STM after the deposition of one Zn monolayer on Ag(111) and Ag(110).

Experimental set-up

The experiments are performed in three different ultra-high vacuum (UHV) chambers connected all together (P < 10 -9 mBar). The main chamber contains the Zn evaporator, an Auger spectrometer (CMA) and a LEED optics. Attached to this main chamber there is a STM (Omicron STM-1) working at room temperature with a tungsten tip cleaned by heating. The sample surface cleaning is performed in a third chamber also attached to the main chamber. The sample preparation consists of repeating surface Ar ion sputtering (1 hour, 550eV) followed by annealing at 800K for 1h in UHV conditions. The surface cleanness is checked by AES and LEED. The sample is heated via a tungsten wire placed under the sample holder and the sample temperature is controlled by a thermocouple located close to the sample. The evaporation of Zn is performed from an alumina crucible heated with a tungsten filament. The evaporation rate and the calibration of Zn amounts are deduced from Auger, LEED and STM measurements (see below). The experimental protocol to record growth kinetics consists of maintaining the sample alternatively in front of the Zn evaporator for a constant time (2 min) then in front of the Auger analyzer to record the chemical surface evolution and finally in front of the LEED optics to observe the surface structure evolution. All the STM images are recorded in the filled state mode.

Zn deposition on Ag(111)

The AES-LEED study Figure 1 shows the variations at room temperature, of the peak-to-peak Auger signal intensities of Ag (355 eV), and Zn (56eV) versus Zn deposition time. The shape of this Auger growth kinetics is very close to the one presented by Kourouklis et al. [START_REF] Kourouklis | The growth and structure of ZnOx overlayers on low index silver surfaces[END_REF] on the Ag(100) face at room temperature. The intensity of the Zn (56eV) Auger peak presents at the beginning of the growth the same delay. After this delay, there is a quasi linear increase of the Zn intensity up to a slope change (a break) at about 10 min of deposition. After this break the Zn intensity increases slowly up to plateau. In a concomitant way, the intensity of the Ag Auger peak is continuously decreasing down a value close to zero. From these curves and from LEED and STM characterizations (see below) we deduced that the Zn ML is obtained after about 10 min of Zn deposition time (pointed out by a black vertical line on Figure 1). 2b) to completely disappear with an increase of the background after 13 min of deposition. At first glance this LEED pattern is in line with a dense (111) Zn plane in epitaxy on the Ag(111) substrate. Indeed, the ratio between the lattice parameters deduced from the LEED pattern of Ag and Zn is about 1.1 in agreement with the expected ratio between Ag (0.289 nm) and Zn (0.266 nm) interatomic distances (1.086). Nevertheless, a slight elongation of Zn spots indicates small rotations of the Zn layer with respect to the substrate.

The STM study

The STM study has been performed when the LEED pattern shows the superstructure reported on Figure 2b, i.e. after 10 min of deposition time. In order to determine the MP dispersion we have measured its size () and angle ()

directly on eleven different areas on the sample. The corresponding values are reported in Table 1. We deduced an average angle () of the MP relatively to the Ag [START_REF] Wynblatt | Surface energy and solute strain energy effects in surface segregation[END_REF] direction (=18°  7°)

and an average size of the unit cell (= 3.3 nm  0.8nm).

𝑑 𝑍𝑛 = 𝜆 √ 1+( 𝜆 𝑑 𝐴𝑔 ) 2 +2( 𝜆 𝑑 𝐴𝑔 (1)
) cos 𝛾 [START_REF] Novoselov | Electric field effect in atomically thin carbon films[END_REF] dZn from 0.261 nm to 0.270 nm. It is noteworthy that the observed dispersion is larger than the measurement precision showing that the unit cell of the Zn monolayer fluctuates in size and angle (more in angle than in size).

Figure 5a and 5b display the theoretical variations of and  as a function of  in the case of the two extremum values of dZn (the blue and the red lines) and for its average value (the black line). The eleven experimental values of the MP are also reported. These curves indicate that the average value dZn corresponds to its bulk value in the hexagonal (0.01) plane. It shows too, that a variation of few degrees of gives rise to a large variation of  and . Moreover, the dZn variation remains weak with respect to  variation. As a consequence, the dispersion of  and dZn, explains the elongated shape of the Zn spots of the LEED pattern. 1). This superstructure corresponds to a (156x156)R18° in the Wood's surface structure notation.

Zn deposition on Ag(110)

The AES-LEED study

The STM study

The STM study was performed when the LEED pattern showed the superstructure reported on Figure 8b i. Figure 10a is a high resolution STM image of domain 1 in which we observe Moiré patterns in the shape of diagonal and horizontal lines. There is a large dispersion of the distance between diagonal lines (from 1.9 nm to 3.7 nm with an average value of 2.2 nm), while the distance between the horizontal lines is constant and close to the one between two dense silver rows ( 0.4 nm). Figure 10b is an FFT filtered STM image of a blow-up of part of the STM image Figure 10a. This HR STM image shows that the Moiré line (highlighted by a white dashed line), is generated by a periodic shift of the horizontal lines (highlighted by black lines).

The average distance between two protrusions along a horizontal line is close to dZn (0.26 nm).

The red lines show a perfect and regular alignment of protrusions across the diagonal Moiré lines.

3.2nm

Zn

General discussion

On Ag(111) and on Ag(110) we observe the same delay at the beginning of the Auger growth kinetics that Kourouklis et al. did on Ag(100). They interpreted this delay by a growth mode Volmer-Weber type; i.e. by the formation of Zn 3D islands. At the light of our results we think that this conclusion is not correct, since we observe an epitaxy of a Zn dense (111) monolayer on Ag(111) as well as on Ag(110) faces which show the tendency of Zn atoms to wet the surface.

From a thermodynamics point of view, the formation of a quasi pure Zn monolayer is in line with a Zn surface energy much lower than the Ag one (0.99 and 1.25 J.m -2 respectively [START_REF] Tyson | Surface energies of solid metals[END_REF]). Note that the two other driving forces (size and chemical effects), are not in favor of Zn surface segregation. Indeed, the size (dZn < dAg) and chemical effects (tendency to order) will not yield a Zn surface segregation.

From a structural point of view, on both faces, the MP's are not regular and present local dispersions in size and direction. This could be due to local rotations of the Zn ML and, to a lesser degree, to a size variation of the Zn unit cell. This means that on both faces, the chemical interactions between Ag substrate and Zn ML are weak: in other words, the Zn ML is not strongly linked to the Ag substrate. Nevertheless, this "floating-like" behaviour seems to be more evident on the (111) face than on the (110) one. In any case, this almost "floating-like" behaviour reveals strong in plane Zn-Zn bonds. This could be in relation with the hexagonal compact bulk structure of Zn which presents a large c/a ratio: 1.86, the highest of all metallic elements with an hexagonal compact structure (1.63).

Conclusion

We have studied the deposition of a Zn monolayer on Ag(111) and Ag(110) substrates by AES, LEED and STM. The growth kinetics profile obtained by AES is in agreement with previous work by Kourouklis et al. [START_REF] Kourouklis | The growth and structure of ZnOx overlayers on low index silver surfaces[END_REF]. Nevertheless, contrary to their conclusions there is no formation of 3D Zn clusters at the beginning of the growth. We show that on both faces, there is formation of one flat dense (111) monolayer of Zn covering the entire substrate surface. From a detailed analysis of LEED and Moiré patterns observed by STM, we propose two ball models where the Zn monolayers are rotated with respect to the silver substrate, of about  1.5° on the Ag(111) face and of about  4.5° on the Ag(110) giving rise respectively to (156x156)R18° and c(12x6) superstructures. Hence Moiré patterns can also occur when the deposited elements are smaller than the substrate ones.

The analysis of Moiré patterns has proven to be a powerful technique to the determination of the atomic structure of a monolayer. Such method has been used for the determination of silicene structure on silver [START_REF] Jamgotchian | A comprehensive study of the (2√3 ×2√3)R30° structure of silicene on Ag(1 1 1)[END_REF][START_REF] Jamgotchian | A comprehensive analysis of the (√13 × √13) R 13.9° type II structure of silicene on Ag(1 1 1)[END_REF], graphene on metal [START_REF] Wintterlin | Graphene on metal surfaces[END_REF] or metal on metal [START_REF] Yu | Surface alloying effects in the growth of Au on Pb(1 1 1) thin film[END_REF][START_REF] Aufray | Ag/Cu(111): An incommensurate reconstruction studied with scanning tunnelling microscopy and surface X-ray diffraction[END_REF].

1 MLFigure 1 :Figure 2 :

 112 Figure 1: Auger Signal intensities as a function of the Zn deposition time at room temperature

Figure 3 :

 3 Figure 3: STM image of the Ag(111) surface recorded after 10 min of Zn deposition time

Figure 4 :Figure

 4 Figure 4: STM images a) at low resolution showing the MP and b) with atomic resolution. Their corresponding FFT are shown on (c) and (d)

Figure 5 :Figure 6

 56 Figure 5: Theoretical variations of the MP angle (a) and of the Moiré periodicity (b) versus the angle of rotation of the Zn monolayer with respect to the Ag. The black points correspond to the experimental values measured on different STM images

Figure 6 :

 6 Figure 6: Ball model of a dense plane of Zn (grey balls) rotated 1.5° relatively to silver (black balls). The unit cell of the Moiré pattern forming the ((156x156)R18° superstructure is highlighted in red. a) Large view b) Enlarged view showing details of the epitaxy. In red: the Moiré unit cell. In yellow: the Zn and the Ag [10] directions

Figure 7 Figure 7 :Figure 8 :

 778 Figure7shows the variations at room temperature of the peak-to-peak Auger signal intensities of silver (355 eV) and Zn (56 eV) versus Zn deposition time. As for the (111) orientation we observe a similar shape of the growth kinetics i.e. first a delay at the beginning of the growth, then a quasi linear increase up to a slope change (at about 10 min) and finally a plateau after 13 min of Zn deposition. From these curves and from LEED and STM characterizations (see below) we deduced that the Zn ML is obtained after about 10 min of Zn deposition time pointed out by a black vertical line on Figure7.

  e. after 10 min of Zn deposition time. One observes two domains of stripes which directions are indicated by blue arrows on the STM image. Both directions are symmetrical with respect to [110] direction of Ag. The orientation of the Ag substrate is given by the atomic resolution of the Ag surface before Zn deposition, inserted in the bottom right of the image. These two domains are also visible on the LEED pattern shown in Figure 8b through the two symmetrical extra spots with respect to Ag(-10) direction. Note that the ratio of the spot distances measured on LEED for Zn and Ag is ~1.1 which corresponds to the ratio between Ag and Zn interatomic distances (0.289/0.266=1.086).

Figure 9 :Figure 10 :

 910 Figure 9: STM image of the Ag(110) surface after 10 min of Zn deposition. The insert corresponds to the atomic resolution of a bare Ag(110) which shows the orientation of the substrate

ModelFigure 11 :Figure 12 :

 1112 Figure 11: Ball model of a pseudo triangular Zn monolayer (0.277 x 0.260 nm 2 , 122°,  = 3.7°) deposited on the Ag(110) surface generating a c(12x6) superstructure and the associated Moiré pattern. a) Large view; b) Blow-up view showing details of the epitaxy

Figure 12

 12 Figure12compares the FFT's of the STM image (Figure10a) and of the ball model (Figure11a). The good agreement between the two FFTs and the LEED pattern validates the proposed ball model.

Table 1 :

 1 MP

			2	3	4	5	6	7	8	9	10	11 average dispersion
	 (nm)	3.9 2.7 3.3 2.6 3.6 3.1 3.3 3.9 3.9 2.5 3.5	3.3	
	measured
	 (°)	15	13	22	20	14	20	16	19	14	23	25	18	
	measured
		1.1 1.3 1.8 1.9 1.0 1.7 1.2 1.3 1.0 2.3 1.9	1.5	
	calculated
	dZn (pm)	270 261 267 261 268 265 266 270 270 261 269	266	
	calculated

parameters measured on STM images recorded on eleven different areas.  is the rotation angle of the MP with respect to the Ag

[START_REF] Wynblatt | Surface energy and solute strain energy effects in surface segregation[END_REF]

direction and  is the Moiré size.  is the rotation angle of the Zn monolayer with respect to the Ag

[START_REF] Wynblatt | Surface energy and solute strain energy effects in surface segregation[END_REF]

direction and dZn is the distance between two Zn atoms (and dZnare deduced from the experiments using relations 1 and 2 see below) Model K. Herman

[START_REF] Hermann | Periodic overlayers and moiré patterns: Theoretical studies of geometric properties[END_REF]

studied the theoretical geometric relations of an MP formed by the superposition of two periodic structures. He deduced two relations linking the parameters of the two periodic structures and of the Moiré one. When applied to two triangular structures like Ag(111) and Zn(111) the relations become:

For each of the eleven different values, the relations allow to calculate  (the rotation angle of the Zn monolayer with respect to the substrate) and dZn (distance between two Zn atoms) which both are reported on Table

1

. Calculated  values are between 1.0° to 2.3° and

Acknowledgements

The authors gratefully acknowledge G. Tréglia and J. Rothwell for many helpful discussions and for critically reviewing this manuscript.