Stability of Linear Set-Membership Filters With Respect to Initial Conditions: An Observation-Information Perspective

Set-Membership Filter (SMF) is a very important class of non-stochastic filters, which gives the optimal solution to the filtering problems with bounded noises whose probability distributions are unknown. It is fundamentally equivalent to the Bayes filter [23] under the non-stochastic Markov condition (caused by unrelated noises) [10]. For linear systems, it can be regarded as a non-stochastic counterpart of the well-known Kalman filter. Therefore, the SMF has great potentials in many important fields like control systems, telecommunications, and navigation, as the Bayes filter does. However, the linear SMFing has not drawn an adequate amount of attention to realize its full potential. One important issue is stability w.r.t. the initial condition¹¹1Similarly to the true initial distribution/measure and the initial condition for stochastic filters [22, 26], in this article: the term true initial set refers to the set of all possible initial states (objectively determined by the system), which could be a singleton when we focus on one trial; the term initial condition (for SMFs) represents the initial set subjectively chosen in the design of a filter., which characterizes whether the resulting estimate, as time elapses, remains reliable when the filter is improperly initialized [22, 26].

For Kalman filters, stability w.r.t. the initial condition is a central feature and well-established in an asymptotic manner: the posterior distribution, under some simple system assumptions, converges to the true conditional distribution of the system state (given all observed measurements) regardless of initial conditions [12, 13, 15]. This means measurements in stable filters can help correct/forget the information from the initial condition.

For linear SMFs, in contrast, there is very limited knowledge of the stability w.r.t. the initial condition. The most related work is on the uniform boundedness of the estimate, which guarantees that the size of estimate does not increase unboundedly with time. In the literature, the uniform boundedness analysis is considered for two types of SMFs, i.e., the ellipsoidal and polytopic SMFs.²²2The uniform boundedness of interval observers [18, 29] is not included since their basic structures are linear observers. For ellipsoidal SMFs, [4] proposed an input-to-state stable algorithm that ensures the uniform boundedness of the estimate; since in [4] the input-to-state stability required to solve a time-inefficient polynomial equation at each time step, [16] developed an SMF with increased efficiency based on minimizing an important upper bound; then, [25] provided a parallelotope-bounding technique to reduce the complexity, which was further improved by [3]. For polytopic SMFs, [8] proposed a zonotopic Kalman filter, where a sufficient condition (called robust detectability) for the uniform boundedness of the estimate was given; in [28], a zonotopic SMF was designed for linear parameter-varying systems, and an upper bound on the radius of the estimate was derived by solving linear matrix inequalities (LMIs); based on [28], the article [11] proposed a zonotopic SMF for switched linear systems, where an LMI-based upper bound was obtained for the radius of the estimate.

It is important to note that the uniform boundedness of the estimate does not imply reliable estimates when the initial condition is improperly chosen. Therefore, existing linear SMFs still face the issue of stability w.r.t. the initial condition, reflected in two aspects³³3Note that stability of SMFs w.r.t. their initial conditions is different from stability of control systems with estimation [5, 6, 19, 20]; for an unstable system, an stable SMF w.r.t. the initial condition can still be designed.:

• •

  Ill-posedenss: In the literature, the initial condition of an SMF should include the true initial set of the system state. But if the initial condition does not contain the true initial set, the resulting estimate at some time steps can be an empty set; in this case, we say the SMF is ill-posed⁴⁴4In the SMF community, the ill-posedness is a case of the falsification of a priori assumption. To the best of our knowledge, this issue has not been studied in the literature. or not well-posed, which is a key different feature from the stability of Kalman filters. Unfortunately, ill-posedness widely exists, which means the initial condition must be carefully chosen to guarantee non-empty estimates.

• •

  Unbounded estimation gap: Even if the estimate is non-empty, perturbations of the initial condition can gradually amplify the difference (called the estimation gap) between the estimate and the true set of the system states. Consequently, the estimation gap can go unbounded with time: inherently, the classical SMFing framework cannot always ensure the bounded estimation gap (the boundedness condition is unknown); extrinsically, approximation/reduction methods result in the wrapping effect [14] so that the estimation gap is unboundedly accumulated.

To directly tackle the stability issue, we should analyze when the classical linear SMFing framework is stable w.r.t. the initial condition, i.e., well-posed and with a bounded estimation gap; then, it is necessary to propose a new SMFing framework with guaranteed stability.

In addition to the stability, a linear SMF should be fast and accurate, which is also a challenging issue arising from the computational intractability of the optimal estimate. In general, to improve the time efficiency of an existing SMF, one has to sacrifice the estimation accuracy, and vice versa.

