Adaptive set-membership identification in O(m) time for linear-in-parameters models

Some fundamental contributions to the theory and applicability of optimal bounding ellipsoid (OBE) algorithms for signal processing are described. All reported OBE algorithms are placed in a general framework that demonstrates the relationship between the set-membership principles and least square error identification. Within this framework, flexible measures for adding explicit adaptation capability are formulated and demonstrated through simulation. Computational complexity analysis of OBE algorithms reveals that they are of O(m²) complexity per data sample with m the number of parameters identified. Two very different approaches are described for rendering a specific OBE algorithm, the set-membership weighted recursive least squares algorithm, of O(m) complexity. The first approach involves an algorithmic solution in which a suboptimal test for innovation is employed. The performance is demonstrated through simulation. The second method is an architectural approach in which complexity is reduced through parallel competition