Rafael Angarita
email: rangarita@ldc.usb.ve

Yudith Cardinale

Marta Rukoz
email: marta.rukoz@lamsade.dauphine.fr

FaCETa: Backward and Forward Recovery for Execution of Transactional Composite WS

In distributed software contexts, Web Services (WSs) that provide transactional properties are useful to guarantee reliable Transactional Composite WSs (TCWSs) execution and to ensure the whole system consistent state even in presence of failures. Fails during the execution of a TCWS can be repaired by forward or backward recovery processes, according to the component WSs transactional properties. In this paper, we present the architecture and an implementation of a framework, called FaCETa, for efficient, fault tolerant, and correct distributed execution of TCWSs. FaCETa relies on WSs replacement, on a compensation protocol, and on unrolling processes of Colored Petri-Nets to support fails. We implemented FaCETa in a Message Passing Interface (MPI) cluster of PCs in order to analyze and compare the behavior of the recovery techniques and the intrusiveness of the framework.

Introduction

Large computing infrastructures, like Internet increase the capacity to share information and services across organizations. For this purpose, Web Services (WSs) have gained popularity in both research and commercial sectors. Semantic WS technology [START_REF] Mcilraith | Semantic web services[END_REF] aims to provide for rich semantic specifications of WSs through several specification languages such as OWL for Services (OWL-S), the Web Services Modeling Ontology (WSMO), WSDL-S, and Semantic Annotations for WSDL and XML Schema (SAWSDL) [START_REF] Farrell | Semantic annotations for wsdl and xml schema[END_REF]. That technology supports WS composition and execution allowing a user request be satisfied by a Composite WS, in which several WSs and/or Composite WSs work together to respond the user query.

WS Composition and the related execution issues have been extensively treated in the literature by guaranteeing user QoS requirements and fault tolerant execution [START_REF] Cardinale | CPN-TWS: A colored petri-net approach for transactional-qos driven web service composition[END_REF][START_REF] Haddad | TQoS: Transactional and QoS-aware selection algorithm for automatic Web service composition[END_REF][START_REF] Ben Lakhal | FENECIA: failure endurable nested-transaction based execution of compo site Web services with incorporated state analysis[END_REF][START_REF] Liu | FACTS: A Framework for Fault Tolerant Composition of Transactional Web Services[END_REF][START_REF] Mei | A compensation paired net-based refinement method for web services composition[END_REF]. WSs that provide transactional properties are useful to guarantee reliable Transactional Composite WSs (TCWSs) execution, in order to ensure that the whole system remains in a consistent state even in presence of failures. TCWS becomes a key mechanism to cope with challenges of open-world software. Indeed, TCWS have to adapt to the open, dynamically changing environment, and unpredictable conditions of distributed applications, where remote services may be affected by failures and availability of resources [START_REF] Yu | Deploying and managing web services: issues, solutions, and directions[END_REF].

Generally, the control flow and the order of WSs execution is represented with a structure, such as workflows, graphs, or Petri-Nets [START_REF] Brogi | Semantics-based compositionoriented discovery of web services[END_REF][START_REF] Cardinale | Web service selection for transactional composition[END_REF][START_REF] Cardinale | CPN-TWS: A colored petri-net approach for transactional-qos driven web service composition[END_REF][START_REF] Hogg | Learning Hierarchical Task Networks for Nondeterministic Planning Domains[END_REF]. The actual execution of such TCWS, carried out by an Executer, could be deployed with centralized or distributed control. The Executer is in charge of (i) invoking actually WSs for their execution, (ii) controlling the execution flow, according to data flow structure representing the TCWS, and (iii) applying recovery actions in case of failures in order to ensure the whole system consistence; fails during the execution of a TCWS can be repaired by forward or backward recovery processes, according to the component WSs transactional properties.

In previous works [START_REF] Cardinale | Fault tolerant execution of transactional composite web services: An approach[END_REF][START_REF] Cardinale | A framework for reliable execution of transactional composite web services[END_REF] we formalized a fault tolerant execution control mechanism based on Colored-Petri Nets (CPN), which represent the TCWS and the compensation process. In [START_REF] Cardinale | Fault tolerant execution of transactional composite web services: An approach[END_REF] unrolling algorithms of CPNs to control the execution and backward recovery were presented. This work was extended in [START_REF] Cardinale | A framework for reliable execution of transactional composite web services[END_REF] to consider forward recovery based on WS replacement; formal definitions for WSs substitution process, in case of failures, were presented. In [START_REF] Cardinale | A framework for reliable execution of transactional composite web services[END_REF], we also proposed an Executer architecture, independent of its implementation, to execute a TCWS following our proposed fault tolerant execution approach.

In this paper, we present an implementation of our Executer framework, called FaCETa (FAult tolerant Cws Execution based on Transactional properties), for efficient, fault tolerant, and correct distributed execution of TCWSs. We implemented FaCETa in a Message Passing Interface (MPI) cluster of PCs in order to analyze and compare the efficiency and performance of the recovery techniques and the intrusiveness of the framework. The results show that FaC-ETa efficiently implements fault tolerant strategies for the execution of TCWSs with small overhead.

TCWS Fault-Tolerant Execution

This Section recall some important issues related to transactional properties and backward and forward recovery, presented in our previous works [START_REF] Cardinale | CPN-TWS: A colored petri-net approach for transactional-qos driven web service composition[END_REF][START_REF] Cardinale | Fault tolerant execution of transactional composite web services: An approach[END_REF][START_REF] Cardinale | A framework for reliable execution of transactional composite web services[END_REF]. We consider that the Registry, in which all WSs are registered with their corresponding WSDL and OWLS documents, is modeled as a Colored Petri-Net (CPN), where WS inputs and outputs are represented by places and WSs, with their transactional properties, are represented by colored transitions -colors distinguish WS transactional properties [START_REF] Cardinale | CPN-TWS: A colored petri-net approach for transactional-qos driven web service composition[END_REF]. The CPN representing the Registry describes the data flow relation among all WSs.

We define a query in terms of functional conditions, expressed as input and output attributes; QoS constraints, expressed as weights over criteria; and the required global transactional property as follows. A Query Q is a 4-tuple

(I Q , O Q , W Q , T Q ), where:
-I Q is a set of input attributes whose values are provided by the user, -O Q is a set of output attributes whose values have to be produced by the system, -W Q = {(w i , q i ) | w i ∈ [0, 1] with i w i = 1 and q i is a QoS criterion}, and -T Q is the required transactional property; in any case, if the execution is not successful, nothing is changed on the system and its state is consistent.

A TCWS, which answers and satisfies a Query Q, is modeled as an acyclic marked CPN, called CPN-T CW S Q , and it is a sub-net of the Registry CPN1 . The Initial Marking of CPN-T CW S Q is dictated by the user inputs. In this way, the execution control is guided by a unrolling algorithm.

Transactional Properties

The transactional property (T P ) of a WS allows to recover the system in case of failures during the execution. The most used definition of individual WS transactional properties (T P (ws)) is as follows [START_REF] Cardinale | Transactional-aware Web Service Composition: A Survey[END_REF][START_REF] Gaaloul | Event-based design and runtime verification of composite service transactional behavior[END_REF]. Let s be a WS: s is pivot (p), if once s successfully completes, its effects remains forever and cannot be semantically undone (compensated), if it fails, it has no effect at all; s is compensatable (c), if it exists another WS s , which can semantically undo the execution of s, even after s successfully completes; s is retriable (r), if s guarantees a successfully termination after a finite number of invocations; the retriable property can be combined with properties p and c defining pivot retriable (pr) and compensatable retriable (cr) WSs.

In [START_REF] Haddad | TQoS: Transactional and QoS-aware selection algorithm for automatic Web service composition[END_REF] the following T P of TCWS have been derived from the T P of its component WSs and their execution order(sequential or parallel). Let tcs be a TCWS: tcs is atomic (a), if once all its component WSs complete successfully, they cannot be semantically undone, if one component WS does not complete successfully, all previously successful component WSs have to be compensated; tcs is compensatable (c), if all its component WSs are compensatable; tcs is retriable (r), if all its component WSs are retriable; the retriable property can be combined with properties a and c defining atomic retriable (ar) and compensatable retriable (cr) TCWSs.

According to these transactional properties, we can establish two possible recovery techniques in case of failures:

-Backward recovery: it consists in restoring the state (or a semantically closed state) that the system had at the beginning of the TCWS execution; i.e., all the successfully executed WSs, before the fail, must be compensated to undo their produced effects. All transactional properties (p, a, c, pr, ar, and cr) allow backward recovery; -Forward recovery: it consists in repairing the failure to allow the failed WS to continue its execution. Transactional properties pr, ar, and cr allow forward recovery. The execution control of a TCWS is guided by a unrolling algorithm of its corresponding CPN-T CW S Q . A WS is executed if all its inputs have been provided or produced, i.e., each input place has as many tokens as WSs produce them or one token if the user provide them. Once a WS is executed, its input places are unmarked and its output places (if any) are marked.

Backward

The compensation control of a TCWS is also guided by a unrolling algorithm. When a WS represented by a transition s fails, the unrolling process over CPN-T CW S Q is halted,an Initial Marking on the corresponding BRCPN-T CW S Q is set (tokens are added to places associated to input places of the faulty WS s, and to places representing inputs of BRCPN-T CW S Q , i.e., places without predecessors) and a backward recovery is initiated with the unrolling process over BRCPN-T CW S Q . We illustrate a backward recovery in Figure 1. The marked CPN-T CW S Q depicted in Figure 1(a) is the state when ws 4 fails, the unrolling of CPN-T CW S Q is halted, and the Initial Marking on the corresponding BRCPN-T CW S Q is set to start its unrolling process (see Figure 1(b)), after ws 3 and ws 5 are executed and ws 7 is abandoned before its invocation, a new Marking is produced (see Figure 1(c)), in which ws 1 and ws 2 are both ready to be executed and can be invoked in parallel. Note that only compensatable transitions have their corresponding compensation transitions in BRCPN-T CW S Q .

Forward Recovery Process: Execution with WS Substitution