A recent study in [2] showed that the constrained zonotopic SMF proposed by [24] can give tighter estimates than other types of modern SMFs (e.g., ellipsoidal SMFs [16, 17] and zonotopic SMFs [8, 27]), which sheds new light on balancing the efficiency and the accuracy. This is largely because constrained zonotopes are closed under Minkowski sums and set intersections in the prediction and update steps, respectively. Nevertheless, the constrained zonotopic SMF still has a relatively large computation time due to the limitation of the existing approximation techniques. Specifically, the reduction relies on the geometric properties of the constrained zonotopes at each single time step (i.e., without considering the “time correlation”). As a result, overestimation cumulates over time, which means maintaining accuracy would lead to an unnecessary increase of complexity. The situation would be even worse for high-dimensional systems.

Taking the above discussions into account, it is of great theoretical and practical interest to develop a fast constrained zonotopic SMF with guaranteed stability, which is also efficient for high-dimensional systems.

In this work, we focus on understanding and analyzing the stability w.r.t. the initial condition of SMFing for linear time-invariant systems and establish a stability-guaranteed filtering framework to develop a new SMF. The main contribution is to put forward a concept of Observation-Information Tower (OIT). It reflects the impact of the measurements on the estimate, independent of any reliance on the initial condition. The OIT enables to provide a rigorous stability analysis, resolve the ill-posedness issue, and develop an efficient filtering algorithm. More specifically:

• •

  Applying the OIT to a projected system, we analyze the stability of the classical linear SMFing framework. An explicit stability criterion (sufficient condition) is given, which turns out to be surprisingly close to the necessity w.r.t. the bounded estimation gap.

• •

  The OIT inspires a new SMFing framework, through a rigorously proven invariance property. This framework completely fixes the ill-posedness problem of the existing linear SMFing, without relying on any information of the true initial set.

• •

  With this new framework, we design a stable and fast constrained zonotopic SMF with uniform boundedness; different from the existing reduction methods based on geometric properties of constrained zonotopes, our method utilizes the properties of system dynamics via the OIT, which has high efficiency and significantly overcomes the wrapping effect.

In Section 2, the system model is given and three problems (on stability of classical linear SMFing framework, new framework with guaranteed stability, and stable and fast constrained zonotopic SMF) are described. We propose the OIT in Section 3 which is the key to solving those three problems, and the solutions are provided in Sections 4–6, respectively. Section 7 gives the simulation examples to corroborate our theoretical results. Finally, the concluding remarks are given in Section 8.

Notation: Throughout this paper, $\mathbb{R}$, $\mathbb{N}_{0}$, and $\mathbb{Z}_{+}$ denote the sets of real numbers, non-negative integers, and positive integers, respectively. $\mathbb{R}^{n}$ stands for the $n$-dimensional Euclidean space. For an uncertain variable $\mathbf{x}$ defined on a sample space $\Omega$, its range is $\llbracket\mathbf{x}\rrbracket=\{\mathbf{x}(\omega)\colon\omega\in\Omega\}$ and its realization is $x=\mathbf{x}(\omega)$ [21, 10]. For multiple uncertain variables with consecutive indices, we define $\mathbf{x}_{k_{1}:k_{2}}=\mathbf{x}_{k_{1}},\ldots,\mathbf{x}_{k_{2}}$ (with their realizations $x_{k_{1}:k_{2}}=x_{k_{1}},\ldots,x_{k_{2}}$) where $k_{2}\geq k_{1}$. Given two sets $\mathcal{S}_{1}$ and $\mathcal{S}_{2}$ in a Euclidean space, the operation $\oplus$ stands for the Minkowski sum of $\mathcal{S}_{1}$ and $\mathcal{S}_{2}$, i.e., $\mathcal{S}_{1}\oplus\mathcal{S}_{2}=\{s_{1}+s_{2}\colon s_{1}\in\mathcal{S}_{1},s_{2}\in\mathcal{S}_{2}\}$. The summation $\sum_{i=a}^{b}\mathcal{S}_{i}$ represents $\mathcal{S}_{a}\oplus\mathcal{S}_{a+1}\oplus\cdots\oplus\mathcal{S}_{b}$ for $a\leq b$, but returns $\{0\}$ for $a>b$.⁵⁵5This is different from the mathematical convention, but can keep many expressions compact in this paper. We use $\|\cdot\|$ to represent the Euclidean norm (of a vector) or the spectral norm (of a matrix). The set $\mathcal{S}_{k}$ is uniformly bounded⁶⁶6A mathematically rigorous statement should be “the indexed family $(\mathcal{S}_{k})_{k\in\mathcal{K}}$ is uniformly bounded”. However, this minor abuse of notation considerably simplifies the presentation. (w.r.t. $k\in\mathcal{K}$) if there exists $\bar{d}>0$ such that $d(\mathcal{S}_{k})\leq\bar{d}$ for all $k\in\mathcal{K}$, where $d(\mathcal{S}_{k})=\sup_{s,s^{\prime}\in\mathcal{S}_{k}}\|s-s^{\prime}\|$ is the diameter of $\mathcal{S}_{k}$. The interval hull of a bounded set $\mathcal{S}\ni s=(s^{(1)},\ldots,s^{(n)})$ is $\overline{\mathrm{IH}}(\mathcal{S})=\prod_{i=1}^{n}[\underline{s}^{(i)},\overline{s}^{(i)}]$, where $\underline{s}^{(i)}=\inf_{s^{(i)}}\{s\in\mathcal{S}\}$ and $\overline{s}^{(i)}=\sup_{s^{(i)}}\{s\in\mathcal{S}\}$. The limit superior is denoted by $\varlimsup$. Given a matrix $M\in\mathbb{R}^{m\times n}$, the Moore-Penrose inverse is $M^{+}$; the range space and the kernel (null space) are denoted by $\mathrm{ran}(M)$ and $\ker(M)$, respectively. The notation $\circ$ stands for the composition of two maps.

