Gia Quoc

Graduate Student Member, IEEE Bao Tran

Pauline Bernard
email: pauline.bernard@minesparis.psl.eu

Arbitrarily Fast Robust KKL Observer for Nonlinear Time-varying Discrete Systems

Keywords: KKL observer, discrete systems, timevarying systems

This work presents the KKL observer design for nonlinear time-varying discrete systems. We first give sufficient conditions on the existence of a sequence of functions (T k ) k∈N transforming the given system dynamics into an exponentially stable filter of the output in some other target coordinates, where an observer is directly designed. Then, we prove that under uniform Lipschitz backward distinguishability, the maps (T k ) k∈N become uniformly Lipschitz injective after a certain time if the target dynamics are pushed sufficiently fast. This leads to an arbitrarily fast discrete observer after a certain time, which exhibits similarities with the famous high-gain observer for continuous-time systems. Input-to-state stability of the estimation error with respect to uncertainties, input disturbances, and measurement noise is then shown. Next, under the milder backward distinguishability, we show the injectivity of the maps (T k ) k∈N after a certain time for a generic choice of the target filter dynamics. Examples including a discretized permanent magnet synchronous motor (PMSM) illustrate the proposed observer.

I. INTRODUCTION

O BSERVERS are algorithms developed for estimating the state of dynamical systems from their known outputs and inputs. Among many existing routes [START_REF] Bernard | Observer Design for Continuoustime Dynamical Systems[END_REF], the Kazantzis-Kravaris/Luenberger (KKL) observers [START_REF] Andrieu | On the Existence of a Kazantzis-Kravaris/Luenberger Observer[END_REF]- [START_REF] Brivadis | Luenberger Observers for Discrete-time Nonlinear Systems[END_REF] are of interest in nonlinear observer design thanks to their beautiful theory revolving around Coron's Lemma [START_REF] Andrieu | On the Existence of a Kazantzis-Kravaris/Luenberger Observer[END_REF], [START_REF] Coron | On the Stabilization of Controllable and Observable Systems by an Output Feedback Law[END_REF]. They consist in transforming the system dynamics (of dimension n x ) into an exponentially stable filter of the output in some new coordinates (referred to as the target coordinates, of dimension n z ≥ n x ), where an observer readily exists, and inverting this transformation to recover the estimate of the state in the original coordinates. This design then translates into the following three main questions:

• Under what conditions does such a transformation exist?

• Under what conditions is this transformation uniformly injective? • How to find an explicit and implementable expression of this transformation, and more importantly, of its left inverse?

The injectivity property is indeed needed to find a left inverse of the transformation and thus guarantee convergence in the system coordinates. The two main questions about existence and injectivity have been answered in the literature for several classes of systems. Initially, David Luenberger proposed this method for linear time-invariant (LTI) continuous systems in [START_REF] Luenberger | Observing the State of a Linear System[END_REF]-he showed that an invertible linear transformation into a stable filter of the output always exists as long as the given system is observable and the eigenvalues of the filter are picked different from those of the system. Several attempts were then made to extend this theory to nonlinear continuous systems. The existence of a nonlinear transformation was first considered in [START_REF] Shoshitaishvili | Singularities for Projections of Integral Manifolds with Applications to Control and Observation Problems[END_REF]- [START_REF] Krener | Nonlinear Observer Design in the Siegel Domain through Coordinate Changes[END_REF] in the analytic context and around an equilibrium point. Then, the localness was dropped following another perspective in [START_REF] Kreisselmeier | Nonlinear Observers for Autonomous Lipschitz Continuous Systems[END_REF] where a global existence result was proposed based on a strong observability assumption which unfortunately did not provide an indication of the necessary dimension of the filter. This problem was solved in [START_REF] Andrieu | On the Existence of a Kazantzis-Kravaris/Luenberger Observer[END_REF] by proving the existence of an injective transformation under a mild backward distinguishability condition, for complexvalued filters of dimension n x + 1, with almost any choice of n x + 1 distinct complex eigenvalues and recently in [START_REF] Brivadis | Further Remarks on KKL Observers[END_REF] for almost any real diagonalizable filter of dimension 2n x +1, both applied to each output. Stronger uniform injectivity results were also obtained under differential observability conditions, in the case where the eigenvalues of the filter are pushed sufficiently fast [START_REF] Andrieu | Convergence Speed of Nonlinear Luenberger Observers[END_REF]. In parallel, this KKL paradigm was also developed for non-autonomous continuous systems [START_REF] Bernard | Luenberger Observers for Nonautonomous Nonlinear Systems[END_REF] and for autonomous discrete systems [START_REF] Brivadis | Luenberger Observers for Discrete-time Nonlinear Systems[END_REF], under similar backward distinguishability and differential observability conditions. Existing KKL observer results for various system classes are reviewed in Table I at the end of this paper.

Regarding the third question about a constructive design, an explicit and exploitable expression of the transformation can be found in particular contexts such as parameter identification [START_REF] Afri | State and Parameter Estimation: A Nonlinear Luenberger Observer Approach[END_REF] or state/parameter estimation for electrical machines [START_REF] Henwood | A Robust Nonlinear Luenberger Observer for the Sensorless Control of SM-PMSM : Rotor Position and Magnets Flux Estimation[END_REF], [START_REF] Bernard | Estimation of Position and Resistance of a Sensorless PMSM : A Nonlinear Luenberger Approach for a Nonobservable System[END_REF]. When an implementable expression for the transformation or its left inverse is not available, numerical approximation methods based on neural networks are being developed as in [START_REF] Da C. Ramos | Numerical Design of Luenberger Observers for Nonlinear Systems[END_REF]- [START_REF] Buisson-Fenet | Towards Gain Tuning for Numerical KKL Observers[END_REF], but essentially for autonomous systems. The computation of those maps in the time-varying setting still remains a challenge. This aspect being a research direction in its own right, here we leave it aside and focus instead on the questions of existence and injectivity of the transformation in the context of nonlinear time-varying discrete systems.

In this case, assuming the invertibility of the dynamics, we show that there exists a sequence of transformations transforming the dynamics into a discrete stable filter of the output. Under an appropriate uniform Lipschitz backward distinguishability property, this sequence of transformations is shown to become uniformly Lipschitz injective after a certain time when the target filter has an appropriate dimension and is pushed sufficiently fast. Our observer combines two main features. First, it provides an arbitrarily fast convergence of the estimation error in the system coordinates, as soon as allowed by the distinguishability condition. Second, this KKL design allows us to filter the output and provides after that time robust stability of the estimation error in the sense of [START_REF] Allan | Nonlinear Detectability and Incremental Input/Output-to-State Stability[END_REF], with an explicit strict Input-to-State Stable (ISS) Lyapunov function. Such a design may thus be seen as a discrete counterpart of the celebrated high-gain observer for continuous-time systems [START_REF] Gauthier | A Simple Observer for Nonlinear Systems Applications to Bioreactors[END_REF], which as far as we know does not exist for discrete systems (apart from discretizations of continuous high-gain observers [START_REF] Dabroom | Discrete-time Implementation of High-gain Observers for Numerical Differentiation[END_REF]). Reviewing in more detail the literature on discrete-time estimators, our uniform Lipschitz backward distinguishability condition is the same as in [START_REF] Hanba | Further Results on the Uniform Observability of Discrete-Time Nonlinear Systems[END_REF]Definitions 3 and 4]. It requires that for some m ∈ N, the map between a state and its m past outputs is uniformly Lipschitz injective. Such a property is widely exploited in the literature, including moving horizon state estimators [START_REF] Rao | Constrained State Estimation for Nonlinear Discrete-time Systems: Stability and Moving Horizon Approximations[END_REF]- [START_REF] Alessandri | Fast Moving Horizon State Estimation for Discrete-Time Systems Using Single and Multi Iteration Descent Methods[END_REF] (known for their robustness with respect to modeling uncertainties and numerical errors [START_REF] Jazwinski | Limited Memory Optimal Filtering[END_REF]), or discrete (deadbeat) estimators based on the left inversion of this observability map, such as [START_REF] Moraal | Observer Design for Nonlinear Systems with Discrete-time Measurements[END_REF] with Newton algorithms, which provide instantaneous estimation as soon as enough output information is gathered, but no filtering effects against measurement noise.

Forgetting about the condition of uniformity (in time), this distinguishability property was shown to be generic for m = 2n x + 1 in [START_REF] Ammar | On the Genericity of the Differential Observability of Controlled Discrete-Time Systems[END_REF] (and the references therein) when the number of outputs is larger than the number of inputs. Note that relaxing further the Lipschitzness and the uniformity in m leads to a weaker distinguishability condition similar to [30, Definition 3], which we show guarantees injectivity of the KKL transformations, but not uniform injectivity, thus preventing us from stating any convergence result.

In the linear context, the uniform Lipschitz backward distinguishability turns out to coincide with Kalman's well-known uniform complete observability. Under this assumption, [START_REF] Jr | Conditions for Asymptotic Stability of the Discrete Minimum-variance Linear Estimator[END_REF], [START_REF] Zhang | On Stability of the Kalman Filter for Discrete Time Output Error Systems[END_REF] showed asymptotic stability "in the large" of the widely used discrete Kalman filter, in the stochastic and deterministic context respectively. A modification of this filter then led to the Kalman-like observer in [START_REF] Alexandru | Exponential Forgetting Factor Observer in Discrete Time[END_REF], which provides arbitrarily fast exponential convergence with a (quadratic) strict Lyapunov function, unlike in [START_REF] Jr | Conditions for Asymptotic Stability of the Discrete Minimum-variance Linear Estimator[END_REF], [START_REF] Zhang | On Stability of the Kalman Filter for Discrete Time Output Error Systems[END_REF], where the Lyapunov function decreases over a certain finite number of steps. The KKL design thus provides an alternative to those observers for linear systems, with similar features as [START_REF] Alexandru | Exponential Forgetting Factor Observer in Discrete Time[END_REF], but with the crucial advantage of extending to nonlinear systems with guarantees of (semi-)global asymptotic stability. On the contrary, the extended Kalman filter/observer for nonlinear systems typically provides only local convergence, assuming the uniform complete observability condition holds on the linearization of the dynamics along the estimate [START_REF] Song | The Extended Kalman Filter as a Local Asymptotic Observer for Nonlinear Discrete-Time Systems[END_REF]- [START_REF] Boutayeb | A Strong Tracking Extended Kalman Observer for Nonlinear Discrete-Time Systems[END_REF]. Unfortunately, this kind of assumption typically introduces a loop in the analysis, since the estimation error must remain small to guarantee observability along the estimate, which is in turn needed to keep the error small. This loop is broken in [START_REF] Song | The Extended Kalman Filter as a Local Asymptotic Observer for Nonlinear Discrete-Time Systems[END_REF], [START_REF] Barrau | The Invariant Extended Kalman Filter as a Stable Observer[END_REF] but the analysis remains inherently local. Note also that those papers do not mention any explicit stability guarantees.

Other local designs have been proposed for general discrete systems as in [START_REF] Ciccarella | Observers for Discretetime Nonlinear Systems[END_REF] or based on local linearization techniques [START_REF] Lin | Remarks on Linearization of Discrete-time Autonomous Systems and Nonlinear Observer Design[END_REF]- [START_REF] Monaco | The Immersion under Feedback of a Multidimensional Discrete-time Non-linear System into a Linear System[END_REF]. In terms of global designs, some LMI-based approaches have been developed for discrete normal forms with Lipschitz nonlinearities as in [START_REF] Ibrir | Circle-criterion Approach to Discrete-time Nonlinear Observer Design[END_REF]. But to the best of our knowledge, there do not exist systematic global observer designs for general discrete systems. To further highlight our contribution, we are not aware of any other nonlinear discrete observer that can be both arbitrarily fast and robust.

