A probabilistic analysis of linear operator testing

We test for beta -conformance of an implementation linear operator A to a s pecification linear operator S where the operator domain and range are sepa rable Hilbert spaces and the domain space F is equipped with a Gaussian mea sure 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 parall el 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) i s the truncated Gaussian measure to B-q. We present a deterministic algorit hm 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 pro ve that optimal tests are conducted on the eigenvectors of the covariance o perator of mu. They are universal, they are independent of the operators un der consideration and other problem parameters. We show that finite testing is conclusive in this probabilistic setting. In contrast, finite testing i s inconclusive in the worst and average case settings; see [5, 7]. We discu ss the upper and lower bounds on the minimal number of tests. For q = infin ity 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 a pproach by an example with the Wiener measure. (C) 2001 Academic Press.