During the execution of TCWSs, if a failure occurs in an advanced execution point, a backward recovery may incur in high wasted resources. On the other hand, it is hard to provide a retriable TCWS, in which all its components are retriable to guaranty forward recovery. We proposed an approach based on WS substitution in order to try forward recovery [START_REF] Cardinale | A framework for reliable execution of transactional composite web services[END_REF]. TCWS composition and execution processes deal with service classes [START_REF] Azevedo | Handling dissimilarities of autonomous and equivalent web services[END_REF], which group WSs with the same semantic functionality, i.e., WSs providing the same operations but having different WSDL interfaces (input and output attributes), transactional support, and QoS. When a WS fails, if it is not retriable, instead of backward recovery, an substitute WS is searched to be executed on behalf of the faulty WS. In a service class, the functional equivalence is defined according the WSs input and output attributes. A WS s is a functional substitute, denoted by ≡ F , to another WS s * , if s * can be invoked with at most the input attributes of s and s * produces at least the same output attributes produced by s. s is an Exact Functional substitute of s * , denoted by ≡ EF , if they have the same input and output attributes. Figure 2 illustrates several examples: ws 1 ≡ F ws 2 , however ws 2 ≡ F ws 1 , because ws 1 does not produce output a 5 as ws 2 does. ws 1 ≡ F ws 3 , ws 3 ≡ F ws 1 , and also ws 1 ≡ EF ws 3 .

Fig. 2. Example of functional substitute WSs

In order to guarantee the TCWS global T P , a WS s can be replaced by another WS s * , if s * can behave as s in the recovery process. Hence, if T P (s)=p, in which case s only allows backward recovery, it can be replaced by any other WS because all transactional properties allow backward recovery. A WS with T P (s) = pr can be replaced by any other retriable WS (pr,ar,cr), because all of them allow forward recovery. An atomic WS allows only backward recovery, then it can be replaced by any other WS which provides backward recovery. A compensatable WS can be replaced by a WS that also provides compensation as c and cr WSs. A cr WS can be only replaced by another cr WS because it is the only one allowing forward and backward recovery. Thus, a WS s is Transactional substitute of another WS s * , denoted by ≡ T , if s is a Functional substitute of s * and their transactional properties allow the replacement.

In Figure 2, ws 1 ≡ T ws 2 , because ws 1 ≡ F ws 2 and T P (ws 2 ) = cr, then ws 2 can behave as a pr WS; however ws 1 ≡ T ws 3 , even ws 1 ≡ F ws 3 , because as T P (ws 3 ) = p, w 3 cannot behave as a pr WS. Transactional substitution definition allows WSs substitution in case of failures.

When a substitution occurs, the faulty WS s is removed from the CPN-T CW S Q , the new s * is added, but we keep the original sequential relation defined by the input and output attributes of s. In that way, the CPN-T CW S Q structure, in terms of sequential and parallel WSs, is not changed. For compensatable WSs, it is necessary Exact Functional Substitute to do not change the compensation control flow in the respective BRCPN-T CW S Q . In fact, when a compensatable WS is replaced, the corresponding compensate WS must be also replaced by the new corresponding one in the BRCPN-T CW S Q . The idea is to try to finish the TCWS execution with the same properties of the original one.

Protocol in case of Failures

In case of failure of a WS s, depending on the T P (s), the following actions could be executed:

-if T P (s) is retriable (pr, ar, cr), s is re-invoked until it successfully finish (forward recovery); -otherwise, another Transactional substitute WS, s * , is selected to replace s and the unrolling algorithm goes on (trying a forward recovery); -if there not exist any substitute s * , a backward recovery is needed, i.e., all executed WSs must be compensated in the inverse order they were executed; for parallel executed WSs, the order does not matter. When in a service class there exist several WSs candidates for replacing a faulty s, it is selected the one with the best quality measure. The quality of a transition depends on the user query Q and on its QoS values. WSs Substitution is done such that the substitute WS locally optimize the QoS. If several transitions have the same value of quality, they can be randomly selected to be the substitute. A similar quality measure is used in [START_REF] Cardinale | CPN-TWS: A colored petri-net approach for transactional-qos driven web service composition[END_REF] to guide the composition process. Then, during the execution, we keep the same heuristic to select substitutes.

FaCETa: An TCWS Executer with Backward and Forward Recovery Support

In this Section we present the overall architecture of FaCETa, our execution framework. The execution of a TCWS in FaCETa is managed by an Execu-tion Engine and a collection of software components called Engine Threads, organized in a three levels architecture. In the first level the Execution Engine receives the TCWS (represented by a CPN). It is in charge of initiating, controlling, and monitoring the execution of the TCWS. To do so, it launches, in the second layer, an Engine Thread for each WS in TCWS. Each Engine Thread is responsible for the execution control of its WS. They receive WS inputs, invoke the respective WS, and forward its results to its peers to continue the execution flow. In case of failure, all of them participate in the backward or forward recovery process. Actual WSs are in the third layer. Figure 3 roughly depicts the overall architecture. By distributing the responsibility of executing a TCWS across several Engine Threads, the logical model of our Executer allows distributed execution of a TCWS and is independent of its implementation, i.e., this model can be implemented in a distributed memory environment supported by message passing (see Figure 4(a)) or in a shared memory platform, e.g., supported by a distributed shared memory [START_REF] De Oliveira | Efficient distributed shared memory on a single system image operating system[END_REF] or tuplespace [START_REF] Martin | Tuplespace middleware for petri net-based workflow execution[END_REF] systems (see Figure 4(b)). The idea is to place the Executer in different physical nodes (e.g., a high available and reliable cluster computing) from those where actual WSs are placed. The Execution Engine needs to have access to the WSs Registry, which contains the WSDL and OWLS documents. The knowledge required at runtime by each Engine Thread (e.g., WS semantic and ontological descriptions, WSs predecessors and successors,transactional property, and execution control flow) can be directly extracted from the CPNs in a shared memory implementation or sent by the Execution Engine in a distributed memory implementation. In this paper, we have implemented a prototype of FaCETa in a distributed memory platform using MPI.

Typically, a component of a TCWS can be a simple transactional WS or TCWS. Thus, we consider that transitions in the CPN, representing the TCWS, could be WSs or TCWSs. WSs have its corresponding WSDL and OWLS documents. TCWSs can be encapsulated into an Executer; in this case the Execution Engine has its corresponding WSDL and OWLS documents. Hence, TCWSs may themselves become a WS, making TCWS execution a recursive operation (see Figure 3).

Distributed Memory Implementation of FaCETa

We implemented FaCETa in a MPI Cluster of PCs (i.e., a distributed memory platform) following a Master/Slaves-SPDM (Single Process Multiple Data) parallel model. The Execution Engine run in the front-end of the Cluster waiting user execution requests. To manage multiple client requests, the Execution Engine is multithreading. The deployment of a TCWS implies several steps: Initial, WS Invocation, and Final phases. In case of failures, recovery phases could be executed: Replacing phase, allowing forward recovery or Compensation phase for backward recovery.

Whenever the Execution Engine (master) receives a CPN-T CW S Q and its corresponding BRCPN-T CW S Q , it performs the Initial phase: (i) start, in different nodes of the cluster, an Engine Thread (peer slaves) responsible for each transition in CPN-T CW S Q , sending to each one its predecessor and successor transitions as CPN-T CW S Q indicates (for BRCPN-T CW S Q the relation is inverse) and the corresponding WSDL and OWLS documents (they describe the WS in terms of its inputs and outputs, its functional substitute WSs, and who is the compensation WS, if it is necessary); and (ii) send values of attributes in I Q to Engine Threads representing WSs who receive them. Then the master wait for a successfully execution or for a message compensate in case of a backward recovery is needed.

Once Engine Threads are started, they receive the part of CPN-T CW S Q and BRCPN-T CW S Q that each Engine Thread concerns on, sent by the Execution Engine in the Initial phase. Then, they wait for the input values needed to invoke its corresponding WS. When an Engine Thread receives all input values (sent by the master or by other peers) and all its predecessor peers have finished, it executes the WS Invocation phase, in which the actual WS is remotely invoked. If the WS finishes successfully, the Engine Thread sends WS output values to Engine Threads representing its successors and wait for a finish or compensate message. If the WS fails during the execution, the Engine Thread tries a forward recovery: if T P (WS) is retriable, the WS is re-invoked until it successfully finish; otherwise the Engine Thread executes the Replacing phase: the Engine Thread has to determine the best substitute among the set of functional substitute WSs; it calculates the quality of all candidates according their QoS criteria values and the preferences provided in the user query; the one with the best quality is selected to replace the faulty WS; this phase can be executed for a maximum number of times (M AXT ries). If replacing is not possible, the Compensation phase has to be executed: the Engine Thread responsible of the faulty WS sends the message compensate to Execution Engine and control tokens to successor peers of the compensation WS, in order to inform about this failure and start the unrolling process over BRCPN-T CW S Q ; once an Engine Thread receives all control tokens, it invokes the compensation WS; the unrolling of BRCPN-T CW S Q ensure the invocation of compensation WSs, s , in the inverse order in which their corresponding WS, s, were executed. Note that forward recovery is executed only by the Engine Thread responsible of the faulty WS, without intervention of the master neither other peers; while backward recovery need the intervention of all of them.

If the TCWS was successfully executed, in the Final phase the master receives all values of attributes of O Q , in which case it broadcasts a finish message to all slaves to terminate them, and returns the answer to user; otherwise it receive a compensate message indicating that a backward recovery has to be executed, as it was explained above, and return an error message to user.

Assumptions:

In order to guarantee the correct execution of our algorithms, the following assumptions are made: (i) the network ensures that all packages are sent and received correctly; (ii) the Execution Engine and Engine Threads run in a reliable cluster, they do not fail; (iii) the Engine Threads receive all WS outputs when its corresponding WS finishes, they cannot receive partial outputs from its WS; and (iv) the component WSs can suffer silent or stop failures (WSs do not response because they are not available or a crash occurred in the platform); we do not consider runtime failures caused by error in inputs attributes (e.g., bad format or out of valid range) and byzantine faults (the WS still responds to invocation but in a wrong way).

Results

We developed a prototype of FaCETa, using Java 6 and MPJ Express 0.38 library to allow the execution in distributed memory environments. We deployed FaCETa in a cluster of PCs: one node for the Execution Engine and one node for each Engine Thread needed to execute the TCWS. All PCs have the same configuration: Intel Pentium 3.4GHz CPU, 1GB RAM, Debian GNU/Linux 6.0, and Java 6. They are connected through a 100Mbps Ethernet interface.