The KKL design we propose in this paper does not assume any particular form for the system dynamics and provides a systematic arbitrarily fast robust observer design under a distinguishability condition on the system. Lastly, note that although they both rely on transforming the given dynamics into linear dynamics with output injection, the crucial difference between KKL designs and linearization techniques [START_REF] Lin | Remarks on Linearization of Discrete-time Autonomous Systems and Nonlinear Observer Design[END_REF]- [START_REF] Monaco | The Immersion under Feedback of a Multidimensional Discrete-time Non-linear System into a Linear System[END_REF] is that the former does not require a linear output map in the new coordinates (we do not even need its expression), thus leading to much more generic results as the class of systems where the method is applicable is much wider.

This paper is organized as follows. The KKL observer design problem is stated in Section II. Then, sufficient conditions for the existence of a sequence of maps (T k ) k∈N transforming the dynamics into a filter of the output are presented in Section III. Next, Section IV shows uniform Lipschitz injectivity of (T k ) k∈N under the uniform Lipschitz backward distinguishability, giving us an arbitrarily fast observer in discrete time. Section V then shows injectivity of the maps (T k ) k∈N under a weaker backward distinguishability but without any convergence guarantee of the estimation error. Last, Section VI gives examples including the case of linear time-varying systems and a permanent magnet synchronous motor (PMSM) illustrating the interest of using discrete KKL design for discretized continuous systems.

Notations: Let R (resp. N) denote the set of real numbers (resp. natural numbers, i.e., {0, 1, 2, . . .}). Denote R ≥0 = [0, +∞) while R >0 = (0, +∞) and N >0 = N \ {0}. Let R m×n (resp. C m×n ) be the set of real (resp. complex) (m×n)dimensional matrices. For a set E, let cl(E) be its closure and E +σ be the set of points that lie within the distance σ ∈ R >0 from a point in E. Let ℜ(z) and ℑ(z) denote the real and imaginary parts of the complex variable z. Given a vector norm denoted | • |, we denote ∥ • ∥ as the induced matrix norm. For a sequence (x k ) k∈N of vectors in R m indexed by the discrete time k ∈ N, x k is the vector at time k, while x i,k denotes its

i th component at time k. A function ρ : R ≥0 → R ≥0 is class- K if ρ is continuous, ρ(0) = 0, and ρ is strictly increasing. A function β : R ≥0 × R ≥0 → R ≥0 is class-KL if for all r ∈ R ≥0 , β(•, r
) is class-K and for all s ∈ R ≥0 , β(s, •) is decreasing and lim r→+∞ β(s, r) = 0. For two functions f and g, f • g is their composition, namely for all x in the domain of g, g(x) is in the domain of f and (f • g)(x) = f (g(x)). The left inverse f * of the map f on the set X is one such that f * (f (x)) = x for all x ∈ X . Let A ⊗ B be the Kronecker product of matrices A and B. Last, for x ∈ R m , B r (x) denotes the open ball of radius r > 0 centered at x.

II. PROBLEM STATEMENT

Consider the nonlinear time-varying discrete system

x k+1 = f k (x k ), y k = h k (x k ), (1)
where f k : R nx → R nx and h k : R nx → R ny are the dynamics and output maps, x k ∈ R nx is the state, and y k ∈ R ny is the output at discrete time k. Remark 1: Any system of the form

x k+1 = f k (x k , u k ), y k = h k (x k , u k ), (2)
where the input u k ∈ R nu is a known trajectory of time, can be put into form [START_REF] Bernard | Observer Design for Continuoustime Dynamical Systems[END_REF] with the maps (f k , h k ) k∈N depending on a particular sequence of inputs (u k ) k∈N . The results of this paper thus depend on this sequence of inputs, but some can be made uniform with respect to a family of (u k ) k∈N , if the corresponding assumptions also hold uniformly in the inputs. Assumption 1: The solutions of (1) of interest, initialized in a set X 0 , remain in a compact set X ⊇ X 0 in positive time. 1The KKL observer design consists in seeking a sequence of nonlinear maps (T k ) k∈N , with T k : R nx → R nz , transforming the dynamics (1) into an LTI discrete filter of the output, i.e., such that z k = T k (x k ) verifies

z k+1 = Az k + By k , (3)
where A ∈ R nz×nz is Schur and B ∈ R nz×ny such that (A, B) is controllable. In other words, we look for (T k ) k∈N satisfying for all k ∈ N,

T k+1 (x k+1 ) = AT k (x k ) + Bh k (x k ), (4)
along solutions to (1) remaining in X . A sufficient condition for that is to have for all k ∈ N,

(T k+1 • f k )(x) = AT k (x) + Bh k (x), ∀x ∈ X : f k (x) ∈ X . (5)
The observer in the z-coordinates is then made of a simple filter of the output

ẑk+1 = Aẑ k + By k , (6)
since the estimation error then verifies (z k+1 -ẑ k+1 ) = A(z kẑk ), which is exponentially stable. The following Theorem 1 then shows that if the sequence (T k ) k∈N to (5) is uniformly injective after a certain time (as in (8) below), it admits a sequence of left inverses (T * k ) k∈N , with T * k : R nz → R nx , such that the observer

ẑk+1 = Aẑ k + By k , xk = T * k (ẑ k ), (7)
initialized in T 0 (X ), provides an asymptotic estimate xk ∈ R nx of x k , with an asymptotic stability property of the estimation error after a certain time (as in (9) below). The goal of this paper is then to provide sufficient conditions to guarantee the existence of such a sequence of maps (T k ) k∈N . Theorem 1: Assume there exists (T k ) k∈N satisfying (5) with T 0 continuous on X and (T k ) k∈N is uniformly injective after a time, i.e., there exist a concave class-K function ρ and k ⋆ ∈ N such that for all k ≥ k ⋆ and for all (x a , x b ) ∈ X × X ,

|x a -x b | ≤ ρ(|T k (x a ) -T k (x b )|). (8)
Then, there exists (T * k ) k∈N and a class-KL function β such that for any solution k → x k of (1) with x 0 ∈ X 0 and any solution k → ẑk of (7) with ẑ0 ∈ T 0 (X ) and input

y k = h k (x k ), we have for all k ≥ k ⋆ , |x k -xk | ≤ β(|x 0 -x0 |, k).
(9) Remark 2: In this paper, the concavity assumption of ρ is not restrictive because we will achieve, in Theorem 3, uniform Lipschitz injectivity of (T k ) k∈N characterized by a linear ρ. In general, this assumption can also be dropped if there exists a compact set Z ⊂ R nz such that for all k ≥ k ⋆ , T k (X ) ⊆ Z.

Proof: From the uniform injectivity of (T k ) k∈N in ( 8), there exists a sequence of left inverse maps

(T -1 k ) k∈N : T k (X ) → R nx such that for all k ≥ k ⋆ , • For all x ∈ X , T -1 k (T k (x)) = x; • For all (z a , z b ) ∈ T k (X ) × T k (X ), |T -1 k (z a ) -T -1 k (z b )| ≤ ρ(|z a -z b |).
Applying [START_REF] Mcshane | Extension of Range of Functions[END_REF] component-wise, we can extend

(T -1 k ) k∈N into a sequence of left inverse maps (T * k ) k∈N : R nz → R nx such that there exists c 1 ∈ R >0 such that for all k ≥ k ⋆ , • For all x ∈ X , T * k (T k (x)) = x; • For all (z a , z b ) ∈ R nz ×R nz , |T * k (z a )-T * k (z b )| ≤ c 1 ρ(|z a - z b |). It follows that for all k ≥ k ⋆ , |x k -xk | = |T * k (T k (x k )) -T * k (ẑ k )| ≤ c 1 ρ(|T k (x k ) -ẑk |) ≤ c 1 ρ(c 2 c k 3 |T 0 (x 0 ) -ẑ0 |)
, for some c 2 ∈ R >0 and c 3 ∈ (0, 1) thanks to the exponential stability in the z-coordinates given by (z k+1 -ẑk+1 ) = A(z k -ẑk ). Pick x0 ∈ X such that ẑ0 = T 0 (x 0 ). Because T 0 is continuous on the compact set X , it is also uniformly continuous on X , meaning that there exists a class-K function ρ 0 such that for any

x 0 ∈ X 0 and x0 ∈ X , |T 0 (x 0 ) -ẑ0 | = |T 0 (x 0 ) -T 0 (x 0 )| ≤ ρ 0 (|x 0 -x0 |). Finally, for all k ≥ k ⋆ , |x k -xk | ≤ c 1 ρ(c 2 c k 3 ρ 0 (|x 0 -x0 |)),
which is a class-KL function in |x 0 -x0 | and k.

The uniform injectivity of (T k ) k∈N as in ( 8) is thus sufficient to guarantee asymptotic stability of the estimation error. The following academic example shows that it is not necessary, but the injectivity of each map T k alone, without uniformity in k, can sometimes be insufficient to ensure convergence.

Example 1: Consider the first-order time-varying system

x k+1 = x k , y k = h k x k , (10)
where h k ∈ R. We see that the output enables us to reconstruct the constant state x k as soon as h k ̸ = 0 for some k. Let us try to build a KKL observer. Thanks to the dynamics being linear, we look for a transformation of the form T k (x) = m k x, where (m k ) k∈N is a sequence of scalars to be found so that (5) holds. Picking λ ∈ (0, 1), this is achieved if for all k ∈ N,

m k+1 = λm k + h k , of which the solution is m k = λ k m 0 + k-1
j=0 λ k-j-1 h j for some initial m 0 . As long as m 0 ̸ = 0, the m k are always nonzero for k > 0 so that each T k is injective. However, if h k vanishes asymptotically, m k decays to zero as k increases, and the sequence (T k ) k∈N is not uniformly injective. We get

|x k -xk | = 1 m k |z k -ẑk | = λ k m k |z 0 -ẑ0 | = λ k λ k m 0 + k-1 j=0 λ k-j-1 h j |h 0 x 0 -h 0 x0 | = h 0 m 0 + k-1 j=0 hj λ j+1 |x 0 -x0 |.
Consider a first case where for some k ⋆ ∈ N >0 ,

h k = 1 if k ≤ k ⋆ 0 if k > k ⋆ , (11)
then, |x k -xk | does not converge to zero. The reason is that even though each map T k is injective at each k, (T k ) k∈N becomes less and less injective over time. Consider another case where h k = h 0 ϵ k for some constants h 0 ̸ = 0 and ϵ ∈ (0, 1), so the system is instantaneously observable at each k, but "less and less" over time. We have

|x k -xk | = h 0 m 0 + h0 λ k-1 j=0 ϵ λ j |x 0 -x0 | = h 0 m 0 + h0 ϵ-λ ϵ λ k -1 |x 0 -x0 |,
so that if we choose λ < ϵ, the error converges to zero asymptotically. Furthermore, if we initialize (m k ) k∈N as m 0 = h0 ϵ-λ > 0 (note that (h k ) k∈N is known), we even get exponential stability of the error as

|x k -xk | = (ϵ -λ) λ ϵ k |x 0 -x0 |.
This estimation can also be made arbitrarily fast by keeping pushing λ smaller. Therefore, the uniform injectivity of (T k ) k∈N is a sufficient condition according to Theorem 1, but it is not necessary. Convergence, stability, as well as other properties, could still happen without uniformity in k, but it is not guaranteed. □ In this work, we provide sufficient conditions to guarantee:

• Existence of (T k ) k∈N satisfying (5) in Section III;

• Uniform Lipschitz injectivity of (T k ) k∈N after a certain time in Section IV; • Injectivity of each T k after a certain time in Section V.

Actually, in Section IV, we achieve a stronger asymptotic property than (9): we show the exponential stability of the estimation error in the x-coordinates, namely, there exist

