{'fraction_non_alphanumeric': 0.045891808603673014, 'fraction_numerical': 0.010910756673468539, 'mean_word_length': 4.1290046988466464, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 13, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Sample-based observability of linear discrete-time systems

In this work, sample-based observability of linear discrete-time systems is studied. That is, we consider the case where the system output measurements are not available at every time instance. It is shown that some discrete-time systems exhibit particular behaviors that lead to pathological sampling. Depending on the characteristics of the system, different sampling schemes are developed that allow the system state to be reconstructed.


I. INTRODUCTION
In many control applications, only few and infrequent output measurements are available. Such cases can arise due to expensive sensor placement, or the characteristics of the application make it impractical or difficult to measure the system output continuously or at every sampling instant. Consider, for example, the case of biomedical applications, where taking blood samples from a patient for testing cannot be performed too often. This is, e.g., an issue when determining certain hormone concentrations from blood samples in order to detect disorders of the hypothalamic-pituitary-thyroid axis [1] and to devise suitable medication dosages, compare, e.g., [2]. Irregluar sampling sequences can also be generated due to event-triggered sampling of networked control systems to save computation and communication resources [3]. To apply state-feedback control techniques for such systems, suitable state estimators need to recover the internal state by using only this limited output information. Samplebased observability is the area of research that studies the conditions that must be satisfied to ensure that the selected measurements are sufficient to reconstruct the system state.
Different conditions for sample-based observability have been studied for continuous-time linear systems. The most basic instance corresponds to the case where the continuoustime system is discretized under uniform sampling and the sampling period is non-pathological. Sampling periods are said to be pathological, if the discretized system does not preserve the observability and controllability properties of the original system [4]. For every pair of eigenvalues (λ p , λ q ) of the system matrix, the sampling period T needs to satisfy the following to rule out pathological situations if ℜ(λ p ) = ℜ(λ q ), where ℜ(·) and ℑ(·) denote the real and imaginary parts, respectively [4]. In [5] a periodic sampling scheme was presented, that guarantees for every observable continuoustime system observability of the discretized system. Here, each period consists of a sequence of equidistant samples followed by one sample interval of different length. The average sampling period is now independent of the system parameters and can, thus, be chosen arbitrarily. A slightly different sampling scheme was introduced in [6]. Here, a sequence of sampling instances is chosen nonequidistant. However, the sampling process is then periodically repeated.
More recent results in [7] and [8] allow completely irregular sampling of the continuous-time system. In these papers, a lower bound on the number of necessary samples taken at arbitrary time instances is derived to guarantee that the internal state can be reconstructed from the irregularly selected output measurements. To achieve this, an upper bound on the number of time instances where the system output can be zero for nonzero initial states inside the time period of interest is computed.
In spite of these results for continuous-time systems, to the best of our knowledge, no results have been reported for sample-based observability of inherently discrete-time systems. In this paper, we directly study conditions for samplebased observability of discrete-time systems. This addresses systems that are discrete by nature, as well as systems for which only discrete-time models are available. While some of the results we obtain are conceptually similar to those for continuous-time systems, other aspects are fundamentally different and inherent to the considered discrete-time setting. In particular, our contributions are as follows. First, we investigate the conditions for discrete-time systems that lead to pathological sampling periods, analogous to the known conditions (1) for continuous-time systems. On the one hand, we show that this result directly allows for the development of a sampling scheme for arbitrary second-order systems. On the other hand, our analysis gives an insight into the difficulties that arise for higher-order systems. Then, we focus on designing sampling schemes for specific scenarios. For systems with only real eigenvalues, we derive a lower bound on the number of necessary samples taken at arbitrary time instances to guarantee sample-based observability. If the system has arbitrary eigenvalues and we are able to select specific samples to collect, then we show that a regular sampling scheme is necessarily non-pathological if the sampling period is properly selected. Finally, we discuss an extension to the regular sampling result to allow for specific irregular measurements.
The rest of the paper is organized as follows. In Section II, we formulate the sample-based observability problem. An analysis of pathological sampling in discrete-time systems, as well as our first sampling scheme results, are presented in Section III. Section IV explores different sampling schemes for discrete-time systems. The conclusions of the paper are given in Section V.

II. PROBLEM FORMULATION
Consider a MISO (Multiple-Input Single-Output) linear time-invariant discrete-time system where A ∈ R n×n , B ∈ R n×m , C ∈ R 1×n , D ∈ R 1×m , u(t) ∈ R m is the control input, x(t) ∈ R n is the state and y(t) ∈ R is the system output.
Definition 1 (Observability [9]): The system (2)-(3) is said to be observable if for any unknown initial state ξ , there exists a finite t > 0 such that the knowledge of the input u and the output y over [0,t] suffices to determine uniquely the initial state ξ .
where 0 n ∈ R n is a vector of zeros. If measurements are not available at n consecutive samples, the initial state can always be recovered from observations of the output if and only if, for any ξ and η, ξ = η, . . .
Therefore, we consider an observability rank condition depending on the set of sample instances t 1 ,t 2 . . . ,t l .
Definition 2 (Sample-based observability): The system in (2)-(3) is sample-based observable if the sample-based observability matrix has rank n.
In this paper, we investigate sampling schemes for the selection of the sample instances t 1 , . . . ,t l , depending on the system dynamics such that the sample-based observability matrix (6) has full rank. Without loss of generality, the system will be considered in Jordan canonical form. Moreover, the following assumption is made.

Assumption 1: (A,C) is an observable pair.
Additionally, we impose the following assumption on the system matrix A.
Assumption 2: All eigenvalues of the matrix A are nonzero.
To briefly illustrate the meaningfulness of Assumption 2, consider the case where matrix A is given by This yields A k = 0 nn , for all k ≥ n, where 0 nn ∈ R n×n is a matrix of zeros. Therefore, to satisfy the condition in Definition 2 in this example, it is necessary to measure the first n consecutive output samples, and no other sampling scheme can be obtained. In general, a system with a p−dimensional Jordan block of the eigenvalue zero requires measuring the first p samples, independent of the other system characteristics and sampling scheme for later measurements.

DISCRETE-TIME SYSTEMS
In this section, we provide conditions for sample-based observability of two-dimensional systems, and describe the properties present in some discrete-time systems that prevent this result from being generalized to higher-dimensional systems. To begin this analysis, we first study the conditions that result in pathological sampling.

A. Pathological periods
In the following, we take a closer look at some notable behavior of discrete-time systems, that is closely related to pathological sampling periods of the system and, thus, is crucial for the development of possible sampling schemes.
Recall that we consider the system matrix A in (2) in Jordan form, and denote the eigenvalue corresponding to the i-th Jordan block by λ i . Then, for h ∈ N, A h is a block diagonal matrix with each block being an upper triangular matrix with the same eigenvalue λ h i on the diagonal. Notice that if λ h p = λ h q , for two eigenvalues λ p , λ q of A with p = q and some h ∈ N, then A h has multiple blocks with the same eigenvalue. Moreover, this implies, in the case of single-output systems, that (A h ,C) is not an observable pair. This can, e.g., be easily seen from the Hautus test for observability [10], since the matrix [C ⊤ , (λ h p I − A h ) ⊤ ] ⊤ has (at least) two rows of all zeros, and hence cannot have rank n as required for observability. The following lemma states conditions for this behavior to arise.
Proof: Notice that the h-th power of a complex number λ p can be expressed as To have λ h p = λ h q , both λ p and λ q must be an h-th root of Therefore, for some k p , k q = 0, 1, . . . , h − 1, k p = k q . Hence, λ p and λ q are both an h-th root of γ if and only if |λ p | = |λ q | and (8) holds.
Remark 1: Notice that if λ p = −λ q , then (8) is satisfied for every even h. Furthermore, if (λ p , λ q ) is a complex conjugate pair, then φ p = −φ q and γ in the proof of Lemma 1 is a real number. Thus, it follows directly from (9) that hφ p = πk, for some k ∈ {±1, . . . , ±(h − 1)}. Hence, for a complex conjugate pair, (8) can be replaced by (13) Remark 2: Consider a pair of eigenvalues (λ p , λ q ) that satisfies the conditions in Lemma 1. Then, notice that all values of h for which (8) holds are an integer multiple of some minimum valueh. Now, Lemma 2 on pathological measurement sequences can be formulated.
with arbitrary r i ∈ N, i = 1, . . . , l, and l ∈ N, results in a sample-based observability matrix (6) with rank less than n. Proof: If the conditions in Lemma 1 are satisfied and, thus, λ h p = λ h q , then A h has multiple blocks with the same eigenvalue, and hence (A h ,C) is not an observable pair as discussed above Lemma 1. Therefore the sample-based observability matrix (6) with t i as in (14) has always a rank less than n.

B. Sampling scheme for second-order systems
From the preceding analysis of pathological sampling sequences for discrete-time systems, conditions on the sampling for second order systems to guarantee sample-based observability can be straightforwardly concluded.
Lemma 3: For a system (2)-(3) with n = 2 satisfying Assumptions 1 and 2, the sample-based observability matrix (6) has full rank for any two measurement instances, if the conditions in Lemma 1 are not satisfied. If the conditions in Lemma 1 hold, then sample-based observability is guaranteed by measuring N s arbitrary samples inside any time and h assumes the minimum valueh as in Remark 2.
Proof: Recall that we consider A in Jordan form. Since (A,C) is observable by Assumption 1, if λ 1 = λ 2 , then A is a Jordan block of dimension 2. This follows since otherwise, for any C, for a single-output system, contradicting observability. Hence, in case that λ 1 = λ 2 , A h = αI for any α ∈ R (including α = 0 due to Assumption 2) and any h ∈ N.
Together with the fact that C = 0 by Assumption 1, this implies CA h = αC for any α ∈ R and any h ∈ N and, thus, that (6) has full rank for any two samples. In the case that λ 1 = λ 2 , A is a diagonal matrix. If λ h 1 = λ h 2 for all h ∈ N, then again CA h = αC, showing that (6) has full rank for any two samples. If λ h 1 = λ h 2 , let h take the minimum valueh as in Remark 2. Without loss of generality, assume the first sample is selected at t = 0. Then, out of T samples, there exist up to T h time instances t = 0 that result in Hence, taking N s samples as in (15) guarantees that there exists at least one time instance, for which (17) does not hold.

C. Higher-order systems
Lemma 3 cannot be extended straightforwardly to higherorder systems. Finding a lower bound for randomly taken measurements to ensure sample-based observability for general linear systems is a challenging task. In the following, we illustrate with an example some of the difficulties that arise for higher order systems.
Consider the case where A h has more than two blocks with the same eigenvalue and, hence, pathological sampling situations are more likely. In particular, assume the worstcase scenario in which A n has n blocks with the same eigenvalue, i.e., λ n 1 = λ n 2 = . . . = λ n n , λ p = λ q , ∀p, q ∈ {1, . . . , n}, p = q.
In Appendix B, we provide a numerical example for which this is the case. Then, the set of time instances K := {t,t + r 1 n,t + r 2 n, . . . ,t + r n−1 n}, ∀t ∈ N 0 , ∀r i ∈ N, i = 1, . . . , n − 1, generates a sample-based observability matrix (6) with only rank one, since CA t = α i CA t+r i n , for some α i ∈ R. It can be shown that a bound on arbitrary samples in any interval [t,t + T − 1] to guarantee sample-based observability in such a case must satisfy as follows from the example in Appendix B. However, when collecting at least 1 + T (n − 1)/n out of T samples, this includes at least one set of n consecutive samples. This means that for a system with the characteristics in (18), no meaningful scheme for measuring arbitrary samples can be given. As shown in the following lemma, to achieve sample-based observability without taking n consecutive samples, measurements at specific time instances are required.
Proof: see Appendix A.
In this section, conditions for pathological sampling sequences were derived, and it was observed that obtaining a (meaningful) bound on arbitrary samples in order to guarantee sample-based observability is not possible in general. Nevertheless, we provided a first insight on possible sampling schemes for specific systems. In the following section, we will develop further sampling schemes for more general cases.

IV. SAMPLING SCHEMES FOR HIGHER ORDER SYSTEMS
In the preceding section, we stated a sample-based observability result for second-order systems. Now, we will focus on systems with dimension n ≥ 3. First, the case for systems with only real eigenvalues will be studied, followed by our analysis of systems with both complex and real eigenvalues.

A. Systems with only real eigenvalues
In this subsection, we consider linear discrete-time systems with exclusively real eigenvalues. A lower bound on the number of arbitrary measurements is derived such that sample-based observability is guaranteed.
Proof: Consider the sample-based observability matrix for n samples If (22) has rank < n, then CA t n can be expressed as a linear combination of the first n − 1 rows where C = (c 1 , . . . , c n ). Notice that A is in Jordan form, and hence c k = 0, when in the k-th column of A a new Jordan block begins, since (C, A) is an observable pair. Thus, for (23) to hold, each eigenvalue λ j has to be a solution to In case of a p-dimensional Jordan block, the associated eigenvalue is a root of multiplicity p of (24). This is because this eigenvalue is also a root of all derivatives of (24) up to the p-th derivative. For clarity, we illustrate this by considering, e.g., a third-order system with A consisting of two Jordan blocks. Then, (22) can be written as From the first two columns of (25) it follows that, for (23) to hold, λ 1 and λ 2 must both satisfy (24). From the third column it follows, furthermore, that λ 2 is not only a root of (24) but a root of its derivative as well. Hence, λ 2 is a double root of (24). This third-order example can be straightforwardly extended to any p-dimensional Jordan block. Now, we argue that the conditions in Theorem 1 are such that for a specific set of n out of the considered 2n − 1 samples, (24) cannot have n nonzero real solutions, contradicting (23). The polynomial in (24) consists of n terms and, hence, a maximum of n − 1 sign changes in the coefficients can occur. Applying Descartes' rule of signs (see e.g. [11]), both the number of possible positive real solutions and the number of possible negative real solutions is upper bounded by n − 1. Now, consider the case that all exponents of the polynomial (24) are even. Then, (24) has real solutions of the form ±λ j , 1 ≤ j < n. Since (A 2 ,C) being an observable pair rules out the case where A has eigenvalues of the same magnitude but with different signs, (24) with only even exponents cannot hold for all n real nonzero eigenvalues of A. Thus we conclude that, if all t i are even, the matrix in (22) has rank n. Therefore, sample-based observability is achieved if at least n of the measured samples correspond to even measurement instances t i . Similarly, it is also sufficient to take n odd instances. Finally, taking any 2n − 1 samples guarantees either n even or n odd measurement instances t i , completing the proof.
From the presented proof, the following corollary for the case of only positive eigenvalues can be straightforwardly concluded.
Corollary 1: Let Assumptions 1 and 2 hold. If the system matrix A has only positive real eigenvalues, the collection of any n samples results in rank n of the sample-based observability matrix (6).

Remark 3:
As shown in the preceding proof, the assumption of (A 2 ,C) being an observable pair is required in Theorem 1 to state that any 2n − 1 samples, regardless of the time of measurement, guarantee sample-based observability. If the assumption of (A 2 ,C) being an observable pair is not satisfied, only a time interval-dependent bound similar to Lemma 3 can be derived, i.e., in any interval [t,t + T − 1] arbitrary samples are required, where N p is the number of eigenvalues for which the conditions in Lemma 1 hold for h = 2. We show the bound in (26) in Appendix C.

B. Regular sampling scheme
In the following, a regular (periodic) sampling scheme will be derived. This scheme requires regularly taken measurements, providing less freedom in the selection of samples. However, different from the conditions in Theorem 1, this sampling scheme requires measuring only n samples, and is applicable also for systems with complex eigenvalues.
In Lemma 2, a condition for pathological measurement sequences due to the pathological sampling period h for discrete-time systems was presented. Now, we will show that every regular sampling period other than h is non-pathological.
Proof: The proof is performed by contradiction. Without loss of generality assume t 1 = 0. Suppose that the matrix is not full rank. Then, CA (n−1)t is a linear combination of the first n − 1 rows. Hence, applying the same arguments as in the proof of Theorem 1, it can be seen that each eigenvalue λ j is a solution of multiplicity p j to where p j is the algebraic multiplicity of λ j . Substituting λt by γ in (28) results in It can be shown that if λ j is a root of multiplicity p j of (28), then γ j = λt j is a root of the same multiplicity p j of (29). Furthermore, due to the assumption thatt = h, it always holds that λt p = λt q for all pairs of eigenvalues (λ p , λ q ) with λ p = λ q . Finally, since (29) is a polynomial of order n − 1, and hence has only n − 1 solutions, we can conclude that the above implies that (28) does not hold for all n eigenvalues. Therefore, (27) has full rank.

C. Irregular sampling scheme
In the following, we will take a closer look at the possibility of modifying the regular sampling scheme in Theorem 2 to allow some irregularity of the measurement instances. First, a system of order three will be considered and subsequently the extension to systems with dimension n > 3 is discussed.
1) Third-order system: For a third-order system such that we can derive a sampling scheme consisting of only four samples with mild conditions on the time instances of the measurements to guarantee full rank of the sample-based observability matrix. With (30) being satisfied, we exclude systems for which the sample-based observability matrix can have rank one as in the case described in Subsection III-C.
Theorem 3: Consider system (2)-(3) and let Assumptions 1 and 2 hold. Moreover suppose (30) is satisfied. Consider any two samples t 1 and t 2 and select the two additional samples t 3 = t 1 + ∆ and t 4 = t 2 + ∆ with ∆ ∈ N. Then, the sample-based observability matrix (6) has rank n, if ∆ = h with h being any pathological sampling period as in Lemma 1.
2) Discussion on an extension to higher-order systems: For discussing an extension of Theorem 3 to higher-order systems, first the following lemma is required.
Lemma 5: Consider system (2)-(3) and let Assumptions 1 and 2 hold. Suppose for the set {t 1 ,t 2 . . .t n } of arbitrary samples the sample-based observability matrix (6) has a rank lower than n. Then, the additional samples {t 1 + ∆,t 2 + ∆, . . . ,t n + ∆} will increase the rank of the samplebased observability matrix for all ∆ = h with h being any pathological sampling period as in Lemma 1.
Proof: If for the set {t 1 ,t 2 . . .t n } the sample-based observability matrix has not full rank, then for some scalars α i ∈ R. To argue by contradiction, suppose that for some scalars γ i, j ∈ R. Hence, the rank of the sample-based observability matrix will not be increased by the additional set of samples. Applying (38) r times, it follows that for each r = 1, . . . , n − 1 we have for some β i,r ∈ R. Consequently this leads to rank        CA t n CA t n +∆ CA t n +2∆ . . .
Using Lemma 5 to extend Theorem 3 to higher order systems yields a set K n−1 of sufficient samples. K n−1 is constructed in the following manner . . .
Here, K i + ∆ is defined as the set of time instances resulting from adding a scalar ∆ to each element of K i . By Lemma 5, each of the sets K i in (41) guarantees the addition of at least 1 to the rank of matrix (6), when compared to the set K i−1 , in case the rank is still less than n. However, this sampling scheme may not be convenient for high order systems, since the number of necessary samples increases exponentially with the system order. In particular, for an n th -order system, 2 n−1 samples are required in the set K n−1 .
Hence, compared to the regular sampling scheme from Theorem 2, using irregular sampling (i.e., ∆ i = ∆ j ) comes at the price of a (significantly) higher bound on the required maximum number of samples in order to guarantee samplebased observability.

V. CONCLUSION
In this paper, we investigated the observability of linear discrete-time systems for the case that measurements are not available at every time instance.
First, pathological sampling sequences were analyzed. Second, we showed that for systems with only real eigenvalues, under certain conditions an arbitrary choice of 2n − 1 (irregular) sampling instances is sufficient for sample-based observability. Furthermore, building on the results on pathological sampling sequences, it was shown that for every sampling period other than the pathological sampling period h as in Lemma 1, a regular sampling scheme leads to samplebased observability for general discrete-time systems (with real and/or complex eigenvalues). It was also shown how to relax the strict regularity of the sampling scheme while still guaranteeing sample-based observability; however, this might only be convenient for lower-order systems.
Relaxing the conditions for an irregular sampling scheme for high order systems with general real and/or complex eigenvalues is an interesting subject of future research. and, thus, (54) cannot be satisfied for both λ p and λ q . Considering that all other additional t i , i ≥ N e + 2 are odd and using the above arguments recursively, it can be shown that each additional row increases the rank of the concatenated matrix as long as it is less than n, and hence (53) holds. Finally, we show that rank O e + rank O o ≥ n. Applying which shows that N s samples guarantee sample-based observability.