Guangshuo Chen
email: guangshuo.chen@inria.fr

Aline Carneiro

Marco Fiore
email: marco.fiore@ieiit.cnr.it

Takeaways in Large-scale Human Mobility Data Mining (Invited Paper)

Employing mobile devices to perform data analytics is a typical fog computing application that utilizes the intelligence at the edge of networks. Such an application relies on the knowledge of the mobility of mobile devices and their users, e.g., to deploy computation tasks efficiently at the edge. This paper surveys the literature on the mobility-related utilization of operator-collected CDR (charging data records) -the most significant proxy of large-scale human mobility studies. We provide an innovative introductory guide to the CDR data preliminary. It reveals original issues regarding CDR-based mobility feature computation and applications at the edge. Our survey plays an important role in utilizing mobile devices in terms of both human mobility investigation and fog computing.

I. INTRODUCTION

The proliferation of mobile devices at the edge of cellular networks brings the possibility of collecting large-scale human behavioral data [START_REF] Garcia Lopez | Edge-centric computing: Vision and challenges[END_REF]. In the past decade, mobile devices have become the most popular data source for investigating human behavior or related issues [START_REF] Naboulsi | Largescale mobile traffic analysis: A survey[END_REF], such as social relationship [START_REF] Wang | Human mobility, social ties, and link prediction[END_REF], network traffic [START_REF] Chen | The spatiotemporal interplay of regularity and randomness in cellular data traffic[END_REF], and human mobility [START_REF] Song | Limits of predictability in human mobility[END_REF][START_REF] Mucelli | On the regularity of human mobility[END_REF].

Meanwhile, recent advances in mobile devices and mobile operating systems make it possible to employ mobile devices as data processing nodes rather than human behavior sensors. Applying distributed data analytics at the edge of cellular networks allows conducting data gathering and processing more efficiently and securely [START_REF] Garcia Lopez | Edge-centric computing: Vision and challenges[END_REF], which alleviates heavy computation or storage pressure and resolves data privacy concerns as in centralized data processing [START_REF] Barik | Foggis: Fog computing for geospatial big data analytics[END_REF][START_REF] Dubey | Fog data: Enhancing telehealth big data through fog computing[END_REF].

To this end, it is essential to understand the behavior of mobile users in the network, particularly their mobility, to conduct intelligent utilization of network resources at the edge. The knowledge of such behavior helps to understand where mobile devices are located and consequently, where and when their resources can be leveraged. Therefore, it is necessary to study the way human behaves regarding the mobility habits, what will drive the spatiotemporal availability of mobile devices playing as both resource consumers and providers in fog computing.

Mobile devices, having their roles in fog computing, are also service consumers in cellular networks. The mobility of mobile users can be obtained and investigated by leveraging operatorcollected mobile phone records, or namely CDR (charging data records) [START_REF] Gpp | Telecommunication management; Charging management; Charging Data Record (CDR) parameter description[END_REF]. Nowadays, enriching CDR is the most common way of acquiring human behavioral data, which can cover broad areas and user groups with minimal cost [START_REF] Naboulsi | Largescale mobile traffic analysis: A survey[END_REF]. Accordingly, CDR datasets are often employed in human mobility studies, bringing large-scale populations and long observing periods [START_REF] Naboulsi | Largescale mobile traffic analysis: A survey[END_REF] as the main advantage.

This paper reviews the literature on the CDR data utilization for human mobility studies. The nature of human communications, which varies widely across users, determines the quality of CDR-based mobility data. Thus, both data preliminary and processing need to be carefully designed and implemented to adjust the diversity of mobility data. Nevertheless, the description of the data preliminary is neglected in some research works, which questions the validity of their results and conclusions. Hence in this paper, we summarize the common practices and our experience on dealing with mobility data extracted from CDR datasets. We provide the significant takeaways in terms of data preliminary, mobility feature computation, applications, and future research directions.

Our survey differs from the previous literature reviews of human mobility or network traffic analyses. They either summarize the models, applications, and techniques that are designed or employed for characterizing and utilizing human mobility as in [START_REF] Barbosa | Human mobility: Models and applications[END_REF][START_REF] Toch | Analyzing large-scale human mobility data: a survey of machine learning methods and applications[END_REF] or cover the vast literature of multiple research communities on mining mobile phone records as in [START_REF] Naboulsi | Largescale mobile traffic analysis: A survey[END_REF]. Instead of the "outcomes" that are originated from CDR or other mobility data proxies, this paper mainly focuses on how they conduct the data preliminary and processing on CDR (via concepts, methodologies, and techniques) to obtain reliable and convincible results. We believe that our discussion in this paper, summarized as the takeaways regarding CDR data mining, will be direct and valuable guidance to those who are working on mobility data.

II. COLLECTING HUMAN MOBILITY DATA

A. Telecommunication events and their CDR

The availability of mobility data is the most fundamental requirement for human mobility analyses. In the literature, CDR, generated by mobile devices and collected by cellular operators, are the primary choice among a variety of mobility data proxies (CDR, WiFi, GPS, and travel surveys). CDR describe mobile devices' telecommunication events and are usually time-stamped and geo-referenced so that they can be leveraged as a proxy of human mobility data [START_REF] Naboulsi | Largescale mobile traffic analysis: A survey[END_REF]. Moreover, as the necessary data of cellular operators for billing or network management purposes, they are collected in a substantial population at a small cost.

In the 3GPP lexicon, a series of CDR types are defined corresponding to telecommunication events such as voice calls, text messages, internet visits, mobility updates, and location requests [START_REF] Gpp | Telecommunication management; Charging management; Charging Data Record (CDR) parameter description[END_REF]. Nevertheless, not all of them contribute to research works: only voice call and text message CDR are commonly seen [START_REF] Naboulsi | Largescale mobile traffic analysis: A survey[END_REF], with a large and growing body of the literature on their corresponding events (e.g., [START_REF] Dong | How long will she call me? distribution, social theory and duration prediction[END_REF]) and the mobility data extracted from them (e.g., [START_REF] Ranjan | Are call detail records biased for sampling human mobility?[END_REF][START_REF] Ficek | Inter-call mobility model: A spatiotemporal refinement of call data records using a Gaussian mixture model[END_REF]). It is known that such mobility data has a limited spatiotemporal granularity and also suffers from a high degree of temporal heterogeneity and sparsity [START_REF] Chen | Enriching sparse mobility information in call detail records[END_REF]. Internet visit CDR appear in a few of human mobility studies. They provide better mobility data with higher spatiotemporal granularities than voice call CDR and thus are often used as the latter's ground-truth as in [START_REF] Ranjan | Are call detail records biased for sampling human mobility?[END_REF], while they are mostly collected within short observing periods [START_REF] Naboulsi | Largescale mobile traffic analysis: A survey[END_REF].

B. Real-world CDR dataset

Now we give an overview of the two most important CDR datasets employed by our mobility analyses, as an example of real-world CDR datasets.

The first one consists of voice call CDR generated by 3.6M prepaid mobile subscribers in Mexico during approximately one-year. Each voice call CDR contains the caller's and callee's hashed identifiers, the call duration, the call initial timestamp, and the location of the cell tower to which the caller's device is connected to when the call originates. We portray in Fig. 1a the heatmap of the number of users in each hour of the voice call CDR dataset. We see daily and weekly repetitive patterns of voice call behavior: there is an active period of making phone calls on each day and these active periods of each week are quite similar.

The second one consists of internet visit CDR of 0.6M of mobile devices in Shanghai while we only have the timestamps and cell tower locations because the data provider removes the other critical CDR attributes for privacy reasons. Similarly, the number of users per hour is illustrated by the heatmap in Fig. 1b. We see that there is still a daily repetitive pattern of internet visits but is less heterogeneous than voice calls, meaning that these CDR can provide more abundant mobility data with less temporal sparsity.

It is worth noting that we observe imperfectness on both heatmaps: the user numbers of certain hours are significantly less than the others. This can be explained by public holidays and data collection abnormalities. Such imperfectness is common in CDR datasets and brings the necessity to perform data preliminary, i.e., selecting appropriate populations of study, observing periods, and CDR attributes. To this end, we integrate our experience on data preliminary and summarize the common practices used in the literature, introduced next.

III. COMMON PRACTICES IN MOBILITY DATA PROCESSING

The reliability of data preliminary determines the quality of data mining and the representativeness of results obtained.

In our experience of mining our CDR datasets, we apply a multitude of data preliminary steps and study the start-ofthe-art works having detailed data preliminary description. In this section, we summarize common and effective practices in terms of data preliminary for CDR-based human mobility investigation.

• Extract location coordinates via third-party services.

Locations are usually inherent as GPS coordinates in CDR while sometimes they appears as their original form, i.e., Cell ID, and their coordinates need to be extracted manually. In this case, certain third-party services are available, including OpenCelliD1 , France OpenData2 , Google Geolocation3 , Unwired Labs4 , OpenSignal 5 and Mozilla Location Service 6 . They are usually powered by community databases and should be chosen carefully according to both their areas of study and data contributors. • Filter out "bad" users. It is common to select users of study for reliability or generality by setting corresponding thresholds. Although there is hardly a standard, a relatively common threshold for voice call CDR is to keep those who have ≥ 0.5 Call/Hr and unique locations N L ≥ 2 as in [START_REF] Song | Limits of predictability in human mobility[END_REF][START_REF] Ranjan | Are call detail records biased for sampling human mobility?[END_REF][START_REF] Gonzalez | Understanding individual human mobility patterns[END_REF], which can keep significant user locations and sufficient mobility information [START_REF] Ranjan | Are call detail records biased for sampling human mobility?[END_REF]. Note that such filters may drop a large number of users and should only be applied on mobility data having a large population.

• Reduce temporal/spatial resolutions. A fairly good setting on resolutions can reduce data quality requirement.

For temporal resolutions, depending on CDR types and data quality, 15 minutes [START_REF] Ranjan | Are call detail records biased for sampling human mobility?[END_REF], 1 hour [START_REF] Song | Limits of predictability in human mobility[END_REF][START_REF] Gonzalez | Understanding individual human mobility patterns[END_REF], and 2 hours [START_REF] De Montjoye | Unique in the crowd: The privacy bounds of human mobility[END_REF] are common. For spatial resolutions, a common practice is to merge adjacent locations via clustering methods (e.g., DBScan, Optics), as in [START_REF] Chen | Enriching sparse mobility information in call detail records[END_REF][START_REF] De Montjoye | Unique in the crowd: The privacy bounds of human mobility[END_REF]. • Segment observing periods. Due to temporal heterogeneity of human behavior, telecommunication events are not captured uniformly over time. Therefore, it is common and effective to divide the data's collecting period into segments of study, e.g., daytime and nighttime hours [START_REF] Chen | Enriching sparse mobility information in call detail records[END_REF], weekdays and weekends [START_REF] Isaacman | Identifying important places in people's lives from cellular network data[END_REF], weeks or months [START_REF] Song | Limits of predictability in human mobility[END_REF]. Despite of possible loss of long-term behavior, this practice can usually ensure more users than using the whole collecting period. • Correlate with the mobility loss. This is to build a function between results and inherent features of human footprints (e.g., the location loss rate) by leveraging groundtruth datasets. The function is then used to fix the biased result obtained by the incomplete mobility information.