c 1 ∈ R >0 , c 2 ∈ (0, 1), and k ⋆ ∈ N such that for all k ≥ k ⋆ , |x k -xk | ≤ c 1 c k 2 |x 0 -x0 |. ( 12
)
Such a property is achieved by strengthening the uniform injectivity of (T k ) k∈N in (8) into uniform Lipschitz injectivity and the continuity of T 0 into Lipschitz continuity (with ρ and ρ 0 linear). This stronger result enables us to obtain a discrete observer with arbitrarily fast robust convergence as soon as allowed by the distinguishability property. More precisely, for any desired convergence rate c ⋆ 2 ∈ (0, 1), there exists a choice of (A, B) such that ( 12) is satisfied with c 2 ≤ c ⋆ 2 . Also, such a design allows for robustness against disturbances/uncertainties and filtering of measurement noise.

III. EXISTENCE OF (T k ) k∈N

This part studies the sufficient conditions for the existence of (T k ) k∈N satisfying [START_REF] Brivadis | Luenberger Observers for Discrete-time Nonlinear Systems[END_REF]. It is established under the following assumption.

Assumption 2: For all k ∈ N, f k is invertible and its inverse function f -1 k is defined on R nx . Remark 3: While invertibility is for now required globally, since the solutions of interest are known to remain in X , it may be possible to modify the maps (f k ) k∈N (and so (f -1 k ) k∈N ) outside of the set X , while still keeping the observability property mentioned below (see Section IV-D).

Such an assumption is common in observer designs for discrete systems, both nonlinear [START_REF] Brivadis | Luenberger Observers for Discrete-time Nonlinear Systems[END_REF], [START_REF] Moraal | Observer Design for Nonlinear Systems with Discrete-time Measurements[END_REF], [START_REF] Califano | On the Observer Design in Discrete-time[END_REF] and linear [START_REF] Jr | Conditions for Asymptotic Stability of the Discrete Minimum-variance Linear Estimator[END_REF]- [START_REF] Song | The Extended Kalman Filter as a Local Asymptotic Observer for Nonlinear Discrete-Time Systems[END_REF], [START_REF] Wang | Fast Interval Estimation for Discrete-time Linear Systems: An L 1 Optimization Method[END_REF], and concerns a wide class of systems. For instance, discrete dynamics that are discretizations of continuous dynamics take the form x k+1 = x k + ∆t k Φ(x k , t k ), which is close to identity for sufficiently small sampling times ∆t k , and therefore invertible. The physical meaning of this assumption is that a given current state has only one possible past. Such invertibility of the dynamics allows us to go back and forth in discrete time and access states at different times, according to

x k+n = (f k+n-1 • f k+n-2 • . . . • f k )(x k ), x k-n = (f -1 k-n • f -1 k-(n-1) • . . . • f -1 k-1 )(x k ), for k, n ∈ N.
Note that the ability to cope with the noninvertibility of the dynamics has been studied in the linear context [START_REF] Moore | Coping with Singular Transition Matrices in Estimation and Control Stability Theory[END_REF]. Under this invertibility assumption, Theorem 2 gives existence results for the function sequence (T k ) k∈N .

Theorem 2: Under Assumption 2, given any T 0 : R nx → R nz , the sequence (T k ) k∈N such that each T k : R nx → R nz is given by

T k (x) = A k (T 0 • f -1 0 • f -1 1 • . . . • f -1 k-1 )(x) + k-1 j=0 A k-j-1 B(h j • f -1 j • f -1 j+1 • . . . • f -1 k-1 )(x), (13)
verifies [START_REF] Brivadis | Luenberger Observers for Discrete-time Nonlinear Systems[END_REF]. Conversely, verifying (5) for all k ∈ N implies (13) for all k ∈ N and for all x ∈ X such that (f

-1 k-1-p • f -1 k-p • . . . • f -1 k-1 )(x) ∈ X for all 0 ≤ p ≤ k -1. Proof: To start, notice that under Assumption 2, (5) is verified for all k ∈ N if and only if for all k ∈ N >0 , T k (x) = A(T k-1 • f -1 k-1 )(x) + B(h k-1 • f -1 k-1 )(x), ∀x ∈ X : f -1 k-1 (x) ∈ X . ( 14
)
Notice that for all k ∈ N >0 , T k defined in ( 13) satisfies [START_REF] Henwood | A Robust Nonlinear Luenberger Observer for the Sensorless Control of SM-PMSM : Rotor Position and Magnets Flux Estimation[END_REF] analytically. We next show by induction that having [START_REF] Henwood | A Robust Nonlinear Luenberger Observer for the Sensorless Control of SM-PMSM : Rotor Position and Magnets Flux Estimation[END_REF] for all k ∈ N >0 implies verifying [START_REF] Afri | State and Parameter Estimation: A Nonlinear Luenberger Observer Approach[END_REF] for all k ∈ N >0 and for all x ∈ X such that (f

-1 k-1-p • f -1 k-p • . . . • f -1 k-1 )(x) ∈ X for all 0 ≤ p ≤ k -1. This is trivial for k = 1. Then, assume having (14) up to rank k ∈ N >0 implies verifying (13) at rank k for all x ∈ X such that (f -1 k-1-p •f -1 k-p •. . .•f -1 k-1 )(x) ∈ X for all 0 ≤ p ≤ k -1. We next show it at rank k + 1. Let x ∈ X such that (f -1 k-p •f -1 k-p+1 •. . .•f -1 k )(x) ∈ X for all 0 ≤ p ≤ k. Then, f -1 k (x) ∈ X and (f -1 k-1-p • f -1 k-p • . . . • f -1 k-1 )(f -1 k (x)) ∈ X for all 0 ≤ p ≤ k -1. Having (14) up to rank k + 1 thus implies (13) at rank k applied to f -1 k (x) and thus T k+1 (x) = A(T k • f -1 k )(x) + B(h k • f -1 k )(x) = A A k (T 0 • f -1 0 • f -1 1 • . . . • f -1 k-1 )(f -1 k (x)) + k-1 j=0 A k-j-1 B(h j • f -1 j • f -1 j+1 • . . . • f -1 k-1 )(f -1 k (x)) + B(h k • f -1 k )(x) = AA k (T 0 • f -1 0 • f -1 1 • . . . • f -1 k-1 • f -1 k )(x) + A k-1 j=0 A k-j-1 B(h j • f -1 j • f -1 j+1 • . . . • f -1 k-1 • f -1 k )(x) + B(h k • f -1 k )(x) = A k+1 (T 0 • f -1 0 • f -1 1 • . . . • f -1 k-1 • f -1 k )(x) + k+1-1 j=0 A k+1-j-1 B(h j • f -1 j • f -1 j+1 • . . . • f -1 k-1 • f -1 k )(x),
which is (13) at rank k + 1 at the point x.

Example 2: Consider the class of ( 1) with linear dynamics and polynomial output (as in [5, Section III] but here with time-varying matrices)

x k+1 = F k x k , y k = H k P d (x k ), (15)
where (F k ) k∈N ∈ R nx×nx and (H k ) k∈N ∈ R ny×n d are sequences of matrices and P d : R nx → R n d is a vector of n d monomials with degrees less than or equal to d. We then look for (T k ) k∈N of the form

T k (x) = M k P d (x).
Since P d (F k (x)) contains polynomials of x of order less than or equal to d, there exists

(D k ) k∈N ∈ R n d ×n d such that P d (F k x) = D k P d (x).
Therefore, we have

T k+1 (x k+1 ) = M k+1 P d (x k+1 ) = M k+1 P d (F k x k ) = M k+1 D k P d (x k
) and ( 5) holds if

M k+1 D k = AM k + BH k . (16)
If (D k ) k∈N is invertible for all k ∈ N, it can be proven by mathematical induction that ( 16) admits the unique solution

M k = A k M 0 k-1 j=0 D -1 j + k-1 j=0 A k-j-1 BH j k-1 q=j D -1 q , for all k ∈ N >0 , initialized as M 0 . So (T k ) k∈N is of the form T k (x) = A k M 0 k-1 j=0 D -1 j + k-1 j=0 A k-j-1 BH j k-1 q=j D -1 q P d (x). (17)
The particular case where the system is fully linear, namely with P d (•) identity, is detailed below in Section VI-A.

□

Now that the existence of (T k ) k∈N has been shown, we next provide sufficient conditions guaranteeing its injectivity.

IV. AN ARBITRARILY FAST ROBUST DISCRETE OBSERVER FROM UNIFORM LIPSCHITZ BACKWARD DISTINGUISHABILITY

This part shows that the uniform Lipschitz injectivity of (T k ) k∈N is obtained after a certain time under uniform Lipschitz backward distinguishability if the target dynamics are pushed sufficiently fast. This leads to an arbitrarily fast robust discrete observer as soon as allowed by distinguishability.

A. Uniform Lipschitz Injectivity of (T k ) k∈N from Uniform Lipschitz Backward Distinguishability

In this part, A is chosen of the form γ à with à Schur, and γ ∈ (0, 1] sufficiently small to ensure uniformly Lipschitz injectivity of (T k ) k∈N after a certain time. This is done under the following distinguishability condition.

Definition 1: The system (1) is uniformly Lipschitz backward distinguishable on a set X if for each output y i , i ∈ {1, 2, . . . , n y }, there exists m i ∈ N >0 such that for all k ≥ m := max i m i , the sequence of backward distinguishability maps (O bw k ) k∈N defined as

O bw k (x) = (O bw 1,k (x), O bw 2,k (x), . . . , O bw ny,k (x)), where O bw i,k (x) ∈ R mi is defined as O bw i,k (x) =        (h i,k-1 • f -1 k-1 )(x) (h i,k-2 • f -1 k-2 • f -1 k-1 )(x) . . . (h i,k-(mi-1) • f -1 k-(mi-1) • . . . • f -1 k-1 )(x) (h i,k-mi • f -1 k-mi • f -1 k-(mi-1) • . . . • f -1 k-1 )(x)       
, is uniformly Lipschitz injective on X , i.e., there exists c o ∈ R >0 such that for all k ≥ m and for all (x a , x b ) ∈ X × X ,

|O bw k (x a ) -O bw k (x b )| ≥ c o |x a -x b |. (18)
Intuitively, the concatenation of a sufficient number m i of the past outputs determines uniquely and uniformly the current state (and equivalently the trajectory as well). Equivalent kinds of uniform observability are assumed in [3, Theorem 4.1] and [4, Theorem 2] for autonomous and time-varying continuous-time systems respectively, leading to similar results with arbitrarily fast convergence of the estimation error.

Remark 4: While the condition in Definition 1 is what is required later for the proof, in practice it is not always easy to obtain the closed forms of the inverse maps of f k in (O bw k ) k∈N . Actually, this condition is satisfied with m i = m for all i ∈ {1, 2, . . . , n y } if both of the following conditions are satisfied.

• There exists m ∈ N >0 such that there exists c o ′ ∈ R >0 such that for all k ∈ N and for all (x a , x b ) ∈ X × X ,

|O f w k (x a ) -O f w k (x b )| ≥ c o ′ |x a -x b |
, where the sequence of forward distinguishability maps

(O f w k ) k∈N is defined as O f w k (x) = (O f w 1,k (x), O f w 2,k (x), . . . , O f w ny,k (x)),
where

O f w i,k (x) ∈ R m is defined as O f w i,k (x) =       h i,k (x) (h i,k+1 • f k )(x) . . . (h i,k+(m-2) • f k+(m-3) • . . . • f k )(x) (h i,k+(m-1) • f k+(m-2) • f k+(m-3) • . . . • f k )(x)       ; • The sequence of inverses (f -1
k ) k∈N is uniformly Lipschitz injective, i.e., there exists c f ∈ R >0 such that for all k ∈ N and for all

(x a , x b ) ∈ R nx × R nx , |f -1 k (x a ) -f -1 k (x b )| ≥ c f |x a -x b |.
Indeed, from the two conditions above, we have for all k ∈ N and for all (x a , x b ) ∈ X × X ,

