A probabilistic approach to optimal estimation part I: Problem formulation and methodology

The classical approach to system identification is based on statistical assumptions about the measurement error and provides estimates that have stochastic nature. Worst-case identification, on the other hand, only assumes the knowledge of deterministic error bounds and provides guaranteed estimates. The focal point of this paper is to provide a rapproachement between these two paradigms and propose a novel probabilistic framework for system identification. The main idea in this line of research is to “discard” sets of measure at most ϵ, where ϵ is a probabilistic accuracy, from the set of deterministic estimates. Therefore, we are decreasing the so-called worst-case radius of information at the expense of a given probabilistic “risk.” The main results of the paper establish rigorous theoretical properties of a trade-off curve, called optimal violation function, which shows how the radius of information decreases as a function of the accuracy. In the companion paper [8], we develop algorithms (randomized and deterministic) which exploit these theoretical results for efficiently computing the optimal violation function.