The goal of this article is to provide a brief and somewhat non-technical introduction to the area of set-membership identification and filtering via the use of optimal bounding ellipsoid (OBE) algorithms. To start, let us review the standard problem of linear system identification. The problem at hand is the following: We are given a system which is generates an observable and measurable output to a certain (known) input. Also, we know the input-output relationship to be linear, in that there exists a parameter vector which linearly maps the input vector to the output. But what is measured, or observed, is a corrupted version of this output signal. This distortion is modeled as additive noise.Figure of the System Identification Model
The assumption employed in set-membership identification is that the additive noise is bounded by a known quantity instantaneously. At this point, it is important to note that set-estimation in general has not been restricted to the linear-in-parameter with bounded noise model. However, the model described above has been the most popular in the system identification/ adaptive signal processing literature and is the focus of the ASPECT group.
This bounded noise assumption can be shown to lead to a constraint on the true parameter which generated the data. This constraint is in the form of a convex set in the parameter space, also called the "observation set". Therefore, as we obtain more data, we infer that the true parameter has to belong to all of these observation sets, implying that it belongs to the intersection of all these observation sets upto that time instant. The intersection set at each time is called the "membership-set" at that instant. The objective in SMI is to estimate this membership-set. Given certain conditions on the input vector, the membership-set asymptotically converges to the true parameter, and so would a "good" estimator of the membership-set.The Membership-Set in the real plane
On the other hand, keeping track of the membership-sets (which are convex polytopes in the parameter space) is not very tractable, though there have been attempts in that direction.
The approach followed by ASPECT is to "optimally" outer bound these membership-sets at each instant by an ellipsoid, which is highy tractable and easy to work with. This brings us to the realm of the so-called "Optimal Bounding Ellipoids" philosophy. Algorithms which recursively achieve this are called OBE algorithms.The center of the bounding ellipsoid is usually chosen as a point estimate if need be. The center has been shown to be intimately connected to the Weighted Recursive Least-Squares estimate but with certain differences and significant advantages, a few of which are:
For more details on these algorithms, the reader is urged to refer to some of the publications by the ASPECT group.OBE algorithms update the estimate selectively, i.e., they discard data which are not very "informative" in refining the estimate. This has been exploited by the ASPECT group for significant savings in computation as it offers a lot of hardware flexibilty and time sharing of processors. OBE algorithms offer huge gains over conventional estimation schemes in terms of tracking for a time-varying parameter. These have widespread implications for applications in wireless communiaction systems.