For instance, Song et al. [START_REF] Song | Limits of predictability in human mobility[END_REF] find a linear correlation between the loss rate of voice calls and the logarithm of the entropy rate of time-ordered locations [START_REF] Song | Limits of predictability in human mobility[END_REF], and then employ this correlation to compute the predictability of human mobility from incomplete CDR-based mobility data.

• Perform controlled experiments. This is to repeat the methodology or the mobility feature computation on controlled datasets, e.g., in [START_REF] Song | Limits of predictability in human mobility[END_REF][START_REF] Gonzalez | Understanding individual human mobility patterns[END_REF]. The controlled dataset usually has a higher resolution than the counterpart. The conclusion is more convincible provided that the same results can be obtained from both datasets. • Fill spatiotemporal gaps. Although CDR cannot provide fully complete mobility information [START_REF] Chen | Enriching sparse mobility information in call detail records[END_REF], it is enough to conduct reliable mobility inference so as to enlarge the availability of human footprints. Although the literature on this topic is fairly thin, several solid works are proposed. Ficek et al. [START_REF] Ficek | Inter-call mobility model: A spatiotemporal refinement of call data records using a Gaussian mixture model[END_REF] propose a probabilistic intercall mobility model to determine users' positions between their consecutive voice calls. Sahar et al. [START_REF] Hoteit | Estimating human trajectories and hotspots through mobile phone data[END_REF] proposes an interpolation-based approach while it only work in the presence of trajectories composed of thousands of locations per day. For that, we also propose machine learning strategies to extend the availability of CDR having low user sampling rates [START_REF] Chen | Enriching sparse mobility information in call detail records[END_REF][START_REF] Chen | Individual Trajectory Reconstruction from Mobile Net-work Data[END_REF].

In summary, a solid data preliminary step is critical to conduct reliable human mobility analyses. To achieve such a step, the practices mentioned above need to be utilized in a comprehensive and flexible way corresponding to actual research or application scenarios.

IV. HOW INDIVIDUAL MOBILITY IS MEASURED?

After the data preliminary, the mobility of each user of the dataset is usually investigated as the next step by computing several straight-forward mobility features, to help the design and implementation of mobility-related analyses or applications. In this section, we first summarize these common mobility features of a users' locations and travels. We then discuss the issue regarding the computation of the radius of gyration.

A. How locations are visited?

In a CDR dataset, each user has a CDR-based trajectory of locations described by tens or hundreds of spatiotemporal points. It is essential to understand how the user has visited these locations. Several typical features answer this question, introduced as follows.

1) Cell coverage: Voronoi tessellations are often computed from all observed locations and are used as an estimation of the dataset's spatial resolution as in [START_REF] Song | Limits of predictability in human mobility[END_REF][START_REF] Chen | Enriching sparse mobility information in call detail records[END_REF][START_REF] De Montjoye | Unique in the crowd: The privacy bounds of human mobility[END_REF]. Actually, the locations of CDR are usually the ones of the cell towers handling telecommunication events. Mobile devices are actually in the areas covered by these cell towers. As an illustration, we plot in Fig. 2a the Voronoi tessellations of our voice call CDR dataset. We see that each Voronoi tessellation occupies an area around 2 km 2 . Besides, we show in [START_REF] Chen | Enriching sparse mobility information in call detail records[END_REF] that the location precision of using CDR dataset in metropolitan areas is around 1 km. Besides, with a large-scale dataset, such Voronoi tessellations can be leveraged to compute the population density of the area [START_REF] Naboulsi | Largescale mobile traffic analysis: A survey[END_REF].

2) Repetitiveness: It is known that each user tends to have a few frequently visited locations [START_REF] Mucelli | On the regularity of human mobility[END_REF][START_REF] Gonzalez | Understanding individual human mobility patterns[END_REF]. Therefore, it is important to understand the repetitiveness of these locations. Given a CDR-based trajectory with multiple locations, the repetitiveness on a per-user basis is computed as the number of unique locations in the trajectory and the probability of each location's appearance. We plot in Fig. 2b the overall probabilities P (L) of the most frequent 50 locations' appearance versus their appearance-based rank L in the CDR dataset. We see that only two locations are visited more than 10% of the time on average. Besides, it is observed that P (L) ∼ (L) -1 as in the other CDR datasets [START_REF] Gonzalez | Understanding individual human mobility patterns[END_REF].

3) Significant locations and categories: It is also often seen in the literature to mark those frequently visited locations with intuitive labels, e.g., extracting important locations. For that, a simple and common way is to divide the observing period into sub-periods on a daily basis and to select the most frequent locations of each sub-period, such as home (nighttime) and work (daytime), as in [START_REF] Gonzalez | Understanding individual human mobility patterns[END_REF][START_REF] Isaacman | Identifying important places in people's lives from cellular network data[END_REF][START_REF] Baumann | How long are you staying?: predicting residence time from human mobility traces[END_REF].

B. How users travel?

The features above describe the mobility of a user from the viewpoint of locations. We also need to understand how a user travels during the observing period, from the viewpoint of his entire trajectory, which are usually described by the following features.

1) Displacement: The traveled distance between each two consecutive spatiotemporal points, i.e., ∆ u , is computed to express the location displacement of a user, as in [START_REF] Gonzalez | Understanding individual human mobility patterns[END_REF]. On a per-user basis, the maximum displacement ∆ max u and the average displacement ∆ u often appears in the literature. We plot the distribution of the ∆ u metric in Fig. 2c. It shows that a majority of the users (90%) have short-range movement (≤ 10 km) between two consecutive locations.

2) Traveled distance: The total traveled distance of a user, represented as ∆ u , is computed as the sum of a user's location displacements. It shows directly the user's movement, which is usually used with the radius of gyration together. We plot in Fig. 2d the distribution of ∆ u across our users of study. We see that a large number of users have small traveled distances because of their low average location displacement and limited numbers of voice calls, while there is still a certain group of users who travel a lot. According to our experience, these users should be carefully addressed in the data preliminary.

3) Span of movement: To represent the movement of a user in a simple and quantitative manner, the radius of gyration of movement is often considered. After being originally adopted in human mobility in [START_REF] Gonzalez | Understanding individual human mobility patterns[END_REF], the radius of gyration has become popular in human mobilities studies [START_REF] Barbosa | Human mobility: Models and applications[END_REF]. It is the perpendicular distance from the point mass to the axis of rotation, originally leveraged to deal with multi-dimensional points in structural engineering or polymer physics. For human mobility investigation, the radius of gyration is computed on a per-user basis from the locations of each trajectory. However, since the locations are spatiotemporal points in this case, how to deal with their temporal factors raises a novel and unresolved issue regarding the computation of the radius of gyration, discussed next.

C. Spatiotemporal computation of radius of gyration

When computing the radius of gyration from a CDR-based trajectory, we have to deal with the situation that a location is likely to appear many times. In other words, the spatiotemporal points of a trajectory may contain a far less number of unique cell tower locations, which raise a question: how to deal with such spatial repetitiveness in the computation of the radius of gyration? Surprisingly, we find that the mobility studies that compute the radius of gyration do not mention how they address this problem except a few (e.g., [START_REF] Gonzalez | Understanding individual human mobility patterns[END_REF]). Thus, we provide a thorough discussion regarding this issue in the following.

To compute the radius of gyration of a user, the simplest way is to ignore temporal information and use only the unique locations in the trajectory. By doing this, we just consider those locations as normal points in a typical 2dimensional space. Suppose a CDR-based trajectory has N unique locations {r 1 , • • • , r N }, its corresponding radius of gyration, represented as RG unique , is computed as follows:

RG unique = 1 N N k=1 (r k -r unique cm ) 2 , r unique cm = 1 N N k=1 r k , (1)
where r unique cm is the center of mass of these unique locations. This computation avoids considering temporal dynamics of the user's movement and follows the general definition of the radius of gyration. Nevertheless, it cannot reflect the actual user's movement: the user's center of mass of r unique cm is strongly biased because those locations which the user stays a majority of the time are regarded as equal as the occasional locations in Eq. [START_REF] Garcia Lopez | Edge-centric computing: Vision and challenges[END_REF].

The second way is to use the spatiotemporal points as they are and take all the points into account even if some of them are repeated, as used and described in [START_REF] Gonzalez | Understanding individual human mobility patterns[END_REF]. It equals to use the locations' numbers of events (CDR) as their weights of importance in the radius of gyration. Suppose the cell tower locations {r 1 , • • • , r N } of the trajectory handles {m 1 , • • • , m N } events, respectively. The corresponding radius of gyration, represented as RG event , is computed as follows:

RG event = N k=1 m k • (r k -r event cm ) 2 N i=1 m i , (2)
r event cm = N k=1 m k r k N i=1 m i . ( 3
)
For voice call CDR, this computation respects the user's movement because those locations with longer dwelling time usually have more voice calls [START_REF] Ranjan | Are call detail records biased for sampling human mobility?[END_REF] and higher importance in Eq. ( 2). However, it may be biased in internet visit CDR, the number of which is determined by not only dwelling time but also internet services and applications. Therefore, we present the third and most reasonable way of computing the radius of gyration, i.e., to divide the trajectory into time slots using a fixed temporal resolution and gather the most frequent location of each time slot. It can relax the impact of bursting events but can still extract the importance from the number of events. Accordingly, if the locations

{r 1 , • • • , r N }
RG time = N k=1 s k • (r k -r time cm ) 2 N i=1 s i , (4)
where the center of mass r time cm is computed similarly as in Eq. ( 3) by replacing all m i with s i .

To evaluate this three computation metrics, we employ them to compute the actual radius of gyration of the users in our voice call and internet visit CDR datasets. As our results, we portray in Fig. 3 the distributions of RG unique , RG event , and RG time (computed with 30-minute time slots). We observe that RG unique is far larger than the other two metrics, indicating a strong bias brought by ignoring temporal factors. In the voice call CDR dataset, the distributions of RG time and RG event are quite similar, as shown in Fig. 3a. This is because the voice call CDR of a user is usually sparse in time and each 30minute time segment tends to have only one or two calls so that the weights computed from time segments and events are highly similar. A large shift between these two distributions is observed in Fig. 3b, indicating that the burst of internet visits biases the radius of gyration if we still employ RG event .

Consequently, to have a realistic measurement of the user's movement span via the radius of gyration, whether or not CDR are sparse, we should measure each trajectory using an appropriate temporal resolution and adopted the time-segmentbased metric as in Eq. (4).

F (π) π PPM (L) π MLP (L) π MLP-CI (L) π MLP-CI (L)PastV Π max u (L) (a)

V. LEVERAGING INDIVIDUAL MOBILITY AT THE EDGE

Still, the mobility of individuals needs to be leveraged by practical applications deployed at the edge of networks. This section presents our efforts on converting CDR-based mobility data into such applications by giving two typical applications that utilize the mobility of individuals as examples, i.e., mobility reconstruction and location prediction.

A. Mobility reconstruction

