1985 Reports

Contributions to information-based complexity, image understanding and logic circuit design.

Lee, David

This work consists of three parts. The first two describe new results In information-based complexity and applications of the general theory to the field of computer vision. The last presents an average case result of a different sort: the design of a binary comparator. Part I is joint work with G. W. Wasilkowski. In this part, we study approximation of linear functionals on a separable Banach space equipped with a Gaussian measure. We study optimal information and optimal algorithms in average case, probabilistic and asymptotic settings, for a general error functional. We prove that adaptive information is not more powerful than non-adaptive information and that µ-spline algorithms, which are linear, are optimal in all three settings. We specialize our results to spaces of functions with continuous rth derivatives, equipped with a Wiener measure. In particular, we show that the interpolation by the natural splines of degree r+1 yields the optimal algorithms. We apply the general results to the problem of integration. Part II of this work studies the following image understanding problems: 2 & 1/2 D sketch, shape from shading, and optical flow. We point out how known general optimality results in the worst case model may be applied to these problems. We indicate some preliminary results and work in progress, concerning the numerical solution of these problems. Algorithms which differ from those currently used in practice are proposed. Part III provides a design of a binary comparator with completion signal, for the purpose of optimizing the average processing time. The average propagation delay is a constant, independent of n, the number of inputs, while the logic complexity is a linear function of n.