We study multivariate tenser product problems in the worst case and average case settings. They are defined on functions of d variables. For arbitrary d, we provide explicit upper bounds on the costs of algorithms which compute an ϵ-approximation to the solution. The cost bounds are of the form (c(d) + 2)β1(β2 + β3(ln 1/ϵ)/(d − 1))β4(d − 1)(1/ϵ)β5. Here c(d) is the cost of one function evaluation (or one linear functional evaluation), and βi′s do not depend on d; they are determined by the properties of the problem for d = 1. For certain tensor product problems, these cost bounds do not exceed c(d)Kϵ−p for some numbers K and p, both independent of d. However, the exponents p which we obtain are too large. We apply these general estimates to certain integration and approximation problems in the worst and average case settings. We also obtain an upper bound, which is independent of d, for the number, n(ϵ, d), of points for which discrepancy (with unequal weights) is at most ϵ, n(ϵ, d) ≤ 7.26ϵ−2.454, ∀d, ϵ ≤ 1.

General zero-crossing-based discontinuity detectors in two dimensions, which include Marr-Hildreth (1980), residual, difference of Gaussians, and other detectors as special cases, are discussed. Mathematical justification for this class of detectors is presented. An optimal detector that maximizes the signal-to-noise ratio is derived. Preliminary experimental results for real images are reported.

Detection and thresholding using a stochastic approach is discussed. A general form of detectors which includes a number of well-known detectors as special cases is discussed. Thresholding is indispensable to eliminate spurious responses from the detection process. The authors propose a weighted thresholding, which is designed to cope with a variety of anomalies. The analysis and experimental results on real images show that intelligent thresholding methods can make a significant difference for discontinuity detection.>

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.

When observations can be made without noise, it is known that adaptive information is no more powerful than nonadaptive information for approximation of linear problems with Gaussian measure. When the noise is additive, independent of the true value, and normal, once again adaption does not help (Theorem 1 in Section 4). However, when those conditions are not satisfied, Examples 1 and 2 of Section 4 show that adaptive information can be much more powerful than nonadaptive information. Finally if orthogonal observations are used with the sample size as well as the number of repetitions fixed, and only the directions of observations are chosen adaptively, then once again adaption does not help (Theorem 2 in Section 5). The issue is analogous to whether sequential designs are more powerful than fixed sample size designs in Bayesian statistics.

We study approximation of linear functionals on separable Banach spaces equipped with a Gaussian measure. We study optimal information and optimal algorithms in average case, probabilistic, and asymptotic settings, for a general error criterion. We prove that adaptive information is not more powerful than nonadaptive information and that μ-spline algorithms, which are linear, are optimal in all three settings. Some of these results hold for approximation of linear operators. We specialize our results to the space of functions with continuous rth derivatives, equipped with a Wiener measure. In particular, we show that the natural splines of degree 2r + I yield the optimal algorithms. We apply the general results to the problem of integration.

We study adaptive information of varying cardinality for linear problems defined on a separable Banach space. It is known that for linear problems adaptive information of fixed cardinality does not help in the worst case setting. It does not help also in the average case setting with Gaussian measures. We prove that in the worst case setting a similar result holds for information of varying cardinality. In the average case setting with Gaussian measures, information of varying cardinality can be more powerful than information of fixed cardinality. However, optimal information has a structure which is almost as simple as nonadaptive information of fixed cardinality. We also give a condition under which varying cardinality does not help. These results are useful for deriving tight bounds on complexity, which is also studied in this paper.

Kung and Traub conjectured that any multipoint iteration without memory which uses n evaluations per iterative step has order of convergence no higher than 2 "-~.It is known that this conjecture is true for n --< 3 and for Hermite information.It is proved here that the Kung-Traub conjecture holds in a wider class of iterations.For example, it holds whenever the problem is well poised in the sense of Birkhoff complex interpolation.

All known globally convergent iterations for the solution of a nonlinear operator equation ƒ( x ) = 0 are either nonstationary or use nonlinear information. It is asked whether there exists a globally convergent stationary iteration which uses linear information. It is proved that even if global convergence is defined in a weak sense, there exists no such iteration for as simple a class of problems as the set of all analytic complex functions having only simple zeros. It is conjectured that even for the class of all real polynomials which have real simple zeros there does not exist a globally convergent stationary iteration using linear information.