Mohamed Amine Boukhaled
email: mohamed.boukhaled@lip6.fr

Jean-Gabriel Ganascia
email: jean-gabriel.ganascia@lip6.fr

Probabilistic Anomaly Detection Method for Authorship Verification

Keywords: Authorship verification, anomaly detection, multivariate Gaussian distribution

Authorship verification is the task of determining if a given text is written by a candidate author or not. In this paper, we present a first study on using an anomaly detection method for the authorship verification task. We have considered a weakly supervised probabilistic model based on a multivariate Gaussian distribution. To evaluate the effectiveness of the proposed method, we conducted experiments on a classic French corpus. Our preliminary results show that the probabilistic method can achieve a high verification performance that can reach an F 1 score of 85%. Thus, this method can be very valuable for authorship verification.

Introduction

Authorship verification is a special case of the authorship attribution problem. The authorship attribution problem can be generally formulated as follows: given a set of candidate authors for whom samples of written text are available, the task is to assign a text of unknown authorship to one of these candidate authors [START_REF] Stamatatos | A survey of modern authorship attribution methods[END_REF]. This task has been addressed mainly as a problem of multi-class discrimination, or as a text categorization task [START_REF] Sebastiani | Machine learning in automated text categorization[END_REF]. In the authorship verification problem, though, we are given samples of texts written by a single author and are asked to assess if a given different text is written by this author or not [START_REF] Koppel | Computational methods in authorship attribution[END_REF]. As a categorization problem, modifying the original attribution problem in this way makes the task of authorship verification significantly more difficult partly because building a characterising model of one author is much harder than building a distinguishing model between two authors [START_REF] Koppel | Authorship verification as a one-class classification problem[END_REF]. Authorship verification has two key steps: an indexing step based on style markers is performed on the text using some natural language processing techniques such as tagging, parsing, and morphological analysis; then an identification step is applied using the indexed markers to verify the validity of the authorship. Many style markers have been used to characterise writing styles, from early studies based on sentence length and vocabulary richness [START_REF] Yule | The statistical study of literary vocabulary[END_REF] to more recent and relevant work based on function words [START_REF] Holmes | Stephen Crane and the New-York Tribune: A case study in traditional and non-traditional authorship attribution[END_REF], [START_REF] Zhao | Effective and scalable authorship attribution using function words[END_REF], punctuation marks [START_REF] Baayen | An experiment in authorship attribution[END_REF], part-of-speech (POS) tags [START_REF] Kukushkina | Using literal and grammatical statistics for authorship attribution[END_REF], parse trees [START_REF] Gamon | Linguistic correlates of style: authorship classification with deep linguistic analysis features[END_REF] and character-based features [START_REF] Kešelj | N-gram-based author profiles for authorship attribution[END_REF]. There is an agreement among researchers that function words are the most reliable indicator of authorship [START_REF] Stamatatos | A survey of modern authorship attribution methods[END_REF].

The verification step can be addressed as a one-class problem (written-by-theauthor) or as a binary classification problem (written-by-the-author as positive vs notwritten-by-the-author as negative). However, both of these formulations of the problem have drawbacks: In the case of binary classification, one should collect a reasonable amount of representative texts of the entire "not-written-by-the-author" class, which is difficult, if not impossible. In the case of one-class classification, one does not take advantage from negative examples that we do not actually lack for them even though they are not representative of the entire class. In this paper, we address the authorship verification problem as an anomaly detection problem where texts written by the candidate author are seen as normal data while texts not written by that author are seen anomalous data. We propose a probabilistic anomaly detection method that can benefit from negative examples for the authorship verification process. We first give an overview of the anomaly detection problem in section 2 and then describe our method in section 3. We than experimentally validate the proposed method in section 4 using a classic French corpus. Finally we use this method to settle a literary mystery case.

Anomaly Detection

Anomaly detection is a challenging task which consists of identifying patterns in data that do not conform to expected (normal) behaviour. These non-conforming patterns are called anomalies or outliers [START_REF] Chandola | Anomaly detection: A survey[END_REF]. Anomaly detection has been successfully used in many applications such as fault detection, radar target detection and hand written digit recognition [START_REF] Markou | Novelty detection: a review-part 1: statistical approaches[END_REF]. This technique has also been used to deal with textual data for various purposes such as detecting novel topics, events, or news stories in a collection of documents or news articles [START_REF] Chandola | Anomaly detection: A survey[END_REF]. Anomaly detection is based on the idea that one can never train a classification algorithm on all the possible classes that the system is likely to encounter in real application. Anomaly detection is also suitable for situations in which the class imbalance problem can affect the accuracy of classification (see Fig. 1) [START_REF] Wressnegger | A close look on n-grams in intrusion detection: anomaly detection vs. classification[END_REF]. Many anomaly detection techniques fall under the statistical approach of modelling data based on its statistical properties and using this information to estimate whether a test sample comes from the same distribution or not [START_REF] Markou | Novelty detection: a review-part 1: statistical approaches[END_REF]. Another common method for anomaly detection is the one-class SVM that determines a hyper sphere enclosing the normal data [START_REF] Heller | One class support vector machines for detecting anomalous windows registry accesses[END_REF]. In this contribution, we describe and use a probabilistic anomaly detection method for authorship verification that straightforwardly follows the definition given above. The method is discussed in the next section.

Proposed Method

In our method, we address the authorship verification problem as an anomaly detection problem where texts written by a given author are seen as normal data, while texts not written by that author are seen anomalous data. We use a probabilistic anomaly detection method that can benefit from anomalous examples for the authorship verification process based on a multivariate Gaussian modelling. Given the fact that unsupervised anomaly detection approaches often fail to match the required detection rates in many tasks and there exists a need for labelled data to guide the model generation [START_REF] Görnitz | Toward supervised anomaly detection[END_REF], our proposed methods is weakly supervised in the sense that it takes into consideration a small amount of representative anomalous data for the model generation.

The approach to anomalous text detection is to train a multivariate Gaussian distribution model on the style markers extracted from sample of text written by an author . Every newly arriving text (data instance) that we went to verify as written by or not is contrasted with the probabilistic model of normality, and a normality probability is computed. The probability describes the likelihood of the new text to have been written by compared to the average data instances seen during the training. If the probability does not surpass a predefined threshold , the instance is considered an anomaly and the text is considered not to have been written by the author . To define the probability threshold, we cross-validate over a data set containing both anomalous and non-anomalous data and we set the threshold to the value that maximizes the authorship verification performance on this data set. The method can be formulated into three steps as follow: Let be a -dimensional vector representing the text 1, … , .

1. Train a Multivariate Gaussian distribution model on the normal data. This is done by estimating the two distribution parameters: the multivariate location μ and the covariance matrix :

μ ∑ (1)
∑ μ μ (2)
2. Given a new instance , compute the probability :

| | ! exp μ % μ (3)
3. Predict the anomaly (& 1) of the instance given the probability threshold ∝ :

& ( 1 ) *∝ 0 ) , ∝ (4)
The nature of the style markers used as attributes to describe and to get andimensional vector representing the text is very important and determines the applicability of our method. In fact, the nature of these attributes should respect the Gaussian assumption made to train the multivariate Gaussian model. For our experiment, we chose to test this method on two types of style markers separately. Each text in our data set is mapped onto a vector of the frequency of the most frequent function words and a vector of the frequency of POS-tags.

Fig. 2. The probability of frequency of the French function word "de" has a Gaussian behavior

There are two main reasons for using the frequency of function words as attributes.

First, because of their high frequency in a written text, function words are very likely to have a Gaussian behaviour (see Figure 2). Secondary, function words, unlike content words, are difficult to consciously control, thus they are more independent from the topic or the genre of the text [START_REF] Chung | The psychological functions of function words[END_REF]. In fact, Koppel and Schler found that all the work of distinguishing the styles of different authors is accomplished with a small set of features containing frequent function words [START_REF] Koppel | Authorship verification as a one-class classification problem[END_REF]. Based on that information and to get a right balance between the features-set size and the dataset size, we limit our study to the most 30th frequent function words. The part-of-speech-based markers are also shown to be very effective because they partly share the advantages of function words.

Experimental Validation

Data Set

To test the effectiveness of our method, we used novels written by: Balzac, Dumas and France. This choice was motivated by our special interest in studying the classic French literature of the 19th century, and by the availability of electronic texts from these authors on the project Gutenberg website1 and in the Gallica electronic library2. Our choice of authors was also affected by the fact that we wished to get a challenging problem since these three authors are knows to have relatively comparable syntactic styles. More information about the data set used for the experimentation is summarized in Table 1.

For each of the three authors mentioned above, we collected 4 novels, so that the total number of novels was 12. The next step was to divide these novels into smaller pieces of texts in order to have enough data instances (artificial documents) to train and test the probabilistic model. Researchers working on authorship attribution in literary texts have used different dividing strategies. For example, Hoover [START_REF] Hoover | Frequent collocations and authorial style[END_REF] decided to take just the first 10,000 words of each novel as a single text, while Argamon and Levitan [START_REF] Argamon | Measuring the usefulness of function words for authorship attribution[END_REF] treated each chapter of each book as a separate text. In our experiment, we chose simply to chunk each novel into approximately equal parts of 2000 words, which is below the threshold proposed by Eder [START_REF] Eder | Does size matter? Authorship attribution, small samples, big problem[END_REF] specifying the smallest reasonable text size to achieve good attribution. This increases the degree of the difficulty of the task. Table 1. Data set used in our experiment

Verification Protocol

In our experiment, the corpus was POS tagged and function words were extracted. Each text is then represented by two vectors -. {0 , 0 , … , 0 . }, one for the normalized frequencies of occurrence of the top 30 function words in the corpus, and another for the normalized frequencies of occurrence of POS-tags. The normalization of the vectors of frequency representing a given text was done according to the size of the text. Then, for each author, we used 75% of the data generated by texts written by this author to estimate the parameters of the model representing this author, and 20% of the data from each author for testing it. The remaining 5% data was merged with 5% of the data (anomalous data) generated by each one of the other authors and was used to estimate the probability threshold á. To get a reasonable estimate of the expected generalization performance, we used a resampling with replacement method. The training and testing process was done 10 times. The overall authorship verification performance is taken as the average performance over these 10 runs. For evaluating the verification performance, we used the standard measures, calculating precision (2), recall (-), and 3 â where:

3 â = ( 5â )67 (â 6)57 (5)
We consider precision and recall to have the same value, so we set â equal to 1.

Baselines

To evaluate the effectiveness of the proposed method we used one-class SVM and binary SVMs classifier using RBF kernel (best performing). The one-class SVM was trained and tested on the same data used to train and test the multivariate Gaussian model respectively. The binary SVM classifier was trained on both the data used to train the probabilistic model and the data used to estimate the probability threshold, and it was tested on the same data as our probabilistic model. The overall baseline classification performance is taken as the average performance over the 10 runs.

Results

The results of measuring the verification performance for the two different style markers presented in our experimental validation are summarized in Table 2 tion words and in Table 3 for POS tags. These results show in general the superiority of the proposed method over the baselines in terms of 3 score and recall. These results also show in general a better performance when using frequent function words than POS-tag for both the proposed method and the baselines.

Our study here indicates that the multivariate Gaussian model for anomaly detection combined with features based on frequent function words can achieve a high verification performance (e.g., F1 = 0.85). By contrast, the one-class SVM performs particularly poorly on this task. The binary SVM achieved relatively good results but doesn't outperform the probabilistic model; this shows that the authorship verification problem should not be handled as a binary class problem unless a sufficient amount of representative negative data is present to avoid the class imbalance problem.

Table 2. Results of the authorship verification using frequent function words Table 3. Results of the authorship verification using frequent POS-tags Finally, these results are in line with previous work that claimed that semi-supervised anomaly detection approaches, originating from a supervised classifier, are inappropriate and hardly detect new and unknown anomalies, and that semi-supervised anomaly detection needs to be grounded in the unsupervised learning paradigm [START_REF] Görnitz | Toward supervised anomaly detection[END_REF].

A Classic French Literary Mystery: "Le Roman de Violette"

In this section, we apply our probabilistic method to settle one of the classic French literary mysteries. "Le Roman de Violette"3 is a novel published in 1883. The authorship of this novel has still not been determined. Even though the novel was edited under the name of Alexandre Dumas, some literary critics state that a serious candidate for its authorship is "La Marquise de Mannoury d'Ectot". But this hypothesis cannot be definitely proved, partly because there is only one known book written by that author, which limits the quantity of text available to validate the computational authorship identification methods including our method. We applied our proposed authorship verification method to handle this case. Since there is not enough available text written by "La Marquise de Mannoury d'Ectot" to verify whether she is the writer of "Le Roman de Violette" or not, we set Alexandre Dumas as the author candidate that we want to verify as the writer or not. We trained the probabilistic model based on frequent function words on texts written by Alexandre Dumas. The only known book written by "La Marquise de Mannoury d'Ectot" was used as the representative anomalous text to set the probability threshold. Finally, the verification test was performed on the "Roman de Violette". The authorship probability produced by the novel using our proposed method is under the threshold needed to validate the authorship. This result suggests that the novel "Le Roman de Violette" was not written by Alexandre Dumas.

Conclusion

In this paper, we have presented a study on using an anomaly detection method for the authorship verification task. We have considered a weakly supervised probabilistic model based on a multivariate Gaussian distribution. To evaluate the effectiveness of the proposed method, we conducted experiments on a classic French literary corpus. Our preliminary results show that the probabilistic method can achieve a high verification performance that can reach an F1 score of 85%.

Based on the current study, we have identified several future research directions. First, we will explore incorporating the non-verification option into our probabilistic model. In fact, in the field of authorship identification, the non-attribution option is better than a false attribution. Second, this study will be expanded to include more style markers. Third, we intend to experiment with other languages and text sizes using standard corpora employed in the field at large.

Fig. 1 .

 1 Fig. 1. The anomaly detection and the classification learning schemas

http://www.gutenberg.org/

http://gallica.bnf.fr/

Acknowledgment

This work was supported by French state funds managed by the ANR within the Investissements d'Avenir programme under reference ANR-11-IDEX-0004-02.


Mohamed Amine Boukhaled
email: mohamed.boukhaled@lip6.fr

Jean-Gabriel Ganascia
email: jean-gabriel.ganascia@lip6.fr

Using Function Words for Authorship Attribution: Bagof-Words vs. Sequential Rules

Authorship attribution is the task of identifying the author of a given document. Various style markers have been proposed in the literature to deal with the authorship attribution task. Frequencies of function words have been shown to be very reliable and effective for this task. However, despite the fact that they are state-of-the-art, they basically rely on the invalid bag-of-words assumption, which stipulates that text is a set of independent words. In this contribution, we present a comparative study on using two different types of style marker based on function words for authorship attribution. We compare the effectiveness of using sequential rules of function words as style marker that do not relay on the bag-of-words assumption to that of the frequency of function words which does. Our results show that the frequencies of function words outperform the sequential rules.

Introduction

Authorship attribution is the task of identifying the author of a given document. The authorship attribution problem can typically be formulated as follows: given a set of candidate authors for whom samples of written text are available, the task is to assign a text of unknown authorship to one of these candidate authors [START_REF] Stamatatos | A survey of modern authorship attribution methods[END_REF]. This problem has been addressed mainly as a problem of multi-class discrimination, or as a text categorization task [START_REF] Sebastiani | Machine learning in automated text categorization[END_REF]. Text categorization is a useful way to organize large document collection. Authorship attribution, as subtask of text categorization, assumes that the categorization scheme is based on the authorial information extracted from the documents. Authorship attribution is a relatively old research field. A first scientific approach to the problem was proposed in the late 19th century, in the work of Mendenhall in 1887, who studied the authorship of texts attributed to Bacon, Marlowe and Shakespeare. More recently, the problem of authorship attribution gained greater importance due to new applications in forensic analysis, humanities scholarship [START_REF] Stamatatos | A survey of modern authorship attribution methods[END_REF]. Current authorship attribution methods have two key steps: (1) an indexing step based on style markers is performed on the text using some natural language processing techniques such as such as tagging, parsing, and morphological analysis; then (2) an identification step is applied using the indexed markers to determine the most likely authorship. An optional features selection step can be employed between these two key steps to determine the most relevant markers. This selection step is done by performing some statistical measures of relevance such us mutual information or Chi-square testing. The identification step involves using methods that fall mainly into two categories: the first category includes methods that are based on statistical analysis, such as principle component analysis [START_REF] Burrows | Delta": A measure of stylistic difference and a guide to likely authorship[END_REF] or linear discriminant analysis [START_REF] Stamatatos | Computer-based authorship attribution without lexical measures[END_REF]; the second category includes machine learning techniques, such as simple Markov Chain [START_REF] Khmelev | Using Markov Chains for Identification of Writer[END_REF], Bayesian networks, support vector machines (SVMs) [START_REF] Koppel | Authorship verification as a one-class classification problem[END_REF] , [START_REF] Diederich | Authorship attribution with support vector machines[END_REF]) and neural networks [START_REF] Ramyaa | Using machine learning techniques for stylometry[END_REF]. SVMs, which have been used successfully in text categorization and in other classification tasks, have been shown to be the most effective attribution method [START_REF] Diederich | Authorship attribution with support vector machines[END_REF]. This is due to the fact that SVMs are less sensitive to irrelevant features in terms of degradation in accuracy, and permit one to handle high dimensional data instances more efficiently.

To achieve high authorship attribution accuracy, one should use features that are most likely to be independent from the topic of the text. Many style markers have been used for this task from early works based on features such as sentence length and vocabulary richness [START_REF] Yule | The statistical study of literary vocabulary[END_REF] to more recent and relevant works based on function words [START_REF] Holmes | Stephen Crane and the New-York Tribune: A case study in traditional and non-traditional authorship attribution[END_REF], [START_REF] Zhao | Effective and scalable authorship attribution using function words[END_REF]), punctuation marks [START_REF] Baayen | An experiment in authorship attribution[END_REF], part-of-speech (POS) tags [START_REF] Kukushkina | Using literal and grammatical statistics for authorship attribution[END_REF], parse trees [START_REF] Gamon | Linguistic correlates of style: authorship classification with deep linguistic analysis features[END_REF] and character-based features [START_REF] Kešelj | N-gram-based author profiles for authorship attribution[END_REF].

There is an agreement among different researchers that function words are the most reliable indicator of authorship. There are two main reasons for using function words in lieu of other markers. First, because of their high frequency in a written text, function words are very difficult to consciously control, which minimizes the risk of false attribution. The second is that function words, unlike content words, are more independent from the topic or the genre of the text, so one should not expect to find great differences of frequencies across different texts written by the same authors on different topics [START_REF] Chung | The psychological functions of function words[END_REF]. However, despite the fact that function word-based markers are state-of-theart, they are basically relying on the bag-of-words assumption, which stipulates that text is a set of independent words. This approach completely ignores the fact that there is a syntactic structure and latent sequential information in the text. De Roeck (2004) has shown that frequent words, including function words, do not distribute homogeneously over a text. This provides evidence of the fact that the bag-of-words assumption is invalid. In fact, cri-tiques have been made in the field of authorship attribution charging that many works are based on invalid assumptions [START_REF] Rudman | The state of authorship attribution studies: Some problems and solutions[END_REF] and that researchers are focusing on attribution techniques rather than coming up with new style markers that are more precise and based on less strong assumptions. In an effort to develop more complex yet computationally feasible stylistic features that are more linguistically motivated, [START_REF] Hoover | Frequent collocations and authorial style[END_REF] pointed out that exploiting the sequential information existing in the text could be a promising line of work. He proved that frequent word sequences and collocations can be used with high reliability for stylistic attribution.

In this contribution, we present a comparative study on using two different types of style marker based on function words for authorship attribution. Our aim is to compare the effectiveness of using a style marker that do not relay on the bag-of-words assumption to that of the frequency of function words which does. In this study, we used sequential rule of function words as style marker relying on the sequential information contained in structure of the text. We first give an overview of the sequential rule mining problem in section 2 and then describe our experimental setup in section 3. Finally, the results of the comparative study are presented in section 4.

Sequential rule extraction

Sequential data mining is a data mining subdomain introduced by [START_REF] Agrawal | Mining association rules between sets of items in large databases[END_REF] which is concerned with finding interesting characteristics and patterns in sequential databases. Sequential rule mining is one of the most important sequential data mining techniques used to extract rules describing a set of sequences. In what follows, for the sake of clarity, we will limit our definitions and annotations to those necessary to understand our experiment.

Considering a set of literals called items, denoted by = { , … , }, an itemset is a set of items ⊆ . A sequence (single-item sequence) is an ordered list of items, denoted by = < . . . > where . . . are items.

Table 1. Sequence database SDB.

A sequence database is a set of tuples ( , ), where is the sequence identifier and a sequence. Interesting characteristics can be extracted from such databases using sequential rules and pattern mining b,d,e > < b,c,e > < a,b,d,e > A sequential rule : ⇒ is defined as a relationship between two itemsets and such that ∩ = ∅ . This rule can be interpreted as follow: if the itemset occurs in a sequence, the itemset will occur afterward in the same sequence. Several algorithms have been developed to efficiently extract this type of rule, such as (Fournier-Viger and Tseng, 2011). For example, if we run this algorithm on the containing the three sequences presented in Table 1, we will get as a result sequential rules, such us ⇒ , with support equal to 2, which means that this rule is respected by two sequences in the (i.e., there exist two sequences of the where we find the item , we also find and afterward in the same sequence).

Sequence ID Sequence 1 2 3 < a,
In our study, the text is first segmented into a set of sentences, and then each sentence is mapped into a sequence of function words appearing with order in that sentence. For example the sentence "J'aime ma maison où j'ai grandi." will be mapped to < , , ù, > as a sequence of French function words, and " ⇒ ù" ; " ⇒ ù, " are examples of sequential rules respected by this sequence. The whole text will produce a sequential database. The rules extracted in our study represent the cadence authors follow when using function words in their writing. This gives us more explanatory properties about the syntactic writhing style of a given author than just what frequencies of function words can do.

Classification Scheme

In the current approach, each text was segmented into a set of sentences based on splitting done using the punctuation marks of the set {'. ', '! ', '? ', ': ', ' … '}, then function words were extracted from each sentence to construct a sequence. The algorithm described in [START_REF] Fournier-Viger | Mining top-k sequential rules[END_REF] was then used to extract sequential rules of function words sequences from each text. Each text is then represented as a vector ' ( of supports of rules, such that ' ( = {) , ) * , … , ) ( } is the ordered set by decreasing normalized frequency of occurrence of the top + rules in terms of support in the training set. Each text is also represented by a vector of normalized frequencies of occurrence of function words. The normalization of the vector of frequency representing a given text was done by the size of the text. Given the classification scheme described above, we used SVMs classifier to derive a discriminative linear model from our data. To get a reasonable estimation of the expected generalization performance, we used common measures: precision (,), recall ( ), andscore based on a 5-fold crossvalidation as follows:

3

Experimental Setup

Data Set

For the comparison experiment, we use texts written by: Balzac, Dumas, France, Gautier, Hugo, Maupassant, Proust, Sand, Sue and Zola. This choice was motivated by our special interest in studying the classic French literature of the 19th century, and the availability of electronic texts from these authors on the Gutenberg project website1 and in the Gallica electronic library2 .

Table 2. Statistics for the data set used in our experiment

We collected 4 novels for each author, so that the total number of novels is 40. The next step was to divide these novels into smaller pieces of texts in order to have enough data instances to train the attribution algorithm.

Researchers working on authorship attribution on literature data have been using different dividing strategies. For example, [START_REF] Hoover | Frequent collocations and authorial style[END_REF] decided to take just the first 10,000 words of each novel as a single text, while [START_REF] Argamon | Measuring the usefulness of function words for authorship attribution[END_REF]

Results

Results of measuring the attribution performance for the different feature sets presented in our experiment setup are summarized in Table 3. These results show in general a better performance when using function words frequencies, which achieved a nearly perfect attribution, over features based on sequential rules for our corpus.

Our study here shows that the SVMs classifier combined with features extracted using sequential data mining techniques can achieve a high attribution performance (That is, F 1 = 0.947 for Top 400 FW-SR ). Until certain limit, adding more rules increases the attribution performance.

Table 3. 5-fold cross-validation results for our data set. FW-SR refers to Sequential Rules of Functions Words.

But contrary to common sense, function-word-frequency features, which fall under the bag-of-word assumption known to be blind to sequential information, outperform features extracted using sequential rule mining technique.

In fact, they achieved nearly a perfect performance. We believe that this due to the presence of some parameters affecting the attribution process. These parameters, that need to be more deeply studied, depend on the linguistic character of the text, such as the syntactic and the lexical differences between narrative and dialogue texts. Finally, these results are in line with previous works that claimed that bag-of-words-based features are very effective indicator of the stylistic character of a text that can enable more accurate text attribution [START_REF] Argamon | Measuring the usefulness of function words for authorship attribution[END_REF].

Feature

Conclusion

In this contribution, we present a comparative study on using two different types of style marker based on function words for authorship attribution. We compared the effectiveness of using sequential rules of function words as style marker that do not relay on the bag-of-words assumption to that of the frequency of function words which does. To evaluate the effectiveness of these markers, we conducted an experiment on a classic French corpus. Our results show that contrary to common sense, the frequencies of function words outperformed the sequential rules.

Based on the current study, we have identified several future research directions. First, we will explore the effectiveness of using probabilistic heuristics to find a minimal sequential rule set that still allows good attribution performance, which can be very useful for stylistic and psycholinguistic analysis. Second, this study will be expanded to include sequential patterns (ngrams with gaps) as sequential style markers. Third, we intend to experiment with this new type of style markers for other languages and text sizes using standard corpora employed in the field at large.

  are true positives, 56 are true negatives, -6 are false negatives, and -, are false positives.

  treated each chapter of each book as a separate text. Since we are considering a sentence as a sequence unit, in our experiment we chose to slice novels by the size of the smallest one in the collection in terms of number

	of sentences.
	More information about the data set used in the experiment is presented in
	Table 2.
	Author Name	# of	# of
		words	texts
	Balzac, Honoré de	548778	20
	Dumas, Alexandre	320263	26
	France, Anatole	218499	21
	Gautier, Théophile	325849	19
	Hugo, Victor	584502	39
	Maupassant, Guy de	186598	20
	Proust, Marcel	700748	38
	Sand, George	560365	51
	Sue, Eugène	1076843	60
	Zola, Émile	581613	67

http://www.gutenberg.org/

http://gallica.bnf.fr/

Acknowledgment

This work was supported by French state funds managed by the ANR within the Investissements d'Avenir programme under reference ANR-11-IDEX-0004-02.


Mohamed-Amine Boukhaled
email: mohamed.boukhaled@lip6.fr

Francesca Frontini
email: francesca.frontini@lip6.fr

Jean-Gabriel Ganascia
email: jean-gabriel.ganascia@lip6.fr

A Peculiarity-based Exploration of Syntactical Patterns: a Computational Study of Stylistics

Keywords: Computational Stylistics, Interestingness Measure, Sequential Pattern Mining, Syntactic Style

In this contribution, we present a computational stylistic study and comparison of classic French literary texts based on a datadriven approach where discovering interesting linguistic patterns is done without any prior knowledge. We propose an objective measure capable of capturing and extracting meaningful stylistic syntactic patterns from a given author's work. Our hypothesis is based on the fact that the most relevant syntactic patterns should significantly reflect the author's stylistic choice and thus they should exhibit some kind of peculiar overrepresentation behavior controlled by the author's purpose with respect to a linguistic norm. The analyzed results show the effectiveness in extracting interesting syntactic patterns from novels, and seem particularly promising for the analysis of such particular texts.

Introduction

Computational stylistics is a subdomain of computational linguistics located at the intersection of several research areas such as natural language processing, literary analysis and data mining. The goal of computational stylistics is to extract style patterns characterizing a particular type of texts using computational and automatic methods [START_REF] Craig | Stylistic analysis and authorship studies[END_REF]). When investigating the writing style of a particular author, the task will automatically explore linguistic forms of his style, which is not only distinguishing features, but also the deliberate overuse of certain structures by the author compared to a linguistic norm [START_REF] Mahlberg | Corpus stylistics and Dickens's fiction[END_REF]. However, the notion of style in the context of computational stylistics appears to be wide enough, and is manifested on several linguistic levels: lexicon, syntax, semantics and pragmatics. Each level has its own markers of styles and its own linguistic units that characterize it.

Many works have been done in the literature to analyze the stylistic traits on these different linguistic levels [START_REF] Biber | University language: A corpus-based study of spoken and written registers[END_REF][START_REF] Biber | Register, genre, and style[END_REF][START_REF] Ramsay | Reading machines: Toward an algorithmic criticism[END_REF], Frontini et al. 2014; see [START_REF] Siemens | A companion to digital literary studies[END_REF] for a discussion and overview ). In this contribution, syntactic style will be targeted.

In their study [START_REF] Quiniou | What about sequential data mining techniques to identify linguistic patterns for stylistics?[END_REF] have shown the interest of using sequential data mining methods for the stylistic analysis of large texts. They have shown that relevant and understandable patterns that are characteristic of a specific type of text can be extracted using sequential data mining techniques such as sequential pattern mining. However, the process of extracting textual patterns is known by its property of producing a large amount of patterns, even from a relatively small sample of text. Thus, a measure of interest is to be applied to identify the most important and relevant patterns for the characterization of the text's style in question.

In this paper, we present a computational stylistic study of classic texts of French literature based on a data-driven approach where the discovery of interesting linguistic forms is done without any prior knowledge. Specifically, the proposed method is based on the assessment of the peculiar overrepresentation of syntactic patterns extracted using sequential data mining technique from texts with respect to a norm corpus. This method is intended to quantitatively support a textual analysis by focusing on the verification of the degree of importance of each syntactic pattern (syntagmatic segments with potential gaps), and by extracting the syntactic patterns that characterize the syntactical style of a work by a particular author.

Approach for extracting relevant syntactic patterns

Our method consists of two steps. First, a sequential pattern mining algorithm is applied to the texts in order to extract recurrent syntactic patterns. Second, a peculiarity-based interestingness measure that evaluates of the overrepresentation (in terms of frequency of occurrence with respect to a norm corpus) is applied to the set of extracted syntactic patterns. Thus, each syntactic pattern will be assigned an interestingness value indicating its importance and its relevance for the characterization of text's syntactic style. In what follows, we present in section 2.1 the corpus used in our experience, and its dividing protocol into two parts: text to analyze and text used as norm. Then, section 2.2 introduces some elements necessary to understand the process of extracting sequential syntactic patterns. Finally, the formulation and the statistical details of the proposed interestingness measure are presented in Section 2.3.

Analyzed Corpus

In our study, we used four novels, belonging to the same genre and the same literary time span, written by four famous classic French authors: Balzac's "Eugenie Grandet", Flaubert's "Madame Bovary", Hugo's "Notre Dame de Paris" and Zola's "Le ventre de Paris". This choice is motivated by our particular interest in studying the style of the classical French literature of the 19th century. At the time of the analysis of the syntactic patterns, each text written by one of the four authors is contrasted with texts written by the three other authors. That is to say that these three texts will be considered as norm corpus from which we will evaluate the hypothesis of the overrepresentation of syntactic patterns in the fourth remaining text, as explained later in this section.

Extraction of syntactic patterns

In our study we consider a syntagmatic approach. The text is first segmented into a set of sentences, each sentence is then represented by a sequence of syntactic labels (POS-tag)1 corresponding to the words of the sentence using Treetagger [START_REF] Schmid | Probabilistic part-of-speech tagging using decision trees[END_REF]. This produces at the end a set of syntactic sequences for each text. For exemple, the sentence "Le silence profond régnait nuit et jour dans la maison." Will be represented by the sequence:

< , , , , , , , , , , >
Then, sequential patterns of a certain length with their supports (a number indicating how many sentences contain the pattern) are extracted from this syntactic sequential database using a sequential pattern extraction algorithm [START_REF] Viger | SPMF: A Java Open-Source Pattern Mining Library[END_REF]. Syntactic pattern consists of a sequential syntagmatic segment (with possible gaps) present in the syntactic sequences. It can be considered as a kind of generalization of the notion of n-gram widely used in the field of automatic language processing. Examples of syntactic patterns present in the sequence of the example above:

• < >< >< > • < >< >< >< > • < >< > < * 2 > < >< >
To avoid the effect of statistical fluctuations on the analysis of patterns with low supports, we considered a support's threshold of 1%. That is to say that we focus only on patterns that are present in at least 1% of the sentences of the analyzed text. However, as sequential pattern mining is known to produce a large quantity of patterns even from relatively small samples of texts, an interestingness measure should be applied on these patterns in order to identify the most important ones. This interestingness measure is explained in the next section.

Evaluation of the relevance of syntactic patterns

Our hypothesis to evaluate the relevance of a syntactic pattern is based on the fact that the most relevant ones should significantly reflect the stylistic choice of the author and should thus be characterized by a significant peculiar quantitative behavior, this peculiar behavior translate into a support's overrepresentation in his texts. However, to capture this overrepresentation one cannot refer only to the absolute frequency of occurrence (support) Indeed, more frequent use of a syntactic pattern by an author (which translates into a relatively high support) does not necessarily indicate a stylistic choice since it can be very well a property imposed by the grammar of the language or by syntactic features that are characteristic of text's genre. Thus, to assess the over-representation of a pattern, we use an empirical approach based on the comparison of the support of a syntactic pattern in a text to that found in a norm corpus. A ratio between these two quantities is calculated as follow:

= frequency of a pattern in the norm corpus frequency pattern in the text

In our experiments we found empirically that the distribution of the ratio exhibits a Gaussian behavior. Indeed, the values of the ratio are normally distributed around a central value (see Fig. 1). This is due to the fact that the frequency of occurrence of a syntactic pattern in a text is highly correlated with the frequency of occurrence in the norm corpus with a few exceptional special cases or outliers (see Fig. 2). These outliers represent the patterns of special interest for our study because they represent a certain linguistic deviation that is specific to the author's style compared to what one would expect to see in the norm corpus.

The configuration described above allows us to use an outlier detection method based on Gaussian distribution and '-score to identify such special patterns [START_REF] Chandola | Anomaly detection: A survey[END_REF]). The over-representation of a pattern in this case will result in a greater negative aberrant behavior compared to other patterns.

The most over-represented patterns will be those associated with lowest values of standard z-score '. The z-score values are calculated as follows:

' ( = ( ) *
Where ( and ' ( are respectively the ratio and the z-score corresponding to the +-th syntactic pattern. , and are respectively the mean and standard deviation of the ratio .

Results and Discussion

In this section, we present some examples of relevant syntactic patterns extracted from our corpus. Using the proposed method, the extracted patterns seem to have a strong relevance to characterize the style of the authors of our corpus but also to the novels' content and the literary genre in which it operates. In the Flaubert's Madame Bovary, several extracted patterns well represent the rhythmic rather than functional role of punctuation that is peculiar to the style of Flaubert [START_REF] Mangiapane | Ponctuation et mise en page dans Madame Bovary: les interventions de Flaubert sur le manuscrit du copiste. Flaubert[END_REF]. For example pattern (1) captures instances of a comma preceding the conjunction, followed by a parenthetical clause.

Pattern (1)

<PUN> < KON>< PUN> <PRP>, with support= 113, sample instances of the pattern in the text:

• , et , à • , mais , avant • ; et , à
In le Ventre de Paris of Zola, and in the same direction, the syntactic patterns extracted as relevant clearly represent the use of nested clauses to describe situations or attitudes in the novel such as in the pattern (2), or to describe public places and objects in displays in long lists as in the pattern In Eugénie Grandet of Balzac, other different communicative functions are performed by the syntactic patterns and their textual instances, for example: Pattern (4): <PUN> <VER> <NAM> <PRP>, support= 49, which is used as post-introducer of direct speech. This rather formulaic way of specifying (in a parenthetical form) the utterer of a reported speech is common to all, but seems to be strongly preferred by Balzac, while the other authors have shown a more varied style in introducing dialogues. Sample instances of the pattern in the novel:

•

, dit Grandet en The few analyzed examples indicate that the presented technique is effective in extracting interesting syntactic patterns from a single text, and this seems particularly promising for the analyses of such classic literary texts. On the other hand, this technique, as well as other similar ones, prompts the question of what is really captured by significant patterns. Some structures may be significant because they are typical of an author's style, its fingerprint -as we may say borrowing a metaphor often used in attribution studies, or they may be dictated by functional needs, due to the particular topic of the novel, or to the conventions of the chosen genre. This is particularly true for syntactic analysis, where the functional constraints on the authorial freedom are more evident. Much further works have to be carried out concerning this issue.

Conclusion

In this paper, we have presented an objective interestingness measure to extract meaningful stylistic syntactic patterns from a given author's work. Our hypothesis is based on the fact that the most relevant syntactic patterns should significantly reflect the author's stylistic choice and thus they should exhibit some kind of peculiar overrepresentation behavior controlled by the author's purpose. To evaluate the effectiveness of the proposed method, we conducted an experiment on a classic French Corpus. The analyzed results show the effectiveness in extracting interesting syntactic patterns from this type of text.

Based on the current study, we have identified several future research directions such as exploring other statistical measures to assess the interestingness of a given syntactic pattern, and expanding the analysis to include morphosyntactic patterns (form and lemma words). Finally, we intend to experiment with other languages and text sizes using standard corpora employed in the field of computational stylistics at large.

Fig. 1 .Fig. 2 .

 12 Fig. 1. Gaussian behaviour of the ratio in Balzac's "Eugénie Grandet" novel

  : Pattern (2) : <PUN> <PRP> <PRP> <NOM>, support= 104, sample instances of the pattern in the text (bold text): « Florent se heurtait à mille obstacles , à des porteurs qui se chargeaient , à des marchandes qui discutaient de leurs voix rudes ; il glissait sur le lit épais d' épluchures et de trognons qui couvrait la chaussée , il étouffait dans l' odeur puissante des feuilles écrasées .» Pattern (3): <NOM> <PUN> <PRP> <NOM> <ADJ>, support= 68, sample instances of the pattern in the text (bold text): • angles , à fenêtres étroites • très-jolies , des légendes miraculeuses • écrevisses , des nappes mouvantes

Frech treetagger tagset: http://www.cis.unimuenchen.de/~schmid/tools/TreeTagger/data/french-tagset.html

<*> denotes a gap that can be filled with any POS tag

Acknowledgment

This work was supported by French state funds managed by the ANR within the Investissements d'Avenir programme under reference ANR-11-IDEX-0004-02.


Frédéric Mazenc
email: frederic.mazenc@l2s.centralesupelec.fr

Vincent Andrieu
email: vincent.andrieu@gmail.com

Michael Malisoff
email: malisoff@lsu.edu

Design of Continuous-Discrete Observers for Time-Varying Nonlinear Systems *

Keywords: observer, continuous-discrete observers, cooperative system, Metzler matrix

We present a new design for continuous-discrete observers for a large class of continuous time nonlinear time-varying systems with discrete time measurements. Using the notion of cooperative systems, we show that the solutions of the observers converge to the solutions of the original system, under conditions on the nonlinear terms and on the largest sampling interval. Our conditions are given by explicit expressions.

Introduction

In real world applications, the state variables may be difficult to measure. Such applications can often be modeled using systems with outputs. Then one builds an observer for the state such that the observation error between the observer value and the state value converges to 0 as time goes to ∞. Much of the observers literature is under continuous measurements. See, e.g., [START_REF] Zemouche | Observers for a class of Lipschitz systems with extension to H ∞ performance analysis[END_REF], which gives observers under continuous state measurements, by expressing the differential equation satisfied by the estimation error in terms of a linear parameter varying system. However, in many engineering applications, measurements are collected at discrete times. This produces continuousdiscrete systems, where the dynamics are continuous time but the output measurements are only available at discrete instants. There is a large literature, spanning over 40 years, on ways to build observers for continuous-discrete systems. See, e.g., [START_REF] Jazwinski | Stochastic Processes and Filtering Theory[END_REF], which used a continuous-discrete Kalman filter to solve a filtering problem for stochastic continuous-discrete time systems.

The high gain observer in [START_REF] Gauthier | A simple observer for nonlinear systems applications to bioreactors[END_REF] was adapted to continuous-discrete systems in [START_REF] Deza | High gain estimation for nonlinear systems[END_REF], where the correction gain of the impulsive correction is obtained by integrating a continuous-discrete time Riccati equation. The robustness of observers with respect to discretization was studied in [START_REF] Arcak | A framework for nonlinear sampled-data observer design via approximate discretetime models and emulation[END_REF]. See also Ahmed-Ali et al. (2013b); [START_REF] Farza | Continuous-discrete time observers for a class of MIMO nonlinear systems[END_REF]; [START_REF] Karafyllis | From continuoustime design to sampled-data design of observers[END_REF] for observers based on output predictors and [START_REF] Andrieu | Observer design for Lipschitz systems with discrete-time measurements[END_REF]; [START_REF] Deza | High gain estimation for nonlinear systems[END_REF]; [START_REF] Hammouri | Constant gain observer for continuous-discrete time uniformly observable systems[END_REF]; Mazenc andDinh (2013, 2014); [START_REF] Tellez-Anguiano | Nonlinear continuous-discrete observer application to distillation columns[END_REF]; [START_REF] Karafyllis | Global exponential observers for two classes of nonlinear systems[END_REF]; and see Ahmed-Ali et al. (2013a), which presents results that allow delayed and sampled measurements. The work [START_REF] Ahmed-Ali | Continuous-discrete adaptive observers for state affine systems[END_REF] builds continuous-discrete observers for nonlinear systems, where the input acts on the system to satisfy a persistent excitation condition, while [START_REF] Nadri | Design of a continuous-discrete observer for state affine systems[END_REF] covers systems with known inputs and which are linear in the state. The work [START_REF] Karafyllis | From continuoustime design to sampled-data design of observers[END_REF] shows that if a system admits a suitable continuous time observer and the observer satisfies certain robustness properties, then one can augment the observer by a new output predictor system to produce a continuous-discrete observer. Also, [START_REF] Karafyllis | From continuoustime design to sampled-data design of observers[END_REF] shows how this observer augmentation process applies to key classes of linear and triangular globally Lipschitz systems. See Remark 3 below for more discussions on [START_REF] Karafyllis | From continuoustime design to sampled-data design of observers[END_REF]; and [START_REF] Astorga | Nonlinear continuous-discrete observers: Applications to emulsion polymerization reactors[END_REF] for continuous-discrete observers for an important model of emulsion polymerization reactors.

Here, we revisit [START_REF] Andrieu | Observer design for Lipschitz systems with discrete-time measurements[END_REF]. We present a new construction of continuous-discrete observers (which are also called hybrid observers in the literature) for continuous time Lipschitz systems with discrete time measurements. Following the approach in [START_REF] Andrieu | Observer design for Lipschitz systems with discrete-time measurements[END_REF]; [START_REF] Deza | High gain estimation for nonlinear systems[END_REF], our continuous-discrete observer is obtained in two steps. First, when no measurement is available, the state estimate is computed by integrating the model. Then, when a measurement occurs, the observer makes an impulsive correction to the estimate. The work [START_REF] Andrieu | Observer design for Lipschitz systems with discrete-time measurements[END_REF]; [START_REF] Dinh | Continuous-discrete time observer design for Lipschitz systems with sampled measurements[END_REF] used this type of algorithm to show that when no measurement occurs, the estimation error is a solution to an unknown linear parameter varying system. This gave a continuous-discrete analog of the continuous time measurement approach from [START_REF] Zemouche | Observers for a class of Lipschitz systems with extension to H ∞ performance analysis[END_REF], and makes it possible to build a set that is guaranteed to contain all relevant solutions for all nonnegative times. Using this set, certain correction terms are designed to ensure that the estimation error asymptotically converges to zero. However, [START_REF] Andrieu | Observer design for Lipschitz systems with discrete-time measurements[END_REF]; [START_REF] Dinh | Continuous-discrete time observer design for Lipschitz systems with sampled measurements[END_REF] find the set by integrating a system with commutation, which does not lead to an explicit analytic expression. This may be an obstruction to using this type of approach in applications. Here, we use tools that are inspired by [START_REF] Haddad | Nonnegative and Compartmental Dynamical Systems[END_REF]; [START_REF] Cacace | A new approach to the internally positive representation of linear MIMO systems[END_REF]; [START_REF] Mazenc | Continuous-discrete interval observers for systems with discrete measurements[END_REF]; [START_REF] Raissi | Interval state estimation for a class of nonlinear systems[END_REF]. We obtain analytical methods for constructing sets that are guaranteed to contain the relevant trajectories. Our results are strong and may be better suited to applications, since we allow nonlinearities in the systems and because we prove robustness to perturbations in the sampling schedule.

In the next section, we provide definitions. In Section 3, we present our new results on framers, which are of independent interest. In Section 4, we use our new results on framers to prove our theorem on continuous-discrete observers. Our closed form formulas for the framers make it possible to check the assumptions using linear matrix inequalities. We illustrate our main result in Section 5, using a motor dynamics and a pendulum system, which show how our approach can lead to a much larger maximal allowable measurement stepsize than was reported in [START_REF] Dinh | Continuous-discrete time observer design for Lipschitz systems with sampled measurements[END_REF]. In Section 6, we summarize the value added by our work and suggest possible topics for follow-up research.

For a tutorial paper on the theory of continuous-discrete observers that states results from this and other recent papers (without giving their proofs and also without the examples we provide below) and also contains a generalization of Lemma 3 below, see Mazenc et al. (2015, to appear).

Notation, Definitions, and Basic Result

Throughout the sequel, we omit arguments of functions when the arguments are clear from the context. We set N = {1, 2, . . .}. For any k and n in N, the k × n ma-trix all of whose entries are 0 will also be denoted by 0, and we use A = [a i,j ] to indicate that an arbitrary matrix A ∈ R k×n has a i,j in its ith row and jth column for each i ∈ {1, 2, . . . , k} and j ∈ {1, 2, . . . , n}. The usual Euclidean norm of vectors, and the induced norm of matrices, of any dimensions are denoted by | • |, and I is the identity matrix in the dimension under consideration. All inequalities and maxima must be understood to hold componentwise, i.e., if A = [a i,j ] and B = [b i,j ] are matrices of the same dimensions, then we use A ≤ B to mean that a i,j ≤ b i,j for all i and j, and max{A, B} is the matrix C = [c i,j ] where c i,j = max{a i,j , b i,j } for all i and j. A square matrix is called cooperative or Metzler provided all of its off-diagonal entries are nonnegative. Recall that the Schur complement of a symmetric matrix of the form

X = A B B C with an invertible matrix A is S = C -B A -1 B,
where means the transpose. The following is well known: X is positive definite if and only if A and S are both positive definite. For each r ∈ N and each function F : [0, ∞) → R r , we set F(t -) = lim s→t,s<t F(s) for all t > 0. For any matrices A and B in R n×n , we use A B (resp., A B) to mean that X (A -B)X ≤ 0 for all X ∈ R n (resp., X (A -B)X > 0 for all X ∈ R n \ {0}). Therefore, has a different meaning from the partial order ≥ on matrices.

A system ẋ(t) = f (t, x(t)) whose solution is uniquely defined on [t 0 , ∞) for each initial condition x(t 0 ) and each t 0 ≥ 0 is called nonnegative provided that for each initial condition satisfying x(t 0 ) ≥ 0, the solution x(t) is nonnegative for all t ≥ t 0 . The following lemma is a direct consequence of (Haddad et al., 2010, Proposition 2.2):

Lemma 1 Consider any system of the form

ż(t) = A(t)z(t) + B(t) (1)
with state space R n , where A : R → R n×n and B : R → R n are continuous. Assume that for all t ≥ 0, the matrix A(t) is Metzler and B(t) ≥ 0. Then (1) is nonnegative.

Preliminary Result on Framers

In this section, we present preliminary results on framers for linear systems that we use in the next section to design our observers for nonlinear systems. We consider any linear time-varying system of the form

ẋ(t) = M(t)x(t) (2)
with state space R n , where all entries of M : [0, ∞) → R n×n are continuous. Let : R 2 → R n×n denote the fundamental solution of (2). Then, ∂ ∂t (t, t 0 ) = M(t) (t, t 0 ) and (t 0 , t 0 ) = I hold for all t 0 ≥ 0 and t ≥ t 0 . In this section, we provide componentwise lower and upper bounds for Γ(t) = (t, 0). Notice for later use that the unique solution φ(•, x 0 ) of the initial value problem (∂φ/∂t)(t, x 0 ) = M(t)φ(t, x 0 ), φ(0, x 0 ) = x 0

(3) satisfies φ(t, x 0 ) = Γ(t)x 0 for all t ≥ 0 and x 0 ∈ R n .

Bounds for Cooperative Linear Systems

We first present a preliminary result on framers, which we use in the next subsection to prove our main result on framers. Throughout this subsection, we assume:

Assumption 1 There are two constant Metzler matrices M ∈ R n×n and M ∈ R n×n such that

M ≤ M(t) ≤ M (4)
hold for all t ≥ 0. Also, M is continuous.

We can then prove:

Lemma 2 If (2)
ψ(t, x 0 ) ≥ 0 , ψ(t, x 0 ) ≥ 0 , and φ(t, x 0 ) ≥ 0 (6)
hold for all t ≥ 0 and x 0 ≥ 0, where the nonnegativity of the flow map φ(t, x 0 ) for ( 2) is also from Lemma 1.

Fix any componentwise nonnegative

x 0 ∈ R n . Then ρ(t, x 0 ) = ψ(t, x 0 ) -φ(t, x 0 ) satisfies ρ(t, x 0 ) = M ψ(t, x 0 ) -M(t)φ(t, x 0 ) = M ρ(t, x 0 ) + M -M(t) φ(t, x 0 ) (7)
for all t ≥ 0. Assumption 1 and the fact that φ(t, x 0 ) ≥ 0 give (M-M(t))φ(t, x 0 ) ≥ 0 for all t ≥ 0. Since M is Metzler and ρ(0, x 0 ) ≥ 0, we can apply Lemma 1 with A = M and

B(t) = (M -M(t))φ(t, x 0 ) to get ρ(t, x 0 ) ≥ 0 for all t ≥ 0. Next note that ρ(t, x 0 ) = φ(t, x 0 ) -ψ(t, x 0 ) satisfies ρ(t, x 0 ) = M(t)φ(t, x 0 ) -Mψ(t, x 0 ) = M(t)ρ(t, x 0 ) + M(t) -M ψ(t, x 0 ) (8)
for all t ≥ 0. Arguing as we did to show that ρ(t, x 0 ) ≥ 0 proves that ρ(t, x 0 ) ≥ 0 for all t ≥ 0. Thus,

ψ(t, x 0 ) ≤ φ(t, x 0 ) ≤ ψ(t, x 0 ) (9)
hold for all t ≥ 0 and x 0 ≥ 0. These inequalities can be written as exp(Mt)x 0 ≤ Γ(t)x 0 ≤ exp(Mt)x 0 . Since they hold for each standard basis vector x o = e i for i = 1, 2, . . . , n and all t ≥ 0, the result follows.

Bounds for General Time-Varying Linear Systems

In this part, we consider the system (2) under the following much weaker assumption than Assumption 1:

Assumption 2 The matrix valued function M : [0, ∞) → R n×n is bounded and continuous.
Assumption 2 provides functions K : R → R n×n and L : R → R n×n , a constant matrix L ≥ 0, and constant Metzler matrices K ∈ R n×n and K ∈ R n×n such that

M(t) = K(t) -L(t), 0 ≤ L(t) ≤ L, and K ≤ K(t) ≤ K (10)
hold for all t ≥ 0. The preceding decomposition can be found by replacing the entries of M(t) = [m i,j (t)] by m i,j (t) + B for a big enough constant B > 0 to produce the Metzler matrices K(t), and then letting L = L be the constant matrix having B as each entry, and K = 0. However, other decompositions of the type (10) exist. We prove:

Lemma 3 Let the system (2) satisfy Assumption 2, and let L, K, L ∈ R n×n , K ∈ R n×n , and K ∈ R n×n satisfy the preceding requirements. Define the

C 1 functions Γ : [0, ∞) → R n×n and Γ : [0, ∞) → R n×n by Γ(t) = e Kt + 1 2 e (K-L)t -e (K+L)t and Γ(t) = 1 2 e (K+L)t + e (K-L)t . ( 11
)
Then the Γ(t) ≤ Γ(t) ≤ Γ(t) hold for all t ≥ 0.

Proof: We introduce the matrices

H(t) = K(t) L(t) L(t) K(t) , H = K L L K
, and

H = K 0 0 K . ( 12
)
Then for the flow map φ(t, x 0 ) of ( 2), the function z(t) = (φ(t, x 0 ), -φ(t, x 0 )) taking values in R 2n satisfies ż(t) = H(t)z(t) for all t ≥ 0 and x 0 ∈ R n . This motivates our study of the system

Λ(t) = H(t)Λ(t) (13)
and its fundamental matrix

G : [0, ∞) 2 → R 2n×2n .
Set Ω(t) = G(t, 0). Then, Ω(0) = I, and the maximal solution of (13) for any initial state Λ(0

) = a ∈ R 2n is Λ(t) = Ω(t)a.
We introduce the block decomposition

Ω(t) = Ω 1,1 (t) Ω 1,2 (t) Ω 2,1 (t) Ω 2,2 (t) , ( 14
)
where Ω i,j (t) ∈ R n×n for all t, i, and j. Since we have (φ(t, x 0 ), -φ(t, x 0 )) is a solution of (13) that satisfies (φ(0, x 0 ), -φ(0, x 0 )) = (x 0 , -x 0 ) for all x 0 ∈ R n , we can use the existence and the uniqueness of solutions of (13) and the fact that φ(t, x 0 ) = Γ(t)x 0 for all t ≥ 0 and

x 0 ∈ R n to get Γ(t)x 0 -Γ(t)x 0 = Ω(t) x 0 -x 0 = (Ω 1,1 (t) -Ω 1,2 (t))x 0 (Ω 2,1 (t) -Ω 2,2 (t))x 0 (15)
for all t ≥ 0. Since the preceding equalities are satisfied for all x 0 ∈ R n , we deduce that

Γ(t) = Ω 1,1 (t) -Ω 1,2 (t) (16)
holds for all t ≥ 0. Moreover, for all t ≥ 0, we have H ≤ H(t) ≤ H, and both H and H are Metzler. Hence, Lemma 2 applies to (13). It ensures that the inequalities exp(Ht) ≤ Ω(t) ≤ exp(Ht) are satisfied for all t ≥ 0. Since the matrices [I 0] and [I 0] are nonnegative, we deduce that [I 0] e Ht I 0

≤ [I 0] Ω(t) I 0 ≤ [I 0] e Ht I 0 (17)
holds for all t ≥ 0. This and similar arguments give

e Kt ≤ Ω 1,1 (t) ≤ [I 0] e Ht I 0 and 0 ≤ Ω 1,2 (t) ≤ [I 0] e Ht 0 I (18)
for all t ≥ 0. By combining ( 16) and ( 18), we deduce that

e Kt -[I 0] e Ht 0 I ≤ Γ(t) ≤ [I 0] e Ht I 0
for all t ≥ 0. The conclusion now follows from our lemma in the appendix, applied with H = H.

Remark 1 Lemma 3 does not require M to be known. Instead, we only need to know that M is bounded and continuous, and we need to know the bounding matrices L, K, and K. Assume that the only information we know about M is that it is continuous, and that there are constant Metzler matrices M and M such that M ≤ M(t) ≤ M hold for all t ≥ 0. Then, Lemma 3 gives the best possible estimate of Γ(t). To see why, notice that in that case, we can choose M(t) = K(t), K = M, K = M, and L(t) = L = 0. Then Lemma 3 gives exp(Kt) ≤ Γ(t) ≤ exp(Kt) for all t. No better bounds can be obtained, because the cases Γ(t) = exp(Kt) and Γ(t) = exp(Kt) can occur. However, if M(t) is not lower bounded by a Metzler matrix, then Lemma 3 can be conservative. For example, take

M(t) = 0 1 -1 0 , K(t) = K = 0 1 0 0 , L(t) = L = 0 0 1 0 , ( 19
)
and K = 0. Then, Γ(t) is bounded, but Lemma 3 gives the unbounded framing functions Γ(t) and Γ(t).

4 Continuous-Discrete Observer

Main Result

We next propose a new solution to the problem of constructing exponentially stable continuous-discrete ob-servers for nonlinear Lipschitz systems with discrete measurements. Our solution relies on Lemma 3.

Let ν > 0 and ν > ν be any two constants, and fix any sequences {t i } and {ν i } in [0, ∞) such that

t 0 = 0 , t i+1 = t i + ν i ,
and

ν i ∈ [ν, ν] for all i ∈ N. ( 20
)
The t i 's will serve as the measurement times for the output in our nonlinear system

ẋ * (t) = A * x * (t) + ϕ * (t, x * (t)) + B * u(t) y * (t) = C * x * (t i ) for all t ∈ [t i , t i+1 ) and i ∈ N (21)
with discrete measurements, where x * and y * are valued in R n and R p respectively for any n and p and where the input u is valued in R q for any choice of q ∈ N. The matrices A * , B * , and C * are constant. Assume:

Assumption 3 There is a constant invertible matrix P ∈ R n×n such that the matrix A = P A * P -1 is Metzler. Also, (

ϕ * : [0, ∞) × R n → R n is
) 22
Then the Fundamental Theorem of Calculus (applied to the function

f (r) = ϕ(t, r(b -a) + a) on the interval [0, 1]) gives ϕ(t, b) -ϕ(t, a) = [ 1 0 (∂ϕ/∂x)(t, r(b -a) + a)dr](b -a) = w(t, a, b)(b -a)
for all t ≥ 0, a ∈ R n , and b ∈ R n . Also, it follows from Assumption 3 that there are nonnegative constants v i,j such that each entry of w

= [w i,j ] satisfies w i,j (t, a, b) ∈ [-v i,j , v i,j ] for all t ≥ 0, a ∈ R n , b ∈ R n , i ∈ {1, ..., n}, and j ∈ {1, ..., n}. Let D = diag{v 1,1 , ..., v n,n } ∈ R n×n and V = [v i,j ] ∈ R n×n ,
and choose the functions

β(ρ) = e (A-D)ρ + 1 2 e (A+D)ρ -e (A+2V -D)ρ and β(ρ) = 1 2 e (A+2V -D)ρ + e (A+D)ρ . (23)
In terms of our bounds ν and ν from (20) and the preceding matrices, our final assumption is:

Assumption 4 There exist a constant matrix K ∈ R n×p , a constant κ ∈ (0, 1), and a constant symmetric positive definite matrix Q ∈ R n×n such that for each constant matrix β ∈ R n×n satisfying

β(ρ) ≤ β ≤ β(ρ) for some ρ ∈ [ν, ν] , (24)
the matrix inequality

β (I -KC) Q(I -KC)β κQ is satisfied.
See the next subsection for ways to verify Assumption 4. We prove the following, where we use the convention that x * (0 -) = x * (0), and where λ min > 0 and λ max > 0 denote the smallest and largest eigenvalues of Q, respectively.

Theorem 1 Let the system (21) satisfy Assumptions 3-4 and choose the continuous-discrete observer

       ẋ * (t) = A * x * (t) + ϕ * (t, x * (t)) + B * u(t), for t ∈ [t i , t i+1 ), i ≥ 0 x * (t i ) = x * (t - i ) + P -1 K[y * (t i ) -CP x * (t - i )], for i ≥ 0 . (25)
Then, the dynamics for x * = x * -x * for ( 21) is uniformly globally exponentially stable to 0. In fact,

|x * (t)| ≤ 1 √ κ P -1 P exp ν(|A| + | V |) λmax λmin ×e ln(κ)t/(2ν) |x * (0)| (26)
holds for all t ≥ 0 and all initial states x * (0).

Proof: First note that Assumption 3 implies that the finite escape time phenomenon does not occur. The change of coordinates x = P x * and our definitions give

ẋ(t) = Ax(t) + ϕ(t, x(t))+Bu(t) y * (t) = Cx(t i ) . ( 27
)
with B = P B * . In a similar way, the change of coordinates x = P x * transforms (25) into

       ẋ(t) = Ax(t) + ϕ(t, x(t))+Bu(t), t ∈ [t i , t i+1 ), i ≥ 0 x(t i ) x(t - i ) + K[Cx(t i ) -C x(t - i )], i ≥ 0 . (28)
Using x = x -x, our choice of w in ( 22), and the Fundamental Theorem of Calculus, and recalling that x(t) is continuous, we get x(t i ) = x(t - i ) for all i and therefore also the following observation error dynamics:

       ẋ(t) = Ax(t) + w(t, x(t), x(t))x(t), t ∈ [t i , t i+1 ), i ≥ 0 x(t i ) = (I -KC)x(t - i ), i ≥ 0. ( 29
)
Choose any solutions x(t) and x(t) of ( 28) and ( 27), respectively, and set V (t) = w(t, x(t), x(t)).

Let D V (t) be the diagonal matrix whose diagonal en-tries are the corresponding diagonal entries of V (t) for all t ≥ 0. Then, all of the diagonal entries of

V N (t) = V (t) -D V (t) are zero. Let V p (t) = max{V N (t), 0}, V q (t) = max{V N (t), 0} -V N (t), and A V (t) = A + D V (t) + V p (t) for all t ≥ 0. Then V N = V p -V q .
Also, our choices of V and D imply that 0 ≤ V q (t) ≤ V -D and A-D ≤ A V (t) ≤ A+V hold for all t ≥ 0, so A V has constant Metzler upper and lower bounds. For each integer i ≥ 0 and sample time t i , we next study the system

Ẋ(t) = A + V (t + t i ) X(t) = A V (t + t i ) -V q (t + t i ) X(t) . (30)
In terms of the fundamental solution J i for (30), the function X(t) = Ξ i (t)X 0 is the unique solution for (30) starting at any vector X(0) = X 0 ∈ R n , where Ξ i (t) = J i (t, 0) for each i. Apply Lemma 3 with

K(t) = A V (t + t i ), L(t) = V q (t + t i ), K = A -D, K = A + V , and L = V -D to get: β(t) ≤ Ξ i (t) ≤ β(t) for all t ≥ 0 , (31)
where β and β are defined in (23). Since the observation error dynamics for x(t) = x(t) -x(t

) = P x * (t) are ẋ(t) = [A + V (t)]x(t) t ∈ [t i , t i+1 ), i ≥ 0 x(t i ) = (I -KC)x(t - i ), i ≥ 0 , , (32)
we can apply the preceding argument to the solution X(t) = x(t i + t) of ( 30) on the interval [0, ν i ) for each i. It follows from (31) that the matrix

α i = J i (ν i , 0) ∈ R n×n satisfies x(t - i+1 ) = α i x(t i ) and β(ν i ) ≤ α i ≤ β(ν i ) for each i.
We next give the stability analysis for the discrete time system x(t i+1 ) = (I -KC)α i x(t i ).

Set W (x) = x Qx. By applying Assumption 4 with β = α i and ρ = ν i , and letting λ min > 0 and λ max > 0 be the smallest and largest eigenvalues of Q, respectively, we get W (x(t i+1 )) ≤ κW (x(t i )) and so also |x(t i )| ≤ κ i/2 λ max /λ min |x(0)| for all i ≥ 0. Since κ ∈ (0, 1), we conclude that x(t i ) converges exponentially to zero as i → ∞. Also, using the bound

b = |A| + | V | on |A + V (t)|, we can integrate (32) to get |x(t)| ≤ exp( bν)|x(t i )| for all t ∈ [t i , t i+1
) and all i ≥ 0, where ν is from (20). Moreover, for each integer i ≥ 0 and each t ∈ [t i , t i+1 ], we have t ≤ t i+1 ≤ ν(i + 1), so i ≥ (t/ν) -1. Recalling that κ ∈ (0, 1] and using our exponential decay estimate on x(t i ), we get

|x(t)| ≤ e bν κ ((t/ν)-1)/2 λ max /λ min |x(0)| = (e bν / √ κ)e ln(κ)t/(2ν) λ max /λ min |x(0)| (33)
for all t ∈ [t i , t i+1 ) and i ≥ 0. Since x(t) = P x * (t) for all t ≥ 0, and since the right side of (33) does not depend on i, the result follows.

Remark 2 For all ρ ≥ 0 and componentwise nonnegative matrices M ∈ R n×n , we have exp(M ρ) ≥ I. Using this property, one can prove that

I ≥ exp(-Dρ) + 1 2 exp Dρ -exp (2V -D)ρ (34)
for all ρ ≥ 0 (which can be checked by left multiplying (34) through by exp( Dρ)). If we now left multiply (34) by exp(Aρ), we get exp(Aρ) ≥ β(ρ). Similar reasoning shows that for all ρ ≥ 0 we have

β(ρ) ≤ e Aρ ≤ β(ρ). (35)
Hence, Assumption 4 (applied with β = e Aρ ) implies for some ρ in [ν, ν], we have exp(A ρ)(I -KC) Q(I -KC)exp(Aρ) κQ. This implies that (exp(Aρ) -KCexp(Aρ)) Q(exp(Aρ) -KCexp(Aρ)) -κQ ≺ 0, so exp(A ρ) -exp(A ρ)C K is Schur stable. This means that the pair (exp(A ρ), exp(A ρ)C ) and so also (exp(A ρ), C ) is discrete time controllable for some ρ ∈ [ν, ν]. This implies that a necessary condition for Assumption 4 to hold is that for some ρ in [ν, ν] the pair (e Aρ , C) (or equivalently, (e A * ρ , C * )) is detectable in the usual sense of linear discrete time systems.

Remark 3 Our framers (31) for the fundamental matrix of the observation error dynamics made it possible to get closed form exponential decay estimates (26) on the observer error, which were not available in the state-of-the art results in [START_REF] Karafyllis | From continuoustime design to sampled-data design of observers[END_REF] that used a very different output predictor method from ours and applied the results to linear and globally Lipschitz triangular systems. When u is the zero function, we can rewrite the x * dynamics in (21) as ẋ * (t) = Ψ * (t, x * (t)), where Ψ * (t, x * ) = A * x * + ϕ * (t, x * ). Then (∂Ψ * /∂x)(t, x) will be bounded and continuous, if (∂ϕ * /∂x)(t, x) is bounded and continuous, so we can replace the conditions on ϕ * in Assumption 3 by the requirements that ϕ * is continuous and that (∂ϕ * /∂x)(t, x) is bounded and continuous, and then simply select A * = 0 and P = I. However, different nonzero choices of A * in the decomposition Ψ * (t, x * ) = A * x * + ϕ * (t, x * ) and different choices of P produce different conditions in our Assumption 4, so it may be helpful to consider different nonzero choices of A * . See Section 5 for more discussions on the effects of different possible decompositions on the right side of (21).

One aspect of the approach in [START_REF] Karafyllis | From continuoustime design to sampled-data design of observers[END_REF] is that the observer is not impulsive, and that the estimate is a continuous function of the time. This is made possible by using an output predictor. If our approach and the approach in [START_REF] Karafyllis | From continuoustime design to sampled-data design of observers[END_REF] produce the same limit when the measurement stepsize approaches zero, it is in general very difficult to say which one is more general than the other one. It would be interesting to find a way to use the tools of cooperative systems in this context, to obtain new conditions in the output predictor approach of [START_REF] Karafyllis | From continuoustime design to sampled-data design of observers[END_REF].

Checking Assumption 4 4.2.1 Detectability Based Result

There is a strong relationship between Assumption 4 and the detectability in the continuous time sense of the pair (A, C). To highlight this, let (A, C) be detectable and let us prove that Assumption 4 is satisfied, provided that the bounds on V and D and ν > 0 and (ν/ν) -1 are small enough. In fact, our analysis makes it possible to explicitly determine bounds on the allowable values of V , D ν and (ν/ν) -1. Detectability of (A, C) ensures the existence of a matrix L such that the matrix A + LC is Hurwitz. This property ensures that there exist a symmetric positive definite matrix Q and a constant c > 0 such that that Q(A + LC) + (A + LC) Q -cQ. Therefore, there is a constant ρ 1 > 0 such that for all constants ρ ∈ (0, ρ 1 ], we have

I +ρ(A+LC) Q I +ρ(A+LC) 1 - 3 4 cρ Q. ( 36
)
Since there is a smooth function G such that (I + ρLC)

e ρA = I + ρ(A + LC) + ρ 2 G(ρ) for all ρ ∈ R, there is a constant ρ 2 ∈ 0, min ρ 1 , 1 c
such that for all ρ ∈ (0, ρ 2 ],

(I + ρLC)e ρA Q(I + ρLC)e ρA 1 - cρ 2 Q. ( 37
)
Consider any matrix β such that β(ρ) ≤ β ≤ β(ρ). Defining χ(β, ρ) = β -exp(Aρ), inequality (37) can be rewritten as

[(I +ρLC) (β -χ(β, ρ))] Q(I +ρLC) (β -χ(β, ρ)) 1-cρ 2 Q. ( 38
)
It is equivalent to 39) and ( 40), we obtain

β (I + ρLC) Q(I + ρLC)β -χ(β, ρ) (I + ρLC) Q(I + ρLC)χ(β, ρ) +2χ(β, ρ) (I +ρLC) Q(I +ρLC)β + 1-cρ 2 Q. ( 39
Q √ Q = Q. Combining (
β (I + ρLC) Q(I + ρLC)β 1 -cρ 2 Q +(a -1)χ(β, ρ) (I + ρLC) Q(I + ρLC)χ(β, ρ) + 1 a β (I + ρLC) Q(I + ρLC)β. ( 41
)
Since ρ 2 ∈ (0, 1 c ] and ρ ∈ (0, ρ 2 ), we have (4/(cρ)) -1 > 1. Then, choosing a = (4/(cρ)) -1, we deduce from (41) that

β (I + ρLC) Q(I + ρLC)β 1 -cρ 4 Q + 4 cρ -1 χ(β, ρ) (I + ρLC) ×Q(I + ρLC)χ(β, ρ).
(42)

We will presently prove that the inequalities

β(ρ) -e Aρ ≤ ρ 2 |2V -D|e (|A|+|2V -D|)ρ + ρ 2 |D|e (|A|+|D|)ρ (43)
and

β(ρ) -e Aρ ≤ ρ|D|e (|A|+|D|)ρ + ρ|V -D|e (|A+2V -D|+2|V -D|)ρ (44)
hold for all ρ > 0; see below. Using ( 43)-( 44), we get

|χ(β, ρ)| ≤ ρk(ρ 2 )
, where ( 45)

k(ρ) = nmax V -D 2 e (|A|+|2V -D|)ρ + |D| 2 e (|A|+|D|)ρ , |D|e (|A|+|D|)ρ + |V -D|e (|A+2V -D|+2|V -D|)ρ . (46)
We deduce that there exist ρ 3 ∈ (0, ρ 2 ] and a constant c * > 0 such that for all ρ ∈ (0, ρ 3 ], we have

β (I + ρLC) Q(I + ρLC)β 1 -cρ 4 Q + c * ρ |V | + |D| Q. ( 47
)
Therefore, when |V | + |D| ≤ c 8c * , the matrix inequality

β (I + ρLC) Q(I + ρLC)β 1 - cρ 8 Q (48) is satisfied. Next, let ρ ∈ [ν, ν] with ν = ρ 3 and ν ∈ (0, ν]
to be selected later. Then

β (I + ρLC) Q(I + ρLC)β κ - cν 16 Q, (49)
with κ = 1 -cν 16 ∈ (0, 1). Let K = -νL. Then ( 49) is equivalent to

β [I -KC +(ρ-ν)LC] Q[I -KC +(ρ-ν)LC]β κ - cν 16 Q. (50)
Therefore, if the constant (ν/ν) -1 is sufficiently small,

β [I -KC] Q[I -KC]β κQ. ( 51
)
Thus Assumption 4 is satisfied. Now, let us establish ( 43) and ( 44). It follows from the Mean Value Theorem that for any matrices X ∈ R n×n and Y ∈ R n×n , the inequality

e X+Y -e X ≤ |Y |e |X|+|Y | (52)
is satisfied. Next, observing that β(ρ)-e Aρ = 1 2 e (A+2V -D)ρ -e Aρ + 1 2 e (A+D)ρ -e Aρ and β(ρ)-e Aρ = e (A-D)ρ -e Aρ + 1 2 e (A+D)ρ -e (A+2V -D)ρ we deduce from ( 52) that ( 43) and ( 44) are satisfied.

Linear Matrix Inequality Formalism

It can be convenient to check Assumption 4 using linear matrix inequalities. To see why, let ν > 0 and ν ≥ ν be any constants. We define β and β by ( 23), and we introduce the finite set S of matrices in R n×n that is defined by

S = ω ∈ R n×n : ω = [ω i,j ] and ω i,j ∈ ω i,j , ω i,j
for all i and j} , where ( 53) 54) This allows us to rewrite Assumption 4 as a linear matrix inequality, as follows:

ω i,j = sup l∈[ν,ν] β i,j (l) and ω i,j = inf l∈[ν,ν] β i,j (l). (
Proposition 1 Assume that there are a positive definite symmetric matrix Q ∈ R n×n and a matrix W ∈ R n×p such that for all ω ∈ S, the linear matrix inequality

Q (Q -W C)ω ω (Q -W C) Q 0 (55)
holds. Then Assumption 4 holds with K = Q -1 W and some constant κ.

Proof: Since the mappings β(ρ) and β(ρ) are continuous, and since eigenvalues are continuous functions of the entries of the corresponding matrix, there exists a constant ∈ (0, 1) such that for all ω ∈ S, we have

(1 -)Q (Q -W C)ω ω (Q -W C) (1 -)Q 0 . (56)
Let ρ ∈ [ν, ν] and let β be such that the matrix inequality (24) holds for this value ρ. Note that β is in the closed convex hull of S.

Set K = Q -1 W . Since the matrix inequality (56) is linear in ω, it follows that (1 -)Q (Q -W C)β β (Q -W C) (1 -)Q 0 . (57)
Hence, the Schur complement of the matrix in ( 57) is

(1 -)Q -1 1-β (Q -W C) Q -1 (Q -W C)β = (1 -)Q -1 1-β (I -KC) Q(I -KC)β 0, so κQ β (I -KC) Q(I -KC)β holds with the choice κ = (1 -) 2 . Therefore, Assumption 4 holds.
It is well known that if a linear system with continuous measurement has an observer, and if the measurement process is discretized with sufficiently small sampling time, then there is a continuous-discrete observer. This can be seen in our nonlinear case by noting that if a condition ensuring the existence of an observer in the case of continuous time measurement holds, then Assumption 4 holds when the ν k 's are small enough. This is made precise in the following proposition:

Proposition 2 Let A ∈ R n×n , C ∈ R p×n ,
and V ∈ R n×n be matrices such that there exist a matrix K 0 ∈ R n×p , a constant κ 0 ∈ (0, 1), and a symmetric positive definite matrix Q ∈ R n×n such that

(α 0 -K 0 C) Q + Q(α 0 -K 0 C) -κ 0 Q (58)
is satisfied for all matrices α 0 ∈ R n×n such that A -V ≤ α 0 ≤ A + V . Then there exists a constant ν * > 0 such that for all ν ∈ (0, ν * ], Assumption 4 is satisfied with the choices ν = ν = ν and K = νK 0 and D is the diagonal matrix whose diagonal entries are identical to the corresponding diagonal entries of V .

Proof: Let β and β be the n × n matrix valued functions defined in (23). We prove that there is a constant ν * > 0 such that the following holds: If ν ∈ (0, ν * ] and β ∈ R n×n satisfy β(ν) ≤ β ≤ β(ν), (59) then the linear matrix inequality

β (I -KC) Q(I -KC)β κQ (60)
holds with κ = 1 -1 2 νκ 0 , κ ∈ (0, 1), and K = νK 0 . To this end, first note that by using the change of variables ω = α 0 -A, we see that our assumptions in the proposition can be written as follows: For all ω that satisfy -V ≤ ω ≤ V , the linear matrix inequality

[A -K 0 C + ω] Q + Q[A -K 0 C + ω] -κ 0 Q (61)
holds. Next, observe that we can determine two continuous functions ϕ 1 and ϕ 2 such that for all ν ∈ R,

β(ν) = I + (A + V )ν + ν 2 ϕ 1 (ν) and β(ν) = I + (A -V )ν + ν 2 ϕ 2 (ν). ( 62
)
Let ν > 0 be given and β satisfy (59), and set θ = (β -(I + νA))/ν. Using the equalities (62), we deduce that ( 59) is equivalent to

-V + νϕ 2 (ν) ≤ θ ≤ V + νϕ 1 (ν). Also, (60) is equivalent to [I + ν(A + θ)] (I -νK 0 C) Q(I -νK 0 C) ×[I + ν(A + θ)] 1 -1 2 νκ 0 Q. (63)
By viewing the left side of (63) as a polynomial in ν with matrix coefficients, collecting the coefficients of ν, and moving the terms involving ν 2 , ν 3 , and ν 4 to the right side, it follows that (63) can be written as

Q -νC K 0 Q -νQK 0 C + ν[A + θ ]Q +νQ[A + θ] 1 -1 2 νκ 0 Q + ν 2 ϕ 3 (ν), (64)
for a suitable continuous function ϕ 3 . By subtracting Q from both sides and dividing through by ν, we deduce that (64) is equivalent to

[A -K 0 C + θ] Q + Q[A -K 0 C + θ] -1 2 κ 0 Q + νϕ 3 (ν). (65)
Using the continuity of the ϕ i 's and (61), we can find values ν a > 0 and ν b > 0 such that

[A -K 0 C + θ] Q + Q[A -K 0 C + θ] -0.75κ 0 Q
holds for all θ that satisfy -V + νϕ 2 (ν) ≤ θ ≤ V + νϕ 1 (ν) and all ν ∈ (0, ν a ), and such that

-0.75κ 0 Q -0.5κ 0 Q + νϕ 3 (ν)
for all ν ∈ (0, ν b ). Hence, (65) holds if (a) 0 < ν ≤ min{ν a , ν b ) and (b) the matrix θ satisfies

-V + νϕ 2 (ν) ≤ θ ≤ V + νϕ 1 (ν).
Therefore, we can satisfy our requirements by taking ν * = min{ν a , ν b , 2}.

Illustrations

Pendulum

As in [START_REF] Dinh | Continuous-discrete time observer design for Lipschitz systems with sampled measurements[END_REF], we first study the pendulum model

ẋ1 (t) = x 2 (t), ẋ2 (t) = sin(x 1 (t)), y(t k ) = x 1 (t k ) (66)
with ν = ν = ν, and x 1 and x 2 both real valued. Since x 1 is the position variable, it is realistic to assume that x 1 is measured. We apply Theorem 1. We verify Assumptions 3 and 4 with the choices P = I,

A = 0 1 0 0 , C = [ 1 0 ], ϕ(t, x) = 0 sin(x 1 ) , (67)
To facilitate finding the exponentials, we write

R(A + 2V )R -1 = √ 2 0 0 - √ 2
, where

R -1 = 1 -1 √ 2 √ 2 and R = 1 2 √ 2 √ 2 1 - √ 2 1 . ( 70
)
This gives

e (A+2V )ν = R -1 e √ 2ν 0 0 e - √ 2ν R =   e √ 2ν +e - √ 2ν 2 e √ 2ν -e - √ 2ν 2 √ 2 e √ 2ν -e - √ 2ν √ 2 e √ 2ν +e - √ 2ν 2   . (71)
Therefore, the bounding functions from (23) are

β(ν) = 1 2   3 -e √ 2ν +e - √ 2ν 2 3ν + e -√ 2ν -e √ 2ν 2 √ 2 e - √ 2ν -e √ 2ν √ 2 3 -e √ 2ν +e - √ 2ν 2   and
β(ν) = 1 2   1 + e √ 2ν +e - √ 2ν 2 ν + e √ 2ν -e - √ 2ν 2 √ 2 e √ 2ν -e - √ 2ν √ 2 1 + e √ 2ν +e - √ 2ν 2   .
We now verify Assumption 4, using the linear matrix inequality condition from Proposition 1. Using the YALMIP package from [START_REF] Löfberg | Yalmip: A toolbox for modeling and optimization in MATLAB[END_REF] in MATLAB, combined with the solver SeDuMi from [START_REF] Sturm | Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones[END_REF], we can verify that (55) is satisfied for all ω ∈ S. In fact, when ν = 1.1, condi-tion ( 55) holds for all ω ∈ S when we pick K = [1.000, 0.8976] and Q = 1534 -5.7 -5.7 10.5

. This is an important improvement, if we compare with [START_REF] Dinh | Continuous-discrete time observer design for Lipschitz systems with sampled measurements[END_REF], where the maximal measurement stepsize allowed is 0.668. Figure 1 shows our simulation of the observer using an integration algorithm of the model with a semi-implicit integration step of 0.001 with the initial conditions x 1 (0) = x 2 (0) = 2 and x1 (0) = x2 (0) = 0.

Robotic DC Motor

The pendulum model in Section 5.1 had the form ẋ = Ax + ϕ(t, x) where A is Metzler, so we were able to use the identity transformation P = I in Assumption 3. To see how our Theorem 1 also applies in higher dimensional cases where a more complicated transformation is needed, consider the case of a single-link direct-drive manipulator actuated by a permanent magnet DC brush motor, which produces the following model from [START_REF] Dawson | Integrator backstepping control of a brush DC motor turning a robotic load[END_REF]:

M q + B q + N sin(q) = I, L İ = V e -RI -K B q, where M = J Kτ + mL 2 0 3Kτ + M0L 2 0 Kτ + 2M0R 2 0 5Kτ , N = mL0G 2Kτ + M0L0G Kτ , and B = B0 Kτ (72)
and where J is the rotor inertia, m is the mass of the link, M 0 is the mass of the load, L 0 is the length of the link, R 0 is the radius of the load, G is the gravitational constant, B 0 is the viscous friction coefficient at the joint, q(t) is the position of the load (which is the angular motor position), I(t) is the motor armature current, the coefficient K τ characterizes the electromagnetic conversion of armature current to torque, L is the armature inductance, R is the armature resistance, K B is the back-emf coefficient, and V e is the input current voltage. All of the constants in (72) are positive. See the schematic diagram in Figure 2 for (72). We rewrite (72) in the form

             ẋ1 * = x 2 * ẋ2 * = b 1 x 3 * -a 1 sin(x 1 * ) -a 2 x 2 * ẋ3 * = b 0 U (t) -a 3 x 2 * -a 4 x 3 * y * = x 1 * , (73)
where

x 1 * = q, x 2 * = q, x 3 * = I, U = V e is the control, a 1 = N/M , a 2 = B/M , a 3 = K B /L, a 4 = R/L, b 0 = 1/L,
A * =     0 1 0 0 -a 2 b 1 0 -a 3 -a 4     , ϕ * (t, x * ) =     0 -a 1 sin(x 1
λ 1 = 0, λ 2 = 1 2 -(a 2 + a 4 ) + √ D , and
λ 3 = 1 2 -(a 2 + a 4 ) - √ D . (75)
On the other hand, when D < 0, then A * has the eigenvalues

λ 1 = 0, λ 2 = 1 2 -(a 2 + a 4 ) + i √ -D , and
λ 3 = 1 2 -(a 2 + a 4 ) -i √ -D . (76)
The proof of [START_REF] Mazenc | Interval observers for linear time-invariant systems with disturbances[END_REF], Theorem 2) provides a time-varying transformation x = P (t)x * that transforms the system ẋ * = A * x * + φ * (t, x * ) into a new system ẋ = Ax + φ(t, x) where A is a constant Metzler matrix.

In general, time-varying state transformations may transform the output and the measurement stepsize. Consider the case where the eigenvalues of A * are distinct real num-bers. In that case, we can take A = diag{λ 1 , λ 2 , λ 3 } = M -1 A * M and P = M -1 , where M is a constant matrix whose columns are corresponding eigenvectors for the eigenvalues. If A * has repeated real eigenvalues, then A is the usual real Jordan canonical form and we can again take P to be constant. Then A is Metzler, and the output is time invariant under this transformation. In the new variable x, Therefore, by continuity of β and β in D and V , Assumption 4 also holds for the motor dynamics ẋ = Ax + ϕ(t, x) (with the same K, Q, ν, and ν that we used in the ϕ = 0 case) when a 1 > 0 is a small enough constant and D ≥ 0, because we can make D > 0 and V > 0 as small as we want by making a 1 > 0 small enough (and because we can make ρ > 0 as small as we want to cover the case where λ 2 = λ 3 , where there is a ρe λ2ρ on the super-diagonal of e Aρ ).

We performed numerical tests to verify Assumption 4, using the linear matrix inequality condition from Proposition 1 with ν = ν. We chose a 1 = 2, a 2 = 3, a 3 = 1, a 4 = 1, b 0 = 1, and b 1 = 1. For these values, we can use the YALMIP package from [START_REF] Löfberg | Yalmip: A toolbox for modeling and optimization in MATLAB[END_REF] in MAT-LAB and the SeDuMi solver from [START_REF] Sturm | Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones[END_REF] to verify that (55) holds for all ω ∈ S with ν = ν = ν = 0.4. The correction term obtained in the initial coordinates is K * = P -1 K = (1, -0.196, -0.307) . We report our simulations in Figure 3 below, which show the good performance of our observer.

Remark 4 There are many other possible choices of A * and ϕ * , besides the ones in (74). Another choice would be to replace -a 1 sin(x 1 * ) in ϕ * in (74) by the second order term a 1 (x 1 * -sin(x 1 * )), and then make the corresponding change in the second row of A * . If the eigenvalues of A * are all real numbers, then we can use more traditional time invariant changes of coordinates to produce real Jordan canonical forms that are also Metzler. The preceding analysis makes it possible to find explicit bounds on the allowable values of a 1 that can be used to satisfy our assumptions of our theorem for any choice of the stepsize ν.

Conclusion

We gave a new method for building continuous-discrete observers for a broad class of continuous time systems where only sampled values of the output are available for measurement. We used a cooperative system approach that produces upper and lower bounds for fundamental solutions of time-varying systems. These bounds are of independent interest. We demonstrated our method using a pendulum dynamics, which showed how our approach gives a larger value for the maximal allowable measurement stepsize than the value that was available in the literature. We also illustrated our result using a motor dynamics, where a preliminary change of coordinates was used to put the system in a form that can be covered by our theorem. Some desirable extensions would quantify the effects of uncertainties in the discrete output observations, or time delays in the original system or in the observations, using input-to-state stability and Lyapunov-Krasovskii functionals.

  , r(b -a) + a)dr .

  ) Since Q is symmetric and positive definite, the inequality 2χ(β, ρ) (I + ρLC) Q(I + ρLC)β aχ(β, ρ) (I + ρLC) Q(I + ρLC)χ(β, ρ) + 1 a β (I + ρLC) Q(I + ρLC)β (40) holds for any constant a > 0. The estimate (40) follows by applying the relation ( √ aR -) 0 with the choices R = √ Q(I + ρLC)χ(β, ρ) and S = √ Q(I + ρLC)β where √ Q denotes any symmetric positive definite matrix such that √

  with P = I and u = 0, because A is Metzler and sin(•) is Lipschitz. To check Assumption 4, first note that we haveA + 2V = A + 2V -

Fig. 1 .

 1 Fig. 1. Evolution with Time of the State Component x2 and its Estimation x2.

Fig. 2 .

 2 Fig. 2. Schematic from Dawson et al. (1994) for the Electromechanical System (72)

  Remark 4 for a discussion of other choices of A * and ϕ * ). Then A * is not Metzler. We now use ideas from(Mazenc and Bernard, 2011, Theorem 2) to transform (73) into a system that is covered by Theorem 1;[START_REF] Mazenc | Interval observers for linear time-invariant systems with disturbances[END_REF], Theorem 2) assumed that the matrix being transformed is Hurwitz, but the Hurwitzness is not needed for what follows. Set D = (a 2 -a 4 ) 2 -4a 3 b 1 . If D ≥ 0, then A * has the eigenvalues

  the system satisfies Assumption 3 with u = 0. (If D is negative, then the eigenvalues of A * from (76) are λ 1 = 0 and a conjugate pair and further studies have to be carried out.) To see how we can satisfy Assumption 4, first consider the simplified dynamics ẋ = Ax where A is the Jordan form of A * and ϕ is not present, which corresponds to setting a 1 = b 0 = 0, and where D > 0. Then λ 2 and λ 3 are negative, and (24) is the requirement β = exp(ρA), by taking V = D = 0. Also, since we take C = (1, 0, 0) in the output, the choices Q = I and K = (1/2, 0, 0) give the diagonal matrix exp(ρA )(I -KC) Q(I -KC)exp(ρA) = diag{1/4, exp(2λ 2 ρ), exp(2λ 3 ρ)}. Hence, when ϕ = 0, we can satisfy the requirement exp(ρA )(I -KC) Q(I -KC)exp(ρA) κQ (77) from Assumption 4 for all ρ ∈ [ν, ν] with V = D = 0, Q = I, K = (1/2, 0, 0) , any ν and ν satisfying 0 < ν < ν, and κ = max {1/4, exp(2λ 2 ρ), exp(2λ 3 ρ)} ∈ (0, 1).

Fig. 3 .

 3 Fig. 3. Evolution with Time of the State Components (x2) * = I and (x3) * = q and their Estimation.

  and b 1 = 1/M , so all of the a i 's and b i 's in (73) are positive constants. We can write (73) in the form ẋ * = A

* x * + ϕ * (t, x * ) and y * = C * x * , where

Preprint submitted to Automatica

Appendix

We used the following lemma at the end of our proof of Lemma 3 in Section 3.2: Lemma A.1 Let K ∈ R n×n and L ∈ R n×n be any constant matrices, and set

where J = e (K+L)t + e (K-L)t and J = e (K+L)t -e (K-L)t .

Then ς 1 (t) = ς 2 (t) holds for all t ≥ 0.

Proof: Simple calculations give

where

By grouping terms, we can rewrite the right side of (A.3) as

where M = K e (K+L)t + e (K-L)t + L e (K+L)t -e (K-L)t and M = K e (K+L)t -e (K-L)t + L e (K+L)t + e (K-L)t .

Therefore ς2 (t) = Hς 2 (t) holds for all t ≥ 0. Since ς1 (t) = Hς 1 (t) holds for all t ≥ 0 and ς 2 (0) = ς 1 (0), we conclude that ς 2 (t) = ς 1 (t) for all t ≥ 0, by the uniqueness of solutions property.