Ellipsoidal outer-bounding of the set of all feasible state vectors under model uncertainty is a natural extension of state estimation for deterministic models with unknown-but-bounded state perturbations and measurement noise. The technique described in this paper applies to linear discrete-time dynamic systems; it can also be applied to weakly non-linear systems if non-linearity is replaced by uncertainty. Many difficulties arise because of the non-convexity of feasible sets. Combined quadratic constraints on model uncertainty and additive disturbances are considered in order to simplify the analysis. Analytical optimal or suboptimal solutions of the basic problems involved in parameter or state estimation are presented, which are counterparts in this context of uncertain models to classical approximations of the sum and intersection of ellipsoids. The results obtained for combined quadratic constraints are extended to other types of model uncertainty. (C) 2004 Elsevier Ltd. All rights reserved.