|O bw k (x a ) -O bw k (x b )| = |O f w k-m ((f -1 k-m • f -1 k-(m-1) • . . . • f -1 k-1 )(x a )) -O f w k-m ((f -1 k-m • f -1 k-(m-1) • . . . • f -1 k-1 )(x b ))| ≥ c o ′ |(f -1 k-m • f -1 k-(m-1) • . . . • f -1 k-1 )(x a ) -(f -1 k-m • f -1 k-(m-1) • . . . • f -1 k-1 )(x b )| ≥ c o ′ c m f |x a -x b | := c o |x a -x b |, by letting c o = c o ′ c m f . Checking uniform Lipschitz backward distinguishability using (O f w k ) k∈N is much more convenient than (O bw k )
k∈N since the forward maps (f k ) k∈N are available. For our uniform Lipschitz injectivity result, we make the following assumptions.

Assumption 3: We assume that:

(A3.1) The sequences (f -1 k ) k∈N and (h k ) k∈N are uniformly Lipschitz, i.e., there exist positive scalars c f , c h such that for all k ∈ N and for all k ) k∈N and (h k ) k∈N . Its relaxation into uniform Lipschitzness over a compact set is analyzed in Section IV-D. Note that for a linear time-varying system, Assumption (A3.1) is reduced to uniform boundedness of the dynamics and output matrices (see Section VI-A).

(x a , x b ) ∈ R nx × R nx , |f -1 k (x a ) -f -1 k (x b )| ≤ c f |x a -x b |, |h k (x a ) -h k (x b )| ≤ c h |x a -x b |; (A3.2) The system (1) is uniformly Lipschitz backward distinguishable on X for some m i ∈ N >0 , i ∈ {1, 2, . . . , n y }.
The following theorem then shows uniform Lipschitz injectivity of (T k ) k∈N after a certain time.

Theorem 3: Suppose Assumptions 1, 2, and 3 hold. Define n z = ny i=1 m i . Consider a globally Lipschitz2 map T 0 : R nx → R nz , and for each i ∈ {1, 2, . . . , n y }, a controllable pair ( Ãi , Bi ) ∈ R mi×mi × R mi with Ãi Schur. Then, there exists γ ⋆ ∈ R >0 such that for any 0 < γ < γ ⋆ , there exists k ⋆ ∈ N such that the sequence (T k ) k∈N defined in [START_REF] Afri | State and Parameter Estimation: A Nonlinear Luenberger Observer Approach[END_REF] with

A = γ Ã = γ diag( Ã1 , Ã2 , . . . , Ãny ) ∈ R nz×nz , (19a)
B = diag( B1 , B2 , . . . , Bny ) ∈ R nz×ny , (19b)
and initialized as T 0 , is uniformly Lipschitz injective on X for all k ≥ k ⋆ , where γ ⋆ and k ⋆ ≥ m are defined in the proof. More precisely, there exists c ∈ R >0 (independent of γ) such that for all k ≥ k ⋆ and for all (x a , x b ) ∈ X × X , we have

|T k (x a ) -T k (x b )| ≥ cγ m-1 |x a -x b |, (20)
where m := max i m i .

Proof: First, pick γ ∈ (0, 1] small enough to ensure that γ∥ Ã∥ < 1. Consider a solution (T k ) k∈N of ( 5) for (A, B) given in [START_REF] Buisson-Fenet | Towards Gain Tuning for Numerical KKL Observers[END_REF]. Then,

T k (x) = (T 1,k (x), T 2,k (x), . . . , T i,k (x), . . . , T ny,k (x)),
where for each i ∈ {1, 2, . . . , n y }, (T i,k ) k∈N is solution to (5) with (A, B) replaced by (γ Ãi , Bi ). Therefore, Theorem 2 applies to each (T i,k ) k∈N . It follows that for each i ∈ {1, 2, . . . , n y }, for all k ≥ m i , and for all (x a , x b ) ∈ X × X , T i,k (x a ) -T i,k (x b ) can be written as the sum of three parts

T i,k (x a ) -T i,k (x b ) = I i,k (x a ) -I i,k (x b ) + T i,k (x a ) -T i,k (x b ) + R i,k (x a ) -R i,k (x b ) ,
where

I i,k (x a ) -I i,k (x b ) = (γ Ãi ) k (T 0 • f -1 0 • f -1 1 • . . . • f -1 k-1 )(x a ) -(T 0 • f -1 0 • f -1 1 • . . . • f -1 k-1 )(x b ) , R i,k (x a ) -R i,k (x b ) = k-mi-1 j=0 (γ Ãi ) k-j-1 Bi (h i,j • f -1 j • f -1 j+1 • . . . • f -1 k-1 )(x a ) -(h i,j • f -1 j • f -1 j+1 • . . . • f -1 k-1 )(x b ) , T i,k (x a ) -T i,k (x b ) = k-1 j=k-mi (γ Ãi ) k-j-1 Bi (h i,j • f -1 j • f -1 j+1 • . . . • f -1 k-1 )(x a ) -(h i,j • f -1 j • f -1 j+1 • . . . • f -1 k-1 )(x b ) = D i (γ)C i (O bw i,k (x a ) -O bw i,k (x b )), where D i (γ) = diag(1, γ, γ 2 , . . . , γ mi-1 ) and C i = Bi Ãi Bi Ã2 i Bi . . . Ãmi i Bi
is the controllability matrix of the pair ( Ãi , Bi ). Now, we will establish bounds on each of the three parts. As (T k ) k∈N is initialized globally Lipschitz, there exists c T ∈ R ≥0 such that for all

(x a , x b ) ∈ R nx × R nx , |T 0 (x a ) -T 0 (x b )| ≤ c T |x a -x b |.
Exploiting Assumption (A3.1), we thus have for all i ∈ {1, 2, . . . , n y }, for all k ≥ m i , and for all (x a , x b ) ∈ X × X ,

|I i,k (x a ) -I i,k (x b )| ≤ c T (γ∥ Ãi ∥c f ) k |x a -x b |.
Then, for γ such that γ max i ∥ Ãi ∥c f < 1, exploiting Assumption (A3.1), we have for all i ∈ {1, 2, . . . , n y }, for all k ≥ m i , and for all (x a , x b ) ∈ X × X ,

|R i,k (x a ) -R i,k (x b )| ≤ k-mi-1 j=0 (γ∥ Ãi ∥) k-j-1 ∥ Bi ∥c h c k-j f |x a -x b | = ∥ Bi ∥c h c f (γ∥ Ãi ∥c f ) mi 1 -γ∥ Ãi ∥c f (1 -(γ∥ Ãi ∥c f ) k-mi-1 )|x a -x b | ≤ ∥ Bi ∥c h c f (γ∥ Ãi ∥c f ) mi 1 -γ∥ Ãi ∥c f |x a -x b |.
Since the pairs ( Ãi , Bi ) ∈ R mi×mi × R mi are controllable, there exists c c ∈ R >0 such that ∥C -1 i ∥ ≤ 1 cc for all i ∈ {1, 2, . . . , n y }. Next, we deduce that for all i ∈ {1, 2, . . . , n y }, for all k ≥ m i , and for all (x a , x b ) ∈ X × X ,

|T i,k (x a ) -T i,k (x b )| ≥ γ mi-1 c c |O bw i,k (x a ) -O bw i,k (x b )|.
Therefore, for all i ∈ {1, 2, . . . , n y }, for all k ≥ m i , and for all (x a , x b ) ∈ X × X ,

|T i,k (x a ) -T i,k (x b )| = | I i,k (x a ) -I i,k (x b ) + T i,k (x a ) -T i,k (x b ) + R i,k (x a ) -R i,k (x b ) | ≥ |T i,k (x a ) -T i,k (x b )| -|R i,k (x a ) -R i,k (x b )| -|I i,k (x a ) -I i,k (x b )| ≥ γ mi-1 c c |O bw i,k (x a ) -O bw i,k (x b )| -∥ Bi ∥c h c f (γ∥ Ãi ∥c f ) mi 1 -γ∥ Ãi ∥c f |x a -x b | -c T (γ∥ Ãi ∥c f ) k |x a -x b | ≥ γ mi-1 c c |O bw i,k (x a ) -O bw i,k (x b )| -∥ Bi ∥c h c f γ(∥ Ãi ∥c f ) mi 1 -γ∥ Ãi ∥c f |x a -x b | -c T γ k-mi+1 (∥ Ãi ∥c f ) k |x a -x b | .
Now, since γ ∈ (0, 1] and thanks to Assumption (A3.2), if we concatenate the outputs, there exists a constant c N ∈ R >0 (depending on the chosen norms only) such that for all k ≥ m and for all (x a , x b ) ∈ X × X , we have

|T k (x a ) -T k (x b )| ≥ c N γ m-1 c c c o -max i ∥ Bi ∥c h c f γ max i ((∥ Ãi ∥c f ) mi ) 1 -γ max i ∥ Ãi ∥c f -c T γ k-m+1 (max i ∥ Ãi ∥c f ) k |x a -x b |.
If we select γ ∈ (0, 1] such that

0 < γ < γ ⋆ = min 1 ∥ Ã∥ , 1 max i ∥ Ãi ∥c f , c c c o max i ∥ Ãi ∥c f c c c o + max i ∥ Bi ∥c h c f max i ((∥ Ãi ∥c f ) mi )
,

then with γ fixed, for all k ≥ k ⋆ where k ⋆ = m if c T = 0 and k ⋆ = max m, (m -1) ln γ + ln c -ln c T ln γ + ln(max i ∥ Ãi ∥c f ) + 1 , where c = c c c o -max i ∥ Bi ∥c h c f γ maxi((∥ Ãi∥cf ) m i ) 1-γ maxi ∥ Ãi∥cf
if c T > 0, there exists a constant c ∈ R >0 (independent of γ and k, because it is picked according to γ ⋆ and k ⋆ ) such that for all (x a , x b ) ∈ X × X , we have [START_REF] Allan | Nonlinear Detectability and Incremental Input/Output-to-State Stability[END_REF].

Remark 6: This is a high-gain result in discrete time since we have to push the (discrete) dynamics sufficiently fast, namely take γ sufficiently small, to guarantee uniform Lipschitz injectivity of (T k ) k∈N . However, as γ is picked closer to zero, the coefficient [START_REF] Allan | Nonlinear Detectability and Incremental Input/Output-to-State Stability[END_REF] increases, making (T k ) k∈N "less (but still) uniformly Lipschitz injective". We also observe that:

1 cγ m-1 quantifying the injectivity of (T k ) k∈N in
• If c o is close to zero, i.e., the system (1) is "less uniformly Lipschitz backward distinguishable", the upper bound

c c c o max i ∥ Ãi ∥c f c c c o + max i ∥ Bi ∥c h c f max i ((∥ Ãi ∥c f ) mi )
on γ is reduced, which means we have to pick γ closer to zero to guarantee uniform Lipschitz injectivity of (T k ) k∈N ;

• As γ is picked closer to zero, the quantity

(m -1) ln γ + ln c -ln c T ln γ + ln(max i ∥ Ãi ∥c f ) + 1
approaches m, so k ⋆ = m, which means (T k ) k∈N becomes uniformly Lipschitz injective right after we have uniform Lipschitz backward distinguishability, namely in m steps. Also, the discontinuity of k ⋆ in c T reflects the time dependence of the injectivity of (T k ) k∈N . Indeed, if c T = 0, then the uniform Lipschitz injectivity of (T k ) k∈N is achieved as soon as we get uniform Lipschitz backward distinguishability, so it is independent of time. For c T > 0, we will have to wait for some time until the terms (I k ) k∈N become dominated. Therefore, this injectivity is time-dependent.

Example 3: Consider the system in Example 1. We have

O bw k (x) =     h k-1 x h k-2 x . . . h k-m x     =     h k-1 h k-2 . . . h k-m     x := H bw k x,
which is not uniformly Lipschitz injective since