Voice call CDR do not have a stable sampling rate due to their heterogeneity and thus, cannot capture one's entire trajectory fully. For that, we address the mobility reconstruction problem to recover missing locations in a CDR-based trajectory, which is also valuable to those trajectories obtained from other CDR types or mobility data proxies because the risk of losing mobility information always exist. Nevertheless, the literature on this topic is relatively thin [START_REF] Chen | Enriching sparse mobility information in call detail records[END_REF].

To fill this research gap, we have designed the mobility reconstruction strategies using Gradient Boosting with decision trees [START_REF] Chen | Enriching sparse mobility information in call detail records[END_REF] and Matrix/Tensor Factorization [START_REF] Chen | Individual Trajectory Reconstruction from Mobile Net-work Data[END_REF]. We also implement the state-of-the-art interpolation method for CDRbased trajectory reconstruction [START_REF] Hoteit | Estimating human trajectories and hotspots through mobile phone data[END_REF]. Leveraging our CDR datasets, we validate these strategies via data-driven simulations, showing that they can recover the missing locations in a user's trajectory with reasonably good accuracy. More importantly, these strategies are highly applicable: (1) they only rely on every single individual's trajectory; (2) they can be implemented on recent mobile devices with AI chips having enough computation power. Therefore, we believe that the mobility reconstruction is a reasonable application scenario deployed at the edge of cellular networks.

B. Location prediction

The accurate knowledge of a user's future whereabouts is significant in mobility-related applications, e.g., optimizing energy consumption of mobile devices [START_REF] Chon | Mobility predictionbased smartphone energy optimization for everyday location monitoring[END_REF]. In our study, we consider relatively "simple" location prediction methods, to ensure that these methods can be implemented and meet the availability of computation and data storage on mobile devices. For example, simple Markov chain can achieve relatively high accuracy in predicting a user's next location [START_REF] Lu | Approaching the limit of predictability in human mobility[END_REF], and clearly, has a low cost of time and space. Recent enhanced mobile devices, such as mobile AI chip integration [START_REF] Guo | Guest editors introduction: Intelligence in the cloud[END_REF], make it possible to consider improved prediction methods. Particularly, we employ the following ones:

• PPM (Prediction by partial matching): a prediction method improved from Markov chain. It achieves better accuracy and requires less preceding samples [START_REF] Moffat | Implementing the PPM data compression scheme[END_REF]. • MLP (Multilayer perceptron): a classical machine learning method employing neuron networks [START_REF] Schmidhuber | Deep learning in neural networks: An overview[END_REF]. For the feasibility of mobile phone deployment, we employ a simple full connected (256,256,256) network as inner layers and the rectified linear unit (ReLU) as the activation function.

Named by the input context, we design three MLP-based predictors, i.e., MLP -only using preceding locations, MLP-CI -using both preceding locations and temporal (weekday, date, hour) features, and MLP-CI-PastVadding features of mobile data traffic consumption into MLP-CI.

With the help of CDR datasets, we can study the location prediction problem and enlarge the population scale to thousands of users. Notably, we perform our study on approximately 7K users with sufficient mobility data in an observing period of 150 days. For each predictor and each user, we let the predictor initialize using the locations of the first 100 days to guarantee an entire "warm up", and using it to predict the remaining locations and compute the accuracy. During the prediction, each predictor is updated every day to simulate an actual mobile phone application. Note that, in our experiment, each location is the most active cell tower location of each one-hour segment in a user's trajectory; the accuracy is the percentage of the correct predictions that attach to the right cell towers.

We evaluate the performance of our predictors and portray the CDF of the prediction accuracy across our users in Fig. 4a, π PPM , π MLP , π MLP-CI , and π MLP-CI PastV show the actual prediction accuracy of each user, and Π max u represents the theoretical performance derived via information theory. Π max u worths some additional explanation. It is computed via information theory [START_REF] Song | Limits of predictability in human mobility[END_REF] and shows the theoretical upper bound of the prediction accuracy from the spatiotemporal correlation in a user's previously seen locations. We see that the theoretical upper bound shows an 85% of the maximum expected accuracy on average while leveraging preceding locations can only achieve 73% (PPM) and 74% (MLP) of the average practical accuracy. Approximately 76% of the average practical predictability is achieved by the MLP-CI predictor which further leverages the time as the context information. The best performance is achieved by the MLP-CI predictor with the knowledge of previous data traffic volumes, which has 79% of the practical predictability.

We also plot in Fig. 4b the CDF of the accuracy enhancement of each user brought by the use of historical data traffic volumes in the prediction. We note that for the PPM and MLP predictors, only less than 50% of the users have such enhancement up to 5%, while the practical predictability of the results even describes at most 10% surprisingly. It indicates that the context information, such as time and data traffic consumption, do have the capability of achieving a better prediction of a user's locations, while only the machine learning techniques could absorb and utilize such information efficiently, nor the Markovian methods.

In summary, we find those simple prediction methods can achieve reasonably good accuracy in location prediction and can be deployed in mobile phones.

VI. CONCLUSION AND DISCUSSION

In the previous sections, we have presented the important issues in terms of data collection, data preliminary, mobility feature completion, and mobility applications. Still, because CDR datasets have appeared as an essential resource for research since only the past decade [START_REF] Naboulsi | Largescale mobile traffic analysis: A survey[END_REF], there is a multitude of remaining open problems and future research directions regarding human mobility. Some critical ones are discussed in the following.

• Is there any better mobility data source? The answer to this question depends on actual application scenarios. For instance, GPS data is usually a better choice -providing higher spatiotemporal resolutions -if a large-scale user population is not necessary. There is general agreement on the fact that no other technique can cover the same amount of users as CDR and meanwhile maintain such low cost of data gathering. In fact, CDR data is still far from its full potential as mobility data source. With increased positioning techniques and enough CDR types released, CDR can keep almost the same spatiotemporal granularity as GPS surveys but provide a higher population. Obtaining such data needs to address non-technical issues such as privacy and security, and requires cellular operators with better openness. • Can mobility reconstruction models perform better?

Inferring missing whereabouts from the mobility data captured by CDR is a useful data preliminary practice while it does not receive enough attention, as discussed in Section III. The current relevant techniques, including ours, mainly utilize the repetitive human mobility patterns. Mobile information can be extracted from CDR and may contribute to mobility reconstruction. For instance, with multiple CDR types, one can reasonably expect to have coarse-grained long-term mobility information of users and finer-grained short-term mobility information of the same users only in some partial observing periods. No existing work studies how to assess the longterm mobility reconstruction problem using such mixed information. Besides, recovering a user's trajectories may benefit from knowing similar trajectories of other users. • How to improve human mobility predicative models? Forecasting future human whereabouts is one of the most important topics of human mobility investigation [START_REF] Barbosa | Human mobility: Models and applications[END_REF][START_REF] Toch | Analyzing large-scale human mobility data: a survey of machine learning methods and applications[END_REF]. So far, relevant studies have covered a variety of techniques such as Markov chains, time series analysis, Naive Bayes, Nonparametric Bayesian inference, and even artificial neural network, considered from single-user models to aggregated models, and analyzed both theoretical and practical predictability of individual mobility. However, there is still a research direction that is nearly untouched, i.e., leveraging contextual information into mobility prediction. For instance, when working with locations, mobile network traffic (e.g., data traffic as in Section V-B) also described by CDR and can contribute to mobility prediction. We believe that more context data (e.g., points of internet, web browsing, and environment of mobile devices) have such power to be revealed and utilized. Moreover, as collecting such data requires deeper mobile device integration and collaboration, there is a vast space of possible fog computing applications.

Consequently, this paper surveyed the literature on utilizing CDR into human mobility studies, and provided the major takeaways in terms of CDR data mining along with open research directions.

Fig. 1 :

 1 Fig. 1: Heatmaps of the number of users of our (a) voice call and (b) internet visit CDR dataset.

Fig. 2 :

 2 Fig. 2: (a) Voronoi tessellations in our area of study; red dots represent cell towers. (b) Probability of appearance of the most frequent 50 locations of each user; locations are ranked by their appearance frequencies on the x-axis. (c)(d) Cumulative distributions of each user's (c) average displacement and travel distance across our users of study.

Fig. 3 :

 3 Fig. 3: CDF of the three radius of gyration across the users of (a) the voice call CDR and (b) the internet visit CDR datasets.

Fig. 4 :

 4 Fig. 4: (1) CDF of the theoretical and practical accuracy of forecasting a user's next cell tower from preceding ones. (2) CDF of the prediction accuracy enhancement by leveraging the knowledge of a user's preceding data traffic generation.

https://www.opencellid.org

https://www.data.gouv.fr/fr/datasets/

http://developers.google.com

http://unwiredlabs.com

http://opensignal.com

https://location.services.mozilla.com


Marco Caponigro
email: marco.caponigro@cnam.fr

Mario Sigalotti
email: mario.sigalotti@inria.fr

Exact controllability in projections of the bilinear Schrödinger equation

We consider the bilinear Schrödinger equation with discrete-spectrum drift. We show, for n ∈ N arbitrary, exact controllability in projections on the first n given eigenstates. The controllability result relies on a generic controllability hypothesis on some associated finite-dimensional approximations. The method is based on Lie-algebraic control techniques applied to the finite-dimensional approximations coupled with classical topological arguments issuing from degree theory.

Introduction

In this paper we study the controllability problem for the multi-input Schrödinger equation i dψ dt (t) = (H 0 + u 1 (t)H 1 + . . . + u p (t)H p )ψ(t) [START_REF] Adami | Controllability of the Schrödinger equation via intersection of eigenvalues[END_REF] where H 0 , . . . , H p are self-adjoint operators on a Hilbert space H and the drift Schrödinger operator H 0 (the internal Hamiltonian) has discrete spectrum. The control functions u 1 (•), . . . , u p (•), representing external fields, are real-valued and ψ(•) takes values in the unit sphere of H. In recent years there has been an increasing interest in studying the controllability of the bilinear Schrödinger equation [START_REF] Adami | Controllability of the Schrödinger equation via intersection of eigenvalues[END_REF], mainly due to its importance for many applications such as laser spectroscopy or quantum information. The problem concerns the design of control laws (u 1 , . . . , u p ) steering the system from a given initial state to a pre-assigned final state in a given time.

The controllability of system (1) is a well-established topic when the state space H is finitedimensional (see for instance [START_REF]Introduction to quantum control and dynamics[END_REF] and reference therein), thanks to general controllability methods for left-invariant control systems on compact Lie groups ( [START_REF] Jurdjevic | Control systems on Lie groups[END_REF][START_REF] Jurdjevic | Control systems on semisimple Lie groups and their homogeneous spaces[END_REF][START_REF] Gauthier | Controlabilité des systèmes bilinéaires[END_REF][START_REF] Assoudi | On subsemigroups of semisimple Lie groups[END_REF]).

