Information-based complexity in nonlinear equations and computer vision (multivariate splines, optimal algorithms, zero-finding)

摘要: This thesis is a foray into the methodologies and applications of information-based complexity. The divided three parts: complexity in nonlinear equations, applying computer vision, psychological experimentation. In Part 1 we explore solution various problems. For zero-finding two dimensions show that non-zero topological degree smoothness are not sufficient assumptions to allow location zero. We then derive tight upper lower bounds on computing for dimensional Lipschitz functions. extend this result n case, however gap between widens. complete our investigation dealing with problems by deriving bound smooth functions 2 dimensions. In 2, investigate application problem visual surface reconstruction. generalized traditional formulation problem, state abstract problem. discuss four realizations solution, including approaches which have been overlooked recent years. thoroughly analyzed numerical properties spline algorithms based reproducing kernels Hilbert spaces. Our conclusions kernel superior sparse data. In 3, describe use experimentation support direct some necessary 2. experiments. first experiment explores detectability discontinuities one curves. conclude humans can detect large jumps second derivative, but able small jumps. used prune space formulations be considered subjectively ranks reconstruction under different conditions. design relies optimal error developed