Before defining the OIT, let us first analyze how a single observed measurement affects the estimate as time elapses.⁹⁹9This is quite similar to analyzing the impulse response of a control system. At $k=0$, from the update step (4) in Algorithm 1 we know that the estimate $\llbracket\hat{\mathbf{x}}_{0}|y_{0}\rrbracket$ is the intersection of $\mathcal{X}_{0}(C,y_{0},\llbracket\mathbf{v}_{0}\rrbracket)=:\mathcal{O}_{0,0}$ and $\llbracket\hat{\mathbf{x}}_{0}\rrbracket=:\mathcal{E}_{0}$, which describes how the observed measurement $y_{0}$ affects the estimate at $k=0$. When we ignore all the successive observed measurements (like the impulse response does), only the prediction step in Algorithm 1 works for $k\geq 1$. Based on “set intersection under Minkowski sum”: for sets $\mathcal{S}_{1},\ldots,\mathcal{S}_{I}$, and $\mathcal{T}$, we have¹⁰¹⁰10The proof is as follows. $\forall l\in\big{(}\bigcap_{i=1}^{I}\mathcal{S}_{i}\big{)}\oplus\mathcal{T}$, $\exists s\in\bigcap_{i=1}^{I}\mathcal{S}_{i}$ and $t\in\mathcal{T}$ such that $l=s+t$. Since $s\in\bigcap_{i=1}^{I}\mathcal{S}_{i}$, we have $s\in\mathcal{S}_{i}$ for all $i\in\{1,\ldots,I\}$. Thus, $\forall i\in\{1,\ldots,I\}$, $l=s+t\in\mathcal{S}_{i}\oplus\mathcal{T}$, which implies $l\in\bigcap_{i=1}^{I}(\mathcal{S}_{i}\oplus\mathcal{T})$, and we get (11).

and hence the estimate at $k=1$ is outer bounded by the intersection of the following two sets:

i.e., $\llbracket\hat{\mathbf{x}}_{1}|y_{0}\rrbracket\subseteq\mathcal{O}_{1,0}\bigcap\mathcal{E}_{1}$, which indicates how $y_{0}$ affects the estimate at $k=1$. As such, we can analyze the effect of $y_{i}$ on the estimate at time $k$. It defines the observation-information and state-evolution sets as follows.

A pictorial illustration of Proposition 1 is given in Fig. 1.

Note that

holds for any integer $\delta\in[0,k]$,¹¹¹¹11In this paper, when an integer is in an interval $[a,b]$, this interval denotes $\{i\in\mathbb{Z}\colon a\leq i\leq b\}$. we define the Right-Hand Side (RHS) of (15) as the OIT (see Definition 6).

Now, we provide a sufficient condition for the uniform boundedness (see Section 1) of the OIT as follows, which is fundamental to the results derived in the rest of this paper.

Note that the uniform boundedness of the OIT indicates the diameter of $\bigcap_{i=k-\delta}^{k}\mathcal{O}_{k,i}$ ($\forall\delta\geq\mu-1$) cannot go unbounded as $k\to\infty$, which is upper bounded by (16).

