A probabilistic analysis of linear operator testing

We test for beta -conformance of an implementation linear operator A to a specification linear operator S where the operator domain and range are separable Hilbert spaces and the domain space F is equipped with a Gaussian measure mu. Given an error bound epsilon > 0 and a tolerance parameter beta is an element of (0. 1), we want to determine either that there is an element f in a ball B-q of radius q in domain F such that parallel to Sf-Af parallel to > epsilon or that A beta -conforms to S on a set of measure at least 1 - beta in the ball B-q: i.e.. mu (q)(f:parallel to Sf-Af parallel to less than or equal to epsilon) greater than or equal to 1 - beta where mu (q) is the truncated Gaussian measure to B-q. We present a deterministic algorithm that solves this problem and uses almost a minimal number of tests where each test is an evaluation of operators S and A at an element of F. We prove that optimal tests are conducted on the eigenvectors of the covariance operator of mu. They are universal, they are independent of the operators under consideration and other problem parameters. We show that finite testing is conclusive in this probabilistic setting. In contrast, finite testing is inconclusive in the worst and average case settings; see {[}5, 7]. We discuss the upper and lower bounds on the minimal number of tests. For q = infinity we derive the exact bounds on the minimal number of tests, which depend on beta very weakly. On the other hand. for a finite q, the bounds on the minimal number of tests depend on beta more significantly. We explain our approach by an example with the Wiener measure. (C) 2001 Academic Press.