|O bw k (x a ) -O bw k (x b )| = ∥H bw k ∥|x a -x b |
and ∥H bw k ∥ cannot be lower bounded by any positive constant uniformly in k for any m. Therefore, this example does not fall into the context of Theorem 3. □

B. Arbitrarily Fast Observer Design

According to the proof of Theorem 1, once (T k ) k∈N has become uniformly Lipschitz injective on X following Theorem 3, there exists a sequence of left inverse maps (T * k ) k∈N : R nz → R nx and c ′ ∈ R >0 such that

T * k (T k (x)) = x, ∀k ≥ k ⋆ , ∀x ∈ X , (21a)
|T * k (z a ) -T * k (z b )| ≤ c ′ cγ m-1 |z a -z b |, ∀k ≥ k ⋆ , ∀(z a , z b ) ∈ R nz × R nz . ( 21b
)
Exploiting Lipschitzness, the result of Theorem 1 can thus be strengthened as follows, obtaining exponential asymptotic stability of the estimation error in the x-coordinates, and an arbitrarily fast discrete observer.

Corollary 1: Under the assumptions of Theorem 3, consider A and B of the form [START_REF] Buisson-Fenet | Towards Gain Tuning for Numerical KKL Observers[END_REF] with γ < γ ⋆ , (T k ) k∈N , and k ⋆ provided by Theorem 3. Then, there exist (T * k ) k∈N and c ∈ R >0 such that for any solution k → x k of (1) with x 0 ∈ X 0 and any solution k → ẑk of (7) with3 ẑ0 ∈ T 0 (X ) and input y k = h k (x k ), we have

|x k -xk | ≤ c(γ∥ Ã∥) k γ m-1 |x 0 -x0 |, ∀k ≥ k ⋆ . ( 22
)
Corollary 1 shows that the observer ( 7) can be made arbitrarily fast after (T k ) k∈N has become uniformly Lipschitz injective, by picking γ closer to zero. Indeed, compared with [START_REF] Brivadis | Further Remarks on KKL Observers[END_REF], the error in the x-coordinates is exponentially stable with c 1 = c γ m-1 and c 2 = γ∥ Ã∥ < 1 (according to the proof of Theorem 3). For any desired convergence rate c ⋆ 2 ∈ (0, 1), by picking γ ≤ min

c ⋆ 2 ∥ Ã∥ , γ ⋆ , we achieve c 2 ≤ c ⋆ 2 . Note that this typically increases c 1 , because if c 2 ≤ c ⋆ 2 then c 1 ≥ c ⋆ 1 = c∥ Ã∥ m-1 (c ⋆
2 ) m-1 . We seem to recover a discrete-time version of the well-known peaking behavior in continuoustime high-gain designs [START_REF] Gauthier | A Simple Observer for Nonlinear Systems Applications to Bioreactors[END_REF]. Note though that since k ⋆ ≥ m, [START_REF] Dabroom | Discrete-time Implementation of High-gain Observers for Numerical Differentiation[END_REF] can actually be re-written as

|x k -xk | ≤ c ′ γ(γ∥ Ã∥) k-m |x 0 -x0 |, ∀k ≥ k ⋆ ,
indicating that the peaking is over after k ⋆ . This observer is illustrated in Section VI.

Remark 7: While we assume in Assumption (A3.1) that the maps (f -1 k ) k∈N and (h k ) k∈N are uniformly Lipschitz, namely the Lipschitz constants c f and c h are the same for all k, we can instead consider sequences of Lipschitz constants (c f,k ) k∈N and (c h,k ) k∈N providing that there are positive scalars c f and c h such that for all k ∈ N, c f,k ≤ c f and c h,k ≤ c h . Assumption (A3.1) then holds with c f = c f and c h = c h . These upper bounds prevent an asymptotic loss of Lipschitzness (when (c f,k ) k∈N and (c h,k ) k∈N diverge to infinity). Similarly, in Assumption (A3.2), we can consider a sequence (c o,k ) k∈N lower bounded by c o > 0 (to prevent an asymptotic loss of observability). Indeed, this allows us to update dynamically γ ∈ (0, 1] at each iteration k, as follows

0 < γ k < µγ ⋆ k = µ min 1 ∥ Ã∥ , 1 max i ∥ Ãi ∥c f,k , ccc o,k max i ∥ Ãi ∥c f,k ccc o,k + max i ∥ Bi ∥c h,k c f,k max i ((∥ Ãi ∥c f,k ) m i ) ,
for some constant µ ∈ (0, 1). The role of µ is to prevent (γ k ) k∈N from converging asymptotically to (γ ⋆ k ) k∈N , which cannot converge to zero thanks to the upper bounds c f and c h . Indeed, this could prevent convergence/injectivity. The interest of allowing γ to vary is that, at some time when we have a lot of observability (large c o,k ) or Lipschitzness (small c f,k or c h,k ), we can afford to let γ k increase while still keeping convergence, thus decreasing the noise amplification (see next Section IV-C) caused by a too fast observer (see Section VI-B for illustrations). Finally, we can pick a timevarying target filter in the z-coordinates, provided that the properties are uniform with respect to this variation. For instance, it was observed on a continuous-time motor [START_REF] Bernard | KKL Observer Design for Sensorless Induction Motors[END_REF], without any rigorous proof, that performance can be improved if the eigenvalues of the filter are adapted to the motor speed. Remark 8: If T 0 is taken constant (or even identically zero) meaning that c T = 0, then for any initial condition x 0 ∈ X 0 of the system and ẑ0 of the observer, we have ẑ0 = T 0 (x 0 ). This leads to ẑk = T k (x k ) for all k ∈ N and so xk = x k for all k ≥ k ⋆ . Therefore, we have finite-time convergence.

C. Robust and Input-to-state Stability of the Error

In this part, we now study the robust stability (in the sense of [START_REF] Allan | Nonlinear Detectability and Incremental Input/Output-to-State Stability[END_REF]) and ISS properties [START_REF] Sontag | On Characterizations of the Input-to-state Stability Property[END_REF] of the observer given by Corollary 1. Suppose the system has dynamics (1) with some disturbance/uncertainty v k and a measurement with noise w k :

x k+1 = f k (x k ) + v k , y k = h k (x k ) + w k . (23)
Then, if the pair (f k ) k∈N , (h k ) k∈N verifies the conditions of Theorem 3, we know that there exists a sequence of left inverses (T * k ) k∈N for k ≥ k ⋆ that verifies [START_REF] Gauthier | A Simple Observer for Nonlinear Systems Applications to Bioreactors[END_REF]. However, in practice, following for instance [START_REF] Da C. Ramos | Numerical Design of Luenberger Observers for Nonlinear Systems[END_REF], such maps are only approximately known. Theorem 4 then shows the robustness of the estimation error in the x-coordinates with respect to all those uncertainties (since γ∥ Ã∥ < 1).

Theorem 4: Under the assumptions of Theorem 3, consider A and B of the form [START_REF] Buisson-Fenet | Towards Gain Tuning for Numerical KKL Observers[END_REF] with γ < γ ⋆ , (T k ) k∈N , and k ⋆ provided by Theorem 3, and (T * k ) k∈N provided by Corollary 1.

Consider an approximation ( T

* k ) k∈N of (T * k ) k∈N and δ ∈ R >0 such that | T * k (z) -T * k (z)| ≤ δ, ∀z ∈ R nz . (24)
Then, there exist positive scalars c, c v , and c w (independent of γ) such that for any solution to the system (23) with x 0 ∈ X 0 and any solution to

ẑk+1 = γ Ãẑ k + By k , xk = T * k (ẑ k ), (25)
initialized as ẑ0 = T 0 (x 0 ) ∈ T 0 (X ), we have for all k ≥ k ⋆ ,

|x k -xk | ≤ c(γ∥ Ã∥) k γ m-1 |x 0 -x0 | + 1 γ m-1 k-1 j=0 (γ∥ Ã∥) k-j-1 (c v |v j | + c w |w j |) + δ. ( 26
)
Proof: First, we prove that (T k ) k∈N provided by Theorem 3 is uniformly Lipschitz. Indeed, from Assumption (A3.1), we have for all k ∈ N and for all

(x a , x b ) ∈ R nx × R nx , |T k (x a ) -T k (x b )| ≤ c T (γ max i ∥ Ãi ∥c f ) k |x a -x b | + k-1 j=0 (γ max i ∥ Ãi ∥) k-j-1 max i ∥ Bi ∥c h c k-j f |x a -x b | ≤ c T |x a -x b | + max i ∥ Bi ∥c h c f 1 -(γ max i ∥ Ãi ∥c f ) k-1 1 -γ max i ∥ Ãi ∥c f |x a -x b | ≤ c T + max i ∥ Bi ∥c h c f 1 -γ max i ∥ Ãi ∥c f |x a -x b | := c L |x a -x b |,
since γ max i ∥ Ãi ∥c f < 1 according to the proof of Theorem 3.

We now prove the robust stability and ISS properties. Consider a solution to the system ( 23) with x 0 ∈ X 0 and a solution to [START_REF] Alessandri | Moving-horizon State Estimation for Nonlinear Discrete-time Systems: New Stability Results and Approximation Schemes[END_REF] with z 0 ∈ T 0 (X ). Denoting z k = T k (x k ), we write the dynamics in the z-coordinates as

z k+1 = T k+1 (f k (x k ) + v k ) = T k+1 (f k (x k )) + T k+1 (f k (x k ) + v k ) -T k+1 (f k (x k )) = γ ÃT k (x k ) + Bh k (x k ) + T k+1 (f k (x k ) + v k ) -T k+1 (f k (x k )) = γ ÃT k (x k ) + B(y k -w k ) + T k+1 (f k (x k ) + v k ) -T k+1 (f k (x k )) = γ Ãz k + By k + T k+1 (f k (x k ) + v k ) -T k+1 (f k (x k )) -Bw k .
Because (T k ) k∈N is uniformly Lipschitz, for all k ∈ N,

|T k+1 (f k (x) + v k ) -T k+1 (f k (x))| ≤ c L |v k |.
According to [START_REF] Alessandri | Moving-horizon State Estimation for Nonlinear Discrete-time Systems: New Stability Results and Approximation Schemes[END_REF], we get for all k ∈ N >0 ,

z k -ẑk = (γ Ã) k (z 0 -ẑ0 ) + k-1 j=0 (γ Ã) k-j-1 (T j+1 (f j (x j )+v j )-T j+1 (f j (x j ))-Bw j ).
Therefore, we have for all k ≥ k ⋆ ,

|x k -xk | = |T * k (z k ) -T * k (ẑ k )| ≤ |T * k (z k ) -T * k (ẑ k )| + δ ≤ c ′ cγ m-1 |z k -ẑk | + δ ≤ c ′ (γ∥ Ã∥) k cγ m-1 |z 0 -ẑ0 | + c ′ cγ m-1 k-1 j=0 (γ∥ Ã∥) k-j-1 |T j+1 (f j (x j ) + v j ) -T j+1 (f j (x j )) -Bw j | + δ ≤ c ′ (γ∥ Ã∥) k cγ m-1 |T 0 (x 0 ) -T 0 (x 0 )| + c ′ cγ m-1 × × k-1 j=0 (γ∥ Ã∥) k-j-1 (c L |v j | + ∥B∥|w j |) + δ.
Since γ∥ Ã∥ < 1 (according to the proof of Theorem 3), this concludes the proof.

Remark 9: Theorem 4 shows that the estimation error in the x-coordinates is robustly stable with respect to the disturbance/uncertainty v k as well as the noise w k and it is ISS with respect to the approximation error δ. The former property, defined in [START_REF] Allan | Nonlinear Detectability and Incremental Input/Output-to-State Stability[END_REF], is stronger than the ISS one defined in [START_REF] Sontag | On Characterizations of the Input-to-state Stability Property[END_REF].