In this section, we study the stability issue w.r.t. the initial condition of the classical linear SMFing framework to address Problem 1, based on the OIT.

Since the uniform boundedness of the OIT requires observability, for general $(A,C)$ we introduce the observability decomposition: there exists a nonsingular $P\in\mathbb{R}^{n\times n}$ such that the equivalence transformation $\tilde{\mathbf{x}}_{k}=[(\tilde{\mathbf{x}}_{k}^{o})^{\mathrm{T}}(\tilde{\mathbf{x}}_{k}^{\bar{o}})^{\mathrm{T}}]^{\mathrm{T}}=P\mathbf{x}_{k}$ transforms (1) and (2) into¹²¹²12The observability decomposition follows Theorem 6.O6 in [5]: $P=[P_{o}^{\mathrm{T}}~{}P_{\bar{o}}^{\mathrm{T}}]^{\mathrm{T}}$ and $U=P^{-1}=[U_{o}~{}U_{\bar{o}}]$, where $P_{o}\in\mathbb{R}^{n_{o}\times n}$, $P_{\bar{o}}\in\mathbb{R}^{n_{\bar{o}}\times n}$, $U_{o}\in\mathbb{R}^{n\times n_{o}}$, and $U_{\bar{o}}\in\mathbb{R}^{n\times n_{\bar{o}}}$, such that $\tilde{A}_{o}=P_{o}AU_{o}$, $\tilde{A}_{21}=P_{\bar{o}}AU_{o}$, $\tilde{A}_{\bar{o}}=P_{\bar{o}}AU_{\bar{o}}$, $\tilde{B}_{o}=P_{o}B$, $\tilde{B}_{\bar{o}}=P_{\bar{o}}B$, and $\tilde{C}_{o}=CU_{o}$. Note that the eigenvalues of $\tilde{A}_{\bar{o}}$ only depends on $(A,C)$ but independent of $P$.

where $\tilde{x}_{k}^{o}\in\mathbb{R}^{n_{o}}$ and $\tilde{x}_{k}^{\bar{o}}\in\mathbb{R}^{n_{\bar{o}}}$; the pair $(\tilde{A}_{o},\tilde{C}_{o})$ is observable with the observability index $\mu_{o}$; it is well-known that $(A,C)$ is detectable if and only if $\rho(\tilde{A}_{\bar{o}})<1$, where $\rho(\cdot)$ returns the spectral radius of a matrix.

Now, we propose a stability condition of the classical linear SMFing framework as follows, where we define $\llbracket\hat{\tilde{\mathbf{x}}}_{0}^{o}\rrbracket$ and $\llbracket\hat{\tilde{\mathbf{x}}}_{0}^{\bar{o}}\rrbracket$ as the projections of $\llbracket\hat{\tilde{\mathbf{x}}}_{0}\rrbracket=\llbracket P\hat{\mathbf{x}}_{0}\rrbracket$ to the subspaces w.r.t. $\tilde{x}_{0}^{o}$ and $\tilde{x}_{0}^{\bar{o}}$, respectively.

As mentioned in Remark 3, condition (ii) in Theorem 2 is a sufficient condition for the boundedness of the estimation gap. To evaluate the difference between the sufficiency and the necessity, we provide a necessary condition for the bounded estimation gap in Proposition 2.

The following corollary gives a sufficient condition for simultaneously guaranteeing the stability w.r.t. the initial condition and the uniform boundedness of the estimate.

In this section, we establish a stability-guaranteed filtering framework, called OIT-inspired filtering (see Algorithm 2), to solve Problem 2.

From Theorem 2, we know that the initial condition $\llbracket\hat{\mathbf{x}}_{0}\rrbracket$ should satisfy $\llbracket\hat{\tilde{\mathbf{x}}}_{0}^{o}\rrbracket\supseteq\llbracket\tilde{\mathbf{x}}_{0}^{o}\rrbracket$ to ensure the stability of Algorithm 1 w.r.t. the initial condition. This motivates us to choose a sufficiently large $\llbracket\hat{\tilde{\mathbf{x}}}_{0}^{o}\rrbracket\supseteq\llbracket\tilde{\mathbf{x}}_{0}^{o}\rrbracket$ so that the ill-posedness can be fully handled. However, it is difficult to choose such $\llbracket\hat{\tilde{\mathbf{x}}}_{0}^{o}\rrbracket$ due to the following two issues:

• •

  Since $\llbracket\tilde{\mathbf{x}}_{0}^{o}\rrbracket$ is unlikely to know exactly, we can hardly $100\%$ guarantee $\llbracket\hat{\tilde{\mathbf{x}}}_{0}^{o}\rrbracket\supseteq\llbracket\tilde{\mathbf{x}}_{0}^{o}\rrbracket$.

• •

  Larger $\llbracket\hat{\tilde{\mathbf{x}}}_{0}^{o}\rrbracket$ can increase the possibility of the inclusion but brings more conservativeness.

In the existing SMFing framework, these two issues cannot be effectively resolved. Thus, we propose a new SMFing framework inspired by OIT, with the help of the following lemma.

A line-by-line explanation of Algorithm 2 is as follows. Line 1 initializes the algorithm. Lines 2-7 give the filtering process at each $k\in\mathbb{N}_{0}$. For $k<k_{*}$, the estimate $\llbracket\hat{\mathbf{x}}_{k}|y_{0:k}\rrbracket$ is identical to that of Algorithm 1 (see Line 3 of Algorithm 2), if it is not an empty set; otherwise, it will be reset by Line 5. In Line 5, we can choose $\hat{\mathcal{T}}_{0}^{o}=\mathcal{B}_{\theta}^{\infty}[0_{n_{o}}]$ with sufficiently large $\theta$, which is used in Algorithm 3. For $k\geq k_{*}$, the estimate $\llbracket\hat{\mathbf{x}}_{k}|y_{0:k}\rrbracket$ is determined by Line 7. Note that Line 7 can be implemented in a recursive manner by its definition in (7).¹⁶¹⁶16Generally speaking, reduction methods are required to balance the accuracy and the complexity in Line 7 for specific filter designs. But it is also possible to reduce the complexity without any accuracy loss (see the cases in Section 7.1).

Theorem 3 indicates that the OIT-inspired filtering framework given in Algorithm 2 does not rely on any information about $\llbracket\mathbf{x}_{0}\rrbracket$ to guarantee the well-posedness.

For Algorithm 2, similar results in Proposition 2 and can also be derived, where the condition $\llbracket\hat{\tilde{\mathbf{x}}}_{0}^{o}\rrbracket\supseteq\llbracket\tilde{\mathbf{x}}_{0}^{o}\rrbracket$ is not needed any more.

In this section, we develop a constrained zonotopic SMF under the new framework described in Algorithm 2, where the OIT plays the pivotal role. This SMF is not only with guaranteed stability but also with high efficiency and good accuracy. We call it the OIT-inspired Constrained Zonotopic SMF (OIT-CZ SMF).

Before presenting the SMF, we introduce the constrained zonotope [24] in Definition 7 with a small extension.

In Definition 7, we slightly generalize the constrained zonotope in [24] by replacing $\|\xi\|_{\infty}\leq 1$, i.e., $\xi\in[-1,~{}1]^{n_{g}}$, with $\xi\in\prod_{j=1}^{n_{g}}\big{[}-\hat{h}^{(j)},\hat{h}^{(j)}\big{]}$. The benefit is twofold: (i) we allow $\hat{h}^{(j)}$ to be infinity such that the posterior sets induced by unbounded prior sets (which is required by the SMFing framework in Algorithm 2) can be fully described; (ii) the numerical stability of our proposed algorithm is improved.

Based on Definition 7, if $\llbracket\hat{\mathbf{x}}_{0}\rrbracket$, $\llbracket\mathbf{w}_{k}\rrbracket$, and $\llbracket\mathbf{v}_{k}\rrbracket$ are constrained zonotopes, the resulting $\llbracket\hat{\mathbf{x}}_{k}|y_{0:k-1}\rrbracket$ and $\llbracket\hat{\mathbf{x}}_{k}|y_{0:k}\rrbracket$ in Algorithm 1 are also constrained zonotopes without any approximations. Specifically, by defining

the prediction step (3) gives the exact $\llbracket\hat{\mathbf{x}}_{k}|y_{0:k-1}\rrbracket$ with

and the update step (4) returns the exact $\llbracket\hat{\mathbf{x}}_{k}|y_{0:k}\rrbracket$ with

The proof of (20) and (21) is straightforward from [24], by rewriting (4) as $\llbracket\mathbf{x}_{k}|y_{0:k}\rrbracket=\{x_{k}\in\llbracket\mathbf{x}_{k}|y_{0:k-1}\rrbracket\colon Cx_{k}\in\{y_{k}\}+\llbracket-\mathbf{v}_{k}\rrbracket\}$.

Now, we are ready to design the OIT-CZ SMF (see Algorithm 3), where Proposition 3 plays an important role.