We are interested here in the case in which H is infinite-dimensional. When the control operators H 1 , . . . , H p are bounded, it is known that the bilinear Schrödinger equation is not exactly controllable (see [START_REF] Ball | Controllability for distributed bilinear systems[END_REF][START_REF] Turinici | On the controllability of bilinear quantum systems[END_REF]). Hence, it is natural to look for weaker controllability properties such as approximate controllability or controllability between eigenstates of the Schödinger operator. In certain cases it is possible to prove exact controllability in suitable functional spaces on a real interval (see [5, 6, Definition 1. Let H be an infinite-dimensional Hilbert space with scalar product ⟨•, •⟩ and A, B 1 , . . . , B p be (possibly unbounded) skew-adjoint operators on H, with domains D(A), D(B 1 ), . . . , D(B p ). Let us introduce the controlled equation

dψ dt (t) = (A + u 1 (t)B 1 + • • • + u p (t)B p )ψ(t), u(t) ∈ U. ( 2
)
We say that A satisfies (A1) if the following assumption holds true.

(A1) A has discrete spectrum with infinitely many distinct eigenvalues (possibly degenerate).

Note that (A1) is true whenever A has compact resolvent. Denote by Φ a Hilbert basis (ϕ k ) k∈N of H made of eigenvectors of A associated with the family of eigenvalues (iλ k ) k∈N and let L be the set of finite linear combinations of eigenstates, that is,

L = ∪ k∈N span{ϕ 1 , . . . , ϕ k }.
We consider the following assumptions on the regularity of the control operators B 1 , . . . , B p : (A2) ϕ k ∈ D(B j ) for every k ∈ N, j = 1, . . . , p;

(A3) A + u 1 B 1 + • • • + u p B p : L → H is essentially skew-adjoint for every u ∈ U .
When (A, B 1 , . . . , B p , Φ, U ) satisfies (A1) -(A2) -(A3) we define the solution of (2) as follows.

Definition 2. We say that u ∈ L ∞ ([0, T ], R p ) is admissible for (2) if u(t) ∈ U for almost every t ∈ [0, T ] and, for every ψ 0 ∈ H, there exists ψ : [0, T ] → H such that ψ(0) = ψ 0 the function t → ⟨ψ(t), ϕ k ⟩ is absolutely continuous for every k ∈ N and satisfies

d dt ⟨ϕ k , ψ(t)⟩ = -⟨(A + u 1 (t)B 1 + • • • + u p (t)B p )ϕ k , ψ(t)⟩, (3)
for almost every t ∈ [0, T ]. The function t → ψ(t) is called solution of (2) with initial condition ψ 0 ∈ H associated with the control u.

Assumption (A3) implies that the norm of the solutions given by Definition 2 is constant along the evolution. In particular it guarantees the uniqueness of solutions. We can therefore define the unitary propagator of (2), denoted by Υ u t , as follows.

Definition 3. Let u : [0, T ] → U be admissible for [START_REF] Agrachev | Dynamics control by a time-varying feedback[END_REF]. The mapping [0, T ] ∋ t → Υ u t where Υ u t ψ 0 is the evaluation at time t of the solution of (2) with initial condition ψ 0 ∈ H associated with u, is called propagator of (2).

Let (A, B 1 , . . . , B p , Φ, U ) satisfy (A1) -(A2) -(A3) and let U ⊂ L ∞ ([0, ∞), U ). We say that (A, B 1 , . . . , B p , Φ, U, U) satisfies (A4) if (A4) every u ∈ U is admissible.
Assumption (A4) holds true for the class of piecewise constant controls and, under suitable regularity conditions, for the class of smooth controls as detailed in the following two remarks. Remark 1. Let (A, B 1 , . . . , B p , Φ, U ) satisfy (A1) -(A2) -(A3) and let u(•) = (u 1 (•), . . . , u p (•)) be a p-tuple of piecewise constant controls on [0, T ] with value in U . Then u is admissible for (2) and the propagator is given by

Υ u t = e (t- ∑ j-1 l=1 t l )(A+u (j) 1 B 1 +•••+u (j) p Bp) • • • • • e t 1 (A+u (1) 1 B 1 +•••+u (1) p Bp) , where ∑ j-1 l=1 t l ≤ t < ∑ j l=1 t l and u(τ ) = (u (j) 1 , . . . , u (j) p ) ∈ U if ∑ j-1 l=1 t l ≤ τ < ∑ j l=1 t l . Indeed, since ⟨ϕ n , e t(A+u 1 B 1 +•••+upBp) ψ 0 ⟩ = ⟨e -t(A+u 1 B 1 +•••+upBp) ϕ n , ψ 0 ⟩ , then t → ψ(t) = Υ u t ψ 0 satisfies (3) for almost every t ∈ [0, T ]. Remark 2. Let u ∈ C 1 ([0, T ], U ) and B 1 , . . . , B p be A-bounded with A-bound smaller than 1/δ in the sense of [32, Section X.2], i.e. • D(B j ) ⊃ D(A),
• there exists a < 1/δ and b ∈ R such that for all ϕ ∈ D(A) one has ∥B j ϕ∥ ≤ a∥Aϕ∥ + b∥ϕ∥, for every j = 1, . . . , p. Then by the Kato-Rellich theorem ([32, Theorem X.12]) and [32,

Theorem X.70] u is admissible for (2). If, moreover, ψ 0 ∈ D(A) then t → Υ u t ψ 0 satisfies (2) for every t ∈ [0, T ]. We say that (A, B 1 , . . . , B p , Φ, U, U) satisfies (A) if it satisfies (A1) -(A2) -(A3) -(A4
) and the following additional assumption.

(A5)

The input-output mapping is continuous in the sense that if (u n ) n∈N ⊂ U and u ∈ U are such that u n → u in L 1 ([0, T ]) as n → ∞ then Υ un t ϕ tends to Υ u t ϕ in H uniformly with respect to t ∈ [0, T ] as n → ∞ for every ϕ ∈ H. Remark 3. In the case in which A satisfies (A1) and B 1 , . . . , B p are bounded operators, assumptions (A2), (A3) are clearly verified. Assumption (A5) is the consequence of [START_REF] Ball | Controllability for distributed bilinear systems[END_REF]Theorem 3.6]. More general conditions on B 1 , . . . , B p ensuring that (A5) holds true can be found for instance in [START_REF] Boussaïd | Regular propagators of bilinear quantum systems[END_REF]Section 2.3].

For n ∈ N we denote by Π n the projection of H on the span of the first n eigenvectors of A, namely

Π n : H → H ψ → ∑ n k=1 ⟨ϕ k , ψ⟩ϕ k .
When it does not create ambiguities we identify Im(Π n ) = span{ϕ 1 , . . . , ϕ n } with C n . Given a linear operator Q on H we identify the linear operator π n Qπ n preserving span{ϕ 1 , . . . , ϕ n } with its n × n complex matrix representation with respect to the basis (ϕ 1 , . . . , ϕ n ). We define

A (n) = Π n AΠ n and B (n) j = Π n B j Π n ,
for every j = 1, . . . , p. Let us introduce the set Σ n of spectral gaps associated with the first n eigenvalues of A as

Σ n = {|λ l -λ k | | l, k = 1, . . . , n}.
For every σ ≥ 0, every m ∈ N, and every m × m matrix M , let

E σ (M ) = (M l,k δ σ,|λ l -λ k | ) m l,k=1 ,
where δ •,• denotes the Kronecker symbol. The n × n matrix E σ (B (n) j ), j = 1, . . . , p, corresponds then to the "selection" in B (n) j of the spectral gap σ: the (l, k)-elements such that |λ l -λ k | ̸ = σ are set to 0.

Define

Ξ n = { (σ, j) ∈ Σ n × {1, . . . , p} | (B j ) k,l δ σ,|λ l -λ k | = 0, for every k = 1, . . . , n and l > n } . ( 4
)
The set Ξ n can be seen as follows: If (σ, j) ∈ Ξ n then the matrix

M = E σ (B (n) j ) is such that E σ (B (N ) j ) = ( M 0 0 * ) for every N > n.
In particular span{ϕ 1 , . . . , ϕ n } is invariant for the evolution of E σ (B (N ) j ) for every N > n. The spectral gaps σ ∈ Ξ n are, therefore, those for which the selections E σ (B (n) j ) define finite dimensional dynamics of order n "decoupled" from the infinite dimensional evolution.

The main assumption of this paper, introduced in the definition below, is a Lie-algebraic condition on the set of the decoupled selections associated with the spectral gaps in Ξ n .

Definition 4 ([10]

). For every n ∈ N define

M n = { A (n) } ∪ { E σ (B (n) j ) | (σ, j) ∈ Ξ n and j is such that (0, j) ∈ Ξ n } ∪ { E σ (B (n) j ) | (σ, j) ∈ Ξ n , σ ̸ = 0, U j = [-δ, δ] } .
We say that the Lie-Galerkin Control Condition holds if for every n 0 ∈ N there exists n > n 0 such that LieM n ⊇ su(n).

The Lie-Galerkin Control Condition is a sufficient condition for approximate controllability as stated in Theorem 1 below. Definition 5. Let (A, B 1 , . . . , B p , Φ, U, U) satisfy (A1) -(A2) -(A3) -(A4). We say that (2) is approximately controllable by means of controls in U if for every ψ 0 , ψ 1 in the unit sphere of H and every ε > 0 there exists u ∈ U and T > 0 such that ∥ψ

1 -Υ u T (ψ 0 )∥ < ε. Theorem 1 ([10, Theorem 2.6]). Let (A, B 1 , . . . , B p , Φ, U ) satisfy (A1) -(A2) -(

A3). If the Lie-Galerkin Control Condition holds then system (2) is approximately controllable by means of piecewise constant controls.

Theorem 1 can be extended to the class of smooth controls as stated in Theorem 2 below. The proof of this result is given in Section 4.

Theorem 2. Let U be the set of C ∞ functions with values in U and (

A, B 1 , . . . , B p , Φ, U, U) satisfy (A1)-(A2)-(A3)-(

A4). If the Lie-Galerkin Control Condition holds then system (2) is approximately controllable by means of controls in U.

Our main result is the approximate controllability in projections as stated below. Theorem 2 is one of the main tools in its proof.

Theorem 3. Let U be either the set of piecewise constant functions with values in U or the set of C ∞

functions with values in U . Let (A, B 1 , . . . , B p , Φ, U, U) satisfy (A). Assume that the Lie-Galerkin Control Condition holds. Then for every n ∈ N, ε > 0, for every initial condition ψ in ∈ H with ∥ψ in ∥ = 1 and every final condition

ψ f ∈ H such that ∥ψ f ∥ = 1 and ∥Π n (ψ f )∥ < 1, there exists u : [0, T ] → U , u ∈ U such that Π n (Υ u T (ψ in )) = Π n (ψ f ) and ∥Υ u T (ψ in ) -ψ f ∥ < ε.

The Lie-Galerkin Control Condition in examples

Non-resonant chain of connectedness

An example of easily verifiable condition in the case of single-input systems which implies the Lie-Galerkin Control Condition is given by the existence of a non-resonant chain of connectedness, as we recall below. Let p = 1 and call, for simplicity,

B = B 1 . Let (A, B, Φ, U ) satisfy assumption (A1) -(A2) -(A3).

Definition 6 ([9]

). A subset S of N 2 couples two levels l, k in N, if there exists a finite sequence

