Checking approximate computations over the reals

This paper provides the first systematic investigation of checking approximate numerical computations over subsets of the reals. In most cases, approximate checking is more challenging than exact checking. Problem conditioning, i.e., the measure of sensitivity of the output to slight changes in the input, and the presence of approximation parameters foil the direct transformation of many exact checkers to the approximate setting. Furthermore, approximate checking over the reals is complicated by the lack of nice finite field properties such as the existence of a samplable distribution which is invariant under addition or multiplication by a scalar. We overcome the above problems by using such techniques as testing and checking over similar but distinct distributions, using functions' random and downward self-reducibility properties, and taking advantage of the small variance of the sum of independent identically distributed random variables. We provide approximate checkers for a variety of computations, including matrix multiplication, linear system solution, matrix inversion, and computation of the determinant. We also present an approximate version of Beigel's trick and extend the approximate linear self tester/corrector of [8] and the trigonometric self-Tester/corrector of [5] to more general computations.