Note that it is the exponential stability (rather than asymptotic stability) of the estimation error that provides the ISS with respect to disturbances and measurement noise. We also see from [START_REF] Alessandri | Fast Moving Horizon State Estimation for Discrete-Time Systems Using Single and Multi Iteration Descent Methods[END_REF] that accelerating the convergence by pushing γ closer to zero will worsen the effect of the disturbances and noise, but not that of the approximation of the inverse transformation.

D. Saturating the Inverse Maps to Relax Assumption 3

In Assumption (A3.1), we require that the map sequences (f -1 k ) k∈N and (h k ) k∈N are globally uniformly Lipschitz, which is due to the fact that we do not have backward invariance of the sequence on X . Here, we would like to study how to relax that into a local requirement on a certain bounded set, without losing Assumption (A3.2).

Let us assume that, given the m i of Assumption (A3.2), there exists a large enough positive scalar σ d such that for all x ∈ X and for all k ≥ m := max i m i , all the pre-images

f -1 k-1 (x), (f -1 k-2 • f -1 k-1 )(x), up to (f -1 k-m • f -1 k-(m-1) • . . . • f -1 k-1 )(x) are in X + σ d .
This means that we can change (f -1 k ) k∈N as we want outside of X + σ d without altering Assumption (A3.2) (and without altering the system dynamics on the set X where the solutions of interest evolve). Now, for any σ c > σ d , let us consider a saturating function χ : R nx → R defined as

χ(x) =    1 if x ∈ X + σ d g(x) if x ∈ (X + σ c ) \ (X + σ d ) 0 if x / ∈ X + σ c , ( 27
)
where g is any locally Lipschitz function such that χ is locally Lipschitz. We then define

(f † k ) k∈N : R nx → R nx as f † k (x) = χ(x)f -1 k (x) + (1 -χ(x))x. ( 28
)
The set 1 is backward invariant with respect to (f † k ) k∈N . Indeed, pick any x ∈ I and any k ∈ N. Then, either x ∈ X + σ c and thus f † k (x) ∈ I, or x / ∈ X + σ c and then χ(x) = 0 and f † k (x) = x ∈ I. It follows that all the requirements of global uniform Lipschitzness of (f -1 k ) k∈N , (h k ) k∈N , and T 0 as in Assumption 3 can be replaced by uniform Lipschitzness on this backward invariant set I, by replacing (f -1 k ) k∈N with (f † k ) k∈N defined in [START_REF] Moraal | Observer Design for Nonlinear Systems with Discrete-time Measurements[END_REF] in all the equations. Similarly, in Remark 4, we can check uniform Lipschitz backward distinguishability using

I = (X + σ c ) ∪ k∈N f † k (X + σ c ) ⊂ R nx illustrated in Figure
(O f w k ) k∈N instead of (O bw k ) k∈N if (f -1 k )
k∈N is uniformly Lipschitz injective on I. Actually, even the invertibility of each f k as in Assumption 2 may only be required on I. In particular, I is bounded if and only if the sequence of sets

X σ c σ d f † 1 (X + σ c ) f † 2 (X + σ c ) f † 3 (X + σ c ) f † k (X + σ c )
(f † k (X + σ c )) k∈N is uniformly bounded, which is guaranteed if (f -1
k ) k∈N is uniformly bounded on X + σ c . In this case, all those assumptions become much more favorable.

Remark 10: In the case of a discretization, f k (x) = x + ∆tΦ(x, t k ), where either ∆t is very small or the function Φ is uniformly bounded (like in the PMSM example below in Section VI-B), then the maps (f † k ) k∈N are close to identity and there is a good chance that the sets (f † k (X + σ c )) k∈N should be close to X + σ c , which is known, and that I should be bounded.

V. INJECTIVITY FROM BACKWARD DISTINGUISHABILITY

In this part, we show the injectivity of (T k ) k∈N after a certain time from non-uniform and non-Lipschitz backward distinguishability only. Note that, as illustrated in Section II, non-uniform injectivity can sometimes be insufficient to guarantee the asymptotic convergence of the observer.

Definition 2: The system (1) is backward distinguishable on a set X after time k ⋆ if there exist an open set O containing cl(X ) and k ⋆ ∈ N such that for each k ≥ k ⋆ , for all (x a , x b ) ∈ O × O with x a ̸ = x b , there exists a j k ∈ {0, 1, . . . , k -1} such that

(h j k • f -1 j k • f -1 j k +1 • . . . • f -1 k-1 )(x a ) ̸ = (h j k • f -1 j k • f -1 j k +1 • . . . • f -1 k-1 )(x b ). (29)
In words, this means that given two different states at a time k, there exists at least one instant in the past where their corresponding outputs have been different. Note that this is much lighter than the uniform Lipschitz backward distinguishability of Section IV-no uniformity of the sequence (j k ) k∈N is required with respect to k nor to the pair (x a , x b ). Therefore, this is one of the weakest forms of observability we may consider. For our injectivity result, we then make the following assumptions.

Assumption 4: We assume that: (A4.1) For all k ∈ N, the functions f -1 k and h k are C 1 ; (A4.2) There exists k ⋆ ∈ N such that the system (1) is backward distinguishable on X after time k ⋆ . Theorem 5 then gives injectivity results for (T k ) k∈N , with T 0 = 0 and for a generic choice of (A, B) of sufficient dimension. Its proof is based on the generalized Coron's Lemma developed recently in [START_REF] Brivadis | Further Remarks on KKL Observers[END_REF].

Theorem 5: Under Assumptions 1, 2, and 4, there exists a set M of zero Lebesgue measure in R (2nx+1)×(2nx+1) × R 2nx+1 such that for any pair ( Ã, B) ∈ (R (2nx+1)×(2nx+1) × R 2nx+1 ) \ M with à Schur and any k ≥ k ⋆ , the sequence of functions (T k ) k∈N defined in [START_REF] Afri | State and Parameter Estimation: A Nonlinear Luenberger Observer Approach[END_REF] for

A = I ny ⊗ Ã ∈ R (2nx+1)ny×(2nx+1)ny , (30a)
B = I ny ⊗ B ∈ R (2nx+1)ny×ny , (30b)
and initialized as T 0 = 0, is injective on X . Remark 11: Actually, the pair ( Ã, B) is chosen controllable and with à diagonalizable, which is true for almost any such pair in R (2nx+1)×(2nx+1) × R 2nx+1 .

Proof: Recall that the set M N D of pairs of real matrices ( Ã, B) where à is non-diagonalizable in C and the set M N C of uncontrollable pairs of real matrices ( Ã, B) are both of zero measure in R (2nx+1)×(2nx+1) × R 2nx+1 . Indeed, they are the zero locus of non-identically zero polynomials: the discriminant of the characteristic polynomial for the former and the determinant of the controllability matrix for the latter. Now, consider ( Ã, B) in R (2nx+1)×(2nx+1) × R 2nx+1 controllable with à Schur and diagonalizable in C. Consider the maps (T k ) k∈N defined in [START_REF] Afri | State and Parameter Estimation: A Nonlinear Luenberger Observer Approach[END_REF] with T 0 = 0, which can be written as

T k (x) = k-1 j=0 A k-j-1 B(h j • f -1 j • f -1 j+1 • . . . • f -1 k-1 )(x), (31)
with (A, B) defined in [START_REF] Hanba | On the "Uniform" Observability of Discrete-Time Nonlinear Systems[END_REF]. Define

Ãreal = diag(Λ 1 , Λ 2 , . . . , Λ l , λ l+1 , λ l+2 , . . . , λ 2nx-l+1 ), Breal =     B 1 B 2 . . . B 2nx-l+1     ,
where

Λ i = ℜλ i -ℑ(λ i ) ℑ(λ i ) ℜ(λ i ) , B i =    1 0 i ∈ {1, 2, . . . , l}
1 i ∈ {l + 1, l + 2, . . . , 2n x -l + 1},
where l ∈ {0, 1, . . . , n x } is the number of complex non-real eigenvalues of à (that come in pairs of conjugates since à is real). As shown in [START_REF] Brivadis | Further Remarks on KKL Observers[END_REF]Appendix B.1], there exists an invertible matrix P ∈ R (2nx+1)×(2nx+1) such that

Ãreal = P -1 Ã P , Breal = P -1 B.
First, since P is invertible, the injectivity of the maps (T k ) k∈N in [START_REF] Jr | Conditions for Asymptotic Stability of the Discrete Minimum-variance Linear Estimator[END_REF] is implied by the injectivity of the maps (T real,k ) k∈N defined as

T real,k (x) = (I ny ⊗ P -1 )T k (x). We have T real,k (x) = (I ny ⊗ P -1 )T k (x) = (I ny ⊗ P -1 ) k-1 j=0 A k-j-1 B(h j • f -1 j • f -1 j+1 • . . . • f -1 k-1 )(x) = (I ny ⊗ P -1 ) k-1 j=0 (I ny ⊗ Ã) k-j-1 (I ny ⊗ B) (h j • f -1 j • f -1 j+1 • . . . • f -1 k-1 )(x) = k-1 j=0 (I ny ⊗ ( P -1 Ã P )) k-j-1 (I ny ⊗ ( P -1 B)) (h j • f -1 j • f -1 j+1 • . . . • f -1 k-1 )(x) = k-1 j=0 A k-j-1 real B real (h j • f -1 j • f -1 j+1 • . . . • f -1 k-1 )(x),
with the pair (A real , B real ) defined as

A real = I ny ⊗ Ãreal , B real = I ny ⊗ Breal .
Second, we prove the injectivity of the maps (T real,k ) k∈N .

Define now the open sets

Υ = {(x a , x b ) ∈ O × O : x a ̸ = x b } and Λ l = (B 1 (0)) l × (-1, 1) 2nx-l+1 . For λ ∈ C, define the map T λ,k as T λ,k (x) = k-1 j=0 λ k-j-1 (h j • f -1 j • f -1 j+1 • . . . • f -1 k-1 )(x).
With the structure of Ãreal and Breal , the functions (T real,k ) k∈N can be written up to a permutation as

T real,k (x) = (ℜ(T λ1,k (x)), ℑ(T λ1,k (x)), . . . , ℜ(T λ l ,k (x)), ℑ(T λ l ,k (x)), T λ l+1 ,k (x), . . . , T λ 2nx -l+1 ,k (x)).
It follows that proving the injectivity of T real,k for some (λ 1 , λ 2 , . . . , λ 2nx-l+1 ) ∈ Λ l is equivalent to proving the injectivity of

T complex,k (x) = (T λ1,k (x), T λ2,k (x), . . . , T λ 2nx -l+1 ,k (x)).
We now prove that this is guaranteed for all k ≥ k ⋆ and for almost any choice of (λ 1 , λ 2 , . . . , λ 2nx-l+1 ) ∈ Λ l in the Lebesgue measure sense. For that, we define the sets

Θ i = B 1 (0) i ∈ {1, 2, . . . , l} (-1, 1) i ∈ {l + 1, l + 2, . . . , 2n x -l + 1}, the counters p i = 2 i ∈ {1, 2, . . . , l} 1 i ∈ {l + 1, l + 2, . . . , 2n x -l + 1},
and the functions g i,k : Υ × Θ i → R for i ∈ {1, 2, . . . , l} and

g i,k : Υ × Θ i → C for i ∈ {l + 1, l + 2, . . . , 2n x -l + 1}, by g i,k ((x a , x b ), λ) = T λ,k (x a ) -T λ,k (x b ) = k-1 j=0 λ k-j-1 (h j • f -1 j • f -1 j+1 • . . . • f -1 k-1 )(x a ) -(h j • f -1 j • f -1 j+1 • . . . • f -1 k-1 )(x b ) .
Now, we check the conditions for the generalized Coron's Lemma in [START_REF] Brivadis | Further Remarks on KKL Observers[END_REF]Lemma B.3]. For any l ∈ {0, 1, . . . , n x },