( (s 1 1 , s 1 2 ), . . . , (s q 1 , s q 2 ) ) in S such that (i) s 1 1 = l and s q 2 = k; (ii) s j 2 = s j+1 1 for every 1 ≤ j ≤ q -1; (iii) ⟨ϕ s j 1 , Bϕ s j 2 ⟩ ̸ = 0 for 1 ≤ j ≤ q.
S is called a connectedness chain for (A, B, Φ, U ) if S couples every pair of levels in N.

A connectedness chain is said to be non-resonant if for every (s

1 , s 2 ) in S, |λ s 1 -λ s 2 | ̸ = |λ t 1 -λ t 2 | for every (t 1 , t 2 ) in N 2 \ {(s 1 , s 2 ), (s 2 , s 1 )} such that ⟨ϕ t 2 , Bϕ t 1 ⟩ ̸ = 0. Proposition 4. Assume that ⟨ϕ l , Bϕ k ⟩ = 0 whenever l ̸ = k and λ l = λ k . If (A, B, Φ, U )

admits a non-resonant connectedness chain then the Lie-Galerkin Control Condition holds.

Proof. The first assumption in the statement of the proposition implies that 0 ∈ Ξ n for every n. The non-resonance condition on the eigenvalues implies that, for every n, Ξ n = Σ n . Hence

M n = { A (n) } ∪ { E σ (B (n) ) | σ ∈ Σ n } . Since, moreover, E |λ l -λ k | (B (n) ) has two nonzero entries if ⟨ϕ l , Bϕ k ⟩ ̸ = 0,

Rotating bipolar molecule

Consider the control of the orientation of a rigid bipolar molecule in R 3 modeled by the following Schrödinger equation on the unit sphere S 2 :

i ∂ψ(θ, φ, t) ∂t = -∆ψ(θ, φ, t)+ + (u 1 (t) sin θ cos φ + u 2 (t) sin θ sin φ + u 3 (t) cos θ)ψ(θ, φ, t), ( 5
)
where θ, φ are the spherical coordinates, which are related to the Euclidean coordinates through the identities x = sin θ cos φ, y = sin θ sin φ, z = cos θ, while ∆ is the Laplace-Beltrami operator on the sphere S 2 (called in this context the angular momentum operator ), i.e.,

∆ = 1 sin θ ∂ ∂θ ( sin θ ∂ ∂θ ) + 1 sin 2 θ ∂ 2 ∂φ 2 .
The wavefunction ψ evolves in the unit sphere S of H = L 2 (S 2 , C). A basis of eigenvectors of the Laplace-Beltrami operator ∆ is given by the spherical harmonics

Y m ℓ (θ, φ), which satisfy ∆Y m ℓ (θ, φ) = -ℓ(ℓ + 1)Y m ℓ (θ, φ). The spectrum of A = i∆ is {-iℓ(ℓ + 1) | ℓ ∈ N}. Each eigenvalue -iℓ(ℓ + 1
) is of finite multiplicity 2ℓ+1. The control operators B 1 , B 2 , B 3 are the multiplication operators by -i cos φ sin θ, -i sin φ sin θ, -i cos θ, respectively, which are bounded.

For symmetry reasons, the system is not controllable if one the three control is constantly switched off. In particular, the argument of Proposition 4 does not apply directly.

The systems satisfies condition (A1) -(A2) -(A3). Assumptions (A4) and (A5), for piecewise constant or C 1 smooth controls, follow from Remarks 1, 2, and 3. Equation ( 5) satisfies the Lie-Galerkin Control Condition as proved in [10, Lemma 3.2].

Quantum harmonic oscillator

The quantum harmonic oscillator is among the most important examples of quantum systems. Consider its controlled version (see, for instance, [START_REF] Mirrahimi | Controllability of quantum harmonic oscillators[END_REF]), in which H = L 2 (R, C) and the equation ( 2)

reads i ∂ψ ∂t (x, t) = 1 2 (-∆ + x 2 )ψ(x, t) + u(t)xψ(x, t). A Hilbert basis of H made of eigenvectors of A = -i 2 (-∆ + x 2
) is given by the Hermite functions (ϕ n ) n∈N , associated with the sequence (-iλ n ) n∈N of eigenvalues, where

λ n = n -1/2. In the basis (ϕ n ) n∈N , B 1 = B = -ix is tri-diagonal since ⟨ϕ j , Bϕ k ⟩ =      i √ k -1 if j = k -1, i √ k if j = k + 1, 0 otherwise.
This system is known to be non-controllable, neither exactly nor approximately as proved in [START_REF] Mirrahimi | Controllability of quantum harmonic oscillators[END_REF], while its Galerkin approximations of every order are [START_REF] Schirmer | Complete controllability of quantum systems[END_REF].

In this example, for every n, Σ n = {0, 1, 2, . . . , n}, Ξ n = Σ n \ {1} and E σ (B (n) ) is the zero matrix for every σ ∈ Ξ n . Hence the Lie-Galerkin Control Condition is not satisfied.

Strategy of the proof

The strategy of the proof of Theorem 3 splits into two main arguments. The first argument is used to formalize the decoupling which we mentioned as the intuition behind the definition of the set M n . More precisely, for every n ∈ N, we show that there exists a family W n of n × n matrices having the same Lie algebra as M n , which defines a control system in C n whose trajectories can be approximated arbitrarily well by the projection Π n of trajectories of (2). The second argument goes as follows: if n is such that the Lie algebra generated by W n (or, equivalently, by M n ) is su(n), then for every point of the unit sphere of C n there exists a control law at which the endpoint map of the control system defined by W n is a submersion. Then, by structural stability of submersions, it is possible to deduce exact controllability in projection of [START_REF] Agrachev | Dynamics control by a time-varying feedback[END_REF].

The first of the two arguments mentioned above spans Sections 3 and 4 and allows, in particular, to provide a proof of Theorem 2. It consists in three steps: an averaging result used to compare (up to phases) the flow of a matrix of W n with a trajectory of (2) corresponding to a control in resonance with one of the frequencies in Ξ n (see Lemma 6), a construction allowing to concatenate the averaging arbitrarily many times (see Proposition 8), and a concluding phase tuning step (see Lemma 9).

Finite-dimensional approximations of infinite-dimensional propagators

In this section we introduce an auxiliary control system whose solutions are, up to phases, trajectories of (2), as showed in Lemma 5 below.

For t, u 1 , . . . , u p ∈ R set Θ(t, u) = Θ(t, u 1 , . . . , u p ) = e -tA (u 1 B 1 + • • • + u p B p )e tA , which is a linear operator from L to H. Note that Θ(t, u 1 , . . . , u p ) jk = ⟨ϕ k , Θ(t, u 1 , . . . , u p )ϕ j ⟩ = e i(λ k -λ j )t (u 1 (B 1 ) jk + • • • + u p (B p ) jk ) .
Consider the nonautonomous control system ẏ(t) = Θ(t, u 1 (t), . . . , u p (t))y(t).

(

) 6
Admissible solutions of [START_REF] Beauchard | Local controllability of 1D linear and nonlinear Schrödinger equations with bilinear control[END_REF]

))⟩ = iλ n e itλn ⟨ϕ n , Υ u t (y(0))⟩ -e itλn ⟨(A + u 1 (t)B 1 + • • • + u p (t)B p )ϕ n , Υ u t (y(0))⟩ = -e itλn ⟨(u 1 (t)B 1 + • • • + u p (t)B p )ϕ n
such that ∫ T 0 v N (t)dt = ν 0 , ∫ T 0 v N (t)e iσt dt = ν 1 , ( 8
)
and

∫ T 0 v N (t)e imσt dt = 0, for every m ≥ 2 such that mσ ∈ Σ N . ( 9
)
Assume that one of the following three conditions is satisfied: (i) (σ, j) and (0, j) are in Ξ n ; (ii) (σ, j) ∈ Ξ n and ν 0 = 0; (iii) (0, j) ∈ Ξ n and ν 1 = 0. Assume, moreover, that ω N /K is admissible for every N ∈ N and every K ∈ N large enough. Then

lim N →∞ lim K→∞ ∥Υ τ ω N /K KT -e KT A exp(τ (ν 0 E 0 (B (n) j ) + ν 1 E σ (B (n) j )))∥ L(Πn(H),H) = 0,
uniformly with respect to τ ∈ [a, b], where exp(τ (ν 0 E 0 (B

(n) j ) + ν 1 E σ (B (n) j ))) : C n → C n is

identified with an operator on H.

Proof. Step 1. Fix, for now, N > n and consider the Galerkin approximation of order N of system (6), namely the system associated with Θ (N ) (t, u) = Π N Θ(t, u)Π N . Then, for every s ≤ t and τ ∈ [a, b],

-→ exp ∫ Kt Ks Θ (N ) ( r, τ ω N (r) K ) dr = -→ exp ∫ t s Θ (N ) (Kr, τ ω N (Kr)) dr = -→ exp ∫ t s e -rKA (N ) τ v N (Kr)B (N ) j e rKA (N ) dr, ( 10
)
where the notation

-→
exp is used to denote the chronological exponent, see [START_REF] Agrachev | Control theory from the geometric viewpoint[END_REF]. We claim that

∫ t s e -rKA (N ) v N (Kr)B (N ) j e rKA (N ) dr → t -s T ( ν 0 E 0 (B (N ) j ) + ν 1 E σ (B (N ) j ) ) (11)
as K → ∞, uniformly with respect to s, t ∈ [0, T ]. Indeed, this follows from ( 9) and the fact that for every

σ ′ ∈ R \ σZ 1 K ∫ Kt Ks v N (r)e iσ ′ r dr → 0
as K → ∞, as it can be seen by developing v N in Fourier series.

Hence by [START_REF] Boscain | Multi-input Schrödinger equation: Controllability, tracking, and application to the quantum angular momentum[END_REF], [START_REF] Boscain | Adiabatic control of the Schroedinger equation via conical intersections of the eigenvalues[END_REF], and averaging arguments (see, for instance, [3, Lemma 8.2]) we deduce that

-→ exp ∫ Kt Ks Θ (N ) ( r, τ ω N (r) K ) dr → exp ( (t -s)τ T ( ν 0 E 0 (B (N ) j ) + ν 1 E σ (B (N ) j )
) )

as K → ∞, uniformly with respect to s, t ∈ [0, T ] and τ ∈ [a, b].

Step 2. Let

y(t) = e -tA Υ τ ω N /K t (ψ),
for ψ ∈ Π n (H). By Lemma 5, y(t) is a solution of [START_REF] Beauchard | Local controllability of 1D linear and nonlinear Schrödinger equations with bilinear control[END_REF]. By variation of constants formula and since Π N Θ(s, u)(I -Π N ) is an operator uniformly bounded with respect to s ∈ R and u ∈ U , we deduce from (7) that

Π n y(t) = Π n -→ exp ∫ t 0 Θ (N ) ( s, τ ω N (s) K ) ds (ψ) + Π n ∫ t 0 ( -→ exp ∫ t s Θ (N ) ( r, τ ω N (r) K ) dr ) Π N Θ ( s, τ ω N (s) K ) (I -Π N )y(s)ds.
We are left to prove that lim