We generated 10 compensatable TCWSs. All those TCWSs were automatically generated by a composition process [START_REF] Cardinale | CPN-TWS: A colored petri-net approach for transactional-qos driven web service composition[END_REF], from synthetic datasets comprised by 800 WSs with 7 replicas each, for a total of 6400 WSs. Each WS is annotated with a transactional property and a set of QoS parameters, however for our experiments we only consider the response time as the QoS criteria. Replicas of WSs have different response times.

The OWLS-API 3.0 was used to parse the WS definitions and to deal with the OWL classification process.

The first group of experiments were focussed on a comparative analysis of the recovery techniques. The second group of experiments evaluates the overhead incurred by our framework in control operations to perform the execution of a TCWS and to execute the fault tolerant mechanisms.

To simulate unreliable environments, we define five different conditions wherein all WSs have the same probability of failure: 0.2, 0.15, 0.1, 0.005, and 0.001. The executions on these unreliable environments were done in three scenarios to support the fails: (i) backward recovery (compensation, red bars in Figure 5), (ii) forward recovery because all WSs are retriable (retry, light blue bars in Figure 5), and (iii) forward recovery (substitution, gray bars in Figure 5). On each scenario all TCWSs were executed 10 times.

Each TCWS was also executed 10 times in a reliable environment, in which all WSs have 0 as probability of failures (no-faulty, blue bars in Figure 5) in order to classify them according their average total execution time in three groups: less than 1500ms (Figure 5(a)), (ii) between 1500ms and 3500ms (Figure 5(b), and (more than 3500ms (Figure 5(c)).

In Figure 5 we plot the average of the total execution time according the number of failed WSs, in order to compare all recovery techniques. The results show that when the number of failed WSs is small (i.e., the probability of failures is less than 20%) backward recovery (compensation) is the worst strategy because almost all component WSs had been executed and have to be compensated. Moreover, when the average of the total execution time of TCWSs is high (greater than 1500ms) forward recovery with retry strategy is better than forward recovery with substitution due to the substitute normally has a bigger response time than the faulty WS. By the other side, in cases in which the probability of failure is greater than 30%, backward recovery whit compensation behaves better than the other ones (even the final results is not produced) because there are many faulty services and only few have to be compensated.

Another issue that can be observed it is the number of outputs received before the backward recovery mechanism has to be executed. In this experiment, the average percentage of outputs received before compensation was 37%. All these outputs are lost or delivered as a set of incomplete (and possibly meaningless and useless) outputs to the user. This percentage is related to the average percentage of compensated services, which is 80%, confirming the overhead, the possible unfulfillment of QoS requirements, and the lost outputs. Definitely, backward The average overhead of FaCETa only depends on the number of components WSs in a TCWS. It does not depend on the total response time of TCWS. It means that while the total response time is higher the overhead % will decrease. It is clear that the reason behind the backward recovery strategy overhead (increased by 2%) is the amount of coordination required to start the compensation and the fact that a new WS execution (the compensation WS execution) has to be performed for each successfully executed WS, in order to restore the consistent system state. Additionally, the compensation process has to be done following the unrolling algorithm of the respective BRCPN-T CW S Q . We do not consider to wait before the retry of a failed WS execution; therefore, the increased overhead of retry a WS is almost imperceptible.

As the service class for each WS is sent by the Execution Engine in the Initial phase, each Engine Thread has the list of the functional substitute WSs sorted according their quality, then there is virtually no overhead when searching for a functional substitute WS to replace a faulty one.

Based on the results presented above, we can conclude that FaCETa efficiently implements fault tolerant strategies for the execution of TCWSs with admissible small overhead.

Related Work

Regarding fault tolerant execution of Composite WSs (CWSs), there exist centralized and distributed approaches. Generally centralized approaches [START_REF] Liu | Fault-tolerant orchestration of transactional web services, Web Information Systems -WISE[END_REF][START_REF] Park | A high performance backoff protocol for fast execution of composite web services[END_REF][START_REF] Schafer | An environment for flexible advanced compensations of web service transactions[END_REF] consider, besides compensation process, alternative WSs in case of failures or absent WSs, however they extend the classical 2PC protocol, which is time consuming, and they are not transparent to users and developers.

In distributed approaches, the execution process proceeds with collaboration of several entities. We can distinct two kinds of distributed coordination approach. In the first one, nodes interact directly based on a peer-to-peer application architecture and collaborate, in order to execute a CWS with every node executing a part of it [START_REF] Behl | Providing fault-tolerant execution of web-service-based workflows within clouds[END_REF][START_REF] Bushehrian | A workflow-based failure recovery in web services composition[END_REF][START_REF] Ben Lakhal | FENECIA: failure endurable nested-transaction based execution of compo site Web services with incorporated state analysis[END_REF][START_REF] Liu | FACTS: A Framework for Fault Tolerant Composition of Transactional Web Services[END_REF][START_REF] Yu | Fault handling and recovery in decentralized services orchestration[END_REF]. In the second one, they use a shared space for coordination [START_REF] Buhler | Enacting BPEL4WS specified workflows with multiagent systems[END_REF][START_REF] Fernandez | Decentralized approach for execution of composite web services using the chemical paradigm[END_REF][START_REF] Martin | Tuplespace middleware for petri net-based workflow execution[END_REF].

FENECIA framework [START_REF] Ben Lakhal | FENECIA: failure endurable nested-transaction based execution of compo site Web services with incorporated state analysis[END_REF] provides an approach for managing fault tolerance and QoS in the specification and execution of CWSs. FENECIA introduces WS-SAGAS, a transaction model based on arbitrary nesting, state, vitality degree, and compensation concepts to specify fault tolerant CWS as a hierarchy of recursively nested transactions. To ensure a correct execution order, the execution control of the resulting CWS is hierarchically delegated to distributed engines that communicate in a peer-to-peer fashion. A correct execution order is guaranteed in FENECIA by keeping track of the execution progress of a CWS and by enforcing forward and backward recovery. To manage failures during the runtime it allows the execution retrial with alternative candidates. FACTS [START_REF] Liu | FACTS: A Framework for Fault Tolerant Composition of Transactional Web Services[END_REF], is another framework for fault tolerant composition of transactional WSs based on FENECIA transactional model. It combines exception handling strategies and a service transfer based termination protocol. When a fault occurs at run-time, it first employs appropriate exception handling strategies to repair it. If the fault cannot be fixed, it brings the TCWS back to a consistent termination state according to the termination protocol (by considering alternative services, replacements, and compensation). In [START_REF] Yu | Fault handling and recovery in decentralized services orchestration[END_REF] a fault handling and recovery process based on continuation-passing messaging, is presented. Nodes interpret such messages and conduct the execution of services without consulting a centralized engine. However, this coordination mechanism implies a tight coupling of services in terms of spatial and temporal composition. Nodes need to know explicitly which other nodes they will potentially interact with, and when, to be active at the same time. In [START_REF] Behl | Providing fault-tolerant execution of web-service-based workflows within clouds[END_REF] all replicas of a WS are simultaneously invoked. Only results of the first replica finished are accepted, other executions are halted or ignored. As our work, in [START_REF] Bushehrian | A workflow-based failure recovery in web services composition[END_REF] a rollback workflow is automatically created considering the service dependencies. Those frameworks support users and developers to construct CWS based on WS-BPEL technologies, then they are not transparent to users and developers.

Another series of works rely on a shared space to exchange information between nodes of a decentralized architecture, more specifically called a tuple space [START_REF] Fernandez | Decentralized approach for execution of composite web services using the chemical paradigm[END_REF][START_REF] Martin | Tuplespace middleware for petri net-based workflow execution[END_REF]. The notion of a tuplespace is a piece of memory shared by all interacting parties. Using tuplespace for coordination, the execution of a (part of a) workflow within each node is triggered when tuples, matching the tem-plates registered by the respective nodes, are present in the tuplespace. Thus, the templates a component uses to consume tuples, together with the tuples it produces, represent its coordination logic. In [START_REF] Martin | Tuplespace middleware for petri net-based workflow execution[END_REF] approach to replace a centralized BPEL engine by a set of distributed, loosely coupled, cooperating nodes, is presented. This approach presents a coordination mechanism where the data is managed using a tuplespace and the control is driven by asynchronous messages exchanged between nodes. This message exchange pattern for the control is derived from a Petri Net model of the workflow. In [START_REF] Martin | Tuplespace middleware for petri net-based workflow execution[END_REF], the workflow definition is transformed into a set of activities, that are distributed by passing tokens in the Petri Net. In [START_REF] Fernandez | Decentralized approach for execution of composite web services using the chemical paradigm[END_REF] an alternative approach is presented, based on the chemical analogy. Molecules (data) are floating in a chemical solution, and react according to reaction rules (program) to produce new molecules (resulting data). The proposed architecture is composed by nodes communicating through a shared space containing both control and data flows, called the multiset. Through a shared multiset, containing the information on both data and control dependencies needed for coordination, chemical WSs are co-responsible for carrying out the execution of a workflow in the CWS in which they appear. Their coordination is decentralized and distributed among individual WS chemical engine executing a part of the workflow. As this approach, in our approach the coordination mechanism stores both control and data information independent of its implementation (distributed or shared memory). However, none of these works manage failures during the execution.

Facing our approach against all these works, we overcome them because the execution control is distributed and independent of the implementation (it can be implemented in distributed or shared memory platforms), it efficiently executes TCWSs by invoking parallel WSs according the execution order specified by the CPN, and it is totally transparent to users and WS developers, i.e., user only provides its TCWS, that could be automatically generated by the composition process [START_REF] Cardinale | CPN-TWS: A colored petri-net approach for transactional-qos driven web service composition[END_REF] and no instrumentation/modification/specification is needed for WSs participating in the TCWS; while most of these works are based on WS-BPEL and/or some control is sitting closely to WSs and have to be managed by programmers.

There exist some recent works related to compensation mechanism of CWSs based on Petri-Net formalism [START_REF] Mei | A compensation paired net-based refinement method for web services composition[END_REF][START_REF] Rabbi | Compensable workflow nets, Formal Methods and Software Engineering -12[END_REF][START_REF] Wang | A paired-net based compensation mechanism for verifying Web composition transactions[END_REF]. The compensation process is represented by Paired Petri-Nets demanding that all component WSs have to be compensatable. Our approach considers other transactional properties (e.g., pr, cr, ar) that also allows forward recovery and the compensation Petri-Net can model only the part of the TCWS that is compensable. Besides, in those works, the Petri-Nets are manually generated and need to be verified, while in our approach they are automatically generated. implementation of WS providers, and is transparent to users and developers. To support failures, FaCETa implements forward recovery by replacing the faulty WS and backward recovery based on a unrolling process over a CPN representing the compensation flow. We have presented a distributed memory implementation of FaCETa in order to compare the behavior of both recovery techniques. The results show that FaCETa efficiently implements fault tolerant strategies for the execution of TCWSs with small overhead.

We are currently working on implementing FaCETa in a distributed shared memory platform in order to test the performance of the framework in centralized and decentralized platforms. Our intention is to compare both implementations under different scenarios (different characterizations of CPNs) and measure the impact of compensation and substitution on QoS.

Fig. 1 .

 1 Fig. 1. Example of Backward Recovery

Fig. 3 .

 3 Fig. 3. FaCETa Architecture

Fig. 4 .

 4 Fig. 4. Implementation of FaCETa.

Fig. 5 .

 5 Fig. 5. Executions on the unreliable environments

  CPN-T CW S Q and BRCPN-T CW S Q .

	Recovery Process: unrolling a Colored Petri-Net
	The global T P of CPN-T CW S Q ensures that if a component WS, whose T P
	does not allow forward recovery fails, then all previous executed WSs can be
	compensated by a backward recovery process. For modeling TCWS backward
	recovery, we have defined a backward recovery CPN, called BRCPN-T CW S Q ,
	associated to a CPN-T CW S Q [9]. The component WSs of BRCPN-T CW S Q are
	the compensation WSs, s , corresponding to all c and cr WSs in CPN-T CW S Q .
	The BRCPN-T CW S Q represents the compensation flow, which is the inverse of
	the execution order flow. In BRCPN-T CW S Q a color of a transition s represents
	the execution state of its associated transition s in the CPN-T CW S Q and is
	updated during CPN-T CW S Q execution. Color(s ) ∈ {I='initial', R='running', E='executed', C='compesated', A='Abandonned'}thus, if color(s )='E' means
	that its corresponding WS s is being executed. In [7, 9] we propose techniques
	to automatically generate both CPNs,

Table 1 .

 1 Table 4 shows the average overhead under all different scenarios. Average overhead incurred by FaCETa

		Average Overhead (ms) % overhead increased
	No Fault	611.7
	Compensation	622.38	2%
	Substitution	612.82	0.2%
	Retry	612.01	0.05%

This work was supported by the Franco-Venezuelan CNRS-FONACIT project N • 22782

A marked CPN is a CPN having tokens in its places, where tokens represent that the values of attributes (inputs or outputs) have been provided by the user or produced by a WS execution.

Conclusions and Future WorkIn this paper we have presented FaCETa, a framework for ensuring correct and fault tolerant execution order of TCWSs. The execution model is distributed, can be implemented in distributed or share memory systems, is independent of


Luca Roatta
email: lucaroa@gmail.com

Discretization of space and time: determining the values of minimum length and minimum time

Assuming that space and time can only have discrete values, we obtain the expression of the minimum length and the minimum time interval. These values are found to be exactly coincident with the Planck's length and the Planck's time but for the presence of h instead of ħ .

Introduction

Let's assume, as work hypothesis, the existence of both discrete space and discrete time, namely spatial and temporal intervals not further divisible; this assumption leads to some interesting consequences. Here we find that the values of the minimum length and of the minimum time interval are (almost) coincident with the Planck's length and the Planck's time. The only difference is that in Planck's units appears the term ħ, while in this discrete context appears h.

So, if we suppose that neither space nor time are continuous, but that instead both are discrete, and following the terminology used in a previous document [START_REF] Roatta | Discretization of space and time in wave mechanics: the validity limit[END_REF] , we call l 0 the fundamental length and t 0 the fundamental time.

Obtaining the values of l 0 and t 0

If we insert, in the graph of the figure here below, all bodies arranging them according to their mass and their radius (assuming that they are spherical), we would have a distribution rather varying because in general there is not a precise relation between the mass of a body and its size: different bodies can have very different densities so they can be distributed very widely in the below figure. However, there are bodies for which this relation is known: they are the black holes, whose relation between radius and mass, obtained in a previous document [START_REF] Roatta | Discretization of space and time: a slight modification to the Newtonian gravitation which implies the existence of black holes[END_REF] , is shown here:

d= GM c 2 ( 1
)
where d is the radius of the black hole of mass M. Let's insert Eq. ( 1) in the figure here below: it must be said that the actual inclination of the line has been greatly increased for representative reasons, because it is so small that the line itself would be visually indistinguishable from the axis of abscissas. Fig. 2 The ray, that indicates the line on which are located the black holes depending on their mass, splits the quadrant into two zones. The top section contains the bodies (almost all, given the actual inclination of the line) whose size is greater than the size of the black hole of equal mass.

The lower section is empty because we have already found [START_REF] Roatta | Discretization of space and time: a slight modification to the Newtonian gravitation which implies the existence of black holes[END_REF] that the black hole is the most compact object for a given mass: so no object can have radius shorter than the radius of the black hole, and no object can be represented below the line.

There is another length related to the mass m of a body: the Compton wavelength, already met in a previous document [START_REF] Roatta | Discretization of space and time in wave mechanics: the validity limit[END_REF] :

λ c = h mc (2)
If we trace this function on the same graph, we get the figure here below: also in this case, for clarity, the correct proportions have not been respected. Fig. 3 The function that describes the Compton wavelength intersects the line identifying the radius of the black hole at a precise point; but, as explained above, in the area below the ray can not exist objects of any kind; then the point of intersection of the two functions is both the upper limit for the mass to which can be associated the Compton wavelength, and the lower limit for the wavelength itself.

It has already been obtained [START_REF] Roatta | Discretization of space and time in wave mechanics: the validity limit[END_REF] that in the equation of the Compton wavelength there is a maximum value for the mass an object can have:

m max = h l 0 c (3)
At this mass corresponds the minimum wavelength, that is the minimum length l 0 . But also for a black hole it has been already obtained [START_REF] Roatta | Discretization of space and time in wave mechanics: consequences of modified gravitational law[END_REF] that there is a lower limit for the mass:

m min = l 0 c 2 G ( 4
)
At this mass corresponds the minimum radius for a black hole, that is again the minimum length l 0 .

Of course it means that the minimum mass for a black hole and the maximum mass that can be associated to a wavelength are equal.

In the figure below is represented this situation. 3) and Eq. ( 4) we have:

h l 0 c = l 0 c 2 G (5)
from which we obtain:

l 0 = √ hG c 3 (6)
that coincides with the Planck's length exactly but for the presence of h instead of ħ.

Substituting the values of h, G, c, we have l 0 ~4.0•10 -35 m. This is a very little value.

We have already obtained [START_REF] Roatta | Discretization of space and time in wave mechanics: the validity limit[END_REF] that t 0 =l 0 /c, so we have also

t 0 = √ hG c 5 (7)
that coincides with the Planck's time exactly but for the presence of h instead of ħ.

Substituting the values of h, G, c, we have t 0 ~1.3•10 -43 s. Also this is a very little value.

At this point we can also obtain the value of m max , equal to the value of m min ; for coherence of notation we denote it by m 0 . It is:

m 0 = √ hc G (8)
that coincides with the Planck's mass exactly but for the presence of h instead of ħ.

Substituting the values of h, G, c, we have m 0 ~5.0•10 -8 kg. This, instead, is not a very little value. This is not the first time (see for instance this document [START_REF] Lake | The Compton-Schwarzschild correspondence from extended de Broglie relations[END_REF] ) that the Compton wavelength and the black hole radius are equalized to obtain the Planck's length, but I think that this theory follows a more natural approach.

So, m 0 is the lower limit for the mass of a black hole: this discrete theory prohibits the existence of black holes with smaller mass. We have already seen [START_REF] Roatta | Discretization of space and time in wave mechanics: consequences of modified gravitational law[END_REF] that m 0 is the validity limit for General Relativity. But m 0 is also the maximum value of the mass of a body to which can be associated a wavelength: this discrete theory states that this is the upper validity limit of wave and quantum mechanics.

The fact that these two limits coincide implies that, in a discrete context, quantum physics and General Relativity operate in different domains, without any possibility of intersection: where we can apply the one, the other can not be applied; and vice versa. This theory of discrete not only justifies the difficulties that are met trying to reconcile quantum mechanics and General Relativity, but, by establishing the same insuperable limit for both, states that it is not at all possible.

Conclusion

Assuming that space and time can only have discrete values, we obtained the values of l 0 , t 0 and m 0 that coincide with the correspondent Planck's units but for the presence of h instead of ħ. We have also shown that quantum mechanics and General Relativity operate in completely separated domains.

Fig. 1

 1 Fig. 1

Fig. 4

 4 Fig. 4Being m max = m min , from Eq. (3) and Eq. (4) we have:h l 0 c = l 0 c


Aline Bonami
email: aline.bonami@univ-orleans.fr

Abderrazek Karoui
email: abderrazek.karoui@fsb.rnu.tn

Random Discretization of the Finite Fourier Transform and Related Kernel Random Matrices

The finite Fourier transform operator, and in particular its singular values, have been extensively studied in relation with band-limited functions. We study here the sequence of singular values of a random discretization of the finite Fourier transform in relation with applications to wireless communication. We prove that, with high probability, this sequence is close to the sequence of singular values of the finite Fourier transform itself. This also leads us to develop 2 estimates for the spectrum of kernel random matrices. This seems to be new to our knowledge. As applications, we give fairly good approximations of the number of degrees of freedom and the capacity of an approximate model of a MIMO wireless communication network. We provide the reader with some numerical examples that illustrate the theoretical results of this paper.

Introduction

In this work, we are interested in the study of the behaviour of the spectrum of the n × n random matrix A, whose j, k entry is given by

a j,k = √ m n exp(2iπmZ j Y k ),
where m is a positive number, 1 ≤ m ≤ n and where the Y j , Z k are independent random variables, following the uniform law on I = (-1/2, +1/2). Note that this matrix depends on a variable ω varying in some probability space Ω but we systematically omit this variable in the expressions. Also, the matrix A may be seen as a random discretization of the finite Fourier transform F m , which is defined on L 2 (I) by

F m (f )(y) = √ m +1/2 -1/2 exp(2iπmyz)f (z)dz, |y| < 1/2.
With the normalization constant √ m n given in the coefficients a j,k , the Hilbert-Schmidt norm of A is equal to the Hilbert-Schmidt norm of F m . Recall that the Hilbert-Schmidt norm of A is given by

A 2 HS = n j,k=1 |a j,k | 2 .
The random matrix n √ m A was proposed by Desgroseilliers, Lévêque and Preissmann [START_REF] Desgroseilliers | Spatial degrees of freedom of MIMO systems in line-of-sight environment[END_REF][START_REF] Desgroseilliers | Partially random matrices in line-of-sight wireless networks[END_REF] as an approximate model for the channel fading matrix (after some renormalization) in a wireless communication MIMO (Multi Input Multi Output) transmission network. This model is done under the assumptions that one has a line of sight propagation and that network nodes are gathered in clusters. They do not add any noise for simplification of the model and studied two main related issues: the first issue is the number of degrees of freedom of the system, the second one is its information capacity. They have partial results and we refer to their papers for the interested reader. We found that the previous issues led us to some interesting mathematical questions, which we discuss in the present paper. As in the previous two references, m and n are assumed to be large, with m n. As far as the network capacity is concerned, a reasonable expression for it, with p the total power of the transmitters that is assumed to be equally distributed, is given by

C(p) = log det I n + np m A * A . (1)
Here I n is the identity matrix. We show that, with a large probability and under assumptions on m, n and p, this capacity is well approximated by m log( np m ). We also prove that the number of degrees of freedom is well approximated by m. We only need to assume that m and n/m are large enough, which is much less restrictive than the previous results in this direction obtained in [START_REF] Desgroseilliers | Spatial degrees of freedom of MIMO systems in line-of-sight environment[END_REF][START_REF] Desgroseilliers | Partially random matrices in line-of-sight wireless networks[END_REF]. Succeeding in this approximation has been the guiding thread of this study.

The whole paper is based on a comparison of the singular values of A with those of the integral operator F m . More precisely, we have the following result, Theorem 1. The singular values of A are close to the singular values of F m . More precisely, for any ξ > 0, we have

  n-1 j=0 |λ j (A * A) -λ j (F * m F m )| 2   1/2 ≤ (2ξ + √ 2)m √ n . (2)
with probability 1 -4e 2 e -ξ 2 /2 .

Here the sequence of the singular values λ j (T ) = (λ j (T * T )) 1/2 , are taken in decreasing order, starting from j = 0. The notation is used for singular values (arranged in the decreasing order) of a Hilbert-Schmidt operator with finite or infinite rank. We recall that for a Hermitian positive semi-definite operator, the singular values are eigenvalues of this later. Note that we also estimate the expectation of the left hand side of [START_REF] Bonami | Spectral Decay of Time and Frequency Limiting Operator[END_REF].

Remark that for small values of m, one could use a Taylor approximation based technique to derive such estimate, see for instance [START_REF] Karoui | The spectrum of kernel random matrices[END_REF]. But, in this work, we are interested in the spectrum of A * A when m and n are large. We will see that m/n small will allow to consider the right hand side of (2) as a rest, so that the spectrum of A * A can be well approximated by the spectrum of the corresponding integral operator F * m F m . The behaviour of this last operator, known as the Sinc kernel operator, has been largely explored in the literature, see for example [START_REF] Bonami | Spectral Decay of Time and Frequency Limiting Operator[END_REF][START_REF] Landau | On the density of Phase-Space Expansions[END_REF][START_REF] Landau | Prolate spheroidal wave functions, Fourier analysis and uncertainty-III. The dimension of space of essentially time-and band-limited signals[END_REF][START_REF] Slepian | Prolate spheroidal wave functions, Fourier analysis and uncertainty-IV: Extensions to many dimensions; generalized prolate spheroidal functions[END_REF]. This gives us precise information on singular values of A. As predicted by our theoretical results, we check numerically that the singular values of A, and F m have some similarity when m/n is small. The similarity increases when m 2 /n is small. Also, by using some precise behaviour and decay estimates of the sequence of the eigenvalues of the Sinc kernel operator, we give fairly good estimates of the number of degrees of freedom and the capacity of the wireless network studied in [START_REF] Desgroseilliers | Spatial degrees of freedom of MIMO systems in line-of-sight environment[END_REF][START_REF] Desgroseilliers | Partially random matrices in line-of-sight wireless networks[END_REF].

Our strategy in proving the previous estimate (2) is simple and essentially based on the use of a generalized version of McDiarmid's inequality. By taking the expectation of the matrix A * A in the Z-random variables, we find the matrix

H = H κm = 1 n      κ m (Y 1 , Y 1 ) κ m (Y 1 , Y 2 ) • • • κ m (Y 1 , Y n ) κ m (Y 2 , Y 1 ) κ m (Y 2 , Y 2 ) • • • κ m (Y 2 -Y n ) . . . . . . . . . . . . κ m (Y n , Y 1 ) κ m (Y n , Y 2 ) • • • κ m (Y n , Y n )      , (3)
where κ m (x, y) is the positive definite Sinc kernel, given by

κ m (x, y) = sinc(m(x -y)) = sin mπ(x -y) π(x -y) . (4)
The previous random matrix is a special case of a more general (kernel) Gram matrix H κ , with entries 1 n κ(Y j , Y k ), where the Y j are sample points drawn randomly according to a probability law P on some input space X and κ(•, •) is a kernel function on X ×X . More precisely, the random variables Y j form an are i.i.d sequence and the kernel κ is symmetric positive semi-definite. Note that we state a large part of our results in this general case. We give a last definition before describing them. Let T κ be the integral operator with kernel κ and defined on L 2 (X , P ), by

T κ (f )(x) = X κ(x, y)f (y) dP, x ∈ X . (5)
It is well-known [START_REF] Shawe-Taylor | Kernel Methods for Pattern Analysis[END_REF], that with large probability, the eigenvalues λ j (H κ ) are comparable with their expectation E(λ j (H κ )). These expectations are themselves comparable with the eigenvalues of the integral operator T κ , associated with the kernel, see [START_REF] Shawe-Taylor | Kernel Methods for Pattern Analysis[END_REF][START_REF] Blanchard | Statistical properties of Kernel Prinicipal Component Analysis[END_REF]. Here, we prove a stronger result by having an inequality in the 2 norms. If we assume that R = sup y κ(y, y) is finite, then we prove the following result, Theorem 2. Let κ be a positive semi-definite kernel, T κ the integral operator and H κ the random kernel matrix as above. We assume that R = sup y κ(y, y) is finite. Then, for any ξ > 0, we have the inequality

n-1 j=0 |λ j (H κ ) -λ j (T κ )| 2 1/2 ≤ (ξ + √ 2)R √ n ,
with probability 1 -2e 2 e -ξ 2 /2 .

Such an inequality has been given in [START_REF] Shawe-Taylor | Kernel Methods for Pattern Analysis[END_REF] for each eigenvalue separately and up to some slightly better constants. The following theorem is central in this work.

Theorem 3. Assume that R = sup y κ(y, y) is finite. Then, under the previous notations, we have

E   n-1 j=0 |λ j (H κ ) -λ j (T κ )| 2   ≤ 2R 2 n . (6)
This seems to be new, even if it is inspired from the work of V. Koltchinskii and E. Giné [START_REF] Koltchinskii | Random matrix approximation of spectra of integral operators[END_REF], who have given estimates of this kind.

Let us make a last remark. In kernel principal component analysis (Kernel-PCA), the subspace spanned by the first m eigenvectors of H κ is used to form a lower m dimensional representation of the given data. For more information on this widely used application, the reader is refereed for example to [START_REF] Blanchard | Statistical properties of Kernel Prinicipal Component Analysis[END_REF] and [START_REF] Shawe-Taylor | Kernel Methods for Pattern Analysis[END_REF]. Such a representation makes also sense for the matrix A and we give estimates for the reconstruction error in the appendix. This work is organized as follows. In section 2, we first give two concentration inequalities for functions of an i.i.d sequence of n random variables with values in a Hilbert space H. Then, we prove some general approximation results in the 2 -norm of the eigenvalues of a random kernel matrix by the eigenvalues of the associated kernel integral operator. Then, we restrict ourselves to the special interesting case of the random Fourier matrix A. In particular, we prove that the spectrum of A * A can be well approximated by the spectrum of the corresponding integral operator F * m F m . In section 3, we use some precise decay and estimate of the eigenvalues of the Sinc kernel operator and give estimates of the number of degrees of freedom and the capacity, associated with the random matrix A. In section 4, we give some numerical examples that illustrate the different results of this work. Finally, in the appendix, we give the proof of Theorem 3, which is a central result of this work. Also, we give some further inequalities relating the singular values of the random discrete finite Fourier and the finite Fourier transform operators.

We will write P, P Z (resp. P Y ) depending whether we take the probability on the whole probability space, or only in

Z 1 , • • • , Z n (resp. Y 1 , • • • , Y n ).
2 Concentration inequalities and approximation of the eigenvalues of kernel random matrices.

We first recall the Hilbert valued version of McDiarmid's concentration inequality, given by the following proposition, which is due to T. Hayes. As it will be seen later on, this inequality plays a central role in our estimates of the eigenvalues of kernel random matrices.

Proposition 1 ([5]

). Let Φ be a measurable function on R n with values in a real Hilbert space H. Assume that

Φ(z 1 , • • • , z , • • • , z n ) -Φ(z 1 , • • • , z , • • • , z n ) H ≤ R for each sequence (z j ) j = , z , z . If Z 1 , • • • Z n are independent
random variables, then we have

P ( Φ(Z 1 , • • • , Z n ) -EΦ(Z 1 , • • • , Z n ) H > ξ) ≤ 2e 2 exp - 2ξ 2 nR 2 .
This is McDiarmid's Inequality when H = R. The previous general McDiarmid's inequality is a direct consequence of the Azuma-Hoeffding inequality for Hilbert-valued random variables given in [START_REF] Hayes | A large-deviation inequality for vector-valued martingales[END_REF]. The proof of this last one is very intricate. We will also be interested in expectations. The proof of the next lemma is standard. It is an easy generalization of the way to deduce McDiarmid's inequality from Azuma-Hoeffding inequality in the scalar case.

Lemma 1. Under the same assumptions as in Proposition 1, we have the inequality

E Φ(Z 1 , • • • , Z n ) -EΦ(Z 1 , • • • , Z n ) 2 H ≤ nR 2 .
Proof. We give it for completeness. We write

Φ(Z 1 , • • • , Z n ) -EΦ(Z 1 , • • • , Z n ) = n k=1 (EΦ(Z 1 , • • • , Z n |F k ) -EΦ(Z 1 , • • • , Z n |F k-1 ) = n k=1 V k with F k the σ-algebra generated by Z 1 , • • • , Z k when k ≥ 1 and F 0 the σ-algebra generated by the constants, so that E(V |F 0 ) = E(V ). For each k > 1, the random variable is F k -measurable and we have the equality E(V k |F k-1 ) = 0. As a consequence, if j < k, then E( V j , V k H ) = E( V j , E(V k |F k-1 ) = 0.
Consequently, we have

E Φ(Z 1 , • • • , Z n ) -EΦ(Z 1 , • • • , Z n ) 2 H = n j=1 V j 2 H .
We then use the fact that V j is obtained as a mean of differences of values of Φ that involve only the j-th coordinate. So each term V j

2

H is bounded by R 2 . This concludes the proof.

The following lemma will be used to study the general eigenvalues approximation of kernel random matrices. Lemma 2. Let X be the input space and Y 1 , • • • , Y n i.i.d with values in X . Let P be their common probability law on X . Let T κ be the integral operator with kernel κ and defined on L 2 (X , P ). Then

E( H κ 2 HS ) = 1 n X κ(x, x) 2 dP + n -1 n T κ 2 HS .
Proof. The proof is straightforward, it suffices to note that

E( H κ 2 HS ) = E 1 n 2 n i=1 (κ(Y i , Y i )) 2 + E   1 n 2 n i,j=1,i =j (κ(Y i , Y j )) 2   = 1 n 2 n i=1 X κ(x, x) 2 dP + 1 n 2 n i,j=1,i =j X ×X (κ(x, y)) 2 dP dP = 1 n X κ(x, x) 2 dP + n 2 -n n 2 T κ 2 HS
Let H κ be the random matrix that we defined in the introduction, namely, the matrix with entries κ(Y j , Y k ). We know, by [START_REF] Shawe-Taylor | Kernel Methods for Pattern Analysis[END_REF] that its eigenvalues λ j (H κ ) are comparable with their expectation E(λ j (H κ )). We prove more by comparing the sum of squares of the differences. Proposition 2. Let κ be a positive semi-definite kernel and let H κ be the corresponding random kernel matrix as in Theorem 2. We assume that R = sup y κ(y, y) is finite. For any ξ > 0, we have the inequality

  n-1 j=0 |λ j (H κ ) -E(λ j (H κ )| 2   1/2 ≤ ξR √ n with probability 1 -2e 2 e -ξ 2 /2 .
Proof. We use Proposition 1 for the mapping (

x 1 , • • • , x n ) → λ(x 1 , • • • , x n ), which maps x = (x 1 , • • • , x n ) ∈ R n into
the ordered spectrum of the matrix with entries 1 n κ(x j , x k ). The Hilbert space used here is 2 n , the space of finite sequences of length n endowed with the Euclidean scalar product. We have to prove that λ(x) -λ(x ) 2 ≤ 2R n when all coordinates of x, x are identical except one of them. It is sufficient to prove that λ(x) -λ(x) 2 n ≤ R n where λ(x) is the ordered sequence of eigenvalues of the matrix H κ , obtained from H κ by substituting the coefficients of j-th row and the j-th column of H κ with zeros. Note that λn-1 (x) = 0 and from the Cauchy eigenvalues interlacing property, we have

λ i (x) ≥ λ i (x) ≥ λ i+1 (x), ∀ 1 ≤ i ≤ n -1.
Hence, by using the previous inequality, together with the trace of a square matrix, one gets

λ(x) -λ(x) 1 n = j (λ j (x) -λj (x)) = 1 n κ(x j , x j ) ≤ R n .
Since the 2 n -norm is bounded by the 1 n -norm, one gets

λ(x) -λ(x) 2 n ≤ R n ,
which we wanted to prove.

One may be interested to compare our results with those of [START_REF] Blanchard | Statistical properties of Kernel Prinicipal Component Analysis[END_REF][START_REF] Shawe-Taylor | Kernel Methods for Pattern Analysis[END_REF], which concern separately each eigenvalue and not the norm of the spectrum in 2 n . It may look surprising that the inequalities that we get from our estimates by just bounding one term by the 2 n are the same as theirs, except for the factor e 2 in the probability. This means that if we are interested in having simultaneously estimates for |λ j (H κ ) -E(λ j (H κ )| ≤ ξR √ n for k different indices j, the bound for the probability given in the previous proposition is better than the one given in [START_REF] Shawe-Taylor | Kernel Methods for Pattern Analysis[END_REF] as soon as n ≥ 8.

End of the proofs of Theorems 3 and 2. The proof of Theorem 3, which is more elaborate, is postponed to the appendix. Proposition 2 and Theorem 3 imply Theorem 2.

Remark that in general there is no reason that the error, which is of order R/ √ n, be small compared to the Hilbert-Schmidt norm of T κ or H κ . But we will see that it is the case for the Sinc kernel.

In the sequel of this section, we are interested in the behaviour of the spectra of the random matrices A * A and H = H κm . The input space is I = (-1/2, +1/2) and the law P is the uniform law on I. We claim that H is the expectation in Z of A * A. Indeed, when considering the (j, k) entry of A * A, we get

E Z m n 2 n =1 exp(2iπmZ (Y k -Y j )) = 1 n E Z m exp(2iπmZ 1 (Y k -Y j )) = 1 n κ m (Y k -Y j ).
Consequently, we have

E Z (A * A) = H. (7)
As it is classical, we note Q m the operator T κm , which is defined on L 2 (I) by

Q m (f )(x) = I sin(mπ(x -y)) π(x -y) f (y) dy. (8)
There is a huge literature on this operator, or more frequently, on the operator Q c with kernel

sin(c(x-y)) π(x-y)
on the interval (-1, +1). A simple dilation allows to pass from one operator to the other, and one has the equality

λ j (Q m ) = λ j ( Q c ) for m = 2c π .
It is well known (see [START_REF] Hogan | Duration and Bandwidth Limiting: Prolate Functions, Sampling, and Applications, Applied and Numerical Harmonic Analysis Series[END_REF], Chapter 1) that for m > 1, we have

m -O(log m) ≤ Q m 2 HS ≤ m. (9)
This implies that Q m HS ∼ √ m for m tending to ∞. The same is valid for H HS when m and n/m tend to ∞. Under these assumptions the error terms, which are multiples of m √ n , tend to ∞ more slowly than √ m. We recall some other elementary properties of the spectrum of Q m . All the eigenvalues of Q m are bounded by 1 and

Trace(Q m ) = ∞ j=0 λ j (Q m ) = m.
Using (9), we deduce that

j≥0 λ j (Q m )(1 -λ j (Q m )) ≤ C 0 log m, (10)
for some constant C 0 independent of m.

Next, we show that the eigenvalues of the random matrix B = A * A are well approximated by the corresponding eigenvalues of the matrix H. For this purpose, it suffices to check that the matrices B and H have comparable Hilbert-Schmidt norms.

Lemma 3. For H as before, depending on Z 1 , • • • , Z n , we have the inequalities

E Z ( A * A -H 2 HS ) 1/2 ≤ m √ n . (11)
Moreover, for all ξ > 0, we have

P Z A * A -H HS > ξ m √ n ≤ 2e 2 e -ξ 2 2 . ( 12
)
Proof. Consider the real Hilbert space H of n × n Hermitian matrices equipped with the real inner product B 1 , B 2 = Trace(B * 2 B 1 ). Note that the norm associated with this inner product is simply given by the Hilbert-Schmidt norm

• HS , that is for M = [m ij ] ∈ H, we have Trace(M * M ) = M 2 HS .
Let the function Φ : R n → H, defined by Φ(z 1 , . . . , z n ) =

j,k = m n 2 exp(2iπm z k (Y k -Y j )). (13)
Hence, we have Φ(z 1 , . . . , z j , . . . , z n ) -Φ(z 1 , . . . , ẑj , . . . , z n

) HS = B(z j ) -B(ẑ j ) HS ≤ 2m n 2 n 2 -n < 2m n = R.
Consequently, by using Proposition 1 and (7), one gets [START_REF] Özgür | Spatial Degrees of Freedom of Large Distributed MIMO Systems and Wireless Ad Hoc Networks[END_REF]. Let us give a direct proof of (11) instead of using Lemma 1, which would give the same result but with a constant 2 in the right hand side. We just remark that

E Z ( A * A -H 2 HS ) = nE Z ( B(Z 1 ) -E(B(Z 1 ) 2 HS ) ≤ nE Z ( B(Z 1 )) 2 HS ) = m 2 n .
The result given by ( 12) is equivalent to the fact that, with probability larger than 1 -2e 2 e -ξ 2 /2 , we have the inequality

A * A -H HS ≤ ξm √ n . ( 14
)
By Hoffman-Wielandt inequality, this implies that

  n-1 j=0 |λ j (A * A) -λ j (H)| 2   1/2 ≤ A * A -H HS ≤ ξm √ n , (15)
with probability larger than 1-2e 2 e -ξ 2 /2 . This inequality makes sense when H HS is large compared to the error term ξm n 1/2 . This is the case when n/m is large enough.

End of the proof of Theorem 1. Theorem 2 and (15) imply Theorem 1.

As a consequence of Theorem 3, (11) and Hoffman-Wielandt inequality, we have also the following proposition.

Proposition 3. The following inequality holds.

  E n-1 j=0 |λ j (A * A) -λ j (F * m F m )| 2   1/2 ≤ (1 + √ 2) m √ n .
3 Degrees of Freedom and Capacity, associated with the random Fourier matrix

In this section, we describe what the previous concentration inequalities imply for the spectra of A * A and H. In particular, we give estimates of the number of degrees of freedom and the capacity associated with the random Sinc kernel matrix H and the matrix A. For this purpose, we first give the decay behaviour of the spectrum of the integral operator Q m .

Decay of the spectra

It is well known that all the eigenvalues of Q m are smaller than 1. Roughly speaking, they are very close to 1 for j ≤ m -c log m and very close to 0 for j > m + c log m, for some constant c. The region in between is called the plunge region. The most complete answer of this behaviour, is an asymptotic formula for m tending to ∞, which has been given by Landau and Widom (see [START_REF] Hogan | Duration and Bandwidth Limiting: Prolate Functions, Sampling, and Applications, Applied and Numerical Harmonic Analysis Series[END_REF]). More precisely, for 0 < α < 1, let

N Qm (α) = #{λ j (Q m ); λ j (Q m ) > α},
then we have

N Qm (α) = m + 1 π 2 log 1 -α α log(m) + o(log(m)). (16)
For the random Sinc kernel matrix H, let N H (α) be as defined by [START_REF] Shawe-Taylor | Kernel Methods for Pattern Analysis[END_REF]. Also, we will frequently use the following constant

γ ξ = ξ + √ 2, ξ > 0. ( 17
)
We know that with a probability larger than 1-2e 2 e -ξ 2 /2 , we have the inequality

|λ j (H)-λ j (Q m )| ≤ γ ξ m √
n , for each j ≥ 0 (for instance, if we exclude an event of probability 1%, then ξ = 4 + 2 log(200), so that γ ξ = √ 2 + 4 + 2 log(200) ≈ 5.) Using the elementary inequality

N m α + γ ξ m √ n ≤ N H (α) ≤ N m α - γ ξ m √ n ,
we have with probability larger than 1

-2e 2 e -ξ 2 /2 , N H (α) = m + 1 π 2 log 1 -α α log(m) + o(log(m)) + O γ ξ m √ n log m, (18)
for

2γ ξ m √ n < α < 1 - 2γ ξ m √
n . This means that Landau-Widom Formula is also an approximate for H with high probability for m 2 /n tending to 0. The same is valid for A * A, with the two following modifications: "high probability" means now that the probability is larger than 1 -4e 2 e -ξ 2 /2 , and γ ξ is substituted with γ 2ξ = √ 2 + 2ξ. We will also make use of Landau's double inequality [START_REF] Landau | On the density of Phase-Space Expansions[END_REF],

λ m (Q m ) ≤ 1/2 ≤ λ [m]-1 (Q m ). ( 19
)
Here, [x] and x refers the to integer part and the least integer greater than or equal to x, respectively. The previous inequalities say that, roughly speaking, λ j ((Q m )) goes through the value 1/2 at m. An approximate result is valid for H and A * A when m 2 n is small. Landau-Widom Theorem gives us an approximate asymptotic decay of the eigenvalues in the plunge region after m, that is

λ k (Q m ) ≈ exp - π 2 (k -m) log m .
One does not know any non asymptotic comparable result. The following result is to the best of our knowledge, the first non asymptotic exponential decay estimate of the λ n (Q m ). It is a consequence of the estimates given in [START_REF] Bonami | Spectral Decay of Time and Frequency Limiting Operator[END_REF]. This kind of statement, with estimates of constants is developed in a separate paper [START_REF] Bonami | Non-Asymptotic decay rate and behaviour of the spectrum of the finite Fourier transform and related integral operators[END_REF].

Theorem 4. There exists a uniform constant η such that, for m > 1 and k ≥ m + log m + 10, one has the inequality

λ k (Q m ) ≤ 1 2 exp -η k -m log m . (20)
A better decay, namely a super-exponential decay rate, is obtained after the plunge region (see [START_REF] Bonami | Spectral Decay of Time and Frequency Limiting Operator[END_REF][START_REF] Bonami | Non-Asymptotic decay rate and behaviour of the spectrum of the finite Fourier transform and related integral operators[END_REF]), but we will not use it here.

Degrees of Freedom

In this paragraph, we are interested in the number of degrees of freedom of a matrix or an operator, which makes sense in the area of wireless communication networks. Different definitions have been given in this context in [START_REF] Somaraju | Degrees of freedom of a communication channel: using DOF singular values[END_REF]. We give here a simple definition in terms of eigenvalues. Similar definitions may be found in approximation theory or in computational complexity theory, where it is known as a complexity number. We aim here to show that it is easily approximated for the integral operator Q m . Consequently, this provides us with a good approximation for the corresponding random matrices H and A * A. Definition 1. Let T be a Hilbert-Schmidt positive semi-definite Hermitian operator. We define the numbers of degree of freedom at level ε by

deg ∞ (T, ε) = min{s; λ s (T ) ≤ ε}. ( 21
)
Depending on the application in view, it makes sense to be interested in small values of ε, or values that are close to the largest eigenvalue of the integral operator, that is close to 1 when considering Q m . Remark that the difference of deg ∞ (Q m , 1/2) with m is bounded by 1 by Landau's double inequality. For other values of ε we have the following proposition. Proposition 4. Let m ≥ 2 be a positive real number. For ε < 1/2, the number of degrees of freedom satisfies the inequalities

m -1 ≤ deg ∞ (Q m , ε) ≤ m + O(ε -1 log m). ( 22
)
For 1/2 < ε < 1, these inequalities are replaced by

m -O((1 -ε) -1 log m) ≤ deg ∞ (Q m , ε) ≤ m + 1. ( 23
)
Proof. The left hand side of the first inequality, as well as the right hand side of the second one, follow from Landau's double inequality (19). Moreover, by using ( 10) and ( 19), we obtain the two inequalities

j≤m-1 (1 -λ j (Q m )) ≤ 2C 0 log m (24) j≥m+1 λ j (Q m ) ≤ 2C 0 log m. ( 25
)
As a consequence of (24), we have the inequality

#{j ≤ m -1 , λ j (Q m ) < ε} ≤ 2C 0 log m 1 -ε .
The left hand side of ( 23) follows at once. The remaining inequality, that is, the right hand side of ( 22), follows from a similar argument, with (25) used in place of (24).

Remark 1. In the inequality (22), it is possible to replace ε -1 by log(ε -1 ). This follows from the decay of eigenvalues given in (20).

Let us now consider the degrees of freedom of the random matrices H and A * A, which we define as follows.

Definition 2. Let M be a positive semi-definite random Hermitian matrix. We define the numbers of degree of freedom at level ε and confidence level α by

deg ∞ (M, ε, α) = min{s; λ s (T ) ≤ ε with probability ≥ α}. (26)
The next lemma allows to prove that with high probability that the degrees of freedom of the random matrices H and A * A are close to the ones of Q m . Lemma 4. Let T 1 , T 2 be two self-adjoint Hilbert-Schmidt operators on the same Hilbert space H, and let

0 < ε 1 < ε 2 . Then deg ∞ (T 2 , ε 2 ) ≤ deg ∞ (T 1 , ε 1 ) + j≥0 (λ j (T 1 ) -λ j (T 2 )) 2 (ε 1 -ε 2 ) 2 . Proof. It is sufficient to write that #{j > deg ∞ (T 1 , ε 1 ) , λ j (T 2 ) > ε 2 } ≤ #{j > deg ∞ (T 1 , ε 1 ) , λ j (T 2 ) -λ j (T 1 ) > ε 2 -ε 1 } ≤ j≥0 (λ j (T 1 ) -λ j (T 2 )) 2 (ε 1 -ε 2 ) 2 .
We deduce from the two previous statements the following property.

Proposition 5. For ε > 0, 0 < δ = 1 -α < 1, we have deg ∞ (H, ε, α) = m + E H , deg ∞ (A * A, ε, α) = m + E A , with |E H |, |E A | ≤ C ε m n log(δ -1 ) + log m .
Here, C ε is a constant depending only on ε.

The errors are small for m large and n/m large. Asymptotically, when these two quantities tend to ∞, we have deg ∞ (H, ε, δ) ∼ m and deg ∞ (A * A, ε, δ) ∼ m for fixed ε and δ.

Capacity of a random matrix

We proceed as we have done for the degrees of freedom. Let us define, for m ≥ 2 and s > 0, the capacity associated with the Sinc kernel integral operator

Q m , C Qm (s) = k≥0 log(1 + sλ k (Q m ).
We claim the following. Proposition 6. For any m ≥ 2 and any s > 0, we have

C Qm (s) = m log(1 + s) + O((log m)(log(1 + s))).
The implicit constant in O is independent of s and m.

Proof. Let us first assume that s ≤ 2. We cut the sum into three parts and write

C Qm (s) = [m] log(1 + s) + k<[m] log 1 + sλ k (Q m ) 1 + s + k≥[m] log(1 + sλ k (Q m )).
The last term is bounded by 2 k≥[m] λ k (Q m ), which is O(log m) because of (24). In the second term, all the λ k (Q m ) are bounded below by 1/2. Since for 0 ≤ x ≤ 1/2, we have log(1 -x) ≥ -2x, then one gets

log 1 + sλ k (Q m ) 1 + s = log 1 - s 1 + s (1 -λ k (Q m )) ≥ -2(1 -λ k (Q m )). But k<[m] (1 -λ k (Q m ) = [m] -m + k≥[m] λ k (Q m )
and we conclude as before. Next, for s ≥ 2, the proof follows the same lines. Let us consider separately the bounds below and above. For the bound above, we cut the sum at [m s ], where m s is given by

m s = m + max(10, m + 1 η log s) log m. ( 27
)
Here η is the uniform constant given in (20). With this choice, we have

k>ms λ k (Q m )) ≤ C s log m.
When we write

C Qm (s) ≤ [m s ] log(1 + s)) + k>ms log(1 + sλ k (Q m )),
the bound above follows at once. For the bound below, we write

C Qm (s) ≥ [m] log(1 + s) + k<[m] log 1 + sλ k (Q m ) 1 + s ,
and conclude as in the case when s ≤ 2.

We now pass from Q m to A * A.

Proposition 7. There exist three constants C 1 , C 2 , C 3 such that, for all values of m ≥ 1, n and p, we have the following approximation for the expectation of the capacity defined in (1),

E(C(p)) = m log 1 + np m + E, (28)
with

-m -C 1 m 2 n + C 2 log m log 1 + np m ≤ E ≤ m + C 3 log m log 1 + np m .
In particular, when m and n/m tend to ∞,

E(C(p)) ∼ m log 1 + np m .
Proof. Let us first prove the bound above. We cut the sum at m s as before. We conclude for the last term by using the fact that the expectation of the sum j≥k E(λ j (A * A)) is bounded by the corresponding sum for Q m , that is j≥k λ j (Q m ). This is the inequality (36), which is proved in the appendix. For the first sum, we can bound each term by log(1 + np m ) as soon as λ k (A * A) is bounded by 1. For the summation of the terms for which λ k (A * A)) > 1, we have to add

n-1 k=0 (λ k (A * A) -1) + ,
which is bounded by

n-1 k=0 (λ k (A * A)) = m.
The same bound holds for the expectation. This concludes the proof for the bound above.

For the bound below, we can use the concavity of the logarithm. It is sufficient to give a bound below for

k≤m-C1 m 2 n -C2 log m log(1 + np m E(λ k (A * A))).
We claim that we can choose C 1 and C 2 so that E(λ

k (A * A))) ≥ 1/2 for k ≤ m -C 1 m 2 n -C 2 log m. Indeed, #{k < m, |1 -E(λ k (A * A))| ≥ 1/2} ≤ 4 k<m (1 -E(λ k (A * A))) 2 ≤ 8 k<m (1 -λ k (Q m )) 2 + 8 k<m (λ k (Q m ) -E(λ k (A * A))) 2 .
The first sum is O(log m) by ( 24). The second one is bounded by 4m 2 /n by Proposition 3. From now on, C 1 andC 2 are chosen so that

E(λ k (A * A))) ≥ 1/2 for k ≤ m -C 1 m 2 n -C 2 log m. Finally, the difference (m -C 1 m 2 n -C 2 log m) log 1 + np m - k≤m-C1 m 2 n -C2 log m log 1 + np m E(λ k (A * A))
is bounded as before by 2 k<m-C1 m 2 n -C2 log m (1 -E(λ k (A * A)) + , which is bounded by m. We conclude at once. The previous proposition deals with expectation. It is easy to deduce estimates with high probability. Indeed, it suffices to use Mc Diarmid's inequality for the mapping defined by the capacity. This is done in [START_REF] Özgür | Spatial Degrees of Freedom of Large Distributed MIMO Systems and Wireless Ad Hoc Networks[END_REF]. From the computations made in [START_REF] Özgür | Spatial Degrees of Freedom of Large Distributed MIMO Systems and Wireless Ad Hoc Networks[END_REF], it follows that, for ξ > 0 and with probability larger than 1 -2e -ξ 2 /2 , we have

|C(p) -E(C(p))| ≤ ξ log(1 + np) √ n .
Probability value lower bound of n m 99% 90 95% 75 90% 70 85% 65 80% 60

Table 1: Lower bound of n m so that the error given by ( 2) is smaller than √ m, with a given probability.

This gives an error that is very small compared to the estimates that we have given for E.

Remark 2. In [START_REF] Desgroseilliers | Spatial degrees of freedom of MIMO systems in line-of-sight environment[END_REF], the authors have stated that there exists a constant K > 0 such that

C(n) = log det I n + n 2 m A * A ≤ Kn log(n), (29)
with high probability as n gets large and m ≥ √ n. Bounds below have been obtained in [START_REF] Özgür | Spatial Degrees of Freedom of Large Distributed MIMO Systems and Wireless Ad Hoc Networks[END_REF]. The previous proposition generalizes these results, with much more precise estimates.

Numerical examples

Let us first discuss the order of magnitude of the errors given in the different theorems if we want them to be valid with high probability. For example, the eigenvalues approximation result given by Theorem 1 is valid with probability 99%, whenever ξ = 2 √ 1 + log 20 ≈ 4. In this case, the right hand side of the inequality (2) is smaller than √ m for n/m ≥ 90. The following table gives more values for the condition on the ratios n/m, for different probabilities values.

The simulations below are done with a sample of size 2n of the uniform law on (-1/2, +1/2) in place of the Z j 's and the Y k 's for different values of n.

Example 1: In this first example, we illustrate the results of Proposition 3 and Theorem 1. For this purpose, we have computed the spectra of the random matrices A * A and H with n = 200 and different values of 2 ≤ m ≤ 20. Since for each value of m, there is approximately m significant eigenvalues, then we have computed the approximation relative 2 -errors, given by 1 2 . Also, we have computed the magnitude of the corresponding theoretical relative error, given by the quantity m n . The obtained numerical results are given by Table 2.

√ m λ(A * A) - λ(H) 2 , 1 √ m λ(H)-λ(Q m ) 2 and 1 √ m λ(A * A)-λ(Q m )
Example 2: In this example, we have considered the random matrix H, with n = 200 and different values of the bandwidth 2 ≤ m ≤ 20. In Figure 1 (a), we have plotted the eigenvalues (λ j (A * A)) 0≤j≤35 of the random matrix A * A, arranged in the decreasing order, versus the eigenvalues of Q m . Then, we have repeated the previous numerical tests with the random matrix H instead of the matrix A * A. The obtained numerical results are given by Figure 1(b). Note that as predicted by proposition 5, the matrices A * A and H, each has m significant eigenvalues. Also in order to check the decay of the eigenvalues of the random matrices A * A and H. we have plotted in Figures 2 (a) and 2(b), the graphs of log(λ j (A * A)) and log(λ j (H)). Note that as predicted by

n = 200 λ(A * A)-λ(H) 2 √ m λ(H)-λ(Qm) 2 √ m λ(A * A)-λ(Qm) 2 √ m m n m =

Appendices

Appendix A: Proof of Theorem 3.

We will prove the following theorem, which is stronger and in the spirit of the estimates developed in [START_REF] Koltchinskii | Random matrix approximation of spectra of integral operators[END_REF].

M * M v i , v i ,
where the supremum is taken over all orthonormal system of d -1 vectors. We are interested in R d (A). Let v * i be the system for which the maximum is obtained when A * A is replaced by H. Clearly max

d i=1 A * Av i , v i ≥ max d i=1 A * Av * i , v * i .
By taking the expectation on both sides, we obtain the inequality

E Z j<d λ j (A * A) ≥ j<d λ j (H). ( 34
)
The inequality

E j<d λ j (H) ≥ j<d λ j (Q m ) (35)
can be found in [START_REF] Shawe-Taylor | On the Eigenspectrum of the Gram Matrix and the Generalized Error of Kernel-PCA[END_REF]. Its proof follows from the same kind of arguments. As a consequence, we have the inequality

E j≥d λ j (A * A) ≤ j≥d λ j (Q m ). (36)
The same authors also use the Bounded Difference inequality to write that, with probability larger than 1 -2e -ξ 2 /2 , we have

j<d λ j (H) -E j<d λ j (H) | ≤ ξm √ n . ( 37
)
We remark that the trace norm can be used as well as the Hilbert-Schmidt norm in the proof of (3), which allows to use the Bounded Difference Inequality for j<d λ j (A * A) and the probability P Z .

With probability larger than 1 -2e -ξ 2 /2 , we have the inequality

j<d λ j (A * A) -E Z j<d λ j (A * A) ≤ ξm √ n . (38)
Finally, with probability larger than 1 -4e -ξ 2 /2 , we have the inequality

j<d λ j (A) 2 ≥ j<d λ j (Q m ) - 2ξm √ n , (39)
and, as a consequence,

R d (A) = j≥d λ j (A) 2 ≤ j<d λ j (Q m ) + 2ξm √ n . ( 40
)
The same kind of techniques as in [START_REF] Shawe-Taylor | On the Eigenspectrum of the Gram Matrix and the Generalized Error of Kernel-PCA[END_REF] can be used to have a reverse inequality.

Acknowledgements. The authors thank Marguerite Zani for useful comments.

  k ), where the coefficients of the matrix B(z k ) are given by b

Figure 1 :Example 3 :

 13 Figure 1: (a) Graphs of λ(A * A) (circles) versus λ(Q m ) (boxes) with n = 200 and for the various values of m = 2, 4, 6, 10, 20, (from the left to the right), (b) same as (a) with λ(H) instead of λ(A * A).

Figure 2 :Table 3 :

 23 Figure 2: (a) Graphs of log(λ j (A * A)) with n = 200 and for the various values of m = 2, 4, 6, 10, 20, (from the left to the right), (b) same as (a) with log(λ j (H)) instead of log(λ j (A * A)).

Table 2 :

 2 Illustrations of the results of Theorem 1 and Proposition 3.

	2	24.3%	08.6%	20.7%	10.0%
	m = 4	17.4%	08.1%	17.5%	14.1%
	m = 6	14.0%	10.7%	15.0%	17.3%
	m = 10	10.0%	13.4%	14.6%	22.4%
	m = 20	14.5%	29.4%	17.6%	31.6%

This work was supported in part by the French-Tunisian CMCU project 10G 1504 project and the Tunisian DGRST research grants UR 13ES47.

Theorem 5. Let κ be a positive semi-definite kernel as in Theorem 2, T κ be the integral operator with kernel κ, and H κ be the associated random kernel matrix . Then, we have

Proof. The left hand side may be written as

We use Lemma 2 for the first term, and find that the sum of the two first terms is bounded by the right hand side of (32). So it is sufficient to prove that

We use an Abel transformation and see that this sum is equal to

All terms are non negative in this sum: terms λ j (T κ ) -λ j+1 (T κ ) are non negative since the sequence of eigenvalues is non increasing. It is well-known that terms [START_REF] Blanchard | Statistical properties of Kernel Prinicipal Component Analysis[END_REF][START_REF] Shawe-Taylor | Kernel Methods for Pattern Analysis[END_REF]).

To conclude for the proof of Theorem 3, it is sufficient to see that X κ(x, x) 2 dP is bounded by R 2 , and to prove the inequality

But since j≥0 λ j (T κ ) ≤ R and the sequence λ j (T κ ) is decreasing, we have λ j (T κ ) ≤ R n for j ≥ n. Remark 3. Depending on the decay of the sequence λ j (T κ ), the left hand side of (33) may be very small compared to R 2 n . In particular, in our example, we have exponential decay for n > m + log m + 10. So this is rapidly negligible and one may replace the constant 2 by 1 in (6), up to a negligible constant.

Appendix B: Further inequalities for the eigenvalues and reconstruction error.

We first recall that the reconstruction error, when approximating an n × n matrix by its projections P V M P V on subspaces V of dimension d, is defined as

where the minimum is taken over all subspaces V of dimension d. This notion is central in [START_REF] Shawe-Taylor | On the Eigenspectrum of the Gram Matrix and the Generalized Error of Kernel-PCA[END_REF]. It is well-known that the minimum is obtained when V is generated by the first d eigenvectors of M * M, so that R d (M ) = j≥d λ j (M * M ).