• For i ∈ {1, 2, . . . , l}, we see that g i,k ((x a , x b ), •) is holomorphic on B 1 (0) for all (x a , x b ) ∈ Υ. From the chain rule, under Assumption (A4.1), for all λ ∈ B 1 (0),

g i,k (•, λ) is C 1 on Υ for each λ ∈ B 1 (0) because it is a finite composition of C 1 functions; • For i ∈ {l +1, l +2, . . . , 2n x -l +1}, as g i,k ((x a , x b ), •) is a polynomial, it is C ∞ on (-1, 1) for all (x a , x b ) ∈ Υ.
From the chain rule, under Assumption (A4.1), for all λ ∈ (-1, 1) and for all j ∈ N, the maps

∂ j g i,k
∂λ j (•, λ) are C 1 on Υ because they are finite compositions of C 1 functions. We then show that under Assumption (A4.2), for all i ∈ {1, 2, . . . , 2n x -l + 1}, g i,k ((x a , x b ), •) cannot be identically zero on Θ i . Take (x a , x b ) ∈ Υ and take k ∈ N : k ≥ k ⋆ and assume g i,k ((x a , x b ), λ) = 0 for all λ ∈ Θ i . By uniqueness of polynomials, for all j ∈ {0, 1, . . . , k -1}, we have

(h j • f -1 j • f -1 j+1 • . . . • f -1 k-1 )(x a ) = (h j • f -1 j • f -1 j+1 • . . . • f -1 k-1 )(x b
), which contradicts Assumption (A4.2). From the generalized Coron's Lemma [START_REF] Brivadis | Further Remarks on KKL Observers[END_REF] applied at each l ∈ {0, 1, . . . , n x } and each k ≥ k ⋆ , since 2nx-l+1 i=1

p i = 2n x + 1, the set E l,k = (xa,x b )∈Υ (λ 1 , λ 2 , . . . , λ 2nx-l+1 ) ∈ Λ l | ∀i ∈ {1, 2, . . . , 2n x -l + 1}, g i,k ((x a , x b ), λ i ) = 0 ,
which is literally the set of eigenvalues in Λ l making T complex,k (at each k) non-injective, has zero Lebesgue measure. Then, from [START_REF] Brivadis | Further Remarks on KKL Observers[END_REF]Lemma B.2], the set

M l,k = {( Ã, B) ∈ R (2nx+1)×(2nx+1) × R 2nx+1 |
à has the eigenvalues in E l,k } also has zero measure. Now, recall that the countable union of infinitely many zero Lebesgue measure sets also has zero Lebesgue measure [START_REF] Stein | Real Analysis: Measure Theory, Integration, and Hilbert Spaces[END_REF]. Therefore, the set

M = M N D ∪ M N C ∪ k∈N l∈{0,1,...,nx} M l,k also has zero Lebesgue measure.
It is interesting to see that this injectivity result is proven differently from the continuous-time case in [START_REF] Bernard | Luenberger Observers for Nonautonomous Nonlinear Systems[END_REF], due to the different nature of time. Indeed, the continuous time t belongs to the open uncountable set [0, +∞), so the result in [4, Theorem 3] is proven with Coron's Lemma applied only once to a set Υ that contains time. However, the discrete time k belongs to N, which is not open but countable, so the generalized Coron's Lemma is here applied separately at each instant k, and the result is then obtained for the whole time domain by the countable union of zero-measure sets.

Example 4: Consider the system in Example 1. It verifies the backward distinguishability condition in Assumption (A4.2) as long as there exists k such that h k ̸ = 0. Therefore, Theorem 5 applies with T 0 = 0 (so m 0 = 0): there exists a sequence of injective maps (T k ) k∈N (from a certain time) transforming the dynamics into a form [START_REF] Andrieu | Convergence Speed of Nonlinear Luenberger Observers[END_REF]. □

This result only ensures the injectivity of each map T k after a certain time, without any uniformity in k, which may impair convergence, as seen in Example 1. However, we saw in Example 1 that injectivity alone can still suffice in some cases. Therefore, if we initialize T 0 = 0, the observer may still work under backward distinguishability only, which is a very mild observability condition.

Remark 12: In general, solutions to (5) taking the form ( 13) is written as

T k (x) = I k (x) + T k (x) where I k (x) = A k (T 0 • f -1 0 • f -1 1 • . . . • f -1 k-1 )(x) and T k (x) = k-1 j=0 A k-j-1 B(h j • f -1 j • f -1 j+1 • . . . • f -1 k-1 )(x).
In Theorem 5, we prove the injectivity of (T k ) k∈N for all k ≥ k ⋆ assuming T 0 = 0, namely the injectivity of (T k ) k∈N . Therefore, it is advised to initialize (T k ) k∈N such that T 0 is identically zero, if possible. In a stronger case, if (T k ) k∈N is uniformly injective, i.e., there exist a class-K function κ and l ∈ R >0 such that for all k ≥ k ⋆ and for all (x a , x b ) ∈ X × X ,

|T k (x a ) -T k (x b )| ≥ lκ(|x a -x b |),
and if for all k ≥ k ⋆ and for all (x a , x b ) ∈ X × X ,

|T 0 (x a ) -T 0 (x b )| ≤ κ(|x a -x b |), then |T k (x a ) -T k (x b )| = |I k (x a ) -I k (x b ) + T k (x a ) -T k (x b )| ≥ |T k (x a ) -T k (x b )| -|I k (x a ) -I k (x b )| ≥ (l -2∥A∥ k )κ(|x a -x b |),
which implies that (T k ) k∈N becomes uniformly injective after a certain time. This, as seen in Theorem 1, is sufficient for an asymptotic observer assuming that the inverse map of κ is concave, whose dynamics, unfortunately, cannot be assigned arbitrarily fast.

VI. EXAMPLES

A. Linear Time-varying Systems

Consider a linear time-varying discrete system of form

x k+1 = F k x k , y k = H k x k . (32)
A linear transformation x k → z k = T k x k into (3) can be found with the sequence of matrices (T k ) k∈N satisfying

T k+1 F k = AT k + BH k ,
initialized as T 0 . Under invertibility of the sequence (F k ) k∈N , it is defined by the closed form

T k = A k T 0 k-1 j=0 F -1 j + k-1 j=0 A k-j-1 BH j k-1 q=j F -1 q ,
for all k ∈ N >0 . Then, provided each T k is full-rank, and thus left-invertible (see below), the KKL observer takes the form

ẑk+1 = Aẑ k + By k T k+1 = AT k F -1 k + BH k F -1 k , xk = T * k ẑk (33)
where T * k is a left inverse of T k . The system [START_REF] Zhang | On Stability of the Kalman Filter for Discrete Time Output Error Systems[END_REF] is uniformly Lipschitz backward distinguishable (see Definition 1) if and only if there exists m ∈ N >0 such that there exists c o ∈ R >0 such that for all k ≥ m, the backward distinguishability matrix

O bw k =        H k-1 F -1 k-1 H k-2 F -1 k-2 F -1 k-1 . . . H k-(m-1) F -1 k-(m-1) . . . F -1 k-1 H k-m F -1 k-m F -1 k-(m-1) . . . F -1 k-1        verifies O bw⊤ k O bw k ≥ c o I > 0. (34)
Alternatively, under uniform boundedness of (F k ) k∈N , we can use the forward version similar to the one in Remark 4. According to Theorem 3, under [START_REF] Song | The Extended Kalman Filter as a Local Asymptotic Observer for Nonlinear Discrete-Time Systems[END_REF] and the uniform boundedness of (F -1 k , H k ) k∈N , picking A sufficiently fast of dimension m, there exist c t ∈ R >0 and k ⋆ ∈ N such that for all k ≥ k ⋆ , T ⊤ k T k ≥ c t I > 0, namely (T k ) k∈N is (uniformly) left-invertible for k sufficiently large. Therefore, [START_REF] Alexandru | Exponential Forgetting Factor Observer in Discrete Time[END_REF] is implementable and provides arbitrarily fast robust exponentially stable estimation for [START_REF] Zhang | On Stability of the Kalman Filter for Discrete Time Output Error Systems[END_REF].

Interestingly, [START_REF] Song | The Extended Kalman Filter as a Local Asymptotic Observer for Nonlinear Discrete-Time Systems[END_REF] coincides with the uniform complete observability condition required by the Kalman(-like) observers (see [START_REF] Jr | Conditions for Asymptotic Stability of the Discrete Minimum-variance Linear Estimator[END_REF]Condition (13)], [START_REF] Zhang | On Stability of the Kalman Filter for Discrete Time Output Error Systems[END_REF]Definition 3], and [33, Assumption 2-3]), i.e., there exist m ∈ N >0 and c o ∈ R >0 such that for all k ≥ m,

k-1 j=k-m F -1⊤ k-1 F -1⊤ k-2 . . . F -1⊤ j H ⊤ j H j F -1 j . . . F -1 k-2 F -1 k-1 ≥ c o I > 0. ( 35
)
It is thus interesting to compare those designs. In terms of dimensions, the complexity of the Kalman(-like) filter is nx(nx+1) 2

+ n x , while that of the KKL observer is (mn y ) 2 + mn y with mn y ≥ n x (or ny i=1 m i instead of mn y if the observability multiplicities m i are considered in [START_REF] Song | The Extended Kalman Filter as a Local Asymptotic Observer for Nonlinear Discrete-Time Systems[END_REF]). Therefore, the Kalman(-like) filter is advantageous in dimension compared to the KKL observer. However, the advantage of the latter (besides being applicable in the nonlinear context) is that there exists a strict ISS Lyapunov function

V k : R nx × R nx → R ≥0 of quadratic form V k (x k , xk ) = (x k -xk ) ⊤ T ⊤ k P T k (x k -xk ), (36)
where P ∈ R nz×nz is a positive definite solution to A ⊤ P A -P < 0, and verifying

αx ⊤ k x k ≤ V k (x k ), ∀k ≥ k ⋆ , for some α ∈ R >0 independent of k.
Exponential ISS of the estimation error can thus be proven with an explicit quadratic Lyapunov function, unlike the discrete Kalman filter [START_REF] Jr | Conditions for Asymptotic Stability of the Discrete Minimum-variance Linear Estimator[END_REF], [START_REF] Zhang | On Stability of the Kalman Filter for Discrete Time Output Error Systems[END_REF] whose Lyapunov function is not strict. The discrete Kalmanlike observer [START_REF] Alexandru | Exponential Forgetting Factor Observer in Discrete Time[END_REF] on the other hand, which works under the same observability condition, also has a strict Lyapunov function and provides arbitrarily fast exponential stability of the error. It thus shares the same features as KKL, but it is restricted to systems with linear dynamics and output maps. Note that in the case n z = n x (if not, we add extra fictitious dimensions in the original system to equalize dimensions), the linear KKL observer may be equivalently written in the original x-coordinates with an innovation term similar to [START_REF] Jr | Conditions for Asymptotic Stability of the Discrete Minimum-variance Linear Estimator[END_REF]- [START_REF] Alexandru | Exponential Forgetting Factor Observer in Discrete Time[END_REF], and the matrix T ⊤ k P T k in V k plays the role of the inverse of the covariance matrix in the Kalman(-like) designs.

B. Permanent Magnet Synchronous Motor

Consider a permanent magnet synchronous motor (PMSM) with the reproduced model [START_REF] Bernard | Luenberger Observers for Nonlinear Controlled Systems[END_REF]

ẋ = u -Ri, y = |x -Li| 2 -Φ 2 = 0, (37)
where x ∈ R 2 is the electromagnetic flux (in Vs); the voltages u (in V) and currents i (in A) are inputs in R 2 ; the resistance R = 1.45 (Ω), the inductance L = 0.0121 (H), and the flux Φ = 0.1994 (Vs) are constant parameters. Here in this example, the value of the output y is always zero. Even though this system has linear dynamics, its quadratic output map renders observer design very challenging and thus necessitates thorough studies [START_REF] Henwood | A Robust Nonlinear Luenberger Observer for the Sensorless Control of SM-PMSM : Rotor Position and Magnets Flux Estimation[END_REF], [START_REF] Bernard | Estimation of Position and Resistance of a Sensorless PMSM : A Nonlinear Luenberger Approach for a Nonobservable System[END_REF], [START_REF] Bernard | Luenberger Observers for Nonlinear Controlled Systems[END_REF]. We see that the function