N →∞ lim K→∞ Π n e -KT A Υ τ ω N /K KT Π n = exp(ν 0 E 0 (B (n) j ) + ν 1 E σ (B (n) j )) uni- formly with respect to τ ∈ [a, b].
Indeed, by unitarity of the evolution of ( 6), this also implies that lim

N →∞ lim K→∞ (I -Π n )e -KT A Υ τ ω N /K KT Π n = 0, uniformly with respect to τ ∈ [a, b].
By [START_REF] Boussaïd | Regular propagators of bilinear quantum systems[END_REF], for every N > n we have that lim

K→∞ Π n -→ exp ∫ KT 0 Θ (N ) ( s, τ ω N (s) K ) ds Π n = exp(τ (ν 0 E 0 (B (n) j ) + ν 1 E σ (B (n) j ))),
uniformly with respect to τ ∈ [a, b]. Hence, we are left to prove that for every ε > 0 and every N large enough one has lim sup

K→∞ ∥Π n ∫ KT 0 ( -→ exp ∫ KT s Θ (N ) ( r, τ ω N (r) K ) dr ) Π N Θ ( s, τ ω N (s) K ) (I-Π N )e -sA Υ τ ω N /K s dsΠ n ∥ < ε, uniformly with respect to τ ∈ [a, b]. Notice that ∫ KT 0 ( -→ exp ∫ KT s Θ (N ) ( r, τ ω N (r) K ) dr ) Π N Θ ( s, τ ω N (s) K ) (I -Π N )e -sA Υ τ ω N /K s ds = ∫ T 0 ( -→ exp ∫ KT Ks Θ (N ) ( r, τ ω N (r) K ) dr ) Π N Θ ( Ks, τ ω N (Ks) ) (I -Π N )e -KsA Υ τ ω N /K Ks ds.
We are going to prove, therefore, that for every ε > 0 and every N large enough lim sup

K→∞ ∥Π n ( -→ exp ∫ KT Ks Θ (N ) ( r, τ ω N (r) K ) dr ) Π N Θ ( Ks, τ ω N (Ks) ) (I -Π N )∥ < ε, uniformly with respect to s ∈ [0, T ] and τ ∈ [a, b]. We have that Π n ( -→ exp ∫ KT Ks Θ (N ) ( r, τ ω N (r) K ) dr ) Π N Θ ( Ks, τ ω N (Ks) ) (I -Π N ) = Π n ( -→ exp ∫ KT Ks Θ (N ) ( r, τ ω N (r) K ) dr ) Π n Θ ( Ks, τ ω N (Ks) ) (I -Π N ) + Π n ( -→ exp ∫ KT Ks Θ (N ) ( r, τ ω N (r) K ) dr ) (Π N -Π n )Θ ( Ks, τ ω N (Ks) ) (I -Π N ). ( 13
)
Fix N large enough so that ∥Π n Θ (s, u) (I -Π N )∥ < ε T for every s ∈ R and u ∈ U . Concerning the term in [START_REF] Chambrion | Periodic excitations of bilinear quantum systems[END_REF], by assumption (A2) one has that

(Π N -Π n )Θ (s, u) (I -Π N )
is a bounded operator on H, uniformly with respect to s ∈ R and u ∈ U .

Notice that by the assumptions on σ, j, ν 0 , and

ν 1 it holds Π n ( ν 0 E 0 (B (N ) j ) + ν 1 E σ (B (N ) j ) ) (Π N -Π n ) = 0.
Hence, by [START_REF] Boussaïd | Regular propagators of bilinear quantum systems[END_REF],

Π n ( -→ exp ∫ KT Ks Θ (N ) ( r, τ ω N (r) K ) dr ) (Π N -Π n ) tends to 0 as K → ∞

Efficiency of admissible controls

Let us discuss the values of ν 0 and ν 1 which can be obtained with a control satisfying the hypothesis of Lemma 6. We distinguish two cases depending on the nature of the control set U j .

If U j = [-δ, δ] then for every ν 0 , ν 1 ∈ R a simple example of periodic function, independent of N , satisfying (8) and ( 9) is given by

v(t) = σ 2π (ν 0 + 2ν 1 cos(σt)) . ( 14
)
Indeed by orthogonality of trigonometric functions one has that ∫ T 0 v(t)e imσt dt = 0 for every integer m ≥ 2 (in particular for every m ≥ 2 such that mσ ∈ Σ N ).

In the case in which U j = [0, δ] the restriction on the sign of v N represents an additional requirement. If ν 0 = 0 then v N = 0. Otherwise, up to replacing v N by v N /ν 0 , one can assume that ν 0 = 1. In this case, following [13, Section 2.4] we call |ν 1 | the efficiency of the control v N . Notice, for instance, that the efficiency of the functions σ 2π (1 ± cos(σt)) is 1/2. Hence, by convexity, one can choose a v N , independent of N , so that ν 0 = 1 and ν 1 is any prescribed value in [-1/2, 1/2].

However, in both cases, these simple and explicit choices of v N are somehow too rigid for our purposes. Indeed these functions are not piecewise constant and, on the other hand, one cannot concatenate smooth functions of the form [START_REF] Chambrion | Controllability of the discrete-spectrum Schrödinger equation driven by an external field[END_REF] corresponding to distinct values of σ in a smooth (i.e. C ∞ ) way. In order to overcome this issue we restrict condition [START_REF] Boscain | A weak spectral condition for the controllability of the bilinear schrödinger equation with application to the control of a rotating planar molecule[END_REF] to m ≥ 2 such that mσ ∈ Σ N allowing v N to depend on N . This is the rationale for Lemma 7 below, which shows that small perturbations of functions of the form ( 14) yield admissible controls with efficiency arbitrarily close to 1/2. In the C ∞ case we further prescribe the approximating admissible controls to be zero with all derivatives at 0 and T so that concatenations of function of this kind are smooth. Lemma 7. Let σ > 0 and define T = 2π/σ. Denote by U T either the class of nonnegative piecewise constant functions on [0, T ] or the class of nonnegative C ∞ functions on [0, T ] that are zero with all derivatives at 0 and T . Then, for every ν 1 ∈ (-1/2, 1/2) and N ∈ N there exists w ∈ U T such that

(i) ∫ T 0 w(t)dt = 1, (ii) ∫ T 0 w(t)e iσt dt = ν 1 , (iii) ∫ T 0 w(t)e imσt dt = 0 for every m ≥ 2 such that mσ ∈ Σ N . Proof. Let φ 0 ∈ {t → 1 -cos(σt), t → 1 + cos(σt)} and {φ 1 , . . . , φ k } = {t → sin(mσt), t → cos(mσt) | m ≥ 2 such that mσ ∈ Σ N }.
Let α ∈ [4/5, 1). For every ε > 0 consider w 0 , w 1 , . . . , w k ∈ U T such that

w 0 (t) ≥ ε α for every t ∈ [ε, T -ε], ( 15
)
w 0 (t) = 0 for every t ∈ [0, ε 2 ) ∪ (T -ε 2 , T ]
w j (t) = 0 for every j = 1, . . . , k, and

t ∈ [0, ε) ∪ (T -ε, T ],
and such that

∥w j -φ j ∥ L 2 ([0,T ]) < Cε, for every j = 0, . . . , k, (16)
for some C independent of ε. Indeed, since α ≥ 4/5 one easily checks that ( 15) is compatible with [START_REF] Assoudi | On subsemigroups of semisimple Lie groups[END_REF]. Consider the solution (c 1 , . . . , c k ) of the linear system

     ⟨w 1 , φ 1 ⟩c 1 + • • • + ⟨w k , φ 1 ⟩c k = -⟨w 0 , φ 1 ⟩, . . . . . . . . . ⟨w 1 , φ k ⟩c 1 + • • • + ⟨w k , φ k ⟩c k = -⟨w 0 , φ k ⟩.
Notice that the solution exists since the matrix of the system is close to an invertible diagonal matrix for ε sufficiently small. Moreover |c j | ≤ Cε for every j = 1, . . . , k (possibly considering a larger constant C).

Then define

w = w 0 T + k ∑ j=1 c j w j .
The function w belongs to U T . Indeed since α < 1 then w ≥ 0 for ε small enough.

By construction w satisfies (iii). Possibly rescaling w by a factor ( ∫ T 0 wdt

) -1 = 1 + O(ε) point (i) is satisfied. Notice now that ∫ T 0 w(t)e iσt dt = 1 T ∫ T 0 φ 0 (t)e iσt dt + O(ε) = ± 1 2 + O(ε).
The conclusion follows by convexity and letting ε go to zero. The proof of Lemma 6 remains unchanged since the condition in ( 9) is only used in [START_REF] Boscain | Adiabatic control of the Schroedinger equation via conical intersections of the eigenvalues[END_REF].

Proof of Theorem 2 4.1 Finite-dimensional exact controllability implies infinite-dimensional approximate controllability up to phases

Let n 0 ∈ N and n > n 0 be given by the Lie-Galerkin Control Condition. Define the collection of matrices

W n = { A (n) } ∪ { E 0 (B (n) j ) | (0, j) ∈ Ξ n } ∪ { E 0 (B (n) j ) + νE σ (B (n) j ) | (σ, j) ∈ Ξ n and σ, j are such that (0, j) ∈ Ξ n , σ ̸ = 0, ν ∈ (-1/2, 1/2) } ∪ { E σ (B (n) j ) | (σ, j) ∈ Ξ n , σ ̸ = 0, and U j = [-δ, δ] } ,
where Ξ n is defined as in [START_REF] Ball | Controllability for distributed bilinear systems[END_REF]. The matrices in W n correspond to the asymptotic dynamics obtained in Lemma 6 for the admissible choices of values for ν 0 and ν 1 (see Lemma 7). Notice that Lie(W n ) = Lie(M n ) and, by the Lie-Galerkin Control Condition, Lie(W n ) ⊇ su(n).

Consider the auxiliary control system

ẋ = M (t)x, M (t) ∈ W n , ( 17
)
where M plays the role of control. Proposition 8 below, based on Lemma 6, states that any propagator of ( 17) can be approximated by a propagator of system (2).

∥Υ u Tu -e γA • e τ k M k • • • • • e τ 1 M 1 ∥ L(Πn(H),H) < ε
where every e τ ℓ M ℓ is identified with an operator on H. Moreover, γ can be taken independent of

τ 1 , . . . , τ k ∈ [a, b].
More precisely, for ℓ = 1, . . . , k and τ 1 , . . . , τ k ∈ [a, b] there exist T ℓ ≥ 0 and ω ℓ : [0, T ℓ ] → R p , such that for K large enough u can be taken as the concatenation

u = 0| [0,χ 1 ] * τ 1 ω 1 K * • • • * τ 1 ω 1 K K-times * 0| [0,χ 2 ] * τ 2 ω 2 K * • • • * τ 2 ω 2 K K-times * • • • * 0| [0,χ k ] * τ k ω k K * • • • * τ k ω k K K-times
with χ ℓ ≥ 0 continuously depending on τ ℓ , where 0| [0,χ ℓ ] denotes the function [0, χ ℓ ] ∋ t → (0, . . . , 0) ∈ R p .

Proof. We construct u as the concatenation

