We study the average complexity of linear problems, on a separable Banach space equipped with an orthogonally invariant measure μ. The error and the cost of the algorithms are defined on the average. We exhibit an information operator which is optimal among any linear information operators. We apply the general results to the approximation problem of real functions of d variables. The space is now equipped with a Wiener measure placed on partial derivatives. We show that the average complexity of this problem is almost independent of the dimension d if arbitrary linear functionals are permitted in the information. We conjecture that the same result holds if the information is restricted to function and/or partial derivative evaluations only.

We study some computational aspects of determining optical flow. Necessary and sufficient con- ditions are investigated for the existence and uniqueness of the smoothing-spline from regularization. We discuss different boundary conditions: free, Neuman, and Dirich- let boundary conditions. We show that both free and Neuman boundary problems are ill-conditioned, and are not appropriate for optical flow computation. We discuss Dirichlet boundary problem in more details. As a com- mon practice in low-level vision, a continuous problem is formulated, and a discrete version of the problem is solved instead. We estimate the discretization errors, and com- pute the resulting discrete smoothing-splines. We study efficient iterative methods for solving the system of linear equations for the discrete smoothing-splines. We propose the Chebyshev method for the computation. The Cheby- shev method converges faster than the Gauss-Seidel and Jacobi methods, and is parallelizable.