H x, u, i, u, di dt , d 2 i dt 2 =   |x -Li| 2 -Φ 2 2η ⊤ (x -Li) 2 η⊤ (x -Li) + 2η ⊤ η   ,
describing the output and its first two time derivatives, with

η = u -Ri + L di dt , is uniformly Lipschitz injective if there exists c η ∈ R >0 such that η ⊤ η⊤ ⊤ η ⊤ η⊤ ≥ c η I > 0. (38)
It can be shown that this property holds if the motor speed is uniformly bounded away from zero [START_REF] Bernard | Luenberger Observers for Nonlinear Controlled Systems[END_REF]. Following [START_REF] Bernard | Luenberger Observers for Nonlinear Controlled Systems[END_REF], a continuous-time KKL observer with a sufficiently fast continuous pair (A, B) of dimension 3 can be designed for this system. But actually, in practice, the input signals u and i are only known at specific sampling times, typically related to the PWM. Two paths are then possible:

• Design a continuous KKL observer for the continuous model and then discretize it at the sampling rate; or • Build a discretized model of the system at the sampling rate and design a discrete KKL observer for this discrete model. Intuitively, both paths should be equivalent for small sampling times ∆t. However, for a PMSM discretized at the PWM, discretization errors are significant at high speeds and we illustrate here the great interest of following the second path. Indeed, it offers the crucial advantage of using an appropriate discretization, adapted to the physics of the system, which is not the case in the first path where physical insight is much trickier to exploit for the observer discretization. One way to discretize the PMSM is by using Euler's method

x k+1 = x k + ∆t(u k -Ri k ), y k = |x k -Li k | 2 -Φ 2 = 0.
(39) Let us now verify the assumptions needed for observer design, more particularly those required by Theorem 3.

• Assumption 1: The solutions of (39), when injected with sinusoidal inputs, are also sine waves, so they remain in a compact set in positive time;

• Assumption 2: The dynamics map of [START_REF] Lin | Remarks on Linearization of Discrete-time Autonomous Systems and Nonlinear Observer Design[END_REF], with (u k ) k∈N and (i k ) k∈N known, is invertible; • Assumption 3: First, uniform Lipschitzness of the inverse dynamics and output maps of (39) holds since the inputs (u k ) k∈N and (i k ) k∈N are uniformly bounded and solutions remain in a compact set. Second, the uniform Lipschitz backward distinguishability is very hard to check analytically in discrete time because it involves the inversion of the dynamics. We thus use its continuous-time version related to [START_REF] Ciccarella | Observers for Discretetime Nonlinear Systems[END_REF] to argue that the equivalent property should hold in discrete time if the sampling period ∆t is sufficiently small. Guided by Example 2 and the knowledge that a KKL observer of dimension 3 exists in continuous time, we look for a transformation of the form

z k = T k (x k ) = a k |x k | 2 + b k x k + c k ∈ R 3 , (40)
where

a k = a 1,k a 2,k a 3,k ⊤ ∈ R 3 , b k = b 1,k b 2,k b 3,k ⊤ ∈ R 3×2 , c k = c 1,k c 2,k c 3,k ⊤ ∈ R 3 . Note that each b i,k , i = 1, 2, 3 is a vector in R 2 . With A ∈ R 3×3 Schur and the pair (A, B) controllable, z k is solution to (3) if a k+1 = Aa k + B, b k+1 = Ab k -2∆ta k+1 (u k -Ri k ) ⊤ -2LBi ⊤ k , c k+1 = Ac k -∆t 2 a k+1 |u k -Ri k | 2 -∆tb k+1 (u k -Ri k ) + B(L 2 |i k | 2 -Φ 2 ). (41)
Note that a k can be picked constant equal to (I -A) -1 B. Because y k = 0 for all k, z k converges to zero exponentially fast and it is straightforward to pick for instance the particular solution ẑk = 0 for the observer. Then, the estimate is obtained by solving

T k (x k ) = ẑk = 0, namely xk = - a 1,k b 2,k -a 2,k b 1,k a 1,k b 3,k -a 3,k b 1,k -1 a 1,k c 2,k -a 2,k c 1,k a 1,k c 3,k -a 3,k c 1,k . (42)
2) Discrete KKL Observer with Rotation Correction:

According to [START_REF] Bernard | Robust Sensorless Estimation of the Position and Magnet Flux of PMSMs[END_REF], a more appropriate method to discretize the PMSM (37) taking into account its rotating dynamics is

x k+1 = x k + ∆tΩ k (u k -Ri k ) sinc(φ k ), y k = |x k -Li k | 2 -Φ 2 = 0, (43)
where

Ω k = cos(φ k ) -sin(φ k ) sin(φ k ) cos(φ k ) and φ k = ωk ∆t 2 where ωk = sign((u k -u k-1 ) ⊤ u k-1 ) |u k -u k-1 | ∆t|u k |
is the estimate of the motor's rotation speed that is approximately the same for (u k ) k∈N , (i k ) k∈N , and (x k ) k∈N , assuming that this speed does not vary too fast. Notice that when ωk = 0 for all k (no rotation), we recover Euler's discretized version in [START_REF] Lin | Remarks on Linearization of Discrete-time Autonomous Systems and Nonlinear Observer Design[END_REF]. We also see that [START_REF] Mcshane | Extension of Range of Functions[END_REF], with the inputs (u k ) k∈N and (i k ) k∈N being sinusoidal, satisfies all the assumptions required by Theorem 3.

Keeping the same pair (A, B), we get this time

a k+1 = Aa k + B, b k+1 = Ab k -2∆ta k+1 (Ω k (u k -Ri k ) sinc(φ k )) ⊤ -2LBi ⊤ k , c k+1 = Ac k -∆t 2 a k+1 sinc 2 (φ k )|Ω k (u k -Ri k )| 2 -∆tb k+1 Ω k (u k -Ri k ) sinc(φ k ) + B(L 2 |i k | 2 -Φ 2 ), (44)
with a k still possibly constant equal to (I -A) -1 B, and the estimate is still obtained with [START_REF] Ibrir | Circle-criterion Approach to Discrete-time Nonlinear Observer Design[END_REF].

3) Comparison of Performance:

Due to space constraints, we only show the estimation error for one of the two state components, the other one being similar. In Figure 2, the estimation errors with respect to the continuous-time trajectory of (37) are compared among the three cases: 1) A continuous KKL observer designed following [START_REF] Bernard | Luenberger Observers for Nonlinear Controlled Systems[END_REF] and discretized using Euler's method; 2) A discrete KKL observer designed based on the Euler discretization of (37); 3) A discrete KKL observer designed based on the discretization of (37) with rotation correction. From here, we draw two important lessons: 1) It seems better to design a discrete observer from a discretized model than to discretize a continuous observer already designed; 2) The numerical errors due to incorrect discretization may be reduced by taking into account the system's physics in the discrete model. Simulations with multiple choices of γ in the rotation correction case are compared in Figure 3. It is observed that a smaller γ gives a faster convergence, but a more serious amplification of numerical noise, which is coherent with the robustness results in Theorem 4. However, in the region of too high rotating speeds, the three designs tend to perform the same, since the discretized model becomes less appropriate, which is something the observers cannot deal with. Last, it is interesting to notice that in this application case, as we choose ẑk = 0 for the observer in the z-coordinates, it is indeed the transformation (T k ) k∈N that serves to provide the estimation.

VII. CONCLUSION

This work presents the KKL observer design for nonlinear time-varying discrete systems. After giving the closed form of the transformation (T k ) k∈N into an exponentially stable filter of the measurement, we have shown how the uniform Lipschitz injectivity of this transformation is achieved after a certain time under uniform Lipschitz backward distinguishability if the target dynamics are sufficiently fast. This result provides an arbitrarily fast discrete observer that is ISS with respect to uncertainties, input disturbances, and measurement noise. For linear systems, this provides an alternative to the discrete Kalman filter, with an explicit quadratic ISS Lyapunov function. We have also shown how non-uniform injectivity of the transformations is achieved under backward distinguishability, a mild observability condition, which in some cases is enough for observer design. The example of a PMSM with sampled inputs illustrates the efficiency of designing a discrete KKL observer for an appropriate faithful discrete model of the system, instead of discretizing a continuous KKL observer designed for the continuous model. Other examples with nonlinear dynamics would typically require us to approximate (T k ) k∈N using numerical tools, in which case the robustness results in Section IV-C become useful. Indeed, closed-form expressions such as [START_REF] Afri | State and Parameter Estimation: A Nonlinear Luenberger Observer Approach[END_REF] are generally unavailable, apart from particular classes of systems. To address this, numerical tools need to be developed as in [START_REF] Da C. Ramos | Numerical Design of Luenberger Observers for Nonlinear Systems[END_REF], [START_REF] Buisson-Fenet | Learning to Observe : Neural Network-based KKL Observers[END_REF]. Another open question is how to obtain a uniform injectivity result possibly without Lispchitzness and arbitrarily fast convergence, typically through a uniform non-Lipschitz distinguishability property.

x k+1 = f k (x k ) y k = h k (x k ) z k+1 = Az k + By k A Schur, z ∈ R nz , nz ≥ nx T k+1 (f k (x)) = AT k (x) + Bh k (x) T k (x) = A k (T 0 • f -1 0 • f -1 1 • . . . • f -1 k-1 )(x) + k-1 j=0 A k-j-1 B(h j •f -1 j •f -1 j+1 •. . .•f -1 k-

Remark 5 :

 5 Assumption (A3.1) requires global uniform Lipschitzness of the sequences (f -1

Fig. 1 .

 1 Fig. 1. Illustration of the backward invariant set I (the union of all).

1 )

 1 Discrete KKL Observer with Euler's Method:

Fig. 2 .

 2 Fig.2. Estimation error by: 1) The continuous KKL observer from[START_REF] Bernard | Luenberger Observers for Nonlinear Controlled Systems[END_REF] with Ac = -diag(10, 44, 80) discretized at ∆t = 0.001 (s) (Euler); 2) The discrete KKL observer (41),[START_REF] Ibrir | Circle-criterion Approach to Discrete-time Nonlinear Observer Design[END_REF]; 3) The discrete KKL observer with rotation correction (44),[START_REF] Ibrir | Circle-criterion Approach to Discrete-time Nonlinear Observer Design[END_REF], for A = e ∆tAc and B = 1 1 1⊤ .

Fig. 3 .

 3 Fig. 3.Comparison among different choices of γ in the rotation correction case.

1 i+1

 1 T (f (x)) = AT (x) + Bh(x) T (x) = +∞ i=0 A i Bh((f -1 • f -1 • . . . • ft)f (x, u(t)) + ∂T ∂t (x, t) = AT (x, t) + Bh(x, u(t)) T (x, t) = t 0 e A(t-s) Bh(X(x, t; s; u))ds Uniform Lipschitz differential observability or Backward distinguishability Nonlinear non-autonomous discrete (this work)

This is much milder than requiring that X is forward invariant, which means that all trajectories initialized in X , including the ones we are not interested in, remain in X .

This is only a constraint on how to initialize (T k ) k∈N , which should not impact estimation since this will be forgotten. Actually, T 0 does not have to be injective and can even be picked equal to 0.

It is intuitive to initialize ẑ0 in the image of the known set X . If T 0 is globally Lipschitz as in Theorem 3, then x0 can be anywhere in R nx .

ACKNOWLEDGMENT

The authors would like to thank Florent Di Meglio, Vincent Andrieu, and Lucas Brivadis for their useful remarks and fruitful discussions.