u 1 * • • • * u k of k controls u ℓ : [0, ϑ ℓ ] → R p , ℓ = 1, . . . , k, namely, u(t) = u ℓ (t -(ϑ 1 + • • • + ϑ ℓ-1 )) for t ∈ [ϑ 1 + • • • + ϑ ℓ-1 , ϑ 1 + • • • + ϑ ℓ ), with u ℓ = 0| [0,χ ℓ ] * τ ℓ ω ℓ K * • • • * τ ℓ ω ℓ K and ϑ ℓ = χ ℓ + KT ℓ .
If U is the set of piecewise constant functions with values in U then this concatenation clearly results in an admissible control. If U is the set of C ∞ functions with values in U then, in order to guarantee that u is admissible, every control u ℓ is constructed as a smooth function which is zero with all derivatives at 0 and ϑ ℓ .

Let us construct recursively u ℓ and ϑ ℓ for ℓ ∈ {1, . . . , k}.

• For ℓ = 1 we have two cases.

-

If M 1 = A (n) then consider T 1 = 0 and χ 1 = τ 1 . -If M 1 is of the form ν 0 E 0 (B (n) j ) + ν 1 E σ (B (n)
j ) for some σ > 0 and j ∈ {1, . . . , p} then we apply Lemma 6. Therefore there exist N > n, a control ω N and K such that

∥Υ τ 1 ω N /K KT -e KT A e τ 1 M 1 ∥ L(Πn(H),H) < ε/k, for every τ 1 ∈ [a, b], where T = 2π/σ. Then, T 1 = T , χ 1 = 0, ω 1 = ω N | [0,T ] .
• Let ℓ ≥ 2 and assume that, for every τ

1 , . . . , τ ℓ-1 ∈ [a, b], the control u is constructed on [0, ϑ 1 + • • • + ϑ ℓ ). Then there exists γ ≥ 0 such that ∥e -γA Υ u ϑ 1 +•••+ϑ ℓ -e τ ℓ-1 M ℓ-1 • • • • • e τ 1 M 1 ∥ L(Πn(H),H) < ε ℓ -1 k , (18)
for every τ 1 , . . . , τ ℓ-1 ∈ [a, b]. Again we distinguish two cases.

-If M ℓ = A (n) then set T ℓ = 0 and χ ℓ = τ ℓ .

-Consider now the case in which M ℓ is of the form ν 0 E 0 (B

(n) j ) + ν 1 E σ (B (n) j )
for some σ > 0 and j ∈ {1, . . . , p}. Take a time γ ′ ≥ 0 such that γ ′ + γ is an integer multiple of T = 2π/σ, for instance γ ′ = ⌈ γ T ⌉T -γ, and let χ ℓ = γ ′ . Apply now Lemma 6. Then there exist N > n a control ω N and K such that

∥Υ τ ℓ ω N /K KT -e KT A e τ ℓ M ℓ ∥ L(Πn(H),H) < ε/k, for every τ ℓ ∈ [a, b]. Since γ ′ + γ is an integer multiple of T = 2π/σ, we have that [M ℓ , e -(γ+γ ′ )A ] = 0, which implies that [e τ ℓ M ℓ , e -(γ+γ ′ )A ] = 0. Hence ∥e -(γ+γ ′ +KT )A Υ u ϑ 1 +•••+ϑ ℓ+1 -e τ ℓ M ℓ • • • • • e τ 1 M 1 ∥ L(Πn(H),H) = ∥e -(γ+γ ′ +KT )A Υ τ ℓ ω N /K KT e γ ′ A Υ u ϑ 1 +•••+ϑ ℓ -e τ ℓ M ℓ • • • • • e τ 1 M 1 ∥ L(Πn(H),H) ≤ ∥Υ τ ℓ ω N /K KT -e KT A e τ ℓ M ℓ ∥ L(Πn(H),H) + ∥e -(γ+γ ′ )A e τ ℓ M ℓ Υ u ϑ 1 +•••+ϑ ℓ -e τ ℓ M ℓ • • • • • e τ 1 M 1 ∥ L(Πn(H),H) ≤ ε k + ∥e -γA Υ u ϑ 1 +•••+ϑ ℓ -e τ ℓ-1 M ℓ-1 • • • • • e τ 1 M 1 ∥ L(Πn(H),H) ≤ εℓ k ,
which concludes the induction with T ℓ = T and ω ℓ = ω N | [0,T ] and with the role of γ in [START_REF] Glass | On the control of the motion of a boat[END_REF] now played by γ + γ ′ + KT .

This concludes the construction of u with

T u = ϑ 1 + • • • + ϑ k .
Finally, notice that, in the case in which U is the set of C ∞ functions with values in U , thanks to Lemma 7 at each step we can assume that the control ω ℓ is zero with all derivatives at 0 and T (and so the control u is admissible). Indeed, if ν 0 ̸ = 0 then Lemma 7 applies directly, while if ν 0 = 0 then ω ℓ can be defined as the linear combination of two nonnegative controls associated with two distinct values of ν 1 in Lemma 7. Remark 6. Lemma 7 and Proposition 8 are the only steps in the proof of Theorems 3 and 2 where the nature of the class U is used. Actually, the proofs of both results are still valid under the following assumptions on the class U: there exists a subclass V of U which is convex and closed under concatenation, which contains the null function, and such that Lemma 7 holds with ∪ T >0 U T = V.

Phase tuning

The controllability of [START_REF] Gauthier | Controlabilité des systèmes bilinéaires[END_REF], ensured by the Lie-Galerkin Control Condition, together with Proposition 8 implies approximate controllability up to phases of system [START_REF] Agrachev | Dynamics control by a time-varying feedback[END_REF]. In this section we show how to correct the dephasing term e γA appearing in Proposition 8 by letting the system evolve freely for a suitable amount τ of time, as proved below (see Figure 1). Lemma 9. Let ψ ∈ H, µ > 0, N ∈ N, and N be a neighborhood of Π N (e µA ψ) in span{ϕ 1 , . . . , ϕ N }. Then there exists τ ≥ 0 such that e τ A N is a neighborhood of Π N ψ in span{ϕ 1 , . . . , ϕ N }. The main idea underlying phase tuning is that the dephasing between solutions of ( 2) and ( 6) is along A. Here N = 2 and Π 2 (e tA ψ) = (e itλ 1 ⟨ϕ 1 , ψ⟩, e itλ 2 ⟨ϕ 2 , ψ⟩) is identified, using the phases of its components, with elements of the torus S 1 × S 1 . Therefore Π N (ψ) ∈ B 2ε (Π N (e mµA ψ)) = e (m-1)µA B 2ε (Π N (e µA ψ)) = e (m-1)µA N , which proves the lemma with τ = (m -1)µ.

Final step

Proof of Theorem 2. Let ψ 0 and ψ 1 be in the unit sphere of H. For ε > 0 let n 0 ∈ N be such that

ψ 0 - Π n 0 ψ 0 ∥Π n 0 ψ 0 ∥ < ε 3 and ψ 1 - Π n 0 ψ 1 ∥Π n 0 ψ 1 ∥ < ε 3 .
The Lie-Galerkin condition ensures the existence of n > n 0 such that system (17) is controllable. By Proposition 8 there exist u ∈ U , T u ≥ 0, and γ ≥ 0 such that

Υ u Tu ( Π n 0 ψ 0 ∥Π n 0 ψ 0 ∥ ) -e γA Π n 0 ψ 1 ∥Π n 0 ψ 1 ∥ < ε 3 .

  the Lie-Galerkin Control Condition follows easily from the existence of a connectedness chain (see, for instance the proof of [9, Proposition 3.1] for details).

Remark 4 .

 4 As a consequence of Proposition 4, the Lie-Galerkin Control Condition is satisfied by a generic single-input bilinear Schrödinger equation i ψ = (-∆ + V )ψ + uW ψ on Ω bounded domain of R N and V and W are smooth functions from Ω → R N , see [24, Theorem 3.4].

Lemma 6 .

 6 , e tA y(t)⟩ = -⟨Θ(t, u 1 (t), . . . , u p (t))ϕ n , y(t)⟩, for every n ∈ N and for almost every t ∈ [0, T ]. The following lemma is inspired by [13, Theorem 1]. Here we denote by ∥ • ∥ L(E,H) the norm of linear operators from a subspace E of H to H. Let n ∈ N, σ > 0, j ∈ {1, . . . , p}, ν 0 and ν 1 in R, and a, b ∈ R such that 0 < a < b. For every N > n let ω N = (0, . . . , 0 j-1 , v N , 0, . . . , 0 p-j ) : R → R p be a periodic function of period T = 2π/σ,

  uniformly with respect to s ∈ [0, T ] and τ ∈ [a, b]. Hence the term in (13) goes to 0 as K → ∞ uniformly with respect to τ ∈ [a, b].

Remark 5 .

 5 One could relax the condition on v N in (9) by replacing the set Σ N by {|λ l -λ k | | l, k = 1, . . . , N, and ⟨ϕ l , B j ϕ k ⟩ ̸ = 0}.

Proposition 8 .

 8 Let n, k ∈ N, a, b ∈ R with 0 < a < b, and M 1 , . . . , M k ∈ W n . For every ε > 0 and τ 1 , . . . , τ k ∈ [a, b] there exist u ∈ U , T u > 0, and γ ≥ 0 such that

Proof.Figure 1 :

 1 Figure1: Graphic representation of the statement of Lemma 9. The main idea underlying phase tuning is that the dephasing between solutions of (2) and (6) is along A. Here N = 2 and Π 2 (e tA ψ) = (e itλ 1 ⟨ϕ 1 , ψ⟩, e itλ 2 ⟨ϕ 2 , ψ⟩) is identified, using the phases of its components, with elements of the torus S 1 × S 1 .

* This work was supported by the project DISQUO of the DEFI InFIniTI 2017 by CNRS and the QUACO project by ANR number 17-CE40-0007-01

By triangular inequality we have that

Applying Lemma 9 there exists a time τ ≥ 0 such that e τ A Υ u Tu (ψ 0 ) is ε-close to ψ 1 . The concatenation of u and the zero function for a time τ then steers ψ 0 into a ε-neighborhood of ψ 1 . Notice that such a concatenation is admissible since, in the case in which U is the set of C ∞ functions with values in U , the control u, given by Proposition 8, is zero with all derivatives at T u .

Proof of Theorem 3

Theorem 3 states that under the Lie-Galerkin Control Condition it is possible to control approximately system (2) and, at the same time, to control it exactly in projection on a prescribed number of components. The first step in the proof consists in showing that the approximate controllability part is a consequence of the exact controllability in projections.

Exact controllability in projections implies approximate controllability

Lemma 10. Assume that for every n 0 ∈ N, ψ 1 ∈ H with ∥ψ 1 ∥ = 1, and ψ 2 ∈ H such that ∥ψ 2 ∥ = 1 and ∥Π n 0 (ψ 2 )∥ < 1, there exist u ∈ U and T > 0 such that

Then for every n ∈ N, ψ in ∈ H with ∥ψ in ∥ = 1, and ψ f ∈ H such that ∥ψ f ∥ = 1 and ∥Π n (ψ f )∥ < 1, and for every ε > 0, there exist u ∈ U and T > 0 such that

Proof. Let n, ε, ψ in , and ψ f as above. If ψ f ∈ H has an infinite number of non-zero components then it is sufficient to take n 0 ≥ n such that ∥Π n 0 ψ f -ψ f ∥ < ε/2 and apply [START_REF] Herrero-Collantes | Quantum random number generators[END_REF] with ψ 1 = ψ in and ψ 2 = ψ f . If, instead, there exists n 0 ∈ N such that ⟨ϕ n 0 , ψ f ⟩ ̸ = 0 and ⟨ϕ k , ψ f ⟩ = 0 for every k > n 0 then note that n 0 > n and consider ψ 2 defined component-wise as

for η < ε/2. Then apply [START_REF] Herrero-Collantes | Quantum random number generators[END_REF] with ψ 1 = ψ in .

A useful topological tool

The following topological result is standard in degree theory. We provide its proof for completeness. Similar results used in the control literature are, for instance, [2, Lemma 7] and [START_REF] Glass | On the control of the motion of a boat[END_REF]Lemma 4.1].

Lemma 11. Let X ⊂ R n be open and bounded and let F ∈ C(X, R n ) be a homeomorphism between X and F (X). Assume that y 0 is in F (X) and consider

. By definition of ε we have that h(t, x) ̸ = y 0 for every t ∈ [0, 1] and x ∈ ∂X. In particular the topological degree d(h(t, •), X, y 0 ) is well defined for every t ∈ [0, 1]. Since F | X is a homeomorphism and y 0 ∈ F (X) then d(F, X, y 0 ) ̸ = 0 and by homotopy invariance d(G, X, y 0 ) ̸ = 0 which implies that y 0 ∈ int(G(X)).

Normal controllability

In this section we consider ψ 1 and ψ 2 unit vectors in H and n 0 ∈ N such that ∥Π n 0 (ψ 2 )∥ < 1. Let n > n 0 be such that the Lie-Galerkin Control Condition holds. Let now ψ2 ∈ S 2n-1 be such that Π n 0 (ψ 2 ) = Π n 0 ( ψ2 ). By classical results of controllability (see [START_REF] Jurdjevic | Control systems on Lie groups[END_REF] and [34, Theorem 4.3]) system [START_REF] Gauthier | Controlabilité des systèmes bilinéaires[END_REF] is normally controllable at ψ2 , in the sense that there exist M 1 , . . . , M k ∈ W n and t 1 , . . . , t k > 0 such that the map

has rank 2n -1 at (t 1 , . . . , t k ) and E(t 1 , . . . , t k ) = ψ2 .

Since n > n 0 and ∥Π n 0 ( ψ2 )∥ < 1, there exist j 1 , . . . , j 2n 0 ∈ {1, . . . , k} such that the map F (s j 1 , . . . , s j 2n 0 ) → Π n 0 ( E(t 1 , . . . , t j 1 -1 , s j 1 , t j 1 +1 , . . . , t j 2n 0 -1 , s j 2n 0 , t j 2n 0 +1 , . . . , t k ) )

has rank 2n 0 at (t j 1 , . . . , t j 2n 0 ) and

) .

Now let ρ > 0 be such that X := B ρ (t j 1 , . . . , t j 2n 0 ) ⊂ (0, +∞) 2n 0 and F is a diffeomorphism between X and F (X). Let

and note that η > 0.

Lemma 12. There exist γ ≥ 0 and a map associating with every (s 1 , . . . , s 2n 0 ) ∈ X a control v s ∈ U and T s > 0 such that the image of the mapping

) contains Π n 0 (e γA ψ 2 ) in its interior.

Proof. Let η be as in [START_REF] Jurdjevic | Control systems on semisimple Lie groups and their homogeneous spaces[END_REF]. By Theorem 2 there exists w ∈ U steering ψ

Define v s as the concatenation of w and u s . The continuity of G with respect to s is ensured by Assumption (A5). The conclusion then follows from Lemma 11.

Final step

We are now ready to conclude the proof of Theorem 3.

Proof of Theorem 3. By Lemma 10 it enough to prove that for every n 0 ∈ N, ψ 1 ∈ H with ∥ψ 1 ∥ = 1, and ψ 2 ∈ H such that ∥ψ 2 ∥ = 1 and ∥Π n 0 (ψ 2 )∥ < 1, there exist u ∈ U and T > 0 such that

Lemma 12 guarantees the existence of a neighborhood N ⊂ G(X) of Π n 0 (e γA ψ 2 ). By Lemma 9 with µ = γ, there exists τ ≥ 0 and ζ ∈ N such that e τ ζ = Π n 0 (ψ 2 ). Let s ∈ X be such that Π n 0 ( Υ v s Ts (ψ 1 )

The concatenation of v s and the zero function for a time τ then steers ψ 1 to some ψ 3 such that Π n 0 ψ 3 = Π n 0 ψ 2 . Notice that such a concatenation is admissible since, in the case in which U is the set of C ∞ functions with values in U , the control v s , given by Lemma 12 (see also Proposition 8), is zero with all derivatives at T s .


Mustapha Aznag

Mohamed Quafafou

Nicolas Durand

Zahi Jarir
email: zahijarir@ucam.ac.ma

Multiple representations of web services: discovery, clustering and recommendation

Keywords: reputation, representation, WSDL, semantic tagging

This paper analyses several web services representations based on web services descriptions and more generally on the content of WSDL files. We introduce also a new representation called symbolic reputation which is computed from relationships between web services. Different implementation issues are discussed and the results considering real world web services are analysed to determine the usefulness of the introduced representations for three main tasks: web services discovery, clustering and recommendation.

I. INTRODUCTION

Web services use natural language descriptions (ambiguity of sentences), they are multi-languages and cross-domains. In this context, the representation of web service becomes a major challenge. This paper studies different classes of web services representations and compares them considering the following three important tasks: discovery, clustering and recommendation.

II. WEB SERVICES REPRESENTATIONS

We have considered the following representations :

• Baseline representation (B) : A web service can be described by a textual description extracted from WSDL document or given by his provider when publishing in the UDDI. The current UDDI registry only allows to search web services by their textual description. We consider this representation as a baseline representation for a web service. Let us remark that the major disadvantage of this representation is that most web services have an poor or an empty description. • Functions descriptions integration (BFD) : The goal of this representation is to enrich the baseline representation of a service by adding the name and the textual description of all its operations. We apply a textual processing to obtained the resulted representation. Let us remark that such descriptions may be dirty and generally have different sizes. We need more cleaning process to improve such representation. • WSDL types integration (WBFD) : To complete the second representation, we added all information described by WSDL types. The types are used by messages to transmit informations between web services.

Consequently, WSDL types are good features to describe the functionality of a service and are the most informative element in WSDL document. For this reason, we extract all type names (elements, complex types, simple types, attributes, enumerations) from the database and we apply the textual processing to produce a set of words. Thus, we use the obtained set of words to construct the new representation (WBFD).

• Rules based text tagging of WS descriptions (RBFD) :

The approach consists in defining of extraction rules to identify, extract and annotate relevant multi-word terms from web service descriptions. The processing steps (tokenization, Part-Of-Speech tagging, extraction and output generation) of information extraction have been implemented as modules using the LinguaStream platform 1 . LinguaStream [START_REF] Bilhaut | An Integrated Environment for Computational Linguistics Experimentation[END_REF] is an integrated experimentation environment targeted to researchers in natural language processing. Let us note that we used TreeTagger2 for the Part-Of-Speech tagging step. The extracted information is given in a form of XML file.

III. SYMBOLIC REPUTATION MODEL

A. Web services dependency graph

Web services dependency graph was used to represent the structure of the web services space, i.e. web services relationships, by generating a network depending on the I/O of each web service. This induced network is then used for web service composition [START_REF] Mohammed | Dependency Based Automatic Service Composition Using Directed Graph, Next Generation Web Services Practices[END_REF]. The general approach consists of searching first for web services operations dependencies using the I/O parameters of their operations, then the web services dependency graph is induced. For seek of simplicity, we consider here that a dependency occurs between two services when they offer at least two dependent operations: a service requires (resp. provides) data from (resp. to) another service. Of course, other dependency definitions can be used without affecting our general symbolic reputation computing approach.

B. Random walks models for reputation computing

A random walk is a sequence of nodes in graph constructed by the following process: select a random starting node in the graph, then move to select a neighbour of this node at random and so forth. The random walk analysis have been applied to different fields as a fundamental model for random processes in time . More particularly, a formal model was proposed in [START_REF] Rafiei | Mendelzon What is this Page Known for? Computing Web Page Reputations[END_REF] to allow the computation of the reputation of a web page using the web hyperlink structure. We have adapted this model to compute the symbolic reputation of web services.

We consider the dependency graph constructed in Section III-A. The probability of visiting a service s for topic t at step n of the walk, denoted R n (s, t), is defined as follows:

R n (s, t) = (1 -d) q→s R n-1 (s, t) O(s) + d Nt , if t ∈ Ω(s) 0, otherwise (1)
The previous probability is the basis of the algorithm that compute the symbolic reputation. In fact, suppose that with the probability d the random walker jumps into a service uniformly chosen at random from the set of services that contains the term t. In this context, the probability that a random walker visits a service s in a random jump is d Nt (N t denotes the total number of services on the UDDI that contains the term t) if the vectorial representation of service s contains the term t and it is zero otherwise. The probability that the walker visits the service s at step n after visiting one among its parent service ss is 1-d O(s) R n-1 (q, t) where R n-1 (q, t) denotes the probability that the walker visits the service ss for topic t at step n -1 and O(s) denotes the number of services that require data from s (parents of s in the dependency graph).

IV. EXPERIMENTAL RESULTS

We have considered different web service sources like WebservicesX.net3 , xMethods.net4 and seekda.com5 . Our general Meta-UDDI architecture allows to use of different UDDI which are used through specific wrappers. We have collected around 8,500 services. Unfortunately, these services are not classified into categories. This is a real problem when we want to evaluate the usefulness of our representations using precision and recall measures. For this reason, we have considered a new web services source, i.e. service-finder.eu6 , which classifies its services using an ontology. The number of services which are classified into a category by service-finder is only reduced to only 1,647 web services. However, 465 services among them are not available: they are discarded. Moreover, the collected web services are multi-languages. We have automated the recognition of the language and keep only those using English language. Finally, only 993 web services are used. Let us denote 'Collected WS' the number of service collected for each category, 'Available WS' the number of available services and 'Used WS' the number of services used for each category after the process of recognition of the language. See Table I for details the results obtained using each representations and differents categories of web services.

V. CONCLUSION

This paper revisits the traditional representations of web services using their textual descriptions and/or the elements of the WSDL structure as types, attributes, etc. We have proposed two new web services representations. The first one is based on semantic tagging of web services descriptions to keep only the most significant parts. Whereas, the second representation, i.e., symbolic reputation, is more contextual as it considers not only the service itself, but its neighbours.

http://www.linguastream.org

http://www.ims.uni-stuttgart.de/projekte/corplex/TreeTagger/

http://www.webservicex.net/ws/default.aspx

http://www.xmethods.net/ve2/index.po

http://www.seekda.com

http://www.service-finder.eu/