Searching parameter spaces with noisy linear constraints

The authors develop a theoretical framework to facilitate rapid search of high-dimensional spaces. The basic method is predicated on some invariant properties of affine transformations and on the course-to-fine search paradigm. The parameter space is divided into overlapping ellipsoidal cells. The goodness or validity of a cell is measured by the number of constraint surfaces passing through the cell and a heuristic estimate of the probability that the cell contains a solution point satisfying most of the constraints. The natural advantages of the ellipsoidal cell divisions are discussed. Experimental results show that the method has superior search efficiency compared